{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Day 15 - path finding\n",
    "\n",
    "- [Day 15](https://adventofcode.com/2018/day/15)\n",
    "\n",
    "We are asked to play out a battle between elves and goblins. The biggest challenge is figuring out how to move; once next to an enemy stepping through the actions should be simple.\n",
    "\n",
    "We've last seen a similar problem (finding the best options in a simulated battle) in [AoC 2015, day 22](https://adventofcode.com/2015/day/22), and I'll again use [the A\\* search algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm) to find the paths, picking the shortest path (sorting equal lengths by the 'reading' order, `(y, x)` tuple sorting, of the first step). Once a shortest path to a target is found, we can stop the search and execute a move.\n",
    "\n",
    "So the trick here is to see a short path that started off to the left then down as _separate_ from a node that steps down then left. In most A\\* implementations you'd see this as the same node in the graph (position the same, distance the same, same heuristic score to any target goals). So here, we attach the first step of a potential path to the A\\* nodes so that it is used in equality testing and hashing, and include the first positon in the priority for the priority queue to prefer paths whose first step come first in reading order over others when they otherwise have the same cost.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from dataclasses import dataclass, field\n",
    "from enum import Enum\n",
    "from heapq import heappop, heappush\n",
    "from itertools import count\n",
    "from operator import attrgetter\n",
    "from typing import Iterable, Iterator, Mapping, Optional, Sequence, Set, Tuple\n",
    "\n",
    "Position = Tuple[int, int]  # y, x order\n",
    "\n",
    "\n",
    "class NoTargetsRemaining(Exception):\n",
    "    \"\"\"No more targets to attack\"\"\"\n",
    "\n",
    "\n",
    "class NoTargetsReachable(Exception):\n",
    "    \"\"\"No path found that reaches a target\"\"\"\n",
    "\n",
    "\n",
    "class ElfDied(Exception):\n",
    "    \"\"\"We lost, because an elf died\"\"\"\n",
    "\n",
    "\n",
    "class Race(Enum):\n",
    "    elf = \"E\"\n",
    "    goblin = \"G\"\n",
    "\n",
    "\n",
    "@dataclass(order=True)\n",
    "class Unit:\n",
    "    race: Race = field(compare=False)\n",
    "    y: int\n",
    "    x: int\n",
    "    hitpoints: int = field(default=200, compare=False)\n",
    "    attackpower: int = field(default=3, compare=False)\n",
    "\n",
    "    @property\n",
    "    def pos(self) -> Position:\n",
    "        return self.y, self.x\n",
    "\n",
    "    def adjacent(self, cave: \"CaveCombat\") -> Set[Position]:\n",
    "        \"\"\"All cave positions adjacent to the current position\"\"\"\n",
    "        positions = (\n",
    "            (self.y + dy, self.x + dx) for dy, dx in ((-1, 0), (0, -1), (0, 1), (1, 0))\n",
    "        )\n",
    "        return {(y, x) for y, x in positions if cave.map[y][x] == \".\"}\n",
    "\n",
    "    def available(self, cave: \"CaveCombat\") -> Set[Position]:\n",
    "        \"\"\"All positions this unit could move to\"\"\"\n",
    "        return {pos for pos in self.adjacent(cave) if cave[pos] is None}\n",
    "\n",
    "    def turn(self, cave: \"CaveCombat\") -> None:\n",
    "        # find targets to go after\n",
    "        targets = [u for u in cave.units if u.race is not self.race]\n",
    "        if not targets:\n",
    "            # end combat\n",
    "            raise NoTargetsRemaining\n",
    "\n",
    "        # determine if we need to move\n",
    "        adjacent = self.adjacent(cave)\n",
    "        in_range = [\n",
    "            u for pos in adjacent for u in (cave[pos],) if u and u.race is not self.race\n",
    "        ]\n",
    "\n",
    "        # we need to move, make a move if possible\n",
    "        if not in_range:\n",
    "            # find a target to move to\n",
    "            target_positions = set().union(*(t.available(cave) for t in targets))\n",
    "            if not target_positions:\n",
    "                # no positions to move to, turn ends\n",
    "                return\n",
    "\n",
    "            # pick a shortest path to one of the positions, returns our new position\n",
    "            try:\n",
    "                self.y, self.x = cave.search_path(self.pos, target_positions)\n",
    "            except NoTargetsReachable:\n",
    "                pass\n",
    "\n",
    "            # check for in-range targets once more now that we have moved\n",
    "            adjacent = self.adjacent(cave)\n",
    "            in_range = [\n",
    "                u\n",
    "                for pos in adjacent\n",
    "                for u in (cave[pos],)\n",
    "                if u and u.race is not self.race\n",
    "            ]\n",
    "\n",
    "        # attack if in range of a target\n",
    "        if in_range:\n",
    "            # pick target with lowest hitpoints; ties broken by reading order\n",
    "            target = min(in_range, key=attrgetter(\"hitpoints\", \"y\", \"x\"))\n",
    "            target.hitpoints -= self.attackpower\n",
    "            if target.hitpoints <= 0:\n",
    "                # target died, remove them from the cave\n",
    "                cave.units.remove(target)\n",
    "                if cave.no_elf_dies and target.race is Race.elf:\n",
    "                    raise ElfDied\n",
    "            return\n",
    "\n",
    "\n",
    "_sentinel_first_pos: Position = (-1, -1)\n",
    "\n",
    "\n",
    "@dataclass(frozen=True, order=True)\n",
    "class Node:\n",
    "    \"\"\"Node on the A* search graph\"\"\"\n",
    "\n",
    "    y: int\n",
    "    x: int\n",
    "    distance: int = 0\n",
    "    # position of first actual transition node. Needed to distinguish\n",
    "    # between multiple possible paths to the same goal, and this is\n",
    "    # used to set the new unit position once a path has been picked.\n",
    "    first_pos: Position = _sentinel_first_pos\n",
    "\n",
    "    @property\n",
    "    def pos(self) -> Position:\n",
    "        return self.y, self.x\n",
    "\n",
    "    def cost(self, goals: Set[Position]) -> int:\n",
    "        \"\"\"Calculate the cost for this node, f(n) = g(n) + h(n)\n",
    "\n",
    "        The cost of this node is the distance travelled (g) plus\n",
    "        estimated cost to get to nearest goal (h).\n",
    "\n",
    "        Here we use the manhattan distance to the nearest goal as\n",
    "        the estimated cost.\n",
    "\n",
    "        \"\"\"\n",
    "        distances = (abs(y - self.y) + abs(x - self.x) for y, x in goals)\n",
    "        return self.distance + min(distances)\n",
    "\n",
    "    def transitions(self, cave: \"CaveCombat\") -> Iterator[\"Node\"]:\n",
    "        cls = type(self)\n",
    "        positions = (\n",
    "            (self.y + dy, self.x + dx) for dy, dx in ((-1, 0), (0, -1), (0, 1), (1, 0))\n",
    "        )\n",
    "        return (\n",
    "            cls(\n",
    "                y,\n",
    "                x,\n",
    "                self.distance + 1,\n",
    "                (y, x) if self.first_pos == _sentinel_first_pos else self.first_pos,\n",
    "            )\n",
    "            for y, x in positions\n",
    "            if cave.map[y][x] == \".\" and cave[(y, x)] is None\n",
    "        )\n",
    "\n",
    "\n",
    "@dataclass\n",
    "class CaveCombat:\n",
    "    map: Sequence[str]\n",
    "    units: Sequence[Unit]\n",
    "    round: int = 0\n",
    "    no_elf_dies: bool = False\n",
    "\n",
    "    def __post_init__(self):\n",
    "        # internal cache of unit positions, updated before each unit turn\n",
    "        self._unit_positions: Mapping = {}\n",
    "\n",
    "    @classmethod\n",
    "    def from_lines(cls, lines: Iterable[str], elf_attackpower: int = 3) -> \"CaveCombat\":\n",
    "        map = []\n",
    "        units = []\n",
    "        unit_chars = \"\".join(r.value for r in Race)\n",
    "        for y, line in enumerate(lines):\n",
    "            cleaned = []\n",
    "            for x, c in enumerate(line):\n",
    "                if c in unit_chars:\n",
    "                    attackpower = elf_attackpower if c == \"E\" else 3\n",
    "                    units.append(Unit(Race(c), y, x, attackpower=attackpower))\n",
    "                    c = \".\"\n",
    "                cleaned.append(c)\n",
    "            map.append(\"\".join(cleaned))\n",
    "        return cls(map, units)\n",
    "\n",
    "    def __str__(self) -> str:\n",
    "        map = [list(line) for line in self.map]\n",
    "        for unit in self.units:\n",
    "            map[unit.y][unit.x] = unit.race.value\n",
    "        return \"\\n\".join([\"\".join(line) for line in map])\n",
    "\n",
    "    def __getitem__(self, yx: Position) -> Optional[Unit]:\n",
    "        if self._unit_positions:\n",
    "            return self._unit_positions.get(yx)\n",
    "        return next((u for u in self.units if u.pos == yx), None)\n",
    "\n",
    "    def do_battle(self) -> int:\n",
    "        while True:\n",
    "            result = self.turn()\n",
    "            if result is not None:\n",
    "                return result\n",
    "\n",
    "    def turn(self) -> Optional[int]:\n",
    "        for unit in sorted(self.units):\n",
    "            # skip units that are dead; these are still in the sorted\n",
    "            # loop iterable but have been removed from self.units\n",
    "            if unit.hitpoints <= 0:\n",
    "                continue\n",
    "\n",
    "            # cache unit positions once per round\n",
    "            self._unit_positions = {u.pos: u for u in self.units}\n",
    "\n",
    "            try:\n",
    "                unit.turn(self)\n",
    "            except NoTargetsRemaining:\n",
    "                return self.round * sum(u.hitpoints for u in self.units)\n",
    "\n",
    "        self.round += 1\n",
    "        return None\n",
    "\n",
    "    def search_path(self, start: Position, goals: Set[Position]) -> Position:\n",
    "        start_node = Node(*start)\n",
    "        open = {start_node}\n",
    "        unique = count()  # tie breaker when costs are equal\n",
    "        pqueue = [\n",
    "            (start_node.cost(goals), start_node.first_pos, next(unique), start_node)\n",
    "        ]\n",
    "        closed = set()\n",
    "        distances = {\n",
    "            start_node.pos: 0\n",
    "        }  # pos -> distance. Ignore nodes that are longer.\n",
    "        while open:\n",
    "            node = heappop(pqueue)[-1]\n",
    "\n",
    "            if node.pos in goals:\n",
    "                return node.first_pos\n",
    "\n",
    "            open.remove(node)\n",
    "            closed.add(node)\n",
    "            for new in node.transitions(self):\n",
    "                if new in closed or new in open:\n",
    "                    continue\n",
    "                if distances.get(new.pos, float(\"inf\")) < new.distance:\n",
    "                    # already reached this point with a shorter path\n",
    "                    continue\n",
    "                open.add(new)\n",
    "                distances[new.pos] = new.distance\n",
    "                heappush(pqueue, (new.cost(goals), new.first_pos, next(unique), new))\n",
    "\n",
    "        raise NoTargetsReachable"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "movetest = CaveCombat.from_lines(\n",
    "    \"\"\"\\\n",
    "#########\n",
    "#G..G..G#\n",
    "#.......#\n",
    "#.......#\n",
    "#G..E..G#\n",
    "#.......#\n",
    "#.......#\n",
    "#G..G..G#\n",
    "#########\"\"\".splitlines()\n",
    ")\n",
    "outputs = (\n",
    "    \"#########\\n#G..G..G#\\n#.......#\\n#.......#\\n#G..E..G#\\n#.......#\\n#.......#\\n#G..G..G#\\n#########\",\n",
    "    \"#########\\n#.G...G.#\\n#...G...#\\n#...E..G#\\n#.G.....#\\n#.......#\\n#G..G..G#\\n#.......#\\n#########\",\n",
    "    \"#########\\n#..G.G..#\\n#...G...#\\n#.G.E.G.#\\n#.......#\\n#G..G..G#\\n#.......#\\n#.......#\\n#########\",\n",
    "    \"#########\\n#.......#\\n#..GGG..#\\n#..GEG..#\\n#G..G...#\\n#......G#\\n#.......#\\n#.......#\\n#########\",\n",
    ")\n",
    "for expected in outputs:\n",
    "    assert str(movetest) == expected\n",
    "    movetest.turn()\n",
    "\n",
    "combattest = CaveCombat.from_lines(\n",
    "    \"\"\"\\\n",
    "#######\n",
    "#.G...#\n",
    "#...EG#\n",
    "#.#.#G#\n",
    "#..G#E#\n",
    "#.....#\n",
    "#######\"\"\".splitlines()\n",
    ")\n",
    "rounds = (\n",
    "    (\n",
    "        0,\n",
    "        \"#######\\n#.G...#\\n#...EG#\\n#.#.#G#\\n#..G#E#\\n#.....#\\n#######\",\n",
    "        (\"G\", 200),\n",
    "        (\"E\", 200),\n",
    "        (\"G\", 200),\n",
    "        (\"G\", 200),\n",
    "        (\"G\", 200),\n",
    "        (\"E\", 200),\n",
    "    ),\n",
    "    (\n",
    "        1,\n",
    "        \"#######\\n#..G..#\\n#...EG#\\n#.#G#G#\\n#...#E#\\n#.....#\\n#######\",\n",
    "        (\"G\", 200),\n",
    "        (\"E\", 197),\n",
    "        (\"G\", 197),\n",
    "        (\"G\", 200),\n",
    "        (\"G\", 197),\n",
    "        (\"E\", 197),\n",
    "    ),\n",
    "    (\n",
    "        2,\n",
    "        \"#######\\n#...G.#\\n#..GEG#\\n#.#.#G#\\n#...#E#\\n#.....#\\n#######\",\n",
    "        (\"G\", 200),\n",
    "        (\"G\", 200),\n",
    "        (\"E\", 188),\n",
    "        (\"G\", 194),\n",
    "        (\"G\", 194),\n",
    "        (\"E\", 194),\n",
    "    ),\n",
    "    (\n",
    "        23,\n",
    "        \"#######\\n#...G.#\\n#..G.G#\\n#.#.#G#\\n#...#E#\\n#.....#\\n#######\",\n",
    "        (\"G\", 200),\n",
    "        (\"G\", 200),\n",
    "        (\"G\", 131),\n",
    "        (\"G\", 131),\n",
    "        (\"E\", 131),\n",
    "    ),\n",
    "    (\n",
    "        24,\n",
    "        \"#######\\n#..G..#\\n#...G.#\\n#.#G#G#\\n#...#E#\\n#.....#\\n#######\",\n",
    "        (\"G\", 200),\n",
    "        (\"G\", 131),\n",
    "        (\"G\", 200),\n",
    "        (\"G\", 128),\n",
    "        (\"E\", 128),\n",
    "    ),\n",
    "    (\n",
    "        25,\n",
    "        \"#######\\n#.G...#\\n#..G..#\\n#.#.#G#\\n#..G#E#\\n#.....#\\n#######\",\n",
    "        (\"G\", 200),\n",
    "        (\"G\", 131),\n",
    "        (\"G\", 125),\n",
    "        (\"G\", 200),\n",
    "        (\"E\", 125),\n",
    "    ),\n",
    "    (\n",
    "        26,\n",
    "        \"#######\\n#G....#\\n#.G...#\\n#.#.#G#\\n#...#E#\\n#..G..#\\n#######\",\n",
    "        (\"G\", 200),\n",
    "        (\"G\", 131),\n",
    "        (\"G\", 122),\n",
    "        (\"E\", 122),\n",
    "        (\"G\", 200),\n",
    "    ),\n",
    "    (\n",
    "        27,\n",
    "        \"#######\\n#G....#\\n#.G...#\\n#.#.#G#\\n#...#E#\\n#...G.#\\n#######\",\n",
    "        (\"G\", 200),\n",
    "        (\"G\", 131),\n",
    "        (\"G\", 119),\n",
    "        (\"E\", 119),\n",
    "        (\"G\", 200),\n",
    "    ),\n",
    "    (\n",
    "        28,\n",
    "        \"#######\\n#G....#\\n#.G...#\\n#.#.#G#\\n#...#E#\\n#....G#\\n#######\",\n",
    "        (\"G\", 200),\n",
    "        (\"G\", 131),\n",
    "        (\"G\", 116),\n",
    "        (\"E\", 113),\n",
    "        (\"G\", 200),\n",
    "    ),\n",
    "    (\n",
    "        47,\n",
    "        \"#######\\n#G....#\\n#.G...#\\n#.#.#G#\\n#...#.#\\n#....G#\\n#######\",\n",
    "        (\"G\", 200),\n",
    "        (\"G\", 131),\n",
    "        (\"G\", 59),\n",
    "        (\"G\", 200),\n",
    "    ),\n",
    ")\n",
    "for round, expected, *units in rounds:\n",
    "    while combattest.round != round:\n",
    "        combattest.turn()\n",
    "    assert str(combattest) == expected\n",
    "    assert [(u.race.value, u.hitpoints) for u in sorted(combattest.units)] == units\n",
    "\n",
    "assert combattest.turn() == 27730\n",
    "\n",
    "tests = (\n",
    "    (\n",
    "        \"#######\\n#G..#E#\\n#E#E.E#\\n#G.##.#\\n#...#E#\\n#...E.#\\n#######\",\n",
    "        \"#######\\n#...#E#\\n#E#...#\\n#.E##.#\\n#E..#E#\\n#.....#\\n#######\",\n",
    "        36334,\n",
    "    ),\n",
    "    (\n",
    "        \"#######\\n#E..EG#\\n#.#G.E#\\n#E.##E#\\n#G..#.#\\n#..E#.#\\n#######\",\n",
    "        \"#######\\n#.E.E.#\\n#.#E..#\\n#E.##.#\\n#.E.#.#\\n#...#.#\\n#######\",\n",
    "        39514,\n",
    "    ),\n",
    "    (\n",
    "        \"#######\\n#E.G#.#\\n#.#G..#\\n#G.#.G#\\n#G..#.#\\n#...E.#\\n#######\",\n",
    "        \"#######\\n#G.G#.#\\n#.#G..#\\n#..#..#\\n#...#G#\\n#...G.#\\n#######\",\n",
    "        27755,\n",
    "    ),\n",
    "    (\n",
    "        \"#######\\n#.E...#\\n#.#..G#\\n#.###.#\\n#E#G#G#\\n#...#G#\\n#######\",\n",
    "        \"#######\\n#.....#\\n#.#G..#\\n#.###.#\\n#.#.#.#\\n#G.G#G#\\n#######\",\n",
    "        28944,\n",
    "    ),\n",
    "    (\n",
    "        \"#########\\n#G......#\\n#.E.#...#\\n#..##..G#\\n#...##..#\\n#...#...#\\n#.G...G.#\\n#.....G.#\\n#########\",\n",
    "        \"#########\\n#.G.....#\\n#G.G#...#\\n#.G##...#\\n#...##..#\\n#.G.#...#\\n#.......#\\n#.......#\\n#########\",\n",
    "        18740,\n",
    "    ),\n",
    ")\n",
    "for start, end, expected in tests:\n",
    "    testcave = CaveCombat.from_lines(start.splitlines())\n",
    "    assert testcave.do_battle() == expected\n",
    "    assert str(testcave) == end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import aocd\n",
    "\n",
    "data = aocd.get_data(day=15, year=2018)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 1: 195811\n"
     ]
    }
   ],
   "source": [
    "cave = CaveCombat.from_lines(data.splitlines())\n",
    "print(\"Part 1:\", cave.do_battle())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2 - bisection?\n",
    "\n",
    "Runnig a full battle is not that cheap, so incrementing the attack power one step at a time is going to take a long time.\n",
    "\n",
    "So we need a faster method. We could use bisection here; we can figure out a lower and upper bound for Elf strength, then start in between those two points and see if the Elves can survive with that strength. If not, we have a new lower bound, if they can win, we have a new upper bound. Repeat with the new midpoint until we have the lowest viable attack strength. Bisection lets us home in on the ideal minimal attack strength in $O(\\log_2 n)$ steps for $n$ strengths between the low bound (3 at least) and 200 (at most).\n",
    "\n",
    "We could limit those bounds further, perhaps. The lower and upper bounds are determined by the goblin vs. elves mix, and how many elves can take on a goblin together vs. how many goblins might surround an elf to attack together, so we can probably do better than 3 and 200 here.\n",
    "\n",
    "For example, in a scenario with just one elf in the cave and 5 goblins, the best case scenario is that the elf can take on the goblins one by one, while the worst case is that 4 goblins surround our elf right at the start and start hacking away. The elf then has to defeat 2 goblins before the numbers go down.\n",
    "\n",
    "Put generically, with $\\gamma$ goblins and $\\epsilon$ elves:\n",
    "\n",
    "- The worst case involves the goblins all focusing on 1 elf. That single elf has to hack their way through a replentishing number of goblins; $\\gamma$ goblins can sustain $\\gamma - 3$ deaths before they can no longer surround a single elf. We can take this an an average attack strength; $avga = \\frac{12\\max(0, \\gamma - 4) + 3(\\frac{\\min(4, \\gamma)(\\min(4, \\gamma) + 1)}{2})}{\\gamma}$. The single elf can survive $minr = \\lfloor\\frac{200}{avga}\\rfloor$ rounds, so their attack strength needs to be adjusted to match that; $strength = min(200, \\lceil\\frac{200\\gamma}{minr}\\rceil)$; note that the maximum attack power is 200, there is no point in putting this higher, we must assume that we never have to deal with such a no-win setup.\n",
    "\n",
    "- The best case has elves ganging up on goblins 4 elves at a time, so the ganged-up goblins can only do 3 points of damage per round divided over up to 4 elves. Elves can gang up on $maxg = \\lceil\\frac{\\epsilon}{4}\\rceil$ goblins, which have to divide their strength over those $\\epsilon$ elves (we'll assume we can rotate out weakened elves), giving an average gobling attack strength of $avga = \\frac{3maxg}{\\epsilon}$. This means the elves can last $minr = \\lfloor\\frac{200\\epsilon}{avga}\\rfloor$ rounds, and need an attack strength $strength = max(3, \\lceil\\frac{200\\gamma}{minr}\\rceil)$ (the minimum attack strength to win with must be 4, but we do need to test at 3 to find the lowest 'losing' point).\n",
    "\n",
    "Once we have a lower and upper bound for attack strength, we can find the actual minimal strength with bisection.\n",
    "\n",
    "For the example with $\\epsilon = 1$ and $\\gamma = 5$, the minimum is 16, maximum is 44. You run the scenario with a midpoint first, $\\lfloor\\frac{44 - 16}{2}\\rfloor + 16 = 30$. This scenario fails, our single elf dies, so we know 30 to be a new lower bound. We next try with $\\lfloor\\frac{44 - 30}{2}\\rfloor + 30 = 37$ (fails), then at 40 the elf succeeds, so we have a new upper bound and step to 38. Here the elf wins again, and since that's 1 step above our lower bound, we know that that's the right answer here.\n",
    "\n",
    "In the end, for the actual puzzle input, the bounds are 3 and 200 anyway, so the above work was more complicated than actually needed. Oh well.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "\n",
    "def optimise_strength(cavelines: Iterable[str], verbose=False) -> int:\n",
    "    log = print if verbose else lambda *a, **k: None\n",
    "    elves = sum(line.count(\"E\") for line in cavelines)\n",
    "    goblins = sum(line.count(\"G\") for line in cavelines)\n",
    "\n",
    "    # worst case, highest strength required\n",
    "    avga = (\n",
    "        12 * max(0, goblins - 4) + 3 * (min(4, goblins) * (min(4, goblins) + 1)) // 2\n",
    "    ) / goblins\n",
    "    high = min(200, math.ceil(200 * goblins / (200 // avga)))\n",
    "\n",
    "    # best case, lowest strength required\n",
    "    minr = math.ceil(200 * elves / ((3 * math.ceil(elves / 4)) / elves))\n",
    "    low = max(3, math.ceil((200 * goblins) / minr))\n",
    "\n",
    "    last_high_outcome = 0\n",
    "    log(f\"Optimising, strength between {low} and {high}\")\n",
    "\n",
    "    while low < high:\n",
    "        mid = (high - low) // 2 + low\n",
    "        log(f\"\\n - Trying strength {mid}\")\n",
    "        cave = CaveCombat.from_lines(cavelines, mid)\n",
    "        cave.no_elf_dies = True\n",
    "        try:\n",
    "            outcome = cave.do_battle()\n",
    "        except ElfDied:\n",
    "            # not high enough\n",
    "            log(\"   - Too low, an elf died\")\n",
    "            low = mid\n",
    "        else:\n",
    "            log(\"   - Elves victorious\")\n",
    "            high = mid\n",
    "            last_high_outcome = outcome\n",
    "\n",
    "        # See if high is one step above low, that's our sweet spot\n",
    "        if high == low + 1:\n",
    "            return last_high_outcome\n",
    "    raise AssertionError(\"wrong low or high starting points\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "optimise_tests = (\n",
    "    (\"#######\\n#.G...#\\n#...EG#\\n#.#.#G#\\n#..G#E#\\n#.....#\\n#######\", 4988),\n",
    "    (\"#######\\n#E..EG#\\n#.#G.E#\\n#E.##E#\\n#G..#.#\\n#..E#.#\\n#######\", 31284),\n",
    "    (\"#######\\n#E.G#.#\\n#.#G..#\\n#G.#.G#\\n#G..#.#\\n#...E.#\\n#######\", 3478),\n",
    "    (\"#######\\n#.E...#\\n#.#..G#\\n#.###.#\\n#E#G#G#\\n#...#G#\\n#######\", 6474),\n",
    "    (\n",
    "        \"#########\\n#G......#\\n#.E.#...#\\n#..##..G#\\n#...##..#\\n#...#...#\\n#.G...G.#\\n#.....G.#\\n#########\",\n",
    "        1140,\n",
    "    ),\n",
    ")\n",
    "for lines, expected in optimise_tests:\n",
    "    assert optimise_strength(lines.splitlines()) == expected"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 2: 69867\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 2:\", optimise_strength(data.splitlines()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Addendum - Bisection actually can't always work\n",
    "\n",
    "As I checked out the [Advent of Code sub-Reddit discussions](https://www.reddit.com/r/adventofcode/) I found that there are scenarios where the elves win at $strength = n$ but lose at $strength = n + 1$, because it takes longer to kill a goblin at $strength = n$ and so a weak elf won't walk into the healthier goblin that would kill it at $strength = n + 1$. This means there is no strict ordering over the range of strengths (there is no single point where losing turns to winning), and we can't use bisection in that case.\n",
    "\n",
    "So the _correct_ solution is to iterate up from $strength = 4$. As an elf dying means the battle is cut short, this isn't all that bad. We can still complete this task in a few seconds.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def optimise_strength_corrected(cavelines: Iterable[str], verbose=False) -> int:\n",
    "    log = print if verbose else lambda *a, **k: None\n",
    "\n",
    "    for strength in range(4, 200):\n",
    "        log(f\"\\n- Trying strength {strength}\")\n",
    "        cave = CaveCombat.from_lines(cavelines, strength)\n",
    "        cave.no_elf_dies = True\n",
    "        try:\n",
    "            outcome = cave.do_battle()\n",
    "        except ElfDied:\n",
    "            # not high enough\n",
    "            log(\"   - Too low, an elf died\")\n",
    "        else:\n",
    "            log(\"   - Elves victorious\")\n",
    "            return outcome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "for lines, expected in optimise_tests:\n",
    "    assert optimise_strength_corrected(lines.splitlines()) == expected"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Part 2: 69867\n"
     ]
    }
   ],
   "source": [
    "print(\"Part 2:\", optimise_strength_corrected(data.splitlines()))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}