One of my favourite programming exercises is solving the “countdown” numbers game. Basically, you are given a set of input numbers and have to solve the target by adding, multiplying, subtracting or dividing them (using each input number only once).
As before, this isn’t an ideal solution, as I’m still getting to grips with Python. It uses recursion to find the first solution. I don’t keep track of the closest answer yet.
import unittest
class SolverUnitTests(unittest.TestCase):
testCases = (
(0, [], True),
(1, [], False),
(1, [1], True),
(2, [1], False),
(2, [1,1], True),
(2, [1,7], False),
(3, [1,1,1], True),
(1, [3,2], True), # subtract
(1, [2,3], True),
(6, [2,3], True), # multiply
(7, [2,3], False),
(4, [8,2], True), # divide
(4, [2,8], True), # divide
(4, [9,2], False),
(14, [1,7,1], True), # add and multiply
(18, [1,7,3], True), # subtract and multiply
(100, [11, 1, 11, 1], True),
(2010, [25, 4, 2, 10, 5, 2], True),
(2011, [25, 4, 2, 10, 5, 2], True),
(2012, [25, 4, 2, 10, 5, 2], True),
(2013, [25, 4, 2, 10, 5, 2], True),
(2014, [25, 4, 2, 10, 5, 2], True),
(16, [2,2,2], False)
)
def testCanSolve(self):
for (target, numbers, solveable) in self.testCases:
print 'solving', target, 'with', numbers
solver = Solver(target)
self.assertEqual(solveable, solver.Solve(numbers))
def add(first,second):
answer = first + second
return (answer, '%d+%d=%d' % (first,second,answer))
def subtract(first,second):
answer = first - second
if answer < 0:
answer = 0
return (answer, '%d-%d=%d' % (first,second,answer))
def multiply(first,second):
answer = first * second
if answer < 0:
answer = 0
return (answer, '%d*%d=%d' % (first,second,answer))
def divide(first,second):
if (second == 0) or ( first % second != 0):
answer = 0
else:
answer = first / second
return (answer, '%d/%d=%d' % (first,second,answer))
def pairs(list):
for i in range(len(list)):
for j in range(i+1,len(list)):
yield (list[i],list[j])
class Solver:
def __init__(self, target):
self.target = target
self.operations = (add, subtract, multiply, divide)
def Solve(self, numbers):
if (self.target in numbers) or (self.target == 0):
return True
return self.SolveList(numbers, '')
def SolveList(self, numbers, solutionSoFar):
numbers.sort(reverse=True)
for (first, second) in pairs(numbers):
for func in self.operations:
(newNumber,solution) = func(first,second)
if newNumber == self.target:
print self.target, ':', solutionSoFar + ', ' + solution
return True
elif newNumber:
newList = list(numbers)
newList.remove(first)
newList.remove(second)
newList.append(newNumber)
#print 'retry with', newList
if self.SolveList(newList, solutionSoFar + ', ' + solution):
return True
return False
