03 digression by brute force

Tue Dec 11 21:06:59 EST 2018

SYNOPSIS: One way to solve math puzzle by brute force. (message sent earlier disappeared)

Quick note. Jack started by asking why python does not like decimal numbers with leading zeroes. When asked to explain, he said he was trying to solve word problems using python. Someone mentioned problems like solving SEND + MORE = MONEY and I decided to quickly write a function that would solve anything of that sort that only has addition on either side of the equals.

What amused me was that I had 25 solutions to the above when I was told there would be one. Closer examination showed that 24 of those had the ‘M’ in MONEY set to zero which the logicians claimed was not a sensible solution.

This solution is one of a list of 25 dictionaries returned, printed with pprint.print:

{' SYNOPSIS': 'PUZZLE: SEND+MORE=MONEY with SOLUTION #1: 7429+0814=08243',

'D': '9',

'E': '4',

'M': '0',

'N': '2',

'O': '8',

'R': '1',

'S': '7',

'Y': '3'}

Note M == 0

The lone normal answer is:

{' SYNOPSIS': 'PUZZLE: SEND+MORE=MONEY with SOLUTION #25: 9567+1085=10652',

'D': '7',

'E': '5',

'M': '1',

'N': '6',

'O': '0',

'R': '8',

'S': '9',

'Y': '2'}

Apparently, unless you tell the program to skip any attempts where M is not 1, it finds these. I will spare the rest but include the code if you wish to try it. I called the function this (perhaps odd) way:

puzzle = "SeND+ MoRe =    MoNeY???!!!!!!!!!!!!"

solution25 = math_word_puzzle_solver(puzzle)

And it returned a list of the 25 dicts.

So I tried this puzzle:

puzzle = "SeND + MoRe = oNeY"

I guessed (wrongly) that by removing the offending M in MONEY, it would find only the other 24 solutions with the M in MORE being 0.

Not quite. That got 108 solutions! M was just about anything:

[d['M'] for d in solution108 ]

['6', '2', '5', '3', '6', '2', '5', '3', '7', '1', '6', '2', '7', '6', '2', '1', '5', '3', '7', '1', '5', '2', '5', '2', '7', '0', '7', '0', '4', '3', '7', '0', '8', '0', '4', '3', '8', '0', '8', '0', '6', '2', '5', '1', '6', '0', '5', '1', '6', '0', '5', '1', '7', '0', '4', '3', '7', '0', '7', '6', '1', '0', '7', '0', '4', '1', '5', '0', '6', '4', '2', '0', '6', '0', '6', '0', '3', '1', '5', '0', '5', '0', '3', '2', '2', '1', '2', '1', '2', '1', '3', '0', '2', '1', '3', '0', '3', '1', '2', '0', '2', '0', '3', '0', '3', '0', '2', '1']

My main point though is that a leading zero can appear including in bank account numbers, social security numbers and so on. But I accept that historically python is as it is. As I mentioned, some functions like int() can deal with them.

I attach my code in case anyone is interested in seeing the whole output or trying it on other puzzles. The code uses no exec() or eval() and should be safe 😊

########################CODE################

# Module created to solve a specific kind of math word problem.

# FIND all solutions to a puzzle by systematically

# replacing LETTERS with NUMERALS till an equation is True

# Accepts string like "SEND + MORE = MONEY"

# Measure time elapsed, optional:

def math_word_puzzle_solver(puzzle):

    """USAGE: math_word_puzzle_solver(puzzle)"""

    """Solve a puzzle by brute force"""

    """of the form SEND + MORE = MONEY"""

    """with arbitrary sums on either side of"""

    """the equation."""

    # NOTE: comments illustrate what happens to the test case only.

    # Assuming the user typed in garbage, will restrict characters and normalize.

    # Remove whitespace and most other things except +/=, make uppercase, etc.

    puzzle = puzzle.upper()

    retain = set('ABCDEFGHIJKLMNOPQRSTUVWXYZ=+')

    puzzle = ''.join(filter(retain.__contains__, puzzle))

    # puzzle := 'SEND+MORE=money'

    # Split into left/right on the equals sign:

    left_text, right_text = puzzle.split('=')

    # left_text  := 'SEND+MORE'

    # right_text :=  'MONEY' (or 'ONEY')

    # Split each side into a list on "+" and in the test case

    # only the left side has more than one:

    left_list = left_text.split('+')

    right_list = right_text.split('+')

    # At this point we have:

    # left_list: ['SEND', 'MORE']

    # right_list: ['MONEY']

    # Combine everything in both lists to make a set with unique letters.

    letter_set = { letter

                   for word in (left_list + right_list)

                   for letter in word }

    # Letter_set := {'M', 'O', 'R', 'Y', 'N', 'S', 'E', 'D'}

    letter_count = len(letter_set)

    # letter_count := 8

    # Make an iterator to deliver one combination at a time 

    # of the n-tuple of n digits at a time from 0-9 with no replacement

    # and luckily that problem is solved by using the itertools module:

    import itertools

    # We want all permutations taken letter_count at a time

    # so the iterator will return an 8-tuple in this example looking like:

    #    ('0', '1', '2', '3', '4', '5', '6', '7')

    #    ('0', '1', '2', '3', '4', '5', '6', '8')

    # and so on. If run to completion, 1814400 iterations in this case.

    # Next line returns an iterator that will be iterated later.

    n_tuples = itertools.permutations( iterable = "0123456789",

                                       r = letter_count)

    # Overview to minimize comments below. Loop on all such n-tuples.

    # For each result, use a dictionary to make substitutions

    # from letters to numerals on all the text.

    # Convert number strings  to numbers.

    # Calculate if sum of left numbers == sum of right numbers.

    letter_tuple = tuple(letter_set)

    # Make a list to hold solutions and count them.

    solutions = []

    solution_count = 0

    # Now to loop several levels

    for n_tuple in n_tuples:

        # Make a translation dictionary for this iteration

        xlate = dict(zip(letter_tuple, n_tuple))

        # initialize sums to zero each time.

        sum_left = sum_right = 0

        # A tad complex. for each "word" as in "SEND" or "MORE"

        # get the letters in word and replace from the dictionary

        # each letter with a numeral then join the numerals back

        # into a single string and convert that to an integer and

        # add it to the sum. In this case, add something like

        # 9567 + 1085 = 10652

        for word in left_list:

            sum_left += int("".join([ xlate[letter]

                                      for letter in word]))

        # Ditto for the right list which only happens to have

        # a single occupant but could have more. May have a sum of

        # anything but in one case 10652 is tried.

        for word in right_list:

            sum_right += int("".join([ xlate[letter] for letter in word]))

        # Time to see if the sums match. If so, add the original

        # problem statement and the numeric translation/solution to the dict

        # As well as the solution number.

        if sum_left == sum_right:

            solution_count += 1

            # Make a copy of the solution dictionary

            # augmented to replace + and = with themselves.

            temp=xlate.copy()

            temp["="] = "=" 

            temp["+"] = "+"

            solution_xlated = "".join([ temp[letter]

                                       for letter in puzzle])

            annotation = f"PUZZLE: {puzzle} with SOLUTION #{solution_count}: {solution_xlated}"

            # Add an annotation to the dictionary

            xlate[" SYNOPSIS"] = annotation

            # Add the solution to the list to be returned later.

            solutions.append(dict(sorted(xlate.items(), key =lambda x: x[0])))

    return(solutions)           

    #  END function definition for math_word_puzzle_solver(puzzle)

if __name__ == "__main__":

    # This is being run as a program so,

    # calling the function with the default puzzle

    import time, pprint

    start_time = time.time()

    print("=============TWENTY FIVE solutions expected")

    print("=============TWENTY FOUR have M==0")

    puzzle = "SeND+ MoRe =    MoNeY???!!!!!!!!!!!!"

    solution25 = math_word_puzzle_solver(puzzle)

    print("======\nELAPSED TIME: ", time.time() - start_time)

    pprint.pprint( solution25 )

    puzzle = "SeND + MoRe = oNeY"

    solution108 = math_word_puzzle_solver(puzzle)

    print("======\nELAPSED TIME: ", time.time() - start_time)

    pprint.pprint( solution108 )

#########NO MORE CODE#################