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

## No comments:

Post a Comment