Train Numbers

The train number game is as follows:


Given a 4-digit 'train number', insert mathematical operators between all digits (no concatenation) in a way such that the expression evaluates to 10.


The 'train' bit refers to the fact that the game is often played on Sydney public transport, where buses and train carriages have 4-digit serial numbers.


The task I gave myself is this: given a train number and only the operators +-*/, find all the possible solutions. No bracketing! The order of operations should be the default mathematical system: division, multiplication, subtraction and addition. I wanted my solution to be as concise as possible. This is the result:

from __future__ import division
import itertools
n = map(int, raw_input())

for c in itertools.product(*('+-*/',)*3):
        s = 7*'%s' % sum(zip(c, n[1:]), (n[0],))
        try:
            if eval(s) == 10:
                print s
        except ZeroDivisionError:
            pass

...and this is the line-by-line breakdown:

from __future__ import division
import itertools

The first import statement makes '/' evaluate all division as decimal division. This is generally unwanted in older Python versions but it's useful here. In Python 3.0+ you won't need it as '/' always does decimal division. itertools is a fantastic library which includes a variety of useful functions implemented as iterators including a Cartesian product function, permutations/combinations functions and a function to chain iterables. I'm using the Cartesian product function in this code.

n = map(int, raw_input())

Take in a string as input (e.g. '4917'), use it as an iterable and map the int() function onto each element, resulting in [4, 9, 1, 7].

for c in itertools.product(*('+-*/',)*3):

Heh, this one's neat. itertools.product takes a variable number of iterable arguments and finds the Cartesian product of the arguments. I want it to find all possible 3 arrangements of the same operators, I'm giving it 3 identical arguments (by conveniently multiplying my argument tuple by 3) then putting a * at the front to unpack the tuple. It expands as the following:

for c in itertools.product('+-*/', '+-*/', '+-*/'):

Cool. Now for the really cool line:

s = 7*'%s' % sum(zip(c, n[1:]), (n[0],))

If you haven't realised yet, what I'm doing is generating all possible expressions as strings then evaluating them. This is the line that formats the string. It's always going to be in the format 'number operator number operator number operator number': 7 different elements, explaining the 7*'%s' bit.


The sum() function can actually take in a second argument. To illustrate how this argument operates, here is my implementation of the sum function (assuming the first argument is always the iterable you're summing):

def sum(iterable, first=0):
    curSum = first
    for item in iterable:
        curSum += item
    return curSum

So if you want to use sum() to concatenate a list of tuples as I do and you don't supply an argument for the first parameter, the function will default it to 0 then throw an error when it tries to add a tuple to an int. Obviously this could be avoided if the Python implementation of the function was a bit smarter:

def sum(iterable):
    curSum = iterable[1]
    for item in iterable[1:]:
        curSum += item
    return curSum

I don't know why they don't do that. Anyway, what I'm doing is concatenating a bunch of tuples. The tuples I'm concatenating are generated by the zip() function. Zipping is simple: given two iterables, it makes a list of tuples containing respective pairs. For example, zip([1,2], [3,4]) = [(1,3), (2,4)]. The length of the zipped list is the minimum of the length of the two input lists.


Assume the train number is 3149. My code zips the operators with the tail of the train number as follows: zip(['+', '*', '*'], [1, 4, 9]), resulting in [('+', 1), ('*', 4), ('*', 9)].  It then concatenates these tuples using sum(), where the first sum argument is a single-item tuple containing the head of the train number. The result will be the 'sum' (concatenation) of [(3,), ('+', 1), ('*', 4), ('*', 9)]: (3, '+', 1, '*', 4, '*', 9). Conveniently, this tuple can be piped directly into our format string!


Now we just evaluate our expression using eval() (with some exception handling so div-by-zeros are caught) and output the expression if it evaluates to 10.