Verbal arithmetic

verbalArith.py

from pprint import pprint as pp
from time import time

st = time()

def codeForGuess(ch, firsts, indent):
    ind = ' '*indent
    v1 = """\
%sfor %s in %s:
%s    urem(%s)""" % (ind, ch, "udiff(set0)" if ch in firsts else "ucopy()",
                     ind, ch)
    v2 = """%s    uadd(%s)""" % (ind, ch)
    return (v1, v2)

def codeForVerifySum(chCounts, last, indent, eqIndex):
    ind = ' '*indent
    sm0, sm1 = "sm%s" % (eqIndex,), "sm%s" % (eqIndex+1,)
    st = "%s/10" % (sm0, )
    for ch, count in chCounts:
        if ch == last:
            count -= 1
        if count > 1:
            st += ' + %s*%s' % (ch, count)
        elif count == 1:
            st += ' + %s' % (ch, )

    c1 = """\
%s%s = %s
%sif %s == %s %% 10:""" % (ind, sm1, st,
                           ind, last, sm1)
    return (c1, None)

def codeForSolve(chs, chCounts, last, indent, eqIndex, firsts):
    ind = ' '*indent
    sm0, sm1 = "sm%s" % (eqIndex,), "sm%s" % (eqIndex+1,)
    st = "%s/10" % (sm0, )
    for ch, count in chCounts:
        if ch == chs:
            continue
        elif ch == last:
            st += ' + %s*%s' % (ch, count - 1)
        else:
            if count > 1:
                st += ' + %s*%s' % (ch, count)
            else:
                st += ' + %s' % (ch, )

    if chs == last:
        c1 = """\
%s%s = %s
%s%s = %s %% 10
%sif %s in unused%s:
%s    urem(%s)""" % (ind, sm1, st,
                     ind, chs, sm1,
                     ind, chs, (' and %s != 0' % (chs, ))  if chs in firsts else '',
                     ind, chs)

        c2 = """%s    uadd(%s)""" % (ind, chs)
        return c1, c2
    else:
        c1 = """\
%svalue = %s
%s%s = (%s - value) %% 10
%sif %s in unused%s:
%s    urem(%s)
%s    %s = value + %s""" % (ind, st,
                            ind, chs, last,
                            ind, chs, (' and %s != 0' % (chs, )) if chs in firsts else '',
                            ind, chs,
                            ind, sm1, chs)
        c2 = """%s    uadd(%s)""" % (ind, chs)
        return c1, c2

def codeForFinalCheck(eqIndex, chars, indent, prob):
    ind = ' '*indent
    varDict = "{ " + ", ".join("'%s': %s" % (x, x) for x in chars) + " }"
    c1 = """\
%sif %s < 10:
%s    values = %s
%s    lwords = [str(word2num(v, values)) for v in lhs]
%s    rword = str(word2num(rhs, values))
%s    return "%%s = %%s" %% (" + ".join(lwords), rword)\n""" % (ind, "sm%s" % (eqIndex + 1),
                      ind, varDict,
                      ind,
                      ind,
                      ind)

    return c1, None


def createProgram(problem):
    program1 = """
def word2num(word, values):
    num = 0
    for c in word:
        num = num * 10 + values[c]
    return num

def myfunc(words):
    unused = set(range(10))
    urem = unused.remove
    uadd = unused.add
    udiff = unused.difference
    ucopy = unused.copy
    set0 = set([0])
    sm0 = 0
    lhs = words[:-1]
    rhs = words[-1]

"""

    program3 = """\

    return "not solved"

try:
    print myfunc(%s)
except:
    from traceback import print_exc
    print_exc()
""" % (problem)


    problem = [x[::-1] for x in problem]
    firsts = set([x[-1] for x in problem])

    unused = set()
    [unused.union(set(x)) for x in problem]

    lhs, rhs = problem[:-1], problem[-1]

    equations = []

    for i in range(len(rhs)):
        equations.append([word[i] if len(word) > i else None for word in problem])

    charactersWithOccurenceCount = chOcc = []
    unassignedCharsSortedByNumOccurences = unChars = []
    characters = set()

    for eqn in equations:
        used = set([None])
        curr = []
        for ch in eqn:
            characters.add(ch)
            if not ch in used:
                used.add(ch)
                curr.append((ch, eqn.count(ch)))
        chOcc.append(curr)

    if None in characters:
        characters.remove(None)

    used = set([None])
    for eqn in equations:
        curr = []
        for ch in eqn:
            if not ch in used:
                used.add(ch)
                curr.append((ch, eqn.count(ch)))

        unChars.append(sorted(curr, key=lambda x: x[1], reverse=True))

    #pp(chOcc)
    #pp(unChars)

    indent = 4
    c1s, c2s = [], []

    for i, (uchs, chCounts)  in enumerate(zip(unChars, chOcc)):
        luchs = len(uchs)
        verifyRequired = True
        if luchs == 1:
            if uchs[0][1] == 1:
                # one unknown which occurs once
                # solve for value
                # verify its unused and non-zero (if in firsts)
                c1, c2 = codeForSolve(uchs[0][0], chCounts, rhs[i], indent, i, firsts)
                c1s.append(c1), c2s.append(c2)
                indent += 4
                verifyRequired = False
            else:
                # one unknown which occurs multiple times
                # for loop to guess values
                # verify sum
                c1, c2 = codeForGuess(uchs[0][0], firsts, indent)
                c1s.append(c1), c2s.append(c2)
                indent += 4
        elif luchs > 1:
            for ch, occ in uchs[:-1]:
                c1, c2 = codeForGuess(ch, firsts, indent)
                c1s.append(c1), c2s.append(c2)
                indent += 4

            ch, occ = uchs[-1]
            if occ > 1:
                c1, c2 = codeForGuess(ch, firsts, indent)
                c1s.append(c1), c2s.append(c2)
                indent += 4
            else:
                c1, c2 = codeForSolve(uchs[-1][0], chCounts, rhs[i], indent, i, firsts)
                c1s.append(c1), c2s.append(c2)
                indent += 4
                verifyRequired = False

        if verifyRequired:
            c1, c2 = codeForVerifySum(chCounts, rhs[i], indent, i)
            c1s.append(c1), c2s.append(c2)
            indent += 4

    c1, c2 = codeForFinalCheck(i, characters, indent, problem)
    indent += 4
    c1s.append(c1)

    c1s = [x for x in c1s if x]
    c2s = [x for x in c2s if x]

    program = program1 + "\n".join(c1s) + "\n".join(reversed(c2s)) + program3
    return program


test_cases = [
    ["send", "more", "money"],
    ["zeroes", "ones", "binary"],
    ["send", "a", "tad", "more", "money"],
    ["seven", "seven", "six", "twenty"],
    ["saturn", "uranus", "neptune", "pluto", "planets"],
    ["donald", "gerald", "robert"],
    ["fifty", "twenty", "nine", "one", "eighty"],
    ["forty", "ten", "ten", "sixty"],
    ["ein", "ein", "ein", "ein", "vier"],
    ["lets", "solve", "this", "little", "teaser"],
    ["eleven", "lagers", "revive", "general"],
    ["she", "will", "wash", "these", "shirts"],
    ["have", "a", "happy", "happy", "easter"],
    ["ohio", "hawaii", "kansas", "alaska", "indiana"],
    ["tonto", "andthe", "lone", "ranger"],
    ["accentuate", "concertina", "transsonic", "instructor"],
    ["apolitical", "penicillin", "pickpocket", "knickknack"],
    ["coincidence", "electrician", "accelerator"],
    ["compromise", "stretchiest", "microscopic", "homestretch"],
    ["happy", "holidays", "to", "all", "hohohoho"],
    ["aries", "leo", "libra", "pisces"],
    ["gemini", "virgo", "cancer"],
    ["see", "three", "little", "wolves"],
    ["earth", "air", "fire", "water", "nature"],
    ["dclix", "dlxvi", "mccxxv"],
    ["couple", "couple", "quartet"],
    ["fish", "n", "chips", "supper"],
    ["store", "and", "name", "brands"],
    ["this", "isa", "great", "time", "waster"],
    ["the", "dog", "got", "her", "on", "the", "hand", "again"],
    ["when", "i", "really", "want", "a", "thrill"],
    ["what", "a", "week", "at", "news", "this", "has", "been"],
    ["this", "it", "seems", "to", "me", "is", "the", "heart", "of", "the", "matter"],
    ['apperception', 'aristocratic', 'concessionaire', 'conscription',
     'inappropriate', 'incapacitate', 'inconsistent',
     'interception', 'osteoporosis', 'perspiration', 'prescription',
     'proscription', 'prosopopoeia', 'protectorate', 'protestation',
     'statistician', 'transoceanic', 'transpiration',
     'antiperspirant'],
]


for tc in test_cases:
    program = createProgram(tc)
    #print program
    exec program

et = time() - st
print 'elapsed time : %10.6f' % (et)
print 'average time : %10.6f' % (et / len(test_cases))


# Following is a sample program created by this solution

"""
def word2num(word, values):
    num = 0
    for c in word:
        num = num * 10 + values[c]
    return num

def myfunc(words):
    unused = set(range(10))
    urem = unused.remove
    uadd = unused.add
    udiff = unused.difference
    ucopy = unused.copy
    set0 = set([0])
    sm0 = 0
    lhs = words[:-1]
    rhs = words[-1]

    for n in ucopy():
        urem(n)
        for e in ucopy():
            urem(e)
            for c in udiff(set0):
                urem(c)
                for t in udiff(set0):
                    urem(t)
                    for s in udiff(set0):
                        urem(s)
                        value = sm0/10 + n*9 + c*2 + e*4 + t*1 + s
                        a = (t - value) % 10
                        if a in unused and a != 0:
                            urem(a)
                            sm1 = value + a
                            for o in udiff(set0):
                                urem(o)
                                for i in udiff(set0):
                                    urem(i)
                                    value = sm1/10 + o*8 + i*4 + t*3 + n*1 + a
                                    r = (n - value) % 10
                                    if r in unused:
                                        urem(r)
                                        sm2 = value + r
                                        sm3 = sm2/10 + i*10 + t + a*3 + e*2 + s + n
                                        if a == sm3 % 10:
                                            sm4 = sm3/10 + t*10 + a*3 + i + o*2 + r + c
                                            if r == sm4 % 10:
                                                for p in udiff(set0):
                                                    urem(p)
                                                    sm5 = sm4/10 + p*6 + r*3 + n + i*2 + s + a*3 + o + e
                                                    if i == sm5 % 10:
                                                        sm6 = sm5/10 + e*2 + c*3 + o*3 + i*4 + p + r*2 + t*3
                                                        if p == sm6 % 10:
                                                            sm7 = sm6/10 + c*3 + o*3 + i*3 + r*3 + a + s*3 + p*2
                                                            if s == sm7 % 10:
                                                                sm8 = sm7/10 + r*3 + t + s*2 + c*3 + p*3 + n + o*2 + e*2 + i
                                                                if r == sm8 % 10:
                                                                    sm9 = sm8/10 + e*3 + s*8 + p + a + o + t*3 + n
                                                                    if e == sm9 % 10:
                                                                        sm10 = sm9/10 + p*2 + i + e*2 + n*2 + c*2 + t*2 + r + o*4 + a*2
                                                                        if p == sm10 % 10:
                                                                            sm11 = sm10/10 + p + r*7 + c + o + a*2 + n*3 + s + e + t
                                                                            if i == sm11 % 10:
                                                                                sm12 = sm11/10 + a*2 + n*2 + c + i*3 + o + p*6 + s + t + r
                                                                                if t == sm12 % 10:
                                                                                    sm13 = sm12/10 + o + i + t
                                                                                    if n == sm13 % 10:
                                                                                        sm14 = sm13/10 + c
                                                                                        if a == sm14 % 10:
                                                                                            if sm14 < 10:
                                                                                                values = { 'a': a, 'c': c, 'e': e, 'i': i, 'o': o, 'n': n, 'p': p, 's': s, 'r': r, 't': t }
                                                                                                lwords = [str(word2num(v, values)) for v in lhs]
                                                                                                rword = str(word2num(rhs, values))
                                                                                                return "%s = %s" % (" + ".join(lwords), rword)
                                                    uadd(p)
                                        uadd(r)
                                    uadd(i)
                                uadd(o)
                            uadd(a)
                        uadd(s)
                    uadd(t)
                uadd(c)
            uadd(e)
        uadd(n)
    return "not solved"

try:
    print myfunc(['apperception', 'aristocratic', 'concessionaire', 'conscription', 'inappropriate', 'incapacitate', 'inconsistent', 'interception', 'osteoporosis', 'perspiration', 'prescription', 'proscription', 'prosopopoeia', 'protectorate', 'protestation', 'statistician', 'transoceanic', 'transpiration', 'antiperspirant'])
except:
    from traceback import print_exc
    print_exc()

"""