#!/usr/bin/env python3 """Project Euler Problem 1003 - Lonely Singles.""" from __future__ import annotations import argparse import os import sys from dataclasses import dataclass TARGET_K = 80 NEG_INF = -10**9 @dataclass(frozen=True) class Power: constant: int coeff: int @dataclass(frozen=True) class LeftTask: pos: int last: int constant: int coeff: int def build_powers(k: int) -> list[Power]: powers = [Power(0, 0) for _ in range(max(2, k))] powers[0] = Power(1, 0) powers[1] = Power(0, 1) for i in range(2, k): prev = powers[i - 1] powers[i] = Power(-2 * prev.coeff, prev.constant - prev.coeff) return powers[:k] def evaluate_positions(positions: list[int], powers: list[Power]) -> tuple[int, int]: constant = 0 coeff = 0 for pos in positions: constant += powers[pos].constant coeff += powers[pos].coeff return constant, coeff def singleton_positions(n: int, limit: int) -> list[int]: stones = [0] * (limit + 4) positions: list[int] = [] stones[0] = n for i in range(limit): if stones[i] & 1: positions.append(i) moved = stones[i] // 2 stones[i + 1] += moved stones[i + 3] += moved return positions def left_category(last: int, mid: int) -> int: if last < 0 or last <= mid - 3: return 0 if last == mid - 2: return 1 return 2 def right_category(first: int, mid: int) -> int: if first < 0 or first >= mid + 2: return 0 if first == mid + 1: return 1 return 2 def compatible_boundary(left_cat: int, right_cat: int) -> bool: if left_cat == 0: return True if left_cat == 1: return right_cat != 2 return right_cat == 0 def add_right_entry(table: dict[int, int], coeff: int, constant: int) -> None: if coeff in table: raise RuntimeError("unexpected duplicate right-side coefficient") table[coeff] = constant def enumerate_right( pos: int, end: int, mid: int, last: int, first: int, constant: int, coeff: int, powers: list[Power], buckets: list[dict[int, int]], ) -> None: if pos == end: add_right_entry(buckets[right_category(first, mid)], coeff, constant) return enumerate_right(pos + 1, end, mid, last, first, constant, coeff, powers, buckets) if last < 0 or pos - last >= 3: power = powers[pos] next_first = pos if first < 0 else first enumerate_right( pos + 1, end, mid, pos, next_first, constant + power.constant, coeff + power.coeff, powers, buckets, ) def build_left_tasks( pos: int, stop: int, last: int, constant: int, coeff: int, powers: list[Power], tasks: list[LeftTask], ) -> None: if pos == stop: tasks.append(LeftTask(pos, last, constant, coeff)) return build_left_tasks(pos + 1, stop, last, constant, coeff, powers, tasks) if last < 0 or pos - last >= 3: power = powers[pos] build_left_tasks( pos + 1, stop, pos, constant + power.constant, coeff + power.coeff, powers, tasks, ) def query_table(table: dict[int, int], target_coeff: int, left_constant: int) -> int: right_constant = table.get(target_coeff) if right_constant is None: return 0 value = left_constant + right_constant return value if value > 0 else 0 def add_matches( left_cat: int, left_coeff: int, left_constant: int, tables: list[dict[int, int]], ) -> int: total = 0 target_coeff = -left_coeff for right_cat, table in enumerate(tables): if compatible_boundary(left_cat, right_cat): total += query_table(table, target_coeff, left_constant) return total def combine_left_dfs( pos: int, mid: int, last: int, constant: int, coeff: int, powers: list[Power], tables: list[dict[int, int]], ) -> int: if pos == mid: return add_matches(left_category(last, mid), coeff, constant, tables) total = combine_left_dfs(pos + 1, mid, last, constant, coeff, powers, tables) if last < 0 or pos - last >= 3: power = powers[pos] total += combine_left_dfs( pos + 1, mid, pos, constant + power.constant, coeff + power.coeff, powers, tables, ) return total def solve_s(k: int) -> int: if k == 0: return 0 mid = k // 2 powers = build_powers(k) right_buckets: list[dict[int, int]] = [dict(), dict(), dict()] enumerate_right(mid, k, mid, NEG_INF, -1, 0, 0, powers, right_buckets) task_stop = min(mid, 24) tasks: list[LeftTask] = [] build_left_tasks(0, task_stop, NEG_INF, 0, 0, powers, tasks) total = 0 for task in tasks: total += combine_left_dfs( task.pos, mid, task.last, task.constant, task.coeff, powers, right_buckets, ) return total def require_checkpoint(ok: bool, message: str) -> None: if not ok: raise SystemExit(f"Checkpoint failed: {message}") def run_checkpoints() -> None: powers = build_powers(TARGET_K) p68 = [2, 5, 8, 13] p90 = [1, 13] require_checkpoint(evaluate_positions([0], powers) == (1, 0), "n=1 polynomial") require_checkpoint(evaluate_positions(p68, powers) == (68, 0), "n=68 polynomial") require_checkpoint(evaluate_positions(p90, powers) == (90, 0), "n=90 polynomial") require_checkpoint(singleton_positions(1, 40) == [0], "n=1 trace") require_checkpoint(singleton_positions(68, 50) == p68, "n=68 trace") require_checkpoint(singleton_positions(90, 50) == p90, "n=90 trace") require_checkpoint(solve_s(14) == 159, "S(14)") require_checkpoint(solve_s(30) == 33438, "S(30)") print("Validation checkpoints passed.", file=sys.stderr) def parse_args() -> argparse.Namespace: parser = argparse.ArgumentParser(description="Solve Project Euler Problem 1003.") parser.add_argument("k", nargs="?", type=int, default=TARGET_K) parser.add_argument("--skip-checkpoints", action="store_true") parser.add_argument("--single-thread", action="store_true", help=argparse.SUPPRESS) parser.add_argument("--threads", type=int, default=os.cpu_count() or 1, help=argparse.SUPPRESS) args = parser.parse_args() if args.k < 0 or args.k > TARGET_K: parser.error(f"k must satisfy 0 <= k <= {TARGET_K}.") return args def main() -> int: args = parse_args() if not args.skip_checkpoints: run_checkpoints() print(solve_s(args.k)) return 0 if __name__ == "__main__": raise SystemExit(main())