Crypt-arithmetic solver (Brute force) in Python

Question

I'm working on a crypt-arithmetic solver to add two or more numbers. I've used brute-force to find all the permutations. I'm looking forward to improve this algorithm. Kindly review for all the aspects of this code and provide me your comments.

import string
import itertools
inListNumsAsStringArray = [ ['BASE', 'BALL'], 
                            ['SEND', 'MORE'] ]
inResultsArray = [ 'GAMES',
                'MONEY' ]
inPossibleNumsAsStr = '0123456789'

# Input: (string, dictionary)
#   string 'AB'
#   key-value pairs for characters and numbers. Ex: dictCharAndDigit = {'A': '1', 'B': '2'}
# Output:(Number)
#   12
def getNumberFromStringAndMappingInfo(inStr, inDictMapping):
    numAsStr = ''
    for ch in inStr:
        numAsStr = numAsStr + inDictMapping[ch] 
    return int(numAsStr)

def solveCryptarithmeticBruteForce(inListNumsAsString, inResultStr, inPossibleNumsAsStr):
    nonZeroLetters = []
    strFromStrList = ''
    for numStr in inListNumsAsString:
        nonZeroLetters.append(numStr[0])
        strFromStrList = strFromStrList + numStr
    nonZeroLetters.append(inResultStr[0])
    strFromStrList = strFromStrList + inResultStr  
    uniqueStrs = ''.join(set(strFromStrList))
    for tup in itertools.permutations(inPossibleNumsAsStr, len(uniqueStrs)):
        dictCharAndDigit = {}
        for i in range(len(uniqueStrs)):
            dictCharAndDigit[uniqueStrs[i]] = tup[i]            
        nonZeroLetterIsZero = False
        for letter in nonZeroLetters:
            if(dictCharAndDigit[letter] == '0'):
                nonZeroLetterIsZero = True
                break
        if(nonZeroLetterIsZero == True):
            continue
        result = getNumberFromStringAndMappingInfo(inResultStr, dictCharAndDigit)     
        testResult = 0
        for numStr in inListNumsAsString:
            testResult = testResult + getNumberFromStringAndMappingInfo(numStr, dictCharAndDigit)        

        if(testResult == result):
            strToPrint = ''
            for numStr in inListNumsAsString:
                strToPrint = strToPrint + numStr + '(' + str(getNumberFromStringAndMappingInfo(numStr, dictCharAndDigit)) + ')' + ' + '
            strToPrint = strToPrint[:-3]
            strToPrint = strToPrint + ' = ' + inResultStr + '(' + str(result) + ')'
            print(strToPrint)
            break

for i in range(len(inResultsArray)):
    solveCryptarithmeticBruteForce(inListNumsAsStringArray[i], inResultsArray[i], inPossibleNumsAsStr)

Answer 1

1. Review

1. In Python it is helpful to write a docstring for each function or class that you define, explaining what it does, what arguments it takes, and what it returns. Docstrings can be accessed from the interactive interpreter using the built-in help function. For getNumberFromStringAndMappingInfo there is a comment which could be used as the basis for a docstring.

2. solveCryptarithmeticBruteForce does nothing if the puzzle has no solution. This would be easy to miss in a long list of solutions. It would be better to print something like "no solution".

3. Python programmers generally follow the Python style guide when choosing names. According to this guide, functions and variables should have names using lower_case_with_underscores (and not mixedCase as in the code in the post). You're not obliged to follow this convention but if you do then it will make it easier to collaborate with other Python programmers.

4. In Python we don't use "Hungarian" naming, in which a name indicates the type of the object named. That's because Python is a "duck-typed" in which the type of an object is not as important as the set of methods it supports. In general we find that code is clearer if names are chosen to be simple and readable rather than cluttered with details.

5. In Python we don't need to indicate for each argument to a function whether it is used for input or output. That's because functions can easily return a tuple of results, so there is no need for functions to modify their arguments in order to return multiple results.

6. inPossibleNumsAsStr is built into Python as string.digits.

7. The puzzles are represented by two lists, one of which gives the addends for each puzzle, and the other gives the results for each puzzle in the same order:

   inListNumsAsStringArray = [ ['BASE', 'BALL'], 
                               ['SEND', 'MORE'] ]
   inResultsArray = [ 'GAMES',
                   'MONEY' ]
   

   This kind of data organization is hard to follow and error-prone. It's just about ok here where you only have two puzzles, but imagine having a hundred puzzles — how would you check that puzzle 57 had been entered correctly and not accidentally mixed up with puzzles 56 and 58?

   The approach I would take would be to represent the puzzles like this:

   PUZZLES = '''
   BASE + BALL = GAMES
   SEND + MORE = MONEY
   '''
   

   The advantages of this representation are that it is clear what it means (no need for complex documentation) and it keeps each puzzle on one line, so that adding and removing puzzles is easy. The data structure can easily be processed by splitting each line into its constituent pieces, like this:

   for puzzle in PUZZLES.strip().splitlines():
       addition, result = puzzle.split(' = ')
       addends = addition.split(' + ')
       solveCryptarithmeticBruteForce(addends, result, string.digits)
   

8. The initial letters (that must be non-zero) might include duplicates. So it would make sense to remove duplicates in the same way as you do with uniqueStrs.

9. The function getNumberFromStringAndMappingInfo translates a string by mapping each character through a dictionary. But this can be done using the built-in str.translate method. The way you use this is to call str.maketrans to make the translation table. So instead of:

   for tup in itertools.permutations(inPossibleNumsAsStr, len(uniqueStrs)):
       dictCharAndDigit = {}
       for i in range(len(uniqueStrs)):
           dictCharAndDigit[uniqueStrs[i]] = tup[i]            
   

   I would write:

   for perm in itertools.permutations(inPossibleNumsAsStr, len(uniqueStrs)):
       decipher_table = str.maketrans(uniqueStrs, ''.join(perm))
       def decipher(s):
           return s.translate(decipher_table)
   

   and then instead of:

   result = getNumberFromStringAndMappingInfo(inResultStr, dictCharAndDigit)
   

   I would write:

   result = int(decipher(inResultStr))
   

   This would avoid the need for the getNumberFromStringAndMappingInfo function.

10. Instead of building a string strFromStrList that concatentates the addends and result, and then turning this into a set in order to eliminate duplicates, build the set directly. That is, instead of:

    strFromStrList = ''
    for numStr in inListNumsAsString:
        strFromStrList = strFromStrList + numStr
    strFromStrList = strFromStrList + inResultStr  
    

    I would write:

    letters = set(result)
    for addend in addends:
        letters.update(addend)
    letters = ''.join(letters)
    

    And this could be made even shorter using itertools.chain:

    letters = ''.join(chain(result, *addends))
    

11. Similarly, nonZeroLetters could be constructed like this:

    initial_letters = ''.join(set(chain(result[0], (a[0] for a in addends))))
    

12. The sum of the deciphered addends can be computed using the built-in function sum. Instead of:

    testResult = 0
    for numStr in inListNumsAsString:
        testResult = testResult + getNumberFromStringAndMappingInfo(numStr, dictCharAndDigit)        
    

    I would write:

    deciphered_sum = sum(int(decipher(addend)) for addend in addends)
    

2. Revised code

from itertools import chain, permutations
from string import digits

def solve_cryptarithm(addends, result):
    """Print a solution to the cryptarithm, if any exists.
    Arguments are the list of addends and the result of the sum.
    For example:

    >>> solve_cryptarithm(['SEND', 'MORE'], 'MONEY')
    SEND(9567) + MORE(1085) = MONEY(10652)

    """
    letters = ''.join(set(chain(result, *addends)))
    initial_letters = ''.join(set(chain(result[0], (a[0] for a in addends))))
    for perm in permutations(digits, len(letters)):
        decipher_table = str.maketrans(letters, ''.join(perm))
        def decipher(s):
            return s.translate(decipher_table)
        if '0' in decipher(initial_letters):
            continue # leading zeros not allowed
        deciphered_sum = sum(int(decipher(addend)) for addend in addends)
        if deciphered_sum == int(decipher(result)):
            def fmt(s):
                return f"{s}({decipher(s)})"
            print(" + ".join(map(fmt, addends)), "=", fmt(result))
            break
    else:
        print(" + ".join(addends), "=", result, " : no solution")