# 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