Simpler Gleichungslöser für Mathepuzzle

Code-Stücke können hier veröffentlicht werden.
Antworten
BlackJack

Sonntag 22. Juni 2014, 19:29

Ich gehöre ja zu den Menschen die statt Rätsel oder Puzzle direkt zu lösen, lieber darüber nachdenken wie man den Rechner das lösen lassen kann und man so eine allgemeinere Lösung hat. Deshalb ist folgendes Programm entstanden zum Lösen von einfachen mathematischen Gleichungen mit der Einschränkung das alle Variablen die Werte 1 bis Anzahl der Variablen bekommen, alle Variablen unterschiedliche Werte, und alle Zwischenergebnisse müssen ganzzahlig sein.

Das Programm hat Pyparsing als externe Abhängigkeit.

Code: Alles auswählen

#!/usr/bin/env python
"""Tool to solve simple equations/math puzzles with a number of variables
and the four basic operations.

Rules for valid solutions:

* each variable is assigned a number between 1 and the number of variables,
* all assigned values are distinct,
* each subexpression evaluates to an integer, i.e. no fractionals allowed.

The equation may contain up to 26 variables named 'a' to 'z', literal integer
values, and the four operations ``*``, ``/``, ``+``, and ``-``.  The usual
operator precedence applies.  Parentheses may be used to overrule operator
precedence.

Example equation: ``a * b / (23 + c) = 42`` (Has no solution under the rules
stated above.)
"""
from __future__ import division, print_function
import sys
from argparse import ArgumentParser
from future_builtins import filter, zip
from itertools import permutations
from operator import add, mul, sub, truediv

import pyparsing as pp
pp.ParserElement.enablePackrat()


__author__ = "Marc 'BlackJack' Rintsch"
__version__ = '0.1.0'
__date__ = '2014-06-22'


class Value(object):
    def __init__(self, value):
        self.value = value

    def __str__(self):
        return str(self.value)

    def __call__(self, _environment=None):
        return self.value

    @staticmethod
    def get_operation_count():
        return 0

    @staticmethod
    def get_variable_names():
        return set()


class Variable(object):
    def __init__(self, name):
        self.name = name

    def __str__(self):
        return self.name

    def __call__(self, environment):
        return environment[self.name]

    @staticmethod
    def get_operation_count():
        return 0

    def get_variable_names(self):
        return set([self.name])


class BinaryOperation(object):
    
    SYMBOL_TO_FUNCTION = {'*': mul, '/': truediv, '+': add, '-': sub}
    
    def __init__(self, symbol, operand_a, operand_b):
        self.symbol = symbol
        self.function = self.SYMBOL_TO_FUNCTION[symbol]
        self.operand_a = operand_a
        self.operand_b = operand_b

    def __str__(self):
        return '({0.operand_a} {0.symbol} {0.operand_b})'.format(self)

    def __call__(self, environment):
        result = self.function(
            self.operand_a(environment), self.operand_b(environment)
        )
        if result % 1 != 0:
            raise ValueError('fractional result')
        return result

    def get_operation_count(self):
        return (
            1
            + self.operand_a.get_operation_count()
            + self.operand_b.get_operation_count()
        )

    def get_variable_names(self):
        return (
            self.operand_a.get_variable_names()
            | self.operand_b.get_variable_names()
        )


VALUE = pp.Word(pp.nums).setParseAction(lambda toks: Value(int(toks[0])))
VARIABLE = pp.Regex(r'[a-z]').setParseAction(lambda toks: Variable(toks[0]))
OPERAND = VALUE | VARIABLE
EXPRESSION = pp.operatorPrecedence(
    OPERAND, list((pp.Literal(symbol), 2, pp.opAssoc.LEFT) for symbol in '*/+-')
)
EQUATION = EXPRESSION + pp.Suppress('=') + VALUE


def _expression_to_ast(parse_result):
    try:
        operand_a, symbol, operand_b = parse_result
    except TypeError:
        return parse_result
    else:
        return BinaryOperation(
            symbol, _expression_to_ast(operand_a), _expression_to_ast(operand_b)
        )


class Equation(object):
    def __init__(self, expression, result):
        self.expression = expression
        self.result = result

    def __str__(self):
        return '{0.expression} = {0.result}'.format(self)

    def __call__(self, environment):
        try:
            result = self.expression(environment)
        except ValueError:
            return False
        else:
            return result == self.result

    def get_operation_count(self):
        return self.expression.get_operation_count()

    def get_variable_names(self):
        return self.expression.get_variable_names()

    def iter_all_solutions(self):
        variable_names = self.get_variable_names()
        return filter(
            self,
            (
                dict(zip(variable_names, values))
                for values in permutations(xrange(1, len(variable_names) + 1))
            )
        )

    @classmethod
    def parse(cls, source):
        expression, expected_result = EQUATION.parseString(source)
        return cls(_expression_to_ast(expression), expected_result())


def main():
    argument_parser = ArgumentParser(
        description='See at the beginning of {0} for more information.'.format(
            sys.argv[0]
        ),
        version=__version__
    )
    argument_parser.add_argument('equation', help='The equation to solve.')
    options = argument_parser.parse_args()

    equation = Equation.parse(options.equation)
    print('Equation:', equation)
    variable_names = sorted(equation.get_variable_names())
    print(
        equation.get_operation_count(),
        'operations and',
        len(variable_names),
        'variables:',
        ', '.join(variable_names)
    )
    print('Solving...')
    solution_count = 0
    for solution_count, solution in enumerate(equation.iter_all_solutions(), 1):
        print(
            'Solution {0:2d}: '.format(solution_count),
            ', '.join(
                '{0}={1}'.format(name, solution[name])
                for name in variable_names
            )
        )
    print(solution_count, 'solutions found.')


if __name__ == '__main__':
    main()
Antworten