Subscribe to Computing Intelligence

Sunday, March 8, 2009

Puzzle One Solution

It took me longer than I had planned to get around to posting this solution, but here it is. If you recall, puzzle number one was concerned with finding the starting pair of numbers from 0 to 9 which provided the most iterations before reaching zero of taking the new number pair from the digits of the product of the previous pair. While I invented this puzzle as an aid to falling asleep (in which case brute force mental computation was actually the desired outcome), I was curious to see if anyone would come up with an elegant solution based on numerical logic rather than simply trying every single combination. While Scott (whose blog I just discovered is not on my "Places of Interest" list... I could have sworn it was!) mentioned he did spend some time mentally contemplating the solution, both he and Wisefly ended up doing the same thing I did to confirm the answer - write a short computer program that simply tried every starting combination and looped through the iterations. Wisefly used Excel, Scott used python, and I used MatLab. If anyone is curious about the specific code used to find the solution, either leave a comment or send me an email and I can send you my .m file. Roughly, the pseudocode is as follows:
maxCount = 0, maxStart = 0
for i = 1 to 99
count = 1, x = floor(i/10), y = mod(i,10)
while(x*y > 0)
count++, iter = x*y
x = floor(iter/10), y = mod(iter,10)
end while
if(count > maxCount)
maxCount = count, maxStart = i
end if
end for

Of course, for some reason I cannot get white space to stick around even within block-quotes, so my pseudocode comes out looking like crap. Please forgive its lack of spacing. Also, if you are not used to my pseudocode (which is entirely possible), floor yields the rounded down integer value of the value passed to it (for example, floor(5/3) = 1) and mod is the modulus (or remainder) of the first number by the second (for example, mod(10,4) = 2).

Anyway, running the program yields the correct answer of 77 (or x = 7, y = 7) as your starting value. 7*7 = 49, 4*9 = 36, 3*6 = 18, 1*8 = 08, 0*8 = 0. Thus, there are five iterations before the value becomes 0. As was pointed out to me, this was a relatively straightforward puzzle when one wrote a computer program to solve it (and even without the computer program it was feasible to solve by some relatively simple number crunching). Wisefly suggested modifying the puzzle such that instead of being in base 10 (ie. taking starting integers from 0 to 9), it would be interesting to see what the results were for a base n system, where n is anything greater than 2 (taking a base 2 system yields the trivially obvious solution of both x = 1 and y = 1, as the three other starting choices go to 0 immediately). This is relatively easy to do by just replacing the values of 10 in the above code by n and running the for loop from i = 1 to n*n-1. One can then look at the results of this and see if some sort of pattern emerges which would allow one to pick the appropriate best starting digits for a given base n without having to resort to brute force methods. I have completed the modifications to my own program and run it for values from 2 to 6 without spotting any sort of discernable pattern. I do plan on doing some actual work this afternoon, so I have tabled this for now but might explore it in the future. If anyone decides to explore this themselves and comes up with some interesting ideas, feel free to send me your results.

Note: I made the mistake this time of not keeping an accessible list of those who solved the puzzle and sent me solutions. While I think it was just Wisefly and Scott, if my memory has failed me and I forgot someone, please send me an email or leave a disgruntled comment, and I will make the appropriate changes to this post.

Edit: Thanks to Paul's helpful comment, my pseudocode looks a little more readable now.