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 resultOnce 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], ' = ', iWhen 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.

Nice example... they should have run this at my uni when talking about RPN!

ReplyDelete