Spaces:
Running
Running
File size: 5,130 Bytes
50f2856 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | """Find one way to make the target from all the cards.
Every expression tree splits the cards at its root into two groups, and the smaller group has at
most half the cards. So the search enumerates every value a small group (up to four cards) can
make, and asks the rest of the cards for the one number that would complete the target:
``target = v + rest`` needs ``rest = target - v``, and so on for the six ways to put v on either
side of the four operators. Recursing until four cards remain, where the answer is a lookup, makes
the search complete for up to nine cards, and in practice it finds an answer in milliseconds
because big targets have many.
A first pass keeps every intermediate value a whole number (the way people play, as in the
video); a second pass allows fractions. Both stop at a deadline.
"""
from __future__ import annotations
import time
from fractions import Fraction
from functools import lru_cache
from itertools import combinations
from .expr import Tree, evaluate, leaves
LOOKUP_SIZE = 4
class Timeout(Exception):
pass
@lru_cache(maxsize=200_000)
def _reach(values: tuple[int, ...], integers: bool) -> dict[Fraction, Tree]:
"""Every value a sorted group of cards can make, with one tree for each."""
if len(values) == 1:
return {Fraction(values[0]): values[0]}
out: dict[Fraction, Tree] = {}
n = len(values)
seen: set[tuple[int, ...]] = set()
for k in range(1, n // 2 + 1):
for idx in combinations(range(n), k):
left = tuple(values[i] for i in idx)
if left in seen:
continue
seen.add(left)
right = tuple(v for i, v in enumerate(values) if i not in idx)
if k * 2 == n and right in seen and right != left:
continue
lr, rr = _reach(left, integers), _reach(right, integers)
for a, ta in lr.items():
for b, tb in rr.items():
_add(out, a + b, ("+", ta, tb), integers)
_add(out, a * b, ("*", ta, tb), integers)
_add(out, a - b, ("-", ta, tb), integers)
_add(out, b - a, ("-", tb, ta), integers)
if b:
_add(out, a / b, ("/", ta, tb), integers)
if a:
_add(out, b / a, ("/", tb, ta), integers)
return out
def _add(out: dict, value: Fraction, tree: Tree, integers: bool) -> None:
if integers and (value.denominator != 1 or value < 0):
return
out.setdefault(value, tree)
class _Search:
def __init__(self, integers: bool, deadline: float):
self.integers = integers
self.deadline = deadline
self.failed: set[tuple[Fraction, tuple[int, ...]]] = set()
self.nodes = 0
def solve(self, target: Fraction, values: tuple[int, ...]) -> Tree | None:
if len(values) <= LOOKUP_SIZE:
return _reach(values, self.integers).get(target)
key = (target, values)
if key in self.failed:
return None
self.nodes += 1
if self.nodes % 256 == 0 and time.monotonic() > self.deadline:
raise Timeout
n = len(values)
seen: set[tuple[int, ...]] = set()
for k in range(1, n // 2 + 1):
for idx in combinations(range(n), k):
group = tuple(values[i] for i in idx)
if group in seen:
continue
seen.add(group)
rest = tuple(v for i, v in enumerate(values) if i not in idx)
for v, tv in _reach(group, self.integers).items():
for need, build in self._needs(target, v, tv):
if self.integers and (need.denominator != 1 or need < 0):
continue
found = self.solve(need, rest)
if found is not None:
return build(found)
self.failed.add(key)
return None
@staticmethod
def _needs(target: Fraction, v: Fraction, tv: Tree):
yield target - v, lambda r: ("+", tv, r)
yield v - target, lambda r: ("-", tv, r)
yield target + v, lambda r: ("-", r, tv)
if v:
yield target / v, lambda r: ("*", tv, r)
yield target * v, lambda r: ("/", r, tv)
if target and v: # rest = v / target; with v = 0 the rest would have to be 0, a division by zero
yield v / target, lambda r: ("/", tv, r)
def solve(values: list[int], target: int, time_limit: float = 2.0) -> Tree | None:
"""Return a tree using every value once that equals target, or None if none was found in time."""
ordered = tuple(sorted(values))
goal = Fraction(target)
deadline = time.monotonic() + time_limit
for integers in (True, False):
try:
tree = _Search(integers, deadline).solve(goal, ordered)
except Timeout:
return None
if tree is not None:
assert evaluate(tree) == goal and sorted(leaves(tree)) == list(ordered)
return tree
return None
|