From ac1b99879c191770085c43dcdb13027b44eae84c Mon Sep 17 00:00:00 2001
From: Tomasz Kramkowski <tk@the-tk.com>
Date: Sat, 27 Nov 2021 13:39:28 +0000
Subject: all done

---
 22/solution.py | 134 +++++++++++++++++++++++++++++++++++++++++----------------
 25/solution.py |  19 ++++++++
 2 files changed, 117 insertions(+), 36 deletions(-)
 create mode 100644 25/solution.py

diff --git a/22/solution.py b/22/solution.py
index 6df8379..c0ff521 100644
--- a/22/solution.py
+++ b/22/solution.py
@@ -1,42 +1,104 @@
-from functools import cache
-from collections import namedtuple
-
-Opponent = namedtuple('Opponent', ['hp', 'damage'])
-
-def part1(opponent: Opponent) -> int:
-    @cache
-    def min_cost(php: int, pmana: int, ohp: int, sld_timer: int, psn_timer: int, rch_timer: int) -> int | float:
-        psld = 0
-        def effects():
-            nonlocal ohp, pmana, psld, psn_timer, rch_timer, sld_timer
-            if sld_timer > 0:
-                sld_timer -= 1
-                psld = 7
-            else:
-                psld = 0
-            if psn_timer > 0:
-                psn_timer -= 1
-                ohp -= 3
-            if rch_timer > 0:
-                rch_timer -= 1
-                pmana += 101
-
-        def opponent_turn(cost: int) -> int | float:
-            effects()
-            nonlocal php
-            if ohp <= 0:
-                return cost
-            php -= min(1, opponent.attack - psld)
-            if php <= 0:
+from dataclasses import dataclass, astuple, replace
+
+@dataclass
+class State:
+    boss_hp: int
+    boss_damage: int
+    player_hp: int = 50
+    player_mana: int = 500
+    player_shield: int = 0
+    shield_timer: int = 0
+    poison_timer: int = 0
+    recharge_timer: int = 0
+
+@dataclass
+class Effect:
+    timer: str
+    start: int
+
+@dataclass
+class Instant:
+    effects: dict[str, int]
+
+@dataclass
+class Spell:
+    cost: int
+    action: Effect | Instant
+
+def solve(boss_hp: int, boss_damage: int, hard_mode: bool) -> int | float:
+    spells: list[Spell] = [
+        Spell(53, Instant({'boss_hp': -4})),
+        Spell(73, Instant({'boss_hp': -2, 'player_hp': 2})),
+        Spell(113, Effect('shield_timer', 6)),
+        Spell(173, Effect('poison_timer', 6)),
+        Spell(229, Effect('recharge_timer', 6)),
+    ]
+
+    seen: set[tuple] = set()
+
+    def simulate_effects(state: State):
+        if state.shield_timer > 0:
+            state.shield_timer -= 1
+            state.player_shield = 7
+        else:
+            state.player_shield = 0
+        if state.poison_timer > 0:
+            state.poison_timer -= 1
+            state.boss_hp -= 3
+        if state.recharge_timer > 0:
+            state.recharge_timer -= 1
+            state.player_mana += 101
+
+    def player_turn(state: State) -> int | float:
+        t: tuple = astuple(state)
+        if t in seen:
+            return float('inf')
+        seen.add(t)
+        if hard_mode:
+            state.player_hp -= 1
+            if state.player_hp <= 0:
                 return float('inf')
-            return cost + min_cost(php, pmana, ohp, sld_timer, psn_timer, rch_timer)
+        simulate_effects(state)
+        if state.boss_hp <= 0:
+            return 0
+        min_mana: int | float = float('inf')
+        cost: int
+        action: Effect | Instant
+        for spell in spells:
+            if state.player_mana < spell.cost:
+                continue
+            nstate = replace(state)
+            nstate.player_mana -= spell.cost
+            if isinstance(spell.action, Effect):
+                if getattr(nstate, spell.action.timer) != 0:
+                    continue
+                setattr(nstate, spell.action.timer, spell.action.start)
+            else:
+                for attr, delta in spell.action.effects.items():
+                    setattr(nstate, attr, getattr(nstate, attr) + delta)
+            min_mana = min(min_mana, spell.cost + boss_turn(nstate))
+        return min_mana
 
-        effects()
-        if ohp <= 0:
+    def boss_turn(state: State) -> int | float:
+        simulate_effects(state)
+        if state.boss_hp <= 0:
             return 0
+        state.player_hp -= max(1, state.boss_damage - state.player_shield)
+        if state.player_hp <= 0:
+            return float('inf')
+        return player_turn(state)
+
+    return player_turn(State(boss_hp=boss_hp, boss_damage=boss_damage))
+
+def part1(boss_hp: int, boss_damage: int) -> int | float:
+    return solve(boss_hp, boss_damage, False)
+
+def part2(boss_hp: int, boss_damage: int) -> int | float:
+    return solve(boss_hp, boss_damage, True)
 
 if __name__ == '__main__':
-    opponent = Opponent(51, 9)
+    boss_hp: int = 51
+    boss_damage: int = 9
 
-    print(part1(opponent))
-    #print(part2(opponent))
+    print(part1(boss_hp, boss_damage))
+    print(part2(boss_hp, boss_damage))
diff --git a/25/solution.py b/25/solution.py
new file mode 100644
index 0000000..6322ee4
--- /dev/null
+++ b/25/solution.py
@@ -0,0 +1,19 @@
+def part1(row, col):
+    row -= 1
+    col -= 1
+
+    n = row + col
+    n = n * (n + 1) // 2 + col
+
+    code = 20151125
+    for i in range(n):
+        code = code * 252533 % 33554393
+    return code
+
+if __name__ == '__main__':
+    row = 2978
+    col = 3083
+
+    print(part1(1, 1))
+    print(part1(3, 4))
+    print(part1(row, col))
-- 
cgit v1.2.3-54-g00ecf