## Krypto and 24

Daily WTF inspired me to implement a Krypto and 24 solver:

```import functools
import itertools
import operator

class Node:
def evaluate(self): raise NotImplemted()
def print(self): raise NotImplemted()

def __sub__(self, other): return Sub(self, other)
def __mul__(self, other): return Mul(self, other)
def __truediv__(self, other): return Div(self, other)

def __str__(self):
return "<Node: {}>".format(self.print())

def __repr__(self):
return str(self)

class Binary(Node):
def __init__(self, left, right):
self.left = left
self.right = right

def evaluate(self):
try:
return self.op(
self.left.evaluate(),
self.right.evaluate(),
)
except ZeroDivisionError:
return float("NaN")

def print(self):
return "({} {} {})".format(
self.left.print(),
self.symbol(),
self.right.print()
)

def op(self, left, rigth): raise NotImplemted()
def symbol(self): raise NotImplemted()

class Unary(Node):
def __init__(self, op, val):
self.op = op
self.val = val

def evaluate(self):
return self.op(self.val)

def print(self):
return str(self.evaluate())

def BinOp(op, symbol, commutative = True):
class inner(Binary):
def op(self, left, right):
return op(left, right)

def symbol(self):
return symbol

@classmethod
def iscommutative(cls):
return commutative

return inner

Sub = BinOp(operator.sub, "-", commutative = False)
Mul = BinOp(operator.mul, "*")
Div = BinOp(operator.truediv, "/", commutative = False)
Lit = functools.partial(Unary, lambda x: x)

OPS = [Add, Sub, Mul, Div]

def generate_expressions(nodes):
if len(nodes) == 1:
yield first(nodes)

for x, y, op in itertools.product(nodes, nodes, OPS):
isnew = not op.iscommutative() or id(x) > id(y)
if x is not y and isnew:
yield generate_expressions((nodes - set([x, y])) | set([op(x, y)]))

def flatten(xs):
for x in xs:
try:
for y in flatten(x):
yield y
except TypeError:
yield x

def first(xs):
for x in xs:
return x

def krypto(nums, solution):
def issolution(expr):
return expr.evaluate() == solution

nodes = set(map(Lit, nums))
expr = first(filter(issolution, flatten(generate_expressions(nodes))))
print(expr.print(), "=", expr.evaluate())

if __name__ == "__main__":
import sys
args = list(map(int, sys.argv[1:]))
krypto(args[:-1], args[-1])
```

My favourite part is that the core of the algorithm is 6 lines:

```def generate_expressions(nodes):
if len(nodes) == 1:
yield first(nodes)

for x, y, op in itertools.product(nodes, nodes, OPS):
isnew = not op.iscommutative() or id(x) > id(y)
if x is not y and isnew:
yield generate_expressions((nodes - set([x, y])) | set([op(x, y)]))
```

The parametric classes are also a reminder of just how badass python is:

```def BinOp(op, symbol, commutative = True):
class inner(Binary):
def op(self, left, right):
return op(left, right)

def symbol(self):
return symbol

@classmethod
def iscommutative(cls):
return commutative

return inner
```

### Edit

2010-05-16: Apparently Python comes with an implementation of cross product.