03 digression by brute force

jfong at ms4.hinet.net jfong at ms4.hinet.net
Thu Dec 13 21:24:47 EST 2018


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)
-------------------------

--Jach


More information about the Python-list mailing list