24 Game

The24Game.py

class Token:
    def __init__(self, lh, rh):
        self.lh = lh
        self.rh = rh

    def __str__(self):
        return self.stringify()

    def __hash__(self):
        return str(self).__hash__()

class TNum(Token):
    def __init__(self, lh, rh = None):
        self.n = float(lh)

    def evaluate(self):
        return self.n

    def stringify(self):
        return str(int(self.n))

    def __eq__(self, other):
        if isinstance(other, TNum):
            return self.n == other.n
        return False

class TAdd(Token):
    def evaluate(self):
        return self.lh.evaluate() + self.rh.evaluate()

    def stringify(self):
        return "%s + %s" % (self.lh.stringify(), self.rh.stringify())

    def __eq__(self, other):
        if not isinstance(other, TAdd):
            return False
        if self.lh == other.lh:
            return self.rh == other.rh
        if self.lh == other.rh:
            return self.rh == other.lh
        return False

class TSub(Token):
    def evaluate(self):
        res = self.lh.evaluate() - self.rh.evaluate()
        if res < 0:
            raise "No Neg"
        return res

    def stringify(self):
        lh = self.lh.stringify()
        rh = self.rh.stringify()
        if type(self.rh) in [TAdd]:
            rh = "(%s)" % rh
        return "%s - %s"%(lh, rh)

    def __eq__(self, other):
        if isinstance(other, TSub):
            return self.lh == other.lh and self.rh == other.rh
        return False

class TMul(Token):
    def evaluate(self):
        return self.lh.evaluate() * self.rh.evaluate()

    def stringify(self):
        lh = self.lh.stringify()
        rh = self.rh.stringify()
        if type(self.lh) in [TAdd, TSub]:
            lh = "(%s)" % lh
        if type(self.rh) in [TAdd, TSub]:
            rh = "(%s)" % rh
        return "%s * %s"%(lh, rh)

    def __eq__(self, other):
        if not isinstance(other, TMul):
            return False
        if self.lh == other.lh:
            return self.rh == other.rh
        if self.lh == other.rh:
            return self.rh == other.lh
        return False

class TDiv(Token):
    def evaluate(self):
        return self.lh.evaluate() / self.rh.evaluate()

    def stringify(self):
        lh = self.lh.stringify()
        rh = self.rh.stringify()
        if type(self.lh) in [TAdd, TSub]:
            lh = "(%s)" % lh
        if type(self.rh) in [TAdd, TSub, TMul, TDiv]:
            rh = "(%s)" % rh
        return "%s / %s"%(lh, rh)

    def __eq__(self, other):
        if isinstance(other, TDiv):
            return self.lh == other.lh and self.rh == other.rh
        return False

import random

Cards = [TNum(random.randint(1,9)) for x in range(4)]
print("Get Four Cards: ", *[x for x in Cards])

results_may_dup = []

def dig_deep(tokens):
    index = list(range(len(tokens)))
    import itertools, copy
    for choosen_index in itertools.permutations(index, 2):
        left_index = [x for x in index if x not in choosen_index]
        for op in [TAdd, TSub, TMul, TDiv]:
            current_tokens = [op(tokens[choosen_index[0]], tokens[choosen_index[1]])]
            current_tokens += [tokens[x] for x in left_index]
            if len(current_tokens) == 1:
                try:
                    if current_tokens[0].evaluate() == 24:
                        results_may_dup.append(copy.deepcopy(current_tokens[0]))
                except: # div zero
                    pass
            else:
                dig_deep(current_tokens)

def transformer(token):
    def visit(token, callback):
        if isinstance(token, TNum):
            return token
        token = callback(token)
        token.lh = visit(token.lh, callback)
        token.rh = visit(token.rh, callback)
        token = callback(token)
        return token

    def shave(token): # Make btree shorter
        op = type(token)
        if op in [TMul, TAdd]:
            if isinstance(token.lh, TNum) and op is type(token.rh):
                num_token, op_token = token.rh.lh, token.rh.rh
                token.lh = op(num_token, token.lh)
                token.rh = op_token
                if isinstance(op_token, TNum):
                    token.lh, token.rh = token.rh, token.lh

        op = type(token)
        if op is TMul:
            if isinstance(token.lh, TNum):
                if isinstance(token.rh, TDiv):
                    if isinstance(token.rh.rh, TNum):
                        token = TMul(TDiv(token.lh, token.rh.rh), token.rh.lh)
                    elif  isinstance(token.rh.lh, TNum):
                        token = TDiv(TMul(token.lh, token.rh.lh), token.rh.rh)
        
        op = type(token)
        if op is TDiv:
            if isinstance(token.rh, TNum):
                if isinstance(token.lh, TMul) and isinstance(token.lh.lh, TNum):
                    token = TMul(TDiv(token.lh.lh, token.rh), token.lh.rh)
    
        op = type(token)
        if op is TSub:
            if isinstance(token.rh, TNum):
                if isinstance(token.lh, TSub) and isinstance(token.lh.rh, TNum):
                    token = TSub(token.lh.lh, TAdd(token.rh, token.lh.rh))
    
        return token

    def div2mul(token):
        if isinstance(token, TDiv):
            if isinstance(token.rh, TDiv):
                if token.rh.lh.evaluate() <= token.rh.rh.evaluate():
                    token = TMul(token.lh, TDiv(token.rh.rh, token.rh.lh))
            elif isinstance(token.rh, TNum) and token.rh.evaluate() == 1:
                token = TMul(token.lh, token.rh)
        return token

    def sub2add(token):
        if isinstance(token, TSub):
            if isinstance(token.rh, TSub):
                token = TAdd(token.lh, TSub(token.rh.rh, token.rh.lh))
        return token

    def leftify(token):
        if type(token) in [TMul, TAdd]:
            if isinstance(token.rh, TNum):
                if isinstance(token.lh, TNum):
                    if token.lh.evaluate() < token.rh.evaluate():
                        return token
                token.rh, token.lh = token.lh, token.rh
        return token

    def sortnum(token): # Commutative property of add and mul
        op = type(token)
        if op not in [TMul, TAdd]:
            return token
        if isinstance(token.lh, TNum) and isinstance(token.rh, op):
            ordered = sorted([token.lh, token.rh.lh, token.rh.rh], key = lambda t: t.evaluate())
            token = op(ordered[0], op(ordered[1], ordered[2]))
        elif isinstance(token.lh, op) and isinstance(token.rh, op):
            ordered = sorted([token.lh.lh, token.lh.rh, token.rh.lh, token.rh.rh], key = lambda t: t.evaluate())
            token = op(op(ordered[0], ordered[1]), op(ordered[2], ordered[3]))
        else:
            ordered = sorted([token.lh, token.rh], key = lambda t: t.evaluate())
            token = op(ordered[0], ordered[1])
        return token

    def sortop(token): # Add or Mul first than Sub or Div
        op = type(token)
        if op is TAdd:
            if isinstance(token.lh, TNum) and isinstance(token.rh, TSub):
                token = TSub(TAdd(token.lh, token.rh.lh), token.rh.rh)

        if op is TMul:
            if isinstance(token.lh, TNum) and isinstance(token.rh, TDiv):
                token = TDiv(TMul(token.lh, token.rh.lh), token.rh.rh)
        return token

    token = visit(token, div2mul)
    token = visit(token, sub2add)
    token = visit(token, leftify)
    token = visit(token, shave)
    token = visit(token, sortop)
    token = visit(token, sortnum)
    return token

dig_deep(Cards)
results_no_dup = []
for token in results_may_dup:
    token = transformer(token)
    if token not in results_no_dup:
        results_no_dup.append(token)
        print(token)