03 digression by brute force

BlindAnagram no-one at nowhere.org
Sat Dec 15 07:37:51 EST 2018


On 14/12/2018 02:24, jfong at ms4.hinet.net wrote:
> Just for fun:-) On my ooold PC, it takes 0.047 seconds to run the following algorithm on the problem 'SNED + MORE == MONEY".
> 
> -----------------------------
> import time
> import itertools
> 
> #S, E, N, D, M, O, R, Y
> n = 0
> digits = {x for x in range(10)}
> 
> def tenThousand(u, Cin):  # Cin == M
>     global n
>     if Cin == M:
>         print(S, E, N, D, '+', M, O, R, E, '==', M, O, N, E, Y)
>         n += 1
> 
> def thousand(u, Cin):  # Cin + S + M == 10 * Cout + O
>     global S, M, n
>     rest = digits - set(u)
>     for g in itertools.permutations(rest, 2):
>         for Cout in range(2):
>             if Cin + g[0] + g[1] == 10 * Cout + O:
>                 S = g[0];  M = g[1]
>                 tenThousand(u + g, Cout)
>             
> def hundred(u, Cin):  # Cin + E + O == 10 * Cout + N
>     global O, n
>     rest = digits - set(u)
>     for g in itertools.permutations(rest, 1):
>         for Cout in range(2):
>             if Cin + E + g[0] == 10 * Cout + N:
>                 O = g[0]
>                 thousand(u + g, Cout)
> 
> def ten(u, Cin):  # Cin + N + R == 10 * Cout + E
>     global N, R, n
>     rest = digits - set(u)
>     for g in itertools.permutations(rest, 2):
>         for Cout in range(2):
>             if Cin + g[0] + g[1] == 10 * Cout + E:
>                 N = g[0];  R = g[1]
>                 hundred(u + g, Cout)
>             
> def unit():  # D + E == 10 * Cout + Y
>     global D, E, Y, n
>     n = 0
>     for g in itertools.permutations(range(10), 3):  # g is a tuple
>         for Cout in range(2):  # add two items so Cout is 0 or 1
>             if g[0] + g[1] == 10 * Cout + g[2]:
>                 D = g[0];  E = g[1];  Y = g[2]
>                 ten(g, Cout)
>     print(n)
>         
> if __name__ == '__main__':
>     start = time.time()
>     unit()
>     print(time.time() - start)
> -------------------------
> 

There are quite a few Python based solvers for alphametics around on the
net, for example:

http://code.activestate.com/recipes/576615-alphametics-solver/

There is also a long discussion here on ways of doing this:

https://enigmaticcode.wordpress.com/2016/06/22/solving-alphametics-with-python/


More information about the Python-list mailing list