Newsletter

Can you make (10, 10, 9, 9, 1, +, /, -, *) = 4?

Last night at around 10pm I got a text from my friend asking how you could combine the numbers 10, 10, 9, 9, and 1, to make 4, using only addition, subtraction, multiplication, and/or division, provided you use the numbers once each.

I didn't start thinking about it until later (sorry Mike), but at 2 am I got frustrated and, as I seem wont to do, ignored reasonable priorities (such as sleeping, or the rest of my todo list) and sat down to write a program to enumerate all of the possible solutions, instead of just figuring it out myself.

Below is a general solution to the problem. The basic idea is it is simple enough to consider all the valid possible combinations of the numbers in Reverse Polish Notation (postfix), and evaluate them.

#!/usr/bin/python2.5

def add(x, y): return x + y
def sub(x, y): return x - y
def mult(x, y): return x * y
def div(x, y): return float(x) / y
OPERATIONS = [add, sub, mult, div]
REPRESENTATIONS = {add: '+', sub: '-', mult: '*', div: '/'}

def new_counter(counter, item):
  if counter is None: counter = 0
  if type(item) == type(add): return counter - 1
  else: return counter + 1

def valid_perms(lst, counter=None):
  if counter is not None and counter <= 0: return
  if len(lst) == 1:
    if new_counter(counter, lst[0]) != 1: return
    yield lst
  else:
    for i in xrange(len(lst)):
      for perm in valid_perms(lst[:i]+lst[i+1:], new_counter(counter, lst[i])):
        yield [lst[i]] + perm

def all_combos(lst, n):
  if n == 0: yield []
  else:
    for i in xrange(len(lst)):
      for combo in all_combos(lst, n - 1):
        yield [lst[i]] + combo

def uniq(generator):
  seen_things=set([])
  for thing in generator:
    if tuple(thing) not in seen_things:
      seen_things.add(tuple(thing))
      yield thing

def valid_postfix_stacks(nums):
  for op_combo in uniq(all_combos(OPERATIONS, len(nums) - 1)):
    for perm in uniq(valid_perms(nums + op_combo)):
      yield perm

def compute(stack):
  s = []
  for item in stack:
    if type(item) != type(add):
      s.append(item)
    else:
      s.append(item(*reversed([s.pop(), s.pop()])))
  assert len(s) == 1
  return s[0]

def infix(stack):
  s = []
  for item in stack:
    if type(item) != type(add):
      s.append(str(item))
    else:
      s.append('(' + ' '.join(reversed([s.pop(), REPRESENTATIONS[item], s.pop()])) + ')')
  assert len(s) == 1
  return s[0]

def main(nums, answer, tol=.0001, find_all=False):
  print "searching..."
  found = False
  for postfix_stack in uniq(valid_postfix_stacks(nums)):
    try: val = compute(postfix_stack)
    except ZeroDivisionError, e: continue
    if (float(val) + float(tol)/2 >= float(answer) and float(val) - float(tol)/2 <= float(answer)):
      print infix(postfix_stack), '=', val
      found = True
      if not find_all: break
  if not found: print "no solutions found"

if __name__ == "__main__":
  main([10,10,9,9,1], 4)