4x4s in Python

I recently came across a nice little game. As far as I can tell, you are required to make as many numbers as possible using only four 4s. So, for example:
4 * 4 / 4 * 4 = 1
(4 / 4) + (4 / 4) = 2
(4 + 4 + 4) / 4 = 3
etc.

I played the game until I got up to about 5 then thought it would be much more rewarding to write a little Python program to see how many numbers under 100 I could generate using only four 4s.

There may be a better way to do this, but my simple approach was to generate all the permutations of four 4s together with the permissible set of operators (ie. +, -, x, / and ^). This gives us 7 characters. However, we also need to consider parentheses since (4 + 4 + 4) / 4 gives a very different result to 4 + 4 + (4 / 4). As soon as we include parentheses, we start getting into 'intractable land'. In other words, the number of permutations that we can generate becomes impractical. As anyone who has ever owned an HP calculator (the real ones manufactured in the 1980s) knows, any parenthesised expression can be expressed in Reverse Polish Notation without parentheses. Very briefly, this means that we use a stack on push operands onto the stack. As soon as we encounter an operator (we will assume we only have binary operators), we pop two values from the stack, apply the operator and push the result back onto the stack. We can now express the previous two examples using RPN (Reverse Polish Notation).

(4 + 4 + 4) / 4 becomes 444++4/

and

4 + 4 + (4 / 4) becomes 4444/++

Fortunately, writing a function to evaluate an RPN expression is straightforward. Here is one implementation.

def eval_rpn(exp):
    stack = []
    for ch in exp:
        if isdigit(ch):
            stack.append(int(ch))
        if isoperator(ch):
            if len(stack) < 2:
                return None
            rhs = stack.pop()
            lhs = stack.pop()
            if ch == '+':
                stack.append(lhs + rhs)
            elif ch == '-':
                stack.append(lhs - rhs)
            elif ch == '*':
                stack.append(lhs * rhs)
            elif ch == '/':
                if rhs == 0:
                    return None
                stack.append(lhs / rhs)
            elif ch == '^':
                stack.append(lhs ** rhs)
    result = stack.pop()
    return result

Once we have this, the rest is easy. We just generate all permutations of the four digits and the allowable operators. We end up with the following program:

'''
A program to evaluate each combination of 4 digits
'''

import itertools

operators = ['+','-','*','/','^']
digits = ['4','4','4','4']


pattern = operators + digits

results = {}

def isdigit(ch):
    return ch in '0123456789'


def isoperator(ch):
    return ch in '+-*/^'

def eval_rpn(exp):
    stack = []
    for ch in exp:
        if isdigit(ch):
            stack.append(int(ch))
        if isoperator(ch):
            if len(stack) < 2:
                return None
            rhs = stack.pop()
            lhs = stack.pop()
            if ch == '+':
                stack.append(lhs + rhs)
            elif ch == '-':
                stack.append(lhs - rhs)
            elif ch == '*':
                stack.append(lhs * rhs)
            elif ch == '/':
                if rhs == 0:
                    return None
                stack.append(lhs / rhs)
            elif ch == '^':
                stack.append(lhs ** rhs)
    result = stack.pop()
    return result


# Try every permutation of 7 characters...
for exp in itertools.permutations(pattern, 7):
    e = ''.join(exp)
    val = eval_rpn(e)
    if val is not None and int(val) == val and val >= 0:
        results[val] = ''.join(e) 

for i in range (1, 100):
    if i in results:
        print results[i], ' = ', i

When we run the program, we get the following output:

4444*/^  =  1
444+4/-  =  2
444/4^-  =  3
4444^/-  =  4
4444-^+  =  5
4444/-+  =  7
4444/^+  =  8
4444/-*  =  12
44*44/-  =  15
4444/^*  =  16
44/44*+  =  17
4444/+*  =  20
444+*4-  =  28
44^44+/  =  32
44^4/4-  =  60
44^4-4/  =  63
4444/-^  =  64
444^+4/  =  65
444^4/+  =  68
444/-4^  =  81

After doing this, I noticed that we had more gaps than I expected. I reread the rules of the game and realised that an expression like 44 + 44 is also valid. However, I don't think it's a hard feature to add (or is it?). If I was going to spend a little more time on this program, it would be to present the results in infix notation. Maybe for the moment I will leave that as an exercise for the reader.