Four fours

Back in elementary school, I became aware of the four fours puzzle. It is a seemingly simple mathematical exercise where you must generate all the integers from 1 to 100 using arithmetic expressions and the digit 4 exactly four times. A few sample solutions:

1. 44 / 44
2. 4 + 4 – 4 – sqrt(4)
3. (4 + 4 + 4)/4

(For perhaps more than you ever wanted to know about the puzzle, I recommend David Wheeler’s excellent Definitive Four Fours Answer Key.)

Over the years, I have solved the puzzle a few times by hand (sometimes assisted by a TI calculator) but had never seriously attempted it programmatically. That all changes now. I present to you my Four4Sample project on GitHub. The rest of this post describes the design and approach of the code.

Before I even wrote a line of code, I spent some time thinking about how to build up the solution expressions. My first instinct was that traditional infix notation (e.g. “4 + 4” — the operator “+” appears in between the operands) would be rather complicated to deal with. Thus, I set out to write an RPN expression evaluator, using postfix notation (e.g. “4 4 +” — the operator “+” appears after the operands). Postfix has the distinct advantage of requiring absolutely no operator precedence handling; any operator can be applied right away.

The first couple dozen commits built up the base infrastructure to handle rational number calculations. By that point, my calculator could handle the basic arithmetic operators, square root (“R”) and factorial (“!”), along with raw operands for all the numeral 4 expressions (e.g. “4”, “.4”, and “.4_” representing the repeating decimal .4).

The next interesting challenge was handling of invalid results. Several commits were dedicated to NaN propagation (e.g. “4 4 – 4 – R” should result in “NaN” due to the attempt of taking the square root of -4). Given this “NaN hammer,” I chose to treat every error condition as “NaN”. This included too many operands (e.g. “4 4”), too few operands (e.g. “4 +”), division by zero, and so on. Many more commits and a few renames later, I had an Expression class with a good enough Eval method.

Thinking ahead a few steps, I knew I would need to recursively produce expressions to solve the puzzle. For this reason, I began to make all the data structures immutable. This would make it much easier to generate new expressions from old ones without altering previous data, and hence seamlessly allow recursive branching and backtracking. It did make the code a bit weirder, though. (NumberStack as a struct with exactly four item fields?!)

The next set of commits implemented the append operations and tracking of how many digits were used so far. So for example emptyExpr.Append("44").Append("4").Append("+") would produce the result 48 with digit count of 3.

Now in the home stretch, I began to create the ExpressionSearch class. This was the core recursive algorithm to generate all the valid expressions. In plain English, it does the following, starting from a completely empty expression:

• If the current expression is invalid, return.
• If the current expression has a valid result, report it to a callback method.
• If the current expression has fewer than 4 digits, iteratively append every defined operand and recurse on the new expression.
• Iteratively append every defined operator (binary or unary) and recurse on the new expression.

Eventually I added some logic to stop early, to optimize for the traditional case where the user wants only solutions from 1-100.

This algorithm served me well, but initially had some problems. The first thing I noticed is that unary operators were prone to stack overflow. This is because expressions like “4 4 /” (i.e. 1) can have, say, “R” (square root) appended infinitely with no change in the result or the digit count. I “fixed” this by simply redefining “R” to be invalid for any case where x = sqrt(x) — specifically, 0 and 1. The “!” (factorial) operator had the same problem for some numbers, so I applied a similar fix for 1 and 2. (Binary operators were immune to this problem because they always reduced the stack size and would eventually “error out” naturally after the stack reached a size of one.)

The final major tweak I made to the program was to allow presenting the results in the more familiar infix style. Postfix to infix conversion is even easier than postfix parsing, so it only took a handful of commits to get this working to my liking. (I did not attempt to remove redundant parentheses — that would have complicated things quite a bit more.)

Before I was done, I was a little concerned I might need to use parallelism to improve the performance. This would have needed a fundamental rework to the design. Luckily, though, the program already completes surprisingly fast without any special effort.

Found 100 results in 251 ms.
1 = ((4+(4-(4+4))))!
2 = sqrt(sqrt((4+(4+(4+4)))))
3 = (4-((4*(4-4)))!)
4 = sqrt((4+(4+(4+4))))
 . . .

Note that some of the shortcuts I took make it impossible to generate some of the more “clever” solutions, such as those that require irrational numbers in intermediate steps. Nevertheless, I feel pretty good about the result. Like the four fours puzzle itself, it was a fun diversion, as well as a chance to flex my TDD muscles.