A Python in a maze: third fit

italian

Let’s continue the story from a previous post.

Since ONE + ONE = TWO we can hope to constraint the values of N to the value of W somehow. For starters we can say that because of the rightmost column when E>4 then W is odd because of the carry, while W is even when E<5

 1
ONE +
ONE =    when E is greater than 4
-----
TWO

 0
ONE +
ONE =    when E is less than 5
-----
TWO

In a table this becomes:

E W
1 even (0,2,4,6,8)
6 odd (1,3,5,7,9)
2 even (0,2,4,6,8)
7 odd (1,3,5,7,9)

Likewise, there is a similar relationship linking T and N: if T is odd there must be some carry from the nearby column, so that N>4, while T even implies N<5. In a table

T N
4 (0,1,2,3,4)
5 (5,6,7,8,9)
8 (0,1,2,3,4)
9 (5,6,7,8,9)

Notice that there are conflicts: we will resolve them sticking these minitables into the master table we are maintaining, in a moment. When W is even (no carry from E + E) the rightmost digit of N + N is W (when W is odd we must decrease it by 1 of course). A similar argument can be made for the latter table. Since we know that R = 0 we can drop the cases where either W or N are 0, or those where W = N. This leads to the table

W N
2 1
2 6
4 2
4 7
6 3
6 8
8 4
8 9
1 5
3 1
3 6
5 2
5 7
7 3
7 8
9 4

Were we to inject this table – which is quite long – into the master table that would make it too long to be manageable by hand; or not, depending on your laziness: it saturates mine for sure, so we have to find some smarter trick. The following table could be a starting point, we add columns to list the possible values for W

R O T I E W spare (including W)
0 2 4 5 1 even (2,4,6,8) 36789
0 2 4 5 6 odd (1,3,5,7,9) 13789
0 2 5 4 1 even (2,4,6,8) 36789
0 2 5 4 6 odd (1,3,5,7,9) 13789
0 4 8 9 2 even (2,4,6,8) 13567
0 4 8 9 7 odd (1,3,5,7,9) 12356
0 4 9 8 2 even (2,4,6,8) 13567
0 4 9 8 7 odd (1,3,5,7,9) 12356

We now exclude the values of W that conflict with the other letters, so in example in the first row

R O T I E W spare (including W)
0 2 4 5 1 even (2,4,6,8) 36789

W cannot have the values 2 or 4, so we get

R O T I E W spare (including W)
0 2 4 5 1 even (6,8) 36789

Now we add the column for N starting from the values for W

R O T I E W N spare (including W and N)
0 2 4 5 1 even (6,8) (3,8;4,9) 36789

We can exclude the conflicts here too

R O T I E W N spare (including W and N)
0 2 4 5 1 even (6,8) (3,8;9) 36789

Then we get the new table

R O T I E W N spare (including W and N)
0 2 4 5 1 even (6,8) (3,8;9) 36789
0 2 4 5 6 odd (3,7) (1,6;3,8) 13789
0 2 5 4 1 even (6,8) (3,8;9) 36789
0 2 5 4 6 odd (3,7) (1,6;3,8) 13789
0 4 8 9 2 even (6) (3) 13567
0 4 8 9 7 odd (1,3,5) (5;1,6;2) 12356
0 4 9 8 2 even (6) (3) 13567
0 4 9 8 7 odd (1,3,5) (5;1,6;2) 12356

Now since

T N
even (0,1,2,3,4)
odd (5,6,7,8,9)

we obtain

R O T I E W N spare (including W and N)
0 2 4 5 1 even (6) (3) 36789
0 2 4 5 6 odd (3,7) (1;3) 13789
0 2 5 4 1 even (6, 8) (8;9) 36789
0 2 5 4 6 odd (7) (8) 13789
0 4 8 9 2 even (6) (3) 13567
0 4 8 9 7 odd (3, 5) (1;2) 12356
0 4 9 8 2 even (6) () 13567
0 4 9 8 7 odd (1, 3) (5;6) 12356

(Second to last row is empty, so we can drop it)

Now the master table becomes

R O T I E W N spare
0 2 4 5 1 6 3 789
0 2 4 5 6 3 1 789
0 2 4 5 6 7 3 189
0 2 5 4 1 6 8 379
0 2 5 4 1 8 9 367
0 2 5 4 6 7 8 139
0 4 8 9 2 6 3 157
0 4 8 9 7 3 1 256
0 4 8 9 7 5 2 136
0 4 9 8 7 1 5 236
0 4 9 8 7 3 6 125

Now We extract the last bit of information from the statement of the puzzle:

FOU +
 ON =
-----
FIV

Looking the rightmost column we see that

a. the rightmost digit of U+N equals V
b. when I is even there is no carry, hence U+N < 10, on the other hand when I is odd U+N > 9

Let’s augment the master table with the possible values for the sum of U and V

R O T I E W N spare U+N constraint
0 2 4 5 1 6 3 789 (10,11,12) U+N>9
0 2 4 5 6 3 1 789 (8,9,10) U+N>9
0 2 4 5 6 7 3 189 (4,11,12) U+N>9
0 2 5 4 1 6 8 379 (11,15,17) U+N<10
0 2 5 4 1 8 9 367 (12,15,16) U+N<10
0 2 5 4 6 7 8 139 (9,11,17) U+N9
0 4 8 9 7 3 1 256 (3,6,7) U+N>9
0 4 8 9 7 5 2 136 (3,5,8) U+N>9
0 4 9 8 7 1 5 236 (7,8,11) U+N<10
0 4 9 8 7 3 6 125 (7,8,11) U+N<10

We must enforce the constraint, obtaining

R O T I E W N U+N U V
0 2 4 5 1 6 3 (10,11,12) (7,8,9) (0,1,2)
0 2 4 5 6 3 1 (10) (9) (0)
0 2 4 5 6 7 3 (11,12) (8,9) (1,2)
0 2 5 4 6 7 8 (9) (1) (9)
0 4 8 9 2 6 3 (10) (7) (0)
0 4 9 8 7 1 5 (7,8) (2,3) (7,8)
0 4 9 8 7 3 6 (7,8) (1,2) (7,8)

If we eliminate the conflicts we delete most of the rows arriving finally at

R O T I E W N U V
0 2 4 5 6 7 3 (8) (1)
0 2 5 4 6 7 8 (1) (9)

This gives the only two solutions

3496 -
3210 =
------
 286 +
 286 =
------
 572

9516 -
9280 =
------
 236 +
 236 =
------
 472

One can verify these solutions by using the python script presented in the first post of this series.

A Python in a maze: second fit

italian

Previously we saw a strategy to solve this puzzle (each letter stands for one and only one number)

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

First we found a comfortable representation of the space of possible solutions, a representation we could handle with paper and pencil: to do this paradoxically we had to think in an algorithmic manner, as if we were going to instruct a computer to solve the problem – a very limited computer indeed!…

Let’s get started

One can rewrite the operations composing the statement of the puzzle to make the task a little bit easier. For instance rewriting the subtraction

FOUR +
 ONE =
------
FIVE

Therefore the last digit of R + E must equal E. For this to be true R = 0. From the addition

ONE +
ONE =
-----
TWO

Now the rightmost column says that O is the rightmost digit of E + E. Hence O must be one of 2, 4, 6, 8 (not 0, recall our earlier assumption), since TWO is an even number. But from the leftmost column of this sum we know that either O + O = T or (in case of carry from the nearby column) O + O + 1 = T, so that O cannot be greater than 4 (otherwise there would be a carry from the leftmost column, so that the result would be four digits long instead of three). Therefore either O = 2 or O = 4. We can use the rightmost column of the sum to infer that in the former case either E = 1 or E = 6, in the latter either E = 2 or E = 7.
Indeed if O=2

 1 +         6 +
 1 =   and   6 =
----        ----
 2          12  (we keep only the lsd 2)

Likewise for O=4

 2 +       7 +   
 2 =   e   7 =
----      ----
 4        14    (we keep only the lsd 4)

In turn we see from the addition

ONE +
ONE =
-----
TWO

that when O = 2 we can have either T = 4 or T = 5 (according to whether there is carry or not); while O = 4 implies that either T = 8 or T = 9 (again, carry).

To summarize what we’ve found

R O T E
0 2 4 1
0 2 4 6
0 2 5 1
0 2 5 6
0 4 8 2
0 4 8 7
0 4 9 2
0 4 9 7

Now let’s go back to the subtraction: since R = 0 we can write it as follows (just “forgetting” the rightmost column)

FOU +
 ON =
-----
FIV

The middle column says that either O + O = I or O + O + 1 = I (in case of carry, i.e. U + N >9). But wait a moment! We also had that either O + O = T or O + O + 1 = T. Since each letter represents a unique digit T and I cannot e equal. Let’s write this with a table (using what we know about O)

O T I
2 4 5
2 5 4
4 8 9
4 9 8

Put this into the larger table to obtain

R O T I E spare
0 2 4 5 1 36789
0 2 4 5 6 13789
0 2 5 4 1 36789
0 2 5 4 6 13789
0 4 8 9 2 13567
0 4 8 9 7 12356
0 4 9 8 2 13567
0 4 9 8 7 12356

This thing is becoming a bit large, but it enables us to keep the calculation down to a manageable size. I also added a column with the spare digits (i.e. digits we haven’t associated to a letter yet). Recall that we have the letters W, N, U, V, F yet to determine.

Now it’s time enough for another pause to reflect a little bit. I invite you to go on the path shown in this post, at least for a few steps. The end of the story in a following post.

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.

Low level, fine grained tests

A test suite with many stanzas

italian

The suite covers most of the algebraic skills you are required to own. Basically, it is a series of micro-exercises.
Carry on each exercise no matter how simple it seems, then check the answers. Each exercise has a link to the textbook where that precise subject is explained. If your answer doesn’t match the one given in the text, that means you are missing something: go back to the manual and try to fill in the gap, then try again. In the case you are still unable to find the answer all by yourself, ask the teacher during next class.
Remember that you won’t get marks for these tests, they are diagnostic tools: use them wisely!

[2015-04-08]   Update: Test suite updated (found an error on page 5)

Download PDF file