Aug
9
While browsing around I saw a mini Python challenge to build a program that can find all solutions to the game "Total Is Right". The game has the following basic rules:
- Pick a bunch of numbers in the set:
1-10,25,50,75. - Pick a goal in the range:
101-999. - Using each number once and operators +-*/, find a formula that results in the goal.
- Only integer results and sub-results are valid.
(3/2) * 6 is invalid because 3/2 is not an integer result.
For example: Suppose we have the numbers: 3,4,6,7 with a goal of 156. A valid result would be: 4*(3*(6+7)) = 156. Each number is only used once, and the result correctly equals our goal.
This game intrigued me a bit because it's a great opportunity to use Python's itertools, which I don't get to use a lot. Here is the Python program I came up with to find all solutions for a given game. Let me know what you think.
"""
The goal is to arrive at a chosen number (from 101 to 999) using the four basic
arithmetic operations (+, -, * and /) applied to six numbers chosen randomly
from the following alternatives: 1 to 10; 25; 50; 75; 100 (each number is drawn
from the entire set, so the same number may appear more than once). You
may use each of the six numbers originally selected once, and the result of each
operation performed with them once - for example, if a contestant multiplies 4
by 25 to obtain 100, he or she may no longer use the 4 or 25, but may use the
100 in further calculations. It's not mandatory to use all the numbers. All
numbers used must be positive integers.
USAGE: total_is_right.py [-h] NUM [NUM ...] GOAL
EXAMPLE:
>> python total_is_right.py 35 22 4 7 16 100
## <List of solutions>
## Found 22 solutions.
Reference: http://en.wikipedia.org/wiki/Des_chiffres_et_des_lettres
Author: M.Shepanski (2012)
"""
import time
from itertools import permutations, product
from argparse import ArgumentParser
SWAPPABLE = ('+', '*')
OPERATIONS = {
'+': lambda x,y: x + y,
'-': lambda x,y: x - y,
'*': lambda x,y: x * y if 1 not in (x,y) else None,
'/': lambda x,y: x / y if y not in (0,1) and not x % y else None,
}
def total_is_right(nums, goal):
results = set()
for nums in permutations(nums):
for ops in product(OPERATIONS.keys(), repeat=len(nums)-1):
for result in _iter_results(nums[1:], ops, nums[0], nums[0], goal):
if result not in results:
results.add(result)
yield result
def _iter_results(nums, ops, formula, total, goal):
if total == goal: yield formula
if len(ops) > 0 and total is not None:
newformula = _gen_formula(formula, ops[0], nums[0])
newtotal = OPERATIONS[ops[0]](total, nums[0])
for result in _iter_results(nums[1:], ops[1:], newformula, newtotal, goal):
yield result
if ops[0] not in SWAPPABLE and not isinstance(formula, int):
newformula = _gen_formula(nums[0], ops[0], formula)
newtotal = OPERATIONS[ops[0]](nums[0], total)
for result in _iter_results(nums[1:], ops[1:], newformula, newtotal, goal):
yield result
def _gen_formula(x, op, y):
if op in SWAPPABLE: x, y = sorted((x, y))
if isinstance(x, basestring): x = "(%s)" % x
if isinstance(y, basestring): y = "(%s)" % y
return "%s%s%s" % (x, op, y)
if __name__ == "__main__":
parser = ArgumentParser(description="Find solutions to the 'Total Is Right' game.")
parser.add_argument("nums", metavar="NUM", type=int, nargs='+', help="Numbers used in formula.")
parser.add_argument("goal", metavar="GOAL", type=int, help="Goal to achieve.")
args = parser.parse_args()
numresults = 0
starttime = time.time()
for result in total_is_right(args.nums, args.goal):
numresults += 1
print "%s = %s" % (result, args.goal)
runtime = round(time.time() - starttime, 1)
print "Found %s solutions in %s seconds." % (numresults, runtime)
