Instantly share code, notes, and snippets.

# Pagliacii/24-game.py

Last active October 24, 2021 03:43
Show Gist options
• Save Pagliacii/34006654b8af7135a6470547b2309d7f to your computer and use it in GitHub Desktop.
Solutions to the 24 Game
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/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))
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/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()
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #!/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.")

### Pagliacii commented Oct 24, 2021

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
``````