Astute readers may have noticed in my previous post about the four fours that I neglected to include exponents in the set of supported mathematical operations. Well, that is fixed now. Perhaps these imagined readers also noticed that my recursive algorithm was slightly more verbose than required, as it unnecessarily handled unary and binary operators separately. I fixed that too!
While making the above fixes I also experimented with the performance a bit. It turns out that recursing on operators before operands seems to save time when searching for the first 100 solutions. I assume this is because if it is asked to handle operands first, the search ends up producing answers which are ultimately ignored for being too large. While doing this, I also checked to see if switching from my custom stack to the .NET Core ImmutableStack<T> changed the performance in any significant way. It didn’t seem to have a noticeable effect one way or the other, so I ditched my custom stack. All things being equal, less custom code is better (especially if it is “unusual”).
As a final tweak, I swapped the order of 4 and 44 in the operands list. This produced slightly simpler solutions in many cases (e.g. “(44 – 44)!” for 1, instead of “(4!+4-4-4!)!”). Overall, I am pleased with the result. As a bonus, it seems to be a different (simpler?) approach than the one discussed on Wikipedia and on any publicly available code I could find.
Now the only thing left to do is generalize. First, let’s see if it can solve the “three threes” problem. This will require getting rid of any special cases involving the numeral 4. After that, it is a simple matter of propagating a user-defined value for the numeral count instead of assuming we always want four digits. Then it’s a just small fix up to the app to support digits other than 4.
Unfortunately, running the app in “3” mode produces an exception:
Unhandled Exception: System.OverflowException: Arithmetic operation resulted in an overflow. at Four4.Number..ctor(Int32 num, Int32 denom) in Four4Sample\Four4\Number.cs:line 25 at Four4.Number.Pow(Number exp) in Four4Sample\Four4\Number.cs:line 177 at Four4.Expression.<>c.<Append>b__12_4(Number x, Number y) in Four4Sample\Four4\Expression.cs:line 59 at Four4.Expression.NumberStack.Apply2(Func`3 op) in Four4Sample\Four4\Expression.cs:line 187 at Four4.Expression.Binary(String token, Func`3 op) in Four4Sample\Four4\Expression.cs:line 95 at Four4.Expression.Append(String token) in Four4Sample\Four4\Expression.cs:line 59 . . .
The specific expression it fails on is “3 ! ! 3 ^ .3 / 3 ^”, i.e. (((3!)!)^3 / .3)^3. This does indeed overflow the range of a 32-bit signed integer, but I was sure I handled this case…. By adding a few more tests, I should be able to figure out where this breaks down. Indeed, it turns out the problem is not actually with Pow, but with Multiply!
The unit test for the expression “3 ! ! 3 ^ .3 /” reproduces the issue. It should produce “1244160000” but during the course of multiplying the numerators together, it sees an intermediate result greater than int.MaxValue. The fix I have chosen is to return “NaN” for any overflow, even if the reduced result would be in range. It is perhaps a simplistic assumption but it doesn’t affect the goal of finding solutions inside a “reasonable” bound.
Fixing the case for a large positive numerator makes the new tests pass. But running the program results in another unhandled case, “3 ! ! 3 ^ .3 33 – /”, i.e. ((3!)!)^3 / (.3 - 33). In this case, it is more of an “underflow” since the value is a too-small negative number. That can be handled similarly with another lower bound range check.
Alas, another bad expression still slips through, “3 ! ! .3 3 ! – / 3 ^”, i.e. (((3!)!)/(.3 - 3!))^3. This time, Pow is the culprit. It was simply missing a similar lower bound check as above.
With these fixes, the three threes search doesn’t crash but produces incorrect results. First error: the program doesn’t initialize the NumeralCount — easy to fix. Still, it produces the wrong result. Ah, I forgot that Results also specifically checks for a numeral count of 4. A few tests and code changes later, that is also fixed. Now it works!
Found 43 results in 45 ms. 1 = (((((3)!)!-((3)!)!))!^3) 2 = ((((3)!)!+((3)!)!)/((3)!)!) 3 = ((((3)!)!+3)-((3)!)!) 4 = (((((3)!)!-((3)!)!))!+3) 5 = (((3)!/3)+3) . . .
According to my program, the first missing result is 22. In fact, only 43 of the first 100 whole numbers appear to have a solution.
What about the two twos? One more generalization and the program tells us:
Found 9 results in 19 ms. 1 = ((2-2))! 2 = sqrt((2+2)) 3 = sqrt((2/.2_)) 4 = (2+2) 6 = (sqrt((2/.2_)))! 9 = (2/.2_) 10 = (2/.2) 22 = 22 24 = ((2+2))!
The final gauntlet — the five fives!
Found 100 results in 480 ms. 1 = (((55-55))!^5) 2 = (((55-55))!/.5) 3 = sqrt((((55-5)-5)/5)) 4 = (sqrt(sqrt(((55/5)+5)))/.5) 5 = (((55-55))!*5) . . .
Just a few more changes to get the Main() method down to its bare essentials, and set the min and max search values:
Solving 3 3s (min=1, max=1000)... Found 109 results in 44 ms. 1 = (((((3)!)!-((3)!)!))!^3) 2 = ((((3)!)!+((3)!)!)/((3)!)!) 3 = ((((3)!)!+3)-((3)!)!) 4 = (((((3)!)!-((3)!)!))!+3) . . . 936 = (((3)!)!+(((3)!)!*.3)) 960 = ((((3)!)!/3)+((3)!)!) 1000 = ((3/.3)^3)
At that point, I thought I was done, but as I was exploring higher valued solutions of the five fives, I encountered more overflow problems. Drat! This time it was because of a division, which pointed to the denominator of a multiplication being too large. I probably could have predicted this given that I only “spot fixed” the problem last time. Well, now for a real solution. Luckily, we don’t have to deal with underflow because the denominator is never negative. At any rate, while I’m at it, I should fix potential overflow issues in addition (writing tests first, of course).
The final improvement is to ensure that numbers of any allowed size are used. Originally I used the one and two digit numbers for the given digit (e.g. 4 and 44, 5 and 55, etc.). But technically 444, 4444, etc. should be allowed, as well as 55555 for five fives, and so on. One last correction for that:
Solving 4 4s (min=110, max=111)... Found 2 results in 18 ms. 110 = (sqrt(sqrt((44^4)))/.4) 111 = (444/4)
That concludes my four fours exploration. I promise I’ll write about something less overtly mathematical next time!