#!/usr/bin/env python

# Copyright (C) 2008 Jonas Wagner

# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.

# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.

# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

# To contact the autor please write to Jonas Wagner <j.b.w@gmx.ch>.

# Solver for the 1,3,4,6 problem and similar games

import math

class ExpressionTree:
    '''an expression: either '=' and a number or an operator with expressions
    as operands'''

    order = {'=': 1, '+': 2, '-': 3, '*': 4, '/': 5}
    precedence = {'=': 3, '+': 1, '-': 1, '*': 2, '/': 2}
    # operators and commutativity
    operators = {'+': True, '-': False, '*': True, '/': False}

    # numbers is a list of lists of the form [number, boolean] indicating an
    # available number and whether it's used already
    def __init__(self, numbers):
	self.expression = ()
	self.numbers = numbers

    def numbersUsed(self):
	if self.expression == (): return []
	if self.expression[0] == '=':
	    return [self.expression[1]]
	else:
	    return self.expression[1].numbersUsed() + self.expression[2].numbersUsed()
    
    def evaluate(self):
	try:
	    if self.expression[0] == '=':
		return self.numbers[self.expression[1]][0]
	    elif self.expression[0] == '+':
		return self.expression[1].evaluate() + self.expression[2].evaluate()
	    elif self.expression[0] == '-':
		return self.expression[1].evaluate() - self.expression[2].evaluate()
	    elif self.expression[0] == '*':
		return self.expression[1].evaluate() * self.expression[2].evaluate()
	    elif self.expression[0] == '/':
		return self.expression[1].evaluate() / self.expression[2].evaluate()
	except (ZeroDivisionError, TypeError):
	    return "Undefined (division by zero)"

    def multiplicity(self):
	if self.expression[0] == '=' : return 1
	
	if self.expression[0] in ('-', '/') :
	    return self.expression[1].multiplicity() * self.expression[2].multiplicity()
	else: # '*' or '+'
	    return 2 * self.expression[1].multiplicity() * self.expression[2].multiplicity()

    def lessThan(self, other):
	selfOrder = ExpressionTree.order[self.expression[0]]
	otherOrder = ExpressionTree.order[other.expression[0]]
	if selfOrder < otherOrder: return True
	elif selfOrder > otherOrder: return False
	else:
	    if self.expression[0] == '=': return self.expression[1] < other.expression[1] # two numbers
	    else: # two operators
		if self.expression[1].lessThan(other.expression[1]): return True
		elif other.expression[1].lessThan(self.expression[1]): return False
		else:
		    return self.expression[2].lessThan(other.expression[2])

    def __str__(self):
	if not self.expression: return ""

	if (self.expression[0] == '='): return str(self.numbers[self.expression[1]][0])
	
	res = []
	if self.precedence[self.expression[0]] > self.precedence[self.expression[1].expression[0]]:
	    res.append('(' + self.expression[1].__str__() + ')')
	else:
	    res.append(self.expression[1].__str__())
	res.append(self.expression[0])
	if self.precedence[self.expression[0]] >= self.precedence[self.expression[2].expression[0]]:
	    res.append('(' + self.expression[2].__str__() + ')')
	else:
	    res.append(self.expression[2].__str__())

	return ' '.join(res)



def generateExpression(numbers, minNumbers, maxNumbers, commutativeSibling):
    '''Generates an expression that uses numbers from the list numbers
    (at least minNumbers, at most maxNumbers) and that is greater than
    it's commutativeSibling (if it's not empty)'''

    if minNumbers == 1:
	for index, (n, used) in enumerate(numbers):
	    if not used:
		res = ExpressionTree(numbers)
		res.expression = ('=', index)
		if commutativeSibling and res.lessThan(commutativeSibling): continue

		numbers[index][1] = True
		yield res
		numbers[index][1] = False
    
    if maxNumbers > 1:
	for op in ExpressionTree.operators:
	    res = ExpressionTree(numbers)
	    res.expression = [op, None, None]
	    for res.expression[1] in generateExpression(numbers, 1, maxNumbers - 1, ()):
		# How many numbers are left for the second operand?
		used = res.expression[1].numbersUsed()
		minN = max(1, minNumbers - len(used))
		maxN = maxNumbers - len(used)
		if ExpressionTree.operators[op]:
		    cS = res.expression[1]
		else:
		    cS = ()
		for res.expression[2] in generateExpression(numbers, minN, maxN, cS):
		    if commutativeSibling and res.lessThan(commutativeSibling): continue
		    
		    yield res

def main():
    for i in range(9):
	for j in range(i+1, 9):
	    for k in range(j+1, 9):
		for l in range(k+1, 9):

		    greetingPrinted = False;

		    numbers = [[i+1.0, False], [j+1.0, False], [k+1.0, False], [l+1.0, False]]
		    results = {}
		    for exp in generateExpression(numbers, 4, 4, ()):
			value = exp.evaluate()
			try:
			    if abs(value - round(value)) < 0.001: value = round(value)
			except TypeError: pass

			results.setdefault(value, []).append((str(exp), exp.multiplicity()))

		    for value in sorted(results.keys()):
			try:
			    if 0 <= value <= 30 and abs(value - round(value)) < 0.001 and len(results[value]) == 1:
				if not greetingPrinted:
				    print
				    print "=========================="
				    print "i = %1d, j = %1d, k = %1d, l = %1d" % (i+1, j+1, k+1, l+1)
				    print "=========================="
				    greetingPrinted = True

				print "Only one expression for " + str(value) + ":", results[value][0][0]
				if results[value][0][1] > 1:
				    print "   (With multiplicity " + str(results[value][0][1]) + ")"

			except TypeError: pass

main()