Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Solve Number plate game by generating and interpreting Forth programs
#!/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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.