Solve Number plate game by generating and interpreting Forth programs

number_plate_solver.py

#!/usr/bin/env python

"""
Find the operations needed to sum up to TARGET by using all 4 numbers in NUMBERS.
"""

from itertools import permutations, product

NUMBERS = ["3","4","7","8"]
TARGET = 10.0

OPERATORS = {
    "+" : lambda a,b: a+b,
    "-" : lambda a,b: b-a,
    "*" : lambda a,b: b*a,
    "/" : lambda a,b: b*1.0/a
}

class ForthProgram(object):
    """
    A Forth program is a sequence of space-separated words:
        word1 word2 word3 [...] wordn

    This interpreter supports only two kinds of words: numbers and arithmetic operators.

    * When a word is a number, we simply push it on top of the stack.
    * When a word is an operator, we pop two numbers from the stack, perform the
      operation and push the result on top of the stack.

    Example 1: Program for 3 * 4 + 2

    3 4 * 2 +

    Example 2: Program for 3 * (4 + 2)

    3 4 2 + *

    Advantages of this approach:
        - easy to generate programs since they are just strings
        - easy to interpret (no need for parentheses)

    For more information about Forth, see:

    http://en.wikipedia.org/wiki/Forth_(programming_language)
    """

    def __init__(self, program):
        self.program = program

    def interpret(self):
        """
        Interpret the program and return the value on top of the stack.
        """
        return self._interpret()[0]

    def __str__(self):
        """
        Return an easy (for humans) to read version of the computations
        performed by the program.
        """
        return self._interpret()[1]

    def _interpret(self):
        stack = []
        prettyprint = ""

        for word in self.program.split():
            if word in ("+", "-", "*", "/"):
                operand1 = stack.pop()
                operand2 = stack.pop()

                try:
                    res = OPERATORS[word](operand1, operand2)
                except ZeroDivisionError:
                    res = float("inf")

                stack.append(res)
                prettyprint += "%f = %f %s %f\n" % (res, operand2, word, operand1)
            else:
                stack.append(float(word))

        return stack.pop(), prettyprint

def operator_permutations(n):
    """
    Generate the permutations of n operators with replacement.

    Example for n = 3

    [('+', '+', '+'), ('+', '+', '*'), [...], ('/', '/', '-'), ('/', '/', '/')]
    """
    return product(*([OPERATORS.keys()]*n))

def generate_programs():
    """
    Generate all possible programs. May contain duplicates!
    """
    for a,b,c,d in permutations(NUMBERS):
        for op1, op2, op3 in operator_permutations(3):
            yield " ".join((a, b, c, d, op1, op2, op3))
            yield " ".join((a, b, c, op1, d, op2, op3))
            yield " ".join((a, b, op1, c, d, op2, op3))
            yield " ".join((a, b, op1, c, op2, d, op3))
            yield " ".join((a, b, c, op1, op2, d, op3))

for program_str in generate_programs():
    program = ForthProgram(program_str)
    if program.interpret() == TARGET:
        print "Solution: %s\n %s" % (program_str, program)