# 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?

``````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.