Programming Praxis

In the previous exercise we looked at two slow solutions to the SEND + MORE = MONEY cryptarithm. In today’s exercise we look at two more solutions.

Our third solution uses a hill-climbing algorithm. The basic idea is to start with a random solution, score it, then alter it, score the modified solution, keep it if it has a better score than the original, and repeat until the desired solution is found. For the cryptarithm problem, the alteration can be done by swapping the values assigned to two letters chosen randomly, and scoring can be done by computing the difference between SEND + MORE and MONEY; the solution is found when the difference is zero.

The problem with hill-climbing is that it can get stuck at a local optimum with no hope of achieving a global optimum. Consider the correct solution to the SEND + MORE = MONEY problem; we give the solution in a list, with O=0, M=1, and so on, and no letter assigned to 3 or 4: (o m y _ _ e n d r s). It is possible (it happened to me when I was writing the program) for hill-climbing to reach the solution (o m y _ e n _ d r s) with a score of 1. It takes two swaps to find the correct solution, but there is only one possible improvement in the score, from 1 to 0, so if a random hill-climb ever reaches the incorrect solution shown above, it will loop forever without reaching the correct solution.

Thus, our fourth solution is a variant of hill-climbing that adds additional randomization: a modified solution is always accepted if it has a better score than the original, and it is also accepted sometimes even if it has a worse score than the original, say about once in a hundred times. That way, if the hill-climbing reaches a local optimum, it has a way to “jump” to a different hill and continue to the global optimum.

The straight hill-climbing algorithm is fast when it works, taking half a second or less (depending on the randomization). The variant hill-climbing climbing algorithm always works, and is equally fast.

Your task is to write the two cryptarithm algorithms given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2