A Python in a maze: first fit

italian

A puzzle can be a funny exercise for improving mathematical knowledge/technique. When one gets into the habit of mixing coding and maths/science then using a hybrid approach seems quite natural. Since this is a blog on math and teaching now I want to emphasize the way one can turn a puzzle into a chance for training both the maths and the coding skills at once, and also the way one skillset can help the other one to kick in. The following puzzle has been proposed to me by a student in a class.

Each letter stands for a unique one digit number (it is safe to assume that the most significant digits/letters are not zero, i.e. F, O and T are different from zero):


FIVE -
FOUR =
------
 ONE +
 ONE =
------
 TWO

Solving this problem involves doing some deduction based on the statement of the problem and the basic mechanics of addition and subtraction (i.e. rules for carry/borrow).
Surely there is some logic involved in the solution, but by employing what someone calls the “computational thinking” probably one can arrive to the solution(s) in a more convenient way than chaining countless (or at least many) clauses.

What would a machine do to solve the problem? One chance would be to brute-force our way out of the maze. In example one could generate all possible permutations of the values of the letters, and see whether each of them fulfills the constraint. An easy solution could be this very basic Python script

from itertools import permutations


def tonum(*a): # convert tuples to integer numbers
    l = len(a)
    res = 0
    for i in xrange(l):
         res += a[i]*10**(l-i-1)
    return res


solutions = [
    (
        tonum(f,i,v,e), 
        tonum(f,o,u,r), 
        tonum(o,n,e), 
        tonum(t, w, o)
    ) for (f, i, v, e, o, u, r, n, t, w) in permutations(range(10)) 
        if tonum(f,i,v,e)-tonum(f,o,u,r)==tonum(o,n,e) and 
            tonum(o, n, e)*2 == tonum(t, w, o)]


# report

print "%d solutions found:" % (len(solutions), )
print
for five, four, one, two in solutions:
    print "%4d -" % (five,)
    print "%4d =" % (four,)
    print "------"
    print "%4d +" % (one,)
    print "%4d =" % (one,)
    print "------"
    print "%4d" % (two, )
    print

Of course this is not particularly fast/efficient, as it generates all of the 10! permutations and keeps only the good ones. But it teaches us a scheme to solve a combinatorial puzzle like this one. We only have to devise a strategy that allows us to keep track manually of the possibilities saving all unneeded efforts.

Permutations

First things first: how to generate all permutations of (say) the numbers 0, 1, 2?
Start with the first number, like so

level 0     *
            |
level 1     0 (1,2) 

From the remaining numbers (the ones in parentheses) extract next one, and so on

level 0     *
            |
level 1     0 (1,2)
            |
level 2     1 (2) 
            |
level 3     2 ()

When one consumes all the numbers the backtrack occurs: go back on your steps, keeping track of what you have done so far, and try all the possible alternatives along the way

level 0         *
                |
level 1         0 (1,2)
             /--'--\
level 2     1 (2)   2 (1)
            |       |
level 3     2       1

And on again

level 0                        *
                 /-------------|-------------\
level 1         0 (1,2)        1 (0,2)        2 (0,1)
             /--'--\        /--'--\        /--'--\
level 2     1 (2)   2 (1)  0 (2)   2 (0)  0 (1)   1 (0)
            |       |      |       |      |       |
level 3     2       1      2       0      1       0

perm:      012     021    102     120    201     210

I hope the drawing is clear enough, we basically build a tree, and use this to keep track of the possibilities.

From trees to tables (math for carpenters?)

The tree has a beautiful and very terse structure, but can be unwieldy to draw. One can then change it into a table, so that the tree above becomes

level 0 level 1 level 2 level 3 permutation
* 0 1 2 012
2 1 021
1 0 2 102
2 0 120
2 0 1 201
1 0 210

Again, I hope the table speaks by itself: can you see why it is equivalent to the tree above? We will use tables like this one to keep track of the possible solutions, but we’ll keep things from spin out of control, trying to avoid tables too big to handle with pencil and paper.

We’ll work on this again in a following post, but in the meanwhile you can try to go on all by yourselves starting from this point, with a bit of good will, just to have some fun with a bit of exercise.

Advertisements

One thought on “A Python in a maze: first fit

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s