Algorithmic Thinking Guide (Four-Quarter Equation)

Question

I recently saw a 4 Fours logical / math problem where you need to use 4 fours and a series of operators to create equations equal to integers from 0 to N.

How would you write an elegant algorithm to come up with the first 100 ...

I started by creating basic calculations such as 4-4, 4 + 4, 4x4, 4/4, 4 !, Sqrt 4, and made these values ​​integers.

However, I realized that it would be a brute force method that checks combinations to make sure they are equal, 0, then 1, then 2, then 3, etc.

Then I thought about finding all possible combinations of the above values, checking that the result was less than 100 and filling the array and then sorting it ... again inefficient because it can find 1000 numbers from more than 100

Any help on how to approach such a problem would be helpful ... not the actual code ... but how to think over this problem

Thanks!!

Answer 1

This is an interesting problem. There are several different things here. One of the problems is how to describe the sequence of operations and operands that are included in the arithmetic expression. Using parentheses to establish the order of operations is rather messy, so instead I suggest thinking of an expression as a stack of operations and operands, for example - 4 4 for 4-4, + 4 * 4 4 for (4 * 4) +4, * 4 + 4 4 for (4 + 4) * 4, etc. It's like the reverse polish notation on an HP calculator. Then you don’t need to worry about parentheses, as the data structure for expressions will help below when we create larger and larger expressions.

Now let's move on to the algorithm for constructing expressions. Dynamic programming in this situation does not work, in my opinion, because (for example) to build some numbers in the range from 0 to 100, you may need to temporarily go beyond this range.

The best way to conceptualize the problem, I think, is like the first width search (BFS) on a chart. Technically, the graph will be infinite (all positive integers or all integers or all rational numbers, depending on how much you want to get), but at any time you will have only the final part of the graph. A sparse graph structure may be required.

Each node (number) on the graph will have the weight associated with it, the minimum number 4 required to achieve this node, as well as an expression that achieves this result. First you start with node (4), with the number 1 associated with it (it takes 4 to make 4), and the simple expression is “4”. You can also drop (44) with a weight of 2, (444) with a weight of 3 and (4444) with a weight of 4.

To create larger expressions, apply all the different operations that you have to those original nodes. For example, unary negation, factorial, square root; binary operations, such as * 4 at the bottom of your stack, for multiplication by 4, + 4 , - 4 , / 4 , ^ 4 for exponentiality, as well as + 44 , etc. The weight of the operation is the amount of 4s required for this operation; unary operations would have a weight of 0, + 4 would have a weight of 1, * 44 would have a weight of 2, etc. You would add the weight of the operation to the weight of the node it is running on to get the new weight, so for example + 4 acting on node (44) with a weight of 2, and the expression “44” will result in a new node (48) with weight 3 and the expression "+ 4 44". If the result for 48 has a better weight than the existing result for 48, replace the new node with (48).

When applying functions, you have to use a certain meaning. factor (4444) would be a very large number; it would be wise to set a domain for your factorial function, which would prevent you from getting too big a result or go beyond. Same thing with functions like / 4; if you do not want to deal with fractions, say that multiples of 4 are not outside the region / 4 and in this case do not use the operator.

The resulting algorithm is very similar to Dijkstra's algorithm for calculating the distance on the graph, although not quite the same.

Answer 2

I think brute force solution here is the only way to go.
The reason for this is that each number has a different way to get to it, and going to a specific x may not have anything to do with x+1 .

Having said that, you could make brute force decisions faster using obvious steps where possible.
For example, if I got to 20 using "4" three times ( 4*4+4 ), it is obvious that you need to get to 16, 24 and 80. Holding an array of 100 bits and noting the numbers reached

Answer 3

Like the problem of summing sums, it can be solved using Dynamic Programming (DP) , following the recursive formulas:

 D(0,0) = true D(x,0) = false x!=0 D(x,i) = D(x-4,i-1) OR D(x+4,i-1) OR D(x*4,i-1) OR D(x/4,i-1) 

By calculating the above using the DP method, it is easy to find out what numbers can be obtained using these 4, and returning to the solution, you can find out how each number was constructed.

The advantage of this method (when implementing with DP) is that you do not recount several values ​​more than once. I'm not sure that it will really be effective for 4 4, but I believe that in theory this could be a significant improvement for a less limited generalization of this problem.

Answer 4

This answer is simply Amit's extension. Essentially, your operations are:

• Apply a unary operator to an existing expression to get a new expression (this does not use any extra 4s)
• Apply a binary operator to two existing expressions to get a new expression (the new expression has 4s equal to the sum of the two input expressions)

For each n of 1..4, calculate Expressions(n) - pairs of pairs (expression, value) as follows: (For a fixed n , only save 1 expression in a list that evaluates any given value)

• Initialize a list with n 4s concatenation (i.e. 4, 44, 444, 4444)
• For i from 1 to n-1 and each permitted binary op operator, add the expression (and value) e1 op e2 , where e1 is in Expressions(i) and e2 is in Expressions(ni)
• Repeatedly apply unary operators to the expressions / values ​​computed so far in steps 1-3. When stopping (applying 3 recursively) is a bit vague, be sure to stop if the iteration does not produce new values. Potentially limit the allowed values ​​or the size of the expressions.

Examples of unary operators:! , Sqrt , - etc. Example binary operators +-*/^ , etc. You can easily extend this approach to statements with more arguments, if allowed.

You can do something smarter in terms of step 3, never ending for any given n . The simple way (described above) does not start calculating Expressions(i) until Expressions(j) is complete for all j < i . This requires us to know when to stop. An alternative is to create expressions of a certain maximum length for each n , then if you need (because you did not find specific values), increase the maximum length in the outer loop.