# solve24 - Module to solve the arithmetic game 24
#
# Copyright (c) 2006 Lenny Domnitser
#
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation files
# (the "Software"), to deal in the Software without restriction,
# including without limitation the rights to use, copy, modify, merge,
# publish, distribute, sublicense, and/or sell copies of the Software,
# and to permit persons to whom the Software is furnished to do so,
# subject to the following conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.
#
# Example usage at http://domnit.org/2006/07/solving-24
# See also http://www.24game.com/
from __future__ import division
_operations = (
(lambda a, b: a + b, '+'),
(lambda a, b: a - b, '-'),
(lambda a, b: a * b, '*'),
(lambda a, b: a / b, '/')
)
def _solver(*expressions):
if len(expressions) == 1:
yield expressions[0]
for i1 in xrange(len(expressions)):
ex1 = expressions[i1]
for i2 in xrange(len(expressions)):
if i1 == i2:
continue
ex2 = expressions[i2]
the_rest = []
for i3 in xrange(len(expressions)):
if i1 != i3 and i2 != i3:
the_rest.append(expressions[i3])
for operation in _operations:
try:
value = operation[0](ex1[0], ex2[0])
except ZeroDivisionError:
continue
representation = '(%s%s%s)' % (ex1[1], operation[1], ex2[1])
for solution in _solver((value, representation), *the_rest):
yield solution
def solve(a, b, c, d):
a, b, c, d = ((n, str(n)) for n in (a, b, c, d))
for (answer, solution) in _solver(a, b, c, d):
if str(float(answer)) == '24.0':
yield solution
def is_possible(a, b, c, d):
try:
solve(a, b, c, d).next()
return True
except StopIteration:
return False