Solves the generalized version of the "Make 10 with 4 numbers" game. Usage: "$ python MakeNGameSolver.py"

MakeNGameSolver.py

#coding: utf-8
from itertools import combinations
from collections import Counter
from operator import *
import random

targetNum = 10
numlist = sorted([random.randint(1,100) for i in range(100)])
searchMode = 0
# 0: Randomized search (fast for long number lists, doesn't stop if no solutions exist)
# 1: Ordered search (good for short number lists, stops as soon as one solution is found)
# 2: Exhaustive search

#======================================================================
oplist = [sub, add, truediv, mul] if searchMode == 0 else [add, sub, truediv, mul] # Order is important
ophash = {add:"+", sub:"-", mul:"*", truediv:"/"}
commutativeops = [add, mul]
#======================================================================
def allEquationsFrom(numComb):
  if len(numComb) == 1:
    yield (str(numComb[0]), numComb[0])
  else:
    for op in oplist:
      for i in shuffled(range(1,len(numComb))) if (op not in commutativeops) else shuffled(range(1,2+(len(numComb)-1)/2)):
        for leftComb in combinations(Counter(numComb), i):
          for leftEq in allEquationsFrom(leftComb):
            for rightEq in allEquationsFrom(listSubtraction(numComb,leftComb)):
              yield eqValPair(op, leftEq, rightEq)

def eqValPair(op, leftPair, rightPair):
  try: val = op(leftPair[1],rightPair[1])
  except: val = "NaN"
  return ("(" + leftPair[0] + ophash[op] + rightPair[0] + ")", val)

def shuffled(orig):
    dest = list(orig)
    random.shuffle(dest)
    return dest

def listSubtraction(U,S):
  return list((Counter(U) - Counter(S)).elements())

#======================================================================
def randomizedSearch(targetNum, numlist):
  while True:
    iterCounter = 0
    for x in allEquationsFrom(numlist):
      iterCounter += 1
      if iterCounter >= 100:
        break
      elif(x[1] == targetNum):
        print str(targetNum) + " = " + x[0]        
        return

def orderedSearch(targetNum, numlist):
  solutionCount = 0
  for x in allEquationsFrom(numlist):
    if(x[1] == targetNum):
      print str(targetNum) + " = " + x[0]
      solutionCount += 1
      if searchMode == 1:
        return
  print str(solutionCount) + " equations make " + str(targetNum) + " for these numbers (searched exhaustively)"

#======================================================================
if __name__ == '__main__':
  print numlist
  print "Calculating..."
  (randomizedSearch if searchMode == 0 else orderedSearch)(targetNum, numlist)

Sample output: (searchMode = 0)

[1, 2, 4, 5, 5, 6, 6, 7, 7, 7, 8, 9, 9, 10, 11, 11, 15, 16, 16, 17, 18, 20, 22, 24, 24, 25, 25, 25, 28, 30, 31, 32, 34, 34, 35, 36, 39, 39, 40, 42, 43, 43, 48, 48, 49, 49, 50, 52, 54, 54, 54, 54, 56, 58, 60, 63, 63, 64, 64, 64, 65, 66, 67, 68, 68, 71, 74, 75, 76, 77, 77, 79, 80, 80, 81, 81, 82, 82, 83, 83, 84, 84, 85, 87, 87, 88, 90, 91, 91, 93, 95, 95, 97, 97, 97, 98, 98, 99, 99, 100]
Calculating...
10 = (((((((1-2)-(4-5))-5)-6)-((6-7)-((7-7)-(8-9))))-((((9-(10-11))-((11-(((15-16)-(16-17))-(18-20)))-(22-24)))-((24-25)-(25-(25-28))))-(30-(31-32))))-((((34-((34-(35-36))-39))-(((((39-40)-42)-(((43-43)-((((48-(48-49))-49)-(50-52))-(54-54)))-(((54-54)-56)-((58-60)-63))))-(((63-64)-(64-(((64-65)-(66-67))-68)))-(68-(71-(74-(((75-76)-77)-(77-(79-80))))))))-(80-(81-81))))-(82-82))-((83-83)-((((84-84)-85)-((((87-87)-88)-(90-(91-91)))-(((93-95)-95)-(((97-(97-97))-98)-98))))-((99/99)-100)))))