SEND + MORE = MONEY, Part 2
August 3, 2012
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.
Programming Praxis 
[…] Pages: 1 2 […]
Prolog code (mostly since the first exercise was in Prolog, there’s little other reason to use it here, it’s not particularly well suited…)
split(List, Nth, X, A, B) :- append(A, [X|B], List), length(A, Nth), !. swap(List, I, J, List) :- I == J. swap(List, I, J, Result) :- I > J, swap(List, J, I, Result). swap(List, I, J, Result) :- split(List, I, X1, Left, Rest), I2 is J - I - 1, split(Rest, I2, X2, Mid, Right), append([Left, [X2], Mid, [X1], Right], Result). randomSwap(Key0, FirstSet, Key) :- I is random(10), J is random(10), swap(Key0, I, J, Key1), [X|_] = Key1, (member(X, FirstSet) -> Key = Key0 ; Key = Key1). transition(S1, S2) :- S1 > S2. transition(_, _) :- X is random(100), X == 0. climb(_, _, _, _, Key, 0, Key). climb(Xs, Ys, Zs, FirstSet, Key, Score, FinalKey) :- randomSwap(Key, FirstSet, NewKey), score(Xs, Ys, Zs, NewKey, NewScore), (transition(Score, NewScore) -> climb(Xs, Ys, Zs, FirstSet, NewKey, NewScore, FinalKey) ; climb(Xs, Ys, Zs, FirstSet, Key, Score, FinalKey)). score(Xs, Ys, Zs, Key, Score) :- number(Xs, Key, 0, X), number(Ys, Key, 0, Y), number(Zs, Key, 0, Z), Score is abs(X + Y - Z). number([], _, X, Y) :- Y = X. number([A|As], Key, Acc, Result) :- nth0(N0, Key, A), N is 10*Acc + N0, number(As, Key, N, Result). strtoatoms("", []). strtoatoms([Ch|Str], [A|As]) :- name(A, [Ch]), strtoatoms(Str, As). repeat(_, 0, []). repeat(X, Count, [X|Y]) :- succ(DecCount, Count), repeat(X, DecCount, Y). pad(Key, K) :- length(Key, L), L =< 10, PadLen is 10 - L, repeat('_', PadLen, Padding), append(Key, Padding, K). make_key(X, Y, Z, Key) :- Lists = [X, Y, Z], append(Lists, Key0), sort(Key0, Key1), pad(Key1, Key). solve(S1, S2, S3, X, Y, Z) :- strtoatoms(S1, Xs), strtoatoms(S2, Ys), strtoatoms(S3, Zs), [A|_] = Xs, [B|_] = Ys, [C|_] = Zs, sort([A,B,C], FirstSet), make_key(Xs, Ys, Zs, InitialKey), score(Xs, Ys, Zs, InitialKey, InitialScore), climb(Xs, Ys, Zs, FirstSet, InitialKey, InitialScore, FinalKey), number(Xs, FinalKey, 0, X), number(Ys, FinalKey, 0, Y), number(Zs, FinalKey, 0, Z), !. 29 ?- solve("send", "more", "money", X,Y,Z). X = 9567, Y = 1085, Z = 10652. 24 ?- solve("fifty","states","america",X,Y,Z). X = 65682, Y = 981849, Z = 1047531.A Python 2.7 solution based on original Scheme solution:
import random import time def random_solution(*words): solution = list(set(''.join(words))) if len(solution) < 10: for _ in xrange(len(solution), 10): solution.append("_") return solution def number(word, solution): n = 0 for letter in word: n = n * 10 + lookup(letter, solution) return n def lookup(letter, solution): for i, l in enumerate(solution): if letter == l: return i def score(solution, *words): nums = [number(word, solution) for word in words] return abs(sum(nums[:-1]) - nums[-1]) def alter_solution(solution, first_letters): altered = solution[:] i = random.randint(0, 9) j = random.randint(0, 9) altered[i], altered[j] = altered[j], altered[i] if altered[0] in first_letters: return solution return altered def print_solution(solution, *words): nums = [str(number(word, solution)) for word in words] print("%s = %s" % (' + '.join(nums[:-1]), nums[-1])) def solve(*words): start = time.clock() first_letters = set([word[0] for word in words]) best_solution = random_solution(*words) best_score = score(best_solution, *words) while True: if best_score == 0: break alt_sol = alter_solution(best_solution, first_letters) alt_score = score(alt_sol, *words) if alt_score < best_score or random.randint(1, 100) == 1: best_score = alt_score best_solution = alt_sol print_solution(best_solution, *words) print("%.2f" % (time.clock() - start)) solve('send', 'more', 'money') solve('cross', 'roads', 'danger') solve('green', 'orange', 'colors') solve('taurus', 'pisces', 'scorpio') solve('fifty', 'states', 'america') solve('this', 'size', 'short') solve('lynne', 'looks', 'sleepy') solve('nine', 'fine', 'wives') solve('ted', 'has', 'good', 'taste')[…] was a post at Programming Praxis about the old mathematical problem SEND + MORE = MONEY. Basically, you have the following […]
I went ahead and wrote a Scheme version before I actually read yours but they actually ended up pretty similar. Check it out here.
Can you put the C version of this? Thank you.