Solutions to the 24 Game

24-game.py

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import itertools

from typing import Optional

from expression import Expr
from fraction import Frac

TARGET: int = 24
RANGE: list[int] = list(range(1, 14))


def shift(root: Expr) -> None:
    """Shifts the unblanced tree to blanced one.

    Args:
        root: A unbalanced Expr tree

    Examples:
    root --> o               o
            / \           /     \
           o   D         o       o
          / \      =>   / \     / \
         o   C         A   B   C   D
        / \
       A   B
    """
    left: Expr = root.left
    right: Expr = root.right
    if hasattr(left, "right"):
        root.right = Expr(left.right, right)
    if hasattr(left, "left"):
        root.left = left.left

def interchange(root: Expr):
    """
    root --> o              o
          /     \          / \
         o       o   =>   o   D
        / \     / \      / \
       A   B   C   D    A   o
                           / \
                          B   C
    """
    left: Expr = root.left
    right: Expr = root.right
    if hasattr(left, "right") and hasattr(right, "left"):
        root.left = Expr(left.left, Expr(left.right, right.left))
        root.right = root.right.right


def try_solve(exprs: list[Expr]) -> Optional[Expr]:
    """Try to find out a valid solution

    Args:
        exprs: numbers to be calculated

    Returns:
        A valid solution that represents by a Expr instance.
        If it doesn't find out a solution, the return value is None.
    """
    left: Optional[Expr] = None
    right: Optional[Expr] = None
    for expr in exprs:
        if not left:
            left = expr
        elif not right:
            right = expr
        else:
            left = Expr(left, right)
            right = expr

    # 1, 1, 1, 8 => (1 + 1 + 1) * 8
    root: Expr = Expr(left, right)
    for result in root.try_calculate():
        if result.eval() == TARGET:
            return result

    # 1, 1, 1, 11 => (1 + 1) * (1 + 11)
    shift(root)
    for result in root.try_calculate():
        if result.eval() == TARGET:
            return result

    # 1, 5, 5, 5 => (5 - 1 / 5) * 5
    interchange(root)
    for result in root.try_calculate():
        if result.eval() == TARGET:
            return result
    return None


def solve(question: list[int]) -> None:
    """Uses the numbers in question to calculate the TARGET"""
    for one in itertools.permutations(question):
        solution: Optional[Expr] = try_solve([Expr(value=Frac(i)) for i in one])
        if solution:
            print(f"{solution}")
            break
    else:
        print("nope")


if __name__ == "__main__":
    solved: list[str] = []
    for numbers in itertools.product(RANGE, RANGE, RANGE, RANGE):
        question: str = ", ".join(str(n) for n in sorted(numbers))
        if question in solved:
            continue
        solved.append(question)
        print(f"{question}: ", end="")
        solve(list(numbers))

expression.py

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import itertools
from typing import Generator, Optional

from fraction import Frac
from optype import OpType


class Expr:
    left: "Expr"
    right: "Expr"
    op: "OpType"
    value: "Frac"

    def __init__(
        self,
        left: Optional["Expr"] = None,
        right: Optional["Expr"] = None,
        op: Optional["OpType"] = None,
        value: Optional["Frac"] = None,
    ) -> None:
        if value:
            self.value = value
            self.op = OpType.NUM
        if left:
            self.left = left
        if right:
            self.right = right
        if op:
            self.op = op

    def __str__(self) -> str:
        if self.op == OpType.NUM:
            return str(self.value.eval())

        left: str = f"{self.left}"
        right: str = f"{self.right}"
        if self.op in (OpType.MUL, OpType.DIV):
            if self.left.op in (OpType.ADD, OpType.SUB):
                left = f"({self.left})"
            if self.right.op in (OpType.ADD, OpType.SUB):
                right = f"({self.right})"
        return f"{left} {self.op} {right}"

    __repr__ = __str__

    def eval(self) -> int:
        if self.op == OpType.NUM:
            return self.value.eval()
        left: int = self.left.eval()
        right: int = self.right.eval()
        if self.op == OpType.DIV and right == 0:
            return 0
        return self.op.calculate(left, right)

    def try_calculate(self) -> Generator["Expr", None, None]:
        if getattr(self, "op", None) == OpType.NUM:
            yield self
        else:
            left_values: list[Expr] = [v for v in self.left.try_calculate()]
            right_values: list[Expr] = [v for v in self.right.try_calculate()]
            for op in (
                OpType.ADD,
                OpType.SUB,
                OpType.MUL,
                OpType.DIV,
            ):
                for left, right in itertools.product(left_values, right_values):
                    yield Expr(left, right, op)

fraction.py

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import math

from typing import Optional


class Frac:
    num: int
    denom: int

    def __init__(self, num: Optional[int] = None, denom: int = 1) -> None:
        if num:
            self.num = num
        self.denom = denom

    def eval(self) -> int:
        return self.num // self.denom

    def simplify(self) -> "Frac":
        g: int = math.gcd(self.num, self.denom)
        return Frac(self.num // g, self.denom // g)

    def __add__(self, rhs: "Frac") -> "Frac":
        frac: Frac = Frac()
        frac.num = self.num * frac.denom + rhs.num * frac.denom
        return frac.simplify()

    def __sub__(self, rhs: "Frac") -> "Frac":
        frac: Frac = Frac()
        frac.denom = self.denom * rhs.denom
        frac.num = self.num * frac.denom - rhs.num * frac.denom
        return frac.simplify()

    def __mul__(self, rhs: "Frac") -> "Frac":
        frac: Frac = Frac()
        frac.denom = self.denom * rhs.denom
        frac.num = self.num * rhs.num
        return frac.simplify()

    def __truediv__(self, rhs: "Frac") -> "Frac":
        if rhs.eval() == 0:
            raise ZeroDivisionError("division by zero")
        frac: Frac = Frac()
        frac.denom = self.denom * rhs.num
        frac.num = self.num * rhs.denom
        return frac.simplify()

optype.py

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import operator

from enum import Enum
from typing import Callable


class OpType(Enum):
    NUM = 0
    ADD = 1
    SUB = 2
    MUL = 3
    DIV = 4

    def __str__(self) -> str:
        if self == OpType.ADD:
            return "+"
        if self == OpType.SUB:
            return "-"
        if self == OpType.MUL:
            return "*"
        if self == OpType.DIV:
            return "/"
        raise TypeError("OpType.NUM is not support to convert to string.")

    @property
    def calculate(self) -> Callable[[int, int], int]:
        if self == OpType.ADD:
            return operator.add
        if self == OpType.SUB:
            return operator.sub
        if self == OpType.MUL:
            return operator.mul
        if self == OpType.DIV:
            return operator.truediv
        raise TypeError("OpType.NUM is not support to be calculated.")

Output:

1, 1, 1, 1: nope
1, 1, 1, 2: nope
1, 1, 1, 3: nope
1, 1, 1, 4: nope
1, 1, 1, 5: nope
1, 1, 1, 6: nope
1, 1, 1, 7: nope
1, 1, 1, 8: (1 + 1 + 1) * 8
1, 1, 1, 9: nope
1, 1, 1, 10: nope
1, 1, 1, 11: (1 + 1) * (1 + 11)
1, 1, 1, 12: (1 * 1 + 1) * 12
1, 1, 1, 13: (1 + 1) * (13 - 1)
1, 1, 2, 2: nope
1, 1, 2, 3: nope
1, 1, 2, 4: nope
1, 1, 2, 5: nope
1, 1, 2, 6: (1 + 1 + 2) * 6
1, 1, 2, 7: (1 + 2) * (1 + 7)
1, 1, 2, 8: (1 * 1 + 2) * 8
1, 1, 2, 9: (1 + 2) * (9 - 1)
1, 1, 2, 10: (1 + 1) * (2 + 10)
1, 1, 2, 11: 1 + 1 + 2 * 11
1, 1, 2, 12: (1 - 1 + 2) * 12
1, 1, 2, 13: (1 + 1) * 13 - 2
1, 1, 3, 3: nope
1, 1, 3, 4: (1 + 1) * 3 * 4
1, 1, 3, 5: (1 + 3) * (1 + 5)
1, 1, 3, 6: (1 * 1 + 3) * 6
1, 1, 3, 7: (1 * 1 + 7) * 3
1, 1, 3, 8: (1 - 1 + 3) * 8
1, 1, 3, 9: (1 + 1) * (3 + 9)
1, 1, 3, 10: (10 - 1 - 1) * 3
1, 1, 3, 11: (1 + 11) * (3 - 1)
1, 1, 3, 12: (1 * 3 - 1) * 12
1, 1, 3, 13: (1 - 3) * (1 - 13)
1, 1, 4, 4: (1 + 1 + 4) * 4
1, 1, 4, 5: (1 * 1 + 5) * 4
1, 1, 4, 6: (1 - 1 + 4) * 6
1, 1, 4, 7: 1 * 4 * (7 - 1)
1, 1, 4, 8: (1 + 1) * (4 + 8)
1, 1, 4, 9: (1 - 4) * (1 - 9)
1, 1, 4, 10: (1 + 1) * 10 + 4
1, 1, 4, 11: nope
1, 1, 4, 12: (4 - 1 - 1) * 12
1, 1, 4, 13: nope
1, 1, 5, 5: 1 * 5 * 5 - 1
1, 1, 5, 6: (1 * 5 - 1) * 6
1, 1, 5, 7: (1 + 1) * (5 + 7)
1, 1, 5, 8: (5 - 1 - 1) * 8
1, 1, 5, 9: nope
1, 1, 5, 10: nope
1, 1, 5, 11: nope
1, 1, 5, 12: nope
1, 1, 5, 13: nope
1, 1, 6, 6: (1 + 1) * (6 + 6)
1, 1, 6, 7: nope
1, 1, 6, 8: 6 * 8 / (1 + 1)
1, 1, 6, 9: (1 + 1) * 9 + 6