Last active
August 29, 2015 14:10
-
-
Save woodrush/3aec5e84c0c31a6c2da8 to your computer and use it in GitHub Desktop.
Solves the generalized version of the "Make 10 with 4 numbers" game. Usage: "$ python MakeNGameSolver.py"
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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)))))