AoC 2021.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6033f94a",
   "metadata": {},
   "source": [
    "# Day 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "0d6dc10e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import pairwise, tee\n",
    "from pathlib import Path\n",
    "\n",
    "INPUTS = Path(\"aoc2021_inputs\")\n",
    "\n",
    "# With lazy iterator:\n",
    "count = 0\n",
    "with open(INPUTS / \"day1.txt\", \"r\") as f:\n",
    "    for prev_, next_ in pairwise(map(int, f)):\n",
    "        count += next_ > prev_\n",
    "assert count == 1292\n",
    "\n",
    "def triplewise(it):\n",
    "    a, b, c = tee(it, 3)\n",
    "    next(b); next(c); next(c)\n",
    "    yield from zip(a, b, c)\n",
    "    \n",
    "def nwise(it, n):\n",
    "    its = tee(it, n)\n",
    "    for i, it in enumerate(its):\n",
    "        for _ in range(i):\n",
    "            next(it)\n",
    "    yield from zip(*its)\n",
    "    \n",
    "def triplewise_(it):\n",
    "    yield from nwise(it, 3)\n",
    "\n",
    "count = 0\n",
    "with open(INPUTS / \"day1.txt\", \"r\") as f:\n",
    "    sum_prev = float(\"+inf\")\n",
    "    for v1, v2, v3 in triplewise_(map(int, f)):\n",
    "        sum_ = v1 + v2 + v3\n",
    "        count += sum_ > sum_prev\n",
    "        sum_prev = sum_\n",
    "assert count == 1262"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7588a0f",
   "metadata": {},
   "source": [
    "# Day 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "93c99a82",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1905 907 1727835\n"
     ]
    }
   ],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day2.txt\")\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    moves = f.readlines()\n",
    "\n",
    "h, v = 0, 0\n",
    "for line in moves:\n",
    "    move, size = line.split()\n",
    "\n",
    "    if move == \"forward\":\n",
    "        h += int(size)\n",
    "    elif move == \"up\":\n",
    "        v -= int(size)\n",
    "    else:\n",
    "        v += int(size)\n",
    "        \n",
    "print(h, v, h * v)\n",
    "assert h * v == 1727835"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "bfc43ffb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1905 810499 907 1544000595\n"
     ]
    }
   ],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day2.txt\")\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    moves = f.readlines()\n",
    "    \n",
    "horiz, depth, aim = 0, 0, 0\n",
    "for line in moves:\n",
    "    move, size = line.split()\n",
    "    size = int(size)\n",
    "    \n",
    "    if move == \"forward\":\n",
    "        horiz += size\n",
    "        depth += size * aim\n",
    "    elif move == \"down\":\n",
    "        aim += size\n",
    "    else:\n",
    "        aim -= size\n",
    "        \n",
    "print(horiz, depth, aim, horiz * depth)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "550eab23",
   "metadata": {},
   "source": [
    "# Day 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "4c867cfa",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "749376\n",
      "3871\n",
      "613\n",
      "2372923\n"
     ]
    }
   ],
   "source": [
    "from collections import Counter\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day3.txt\")\n",
    "\n",
    "counter = Counter()\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    for line in f:\n",
    "        counter += Counter(enumerate(line.strip()))\n",
    "\n",
    "gamma, epsilon = 0, 0\n",
    "total_bits = len(counter) // 2\n",
    "for n in range(total_bits):\n",
    "    if counter[(n, \"1\")] > counter[(n, \"0\")]:\n",
    "        gamma |= 1 << (total_bits - n - 1)\n",
    "    else:\n",
    "        epsilon |= 1 << (total_bits - n - 1)\n",
    "print(gamma * epsilon)\n",
    "\n",
    "# --- part 2 ---\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    lines = f.readlines()\n",
    "\n",
    "under_consideration = lines\n",
    "prefix = \"\"\n",
    "while len(under_consideration) > 1:\n",
    "    c = Counter(line[:len(prefix) + 1] for line in under_consideration)\n",
    "    c[prefix + \"1\"] += 0.5  # Force ending in \"1\" to win in case of draw.\n",
    "    (prefix, count), = c.most_common(1)\n",
    "    under_consideration = [line for line in under_consideration if line.startswith(prefix)]\n",
    "oxygen = int(under_consideration[0], 2)\n",
    "print(oxygen)\n",
    "\n",
    "under_consideration = lines\n",
    "prefix = \"\"\n",
    "while len(under_consideration) > 1:\n",
    "    c = Counter(line[:len(prefix) + 1] for line in under_consideration)\n",
    "    c[prefix + \"0\"] -= 0.5  # Force ending in \"0\" to lose in case of draw\n",
    "    _, (prefix, count) = c.most_common(2)\n",
    "    under_consideration = [line for line in under_consideration if line.startswith(prefix)]\n",
    "co2 = int(under_consideration[0], 2)\n",
    "print(co2)\n",
    "\n",
    "print(oxygen * co2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab6a16bd",
   "metadata": {},
   "source": [
    "# Day 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e327861d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27027\n",
      "36975\n"
     ]
    }
   ],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day4.txt\")\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    nums = next(f).strip().split(\",\")  # Read order in which numbers are drawn.\n",
    "    data = f.read().strip()\n",
    "\n",
    "# Build dictionary storing the position of each number.\n",
    "num_pos = dict(zip(nums, range(len(nums))))\n",
    "\n",
    "# `boards` is a list of pairs (dirs, nums)\n",
    "# `dirs` contains a list of all the possible winning directions for a board;\n",
    "# `nums` is the set of all the numbers that show up in that board.\n",
    "boards = []\n",
    "for subdata in data.split(\"\\n\\n\"):\n",
    "    # Store the rows and columns in the same list.\n",
    "    directions = []\n",
    "    # Set to keep track of all the numbers the card contains.\n",
    "    numbers = set()\n",
    "    for row in subdata.split(\"\\n\"):\n",
    "        directions.append(row.split())\n",
    "        # Update the numbers with the ones of the current row.\n",
    "        numbers |= {*directions[-1]}\n",
    "    # Add columns to the directions list.\n",
    "    bs = len(directions)\n",
    "    directions += [\n",
    "        [directions[r][c] for r in range(bs)] for c in range(bs)\n",
    "    ]\n",
    "\n",
    "    boards.append((directions, numbers))\n",
    "\n",
    "# Go over each board and figure out when that board is done.\n",
    "done_at = [\n",
    "    min(max(num_pos[n] for n in dir_) for dir_ in dirs)\n",
    "    for dirs, _ in boards\n",
    "]\n",
    "\n",
    "def score_board(winning_move_idx):\n",
    "    _, board_nums = boards[done_at.index(winning_move_idx)]\n",
    "    unmarked_numbers = map(int, board_nums - set(nums[:winning_move_idx + 1]))\n",
    "    return sum(unmarked_numbers) * int(nums[winning_move_idx])\n",
    "\n",
    "print(score_board(min(done_at))) # part 1\n",
    "print(score_board(max(done_at))) # part 2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60ed7a14",
   "metadata": {},
   "source": [
    "# Day 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "7d246906",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7142\n",
      "20012\n"
     ]
    }
   ],
   "source": [
    "from collections import Counter\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day5.txt\")\n",
    "\n",
    "def parse_line(string):\n",
    "    return [list(map(int, point.split(\",\"))) for point in string.split(\" -> \")]\n",
    "\n",
    "def sign(x):\n",
    "    return (x > 0) - (x < 0)\n",
    "\n",
    "def generate_segment(left, right):\n",
    "    (xl, yl), (xr, yr) = left, right\n",
    "    delta = max(abs(xl - xr), abs(yl - yr))\n",
    "    dx, dy = sign(xr - xl), sign(yr - yl)\n",
    "    return [(xl + dx * d, yl + dy * d) for d in range(delta + 1)]\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    points = [parse_line(line.strip()) for line in f]\n",
    "\n",
    "counter = Counter()\n",
    "for left, right in points:\n",
    "    (xl, yl), (xr, yr) = left, right\n",
    "    if xl != xr and yl != yr:\n",
    "        continue\n",
    "    counter += Counter(generate_segment(left, right))\n",
    "\n",
    "print(sum(cnt > 1 for _, cnt in counter.items()))\n",
    "\n",
    "counter = Counter()\n",
    "for left, right in points:\n",
    "    counter += Counter(generate_segment(left, right))\n",
    "\n",
    "print(sum(cnt > 1 for _, cnt in counter.items()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6c944cf",
   "metadata": {},
   "source": [
    "# Day 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "5fb647bc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "345387\n",
      "1574445493136\n"
     ]
    }
   ],
   "source": [
    "from collections import Counter\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day6.txt\")\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    lanternfish = [int(num) for num in f.readline().split(\",\")]\n",
    "    \n",
    "population = Counter(lanternfish)\n",
    "sizes = [population.total()]\n",
    "for cycle in [80, 256 - 80]:\n",
    "    for _ in range(cycle):\n",
    "        next_gen = Counter()\n",
    "        for age in range(8, 0, -1):\n",
    "            next_gen[age - 1] = population[age]\n",
    "        next_gen[8] = population[0]\n",
    "        next_gen[6] += population[0]\n",
    "        population = next_gen\n",
    "        sizes.append(population.total())\n",
    "    print(population.total())  # New in Python 3.10"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3f662f8",
   "metadata": {},
   "source": [
    "# Day 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "71c1a087",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "349812\n",
      "99763899\n"
     ]
    }
   ],
   "source": [
    "from math import ceil\n",
    "from pathlib import Path\n",
    "from statistics import mean, median\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day7.txt\")\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    crabs = [int(num) for num in f.readline().split(\",\")]\n",
    "\n",
    "linear_alignment = round(median(crabs))\n",
    "print(sum(abs(linear_alignment - crab) for crab in crabs))\n",
    "quad_alignment_options = [c := ceil(mean(crabs)), c - 1]\n",
    "print(min(sum(\n",
    "    (d := abs(quad_alignment - crab)) * (d + 1) // 2\n",
    "     for crab in crabs\n",
    ") for quad_alignment in quad_alignment_options))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6239f5a1",
   "metadata": {},
   "source": [
    "# Day 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "ff89fb94",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "264\n",
      "1063760\n"
     ]
    }
   ],
   "source": [
    "from collections import Counter\n",
    "from functools import reduce\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day8.txt\")\n",
    "\n",
    "segment_lengths = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]\n",
    "\n",
    "def with_length(clues, l):\n",
    "    return {s for s in clues if len(s) == l}\n",
    "\n",
    "def comp(clue):\n",
    "    return frozenset(\"abcdefg\") - clue\n",
    "\n",
    "def solve_clues(clues):\n",
    "    one = with_length(clues, 2).pop()\n",
    "    four = with_length(clues, 4).pop()\n",
    "    seven = with_length(clues, 3).pop()\n",
    "    eight = with_length(clues, 7).pop()\n",
    "\n",
    "    zero_six_nine = with_length(clues, 6)\n",
    "    six = [s for s in zero_six_nine if comp(s) < one][0]\n",
    "    zero_nine = zero_six_nine - {six}\n",
    "    zero = [s for s in zero_nine if comp(s) < four][0]\n",
    "    nine = (zero_nine - {zero}).pop()\n",
    "    \n",
    "    two_three_five = with_length(clues, 5)\n",
    "    three = [s for s in two_three_five if one < s][0]\n",
    "    two_five = two_three_five - {three}\n",
    "    five = [s for s in two_five if s < nine][0]\n",
    "    two = (two_five - {five}).pop()\n",
    "    return [zero, one, two, three, four, five, six, seven, eight, nine]\n",
    "    \n",
    "\n",
    "counter = Counter()\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    for line in f:\n",
    "        _, digits = line.split(\" | \")\n",
    "        counter.update(map(len, digits.strip().split()))\n",
    "print(sum(counter[segment_lengths[d]] for d in [1, 4, 7, 8]))\n",
    "\n",
    "outs = []\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    for line in f:\n",
    "        clue_strings, digits = line.split(\" | \")\n",
    "        clues = [frozenset(string) for string in clue_strings.split()]\n",
    "        solutions = solve_clues(clues)\n",
    "        digits = [solutions.index(frozenset(string)) for string in digits.strip().split()]\n",
    "        outs.append(reduce(lambda l, r: 10 * l + r, digits))\n",
    "print(sum(outs))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a92e2075",
   "metadata": {},
   "source": [
    "# Day 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "91552328",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "502\n",
      "1330560\n"
     ]
    }
   ],
   "source": [
    "from math import prod\n",
    "from pathlib import Path\n",
    "\n",
    "def neighbouring_positions(matrix, r, c):\n",
    "    return {\n",
    "        (r_, c_) for r_, c_ in [(r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)]\n",
    "        if 0 <= r_ < len(matrix) and 0 <= c_ < len(matrix[0])\n",
    "    }\n",
    "\n",
    "def get_neighbours(matrix, r, c):\n",
    "    to_try = neighbouring_positions(matrix, r, c)\n",
    "    return {matrix[r_][c_] for r_, c_ in to_try}\n",
    "\n",
    "def find_basin(matrix, r, c):\n",
    "    to_visit, visited, basin = {(r, c)}, set(), set()\n",
    "    while to_visit:\n",
    "        r_, c_ = to_visit.pop()\n",
    "        if matrix[r_][c_] == 9:\n",
    "            continue\n",
    "        basin.add((r_, c_))\n",
    "        next_neighbours = neighbouring_positions(matrix, r_, c_)\n",
    "        to_visit.update(next_neighbours - visited)\n",
    "        visited.update(next_neighbours)\n",
    "    return basin\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day9.txt\")\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    matrix = [\n",
    "        [int(num) for num in line.strip()]\n",
    "        for line in f.readlines()\n",
    "    ]\n",
    "\n",
    "risk = 0\n",
    "low_point_locations = []\n",
    "for r, row in enumerate(matrix):\n",
    "    for c, val in enumerate(row):\n",
    "        neighbs = get_neighbours(matrix, r, c)\n",
    "        if min(neighbs) > val:\n",
    "            risk += val + 1\n",
    "            low_point_locations.append((r, c))\n",
    "print(risk)\n",
    "\n",
    "basin_sizes = []\n",
    "for low_point in low_point_locations:\n",
    "    basin = find_basin(matrix, *low_point)\n",
    "    basin_sizes.append(len(basin))\n",
    "print(prod(sorted(basin_sizes)[-3:]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74ef164b",
   "metadata": {},
   "source": [
    "# Day 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "febfef59",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "370407\n",
      "3249889609\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "from pathlib import Path\n",
    "from statistics import median\n",
    "\n",
    "OPENING = {\"(\", \"[\", \"{\", \"<\"}  # Set with opening characters.\n",
    "CLOSING = {\")\": \"(\", \"]\": \"[\", \"}\": \"{\", \">\": \"<\"}  # Dict with opening character for each closing.\n",
    "CLOSE_WITH = {v: k for k, v in CLOSING.items()}     # Dict with closing character for each opening.\n",
    "CORRUPTED_SCORES = {\")\": 3, \"]\": 57, \"}\": 1197, \">\": 25137}  # Scores.\n",
    "COMPLETION_SCORES = {\")\": 1, \"]\": 2, \"}\": 3, \">\": 4}\n",
    "\n",
    "def from_digits(digits, base):\n",
    "    return reduce(lambda l, r: l * base + r, digits, 0)\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day10.txt\")\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    lines = f.readlines()\n",
    "\n",
    "corrupted_scores = 0\n",
    "completion_scores = []\n",
    "for line in lines:\n",
    "    stack = []\n",
    "    for char in line:\n",
    "        if char in OPENING:\n",
    "            stack.append(char)\n",
    "        elif char in CLOSING:\n",
    "            if stack[-1] == CLOSING[char]:\n",
    "                stack.pop()\n",
    "            else:\n",
    "                corrupted_scores += CORRUPTED_SCORES[char]\n",
    "                break\n",
    "    else:\n",
    "        digits = [COMPLETION_SCORES[CLOSE_WITH[char]] for char in reversed(stack)]\n",
    "        completion_scores.append(from_digits(digits, 5))\n",
    "print(corrupted_scores)\n",
    "print(median(completion_scores))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bbdbf3ab",
   "metadata": {},
   "source": [
    "# Day 11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "e696f716",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1585\n",
      "382\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day11.txt\")\n",
    "\n",
    "grid = defaultdict(lambda: float(\"-inf\"))\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    grid |= {\n",
    "        (r, c): int(val)\n",
    "        for r, line in enumerate(f) for c, val in enumerate(line.strip())\n",
    "    }\n",
    "\n",
    "def neighbouring_positions(r, c):\n",
    "    return [\n",
    "        (r + 1, c), (r + 1, c + 1), (r, c + 1), (r - 1, c + 1),\n",
    "        (r - 1, c), (r - 1, c - 1), (r, c - 1), (r + 1, c - 1),\n",
    "    ]\n",
    "\n",
    "flashes, flashed, step = 0, set(), 0\n",
    "while len(flashed) < 100:\n",
    "    step += 1\n",
    "    flashed = set()\n",
    "    to_increment = [(r, c) for r in range(10) for c in range(10)]\n",
    "    while to_increment:\n",
    "        r, c = to_increment.pop()\n",
    "        if not ((0 <= r < 10) and (0 <= c < 10)):\n",
    "            continue\n",
    "        grid[r, c] += 1\n",
    "        if grid[r, c] > 9 and (r, c) not in flashed:\n",
    "            flashes += 1\n",
    "            flashed.add((r, c))\n",
    "            to_increment.extend(neighbouring_positions(r, c))\n",
    "    for r in range(10):\n",
    "        for c in range(10):\n",
    "            grid[r, c] = 0 if grid[r, c] > 9 else grid[r, c]\n",
    "    if step == 100:\n",
    "        print(flashes)\n",
    "print(step)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0b04567",
   "metadata": {},
   "source": [
    "# Day 12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "ea220213",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3410\n",
      "98796\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day12.txt\")\n",
    "\n",
    "def count_paths(graph, path_built, can_revisit=True):\n",
    "    if path_built and path_built[-1] == \"end\":\n",
    "        return 1\n",
    "\n",
    "    return sum(\n",
    "        count_paths(\n",
    "            graph,\n",
    "            path_built + [next_stop],\n",
    "            can_revisit and not (next_stop.islower() and next_stop in path_built),\n",
    "        )\n",
    "        for next_stop in graph[path_built[-1]]\n",
    "        if next_stop not in path_built or next_stop.isupper() or can_revisit\n",
    "    )\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    lines = f.readlines()\n",
    "\n",
    "graph = defaultdict(list)\n",
    "for line in lines:\n",
    "    pt1, pt2 = line.strip().split(\"-\")\n",
    "    graph[pt1].append(pt2)\n",
    "    graph[pt2].append(pt1)\n",
    "# Make sure no cave points back at the “start” cave.\n",
    "for connections in graph.values():\n",
    "    try:\n",
    "        connections.remove(\"start\")\n",
    "    except ValueError:\n",
    "        pass\n",
    "\n",
    "print(count_paths(graph, [\"start\"], False))\n",
    "print(count_paths(graph, [\"start\"], True))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d9fcf325",
   "metadata": {},
   "source": [
    "# Day 13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "674665b4",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "████  ██  █  █  ██  █  █ ███  ████  ██ \n",
      "█    █  █ █ █  █  █ █ █  █  █    █ █  █\n",
      "███  █    ██   █    ██   ███    █  █   \n",
      "█    █ ██ █ █  █    █ █  █  █  █   █ ██\n",
      "█    █  █ █ █  █  █ █ █  █  █ █    █  █\n",
      "█     ███ █  █  ██  █  █ ███  ████  ███\n"
     ]
    }
   ],
   "source": [
    "from itertools import chain\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day13.txt\")\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    contents = f.read()\n",
    "\n",
    "def fold(points, fold_point):\n",
    "    xf, yf = fold_point\n",
    "    return {\n",
    "        (x if x < xf else 2 * xf - x, y if y < yf else 2 * yf - y)\n",
    "        for x, y in points\n",
    "    }\n",
    "\n",
    "point_data, fold_data = contents.split(\"\\n\\n\")\n",
    "points = {tuple(map(int, line.split(\",\"))) for line in point_data.splitlines()}\n",
    "folds = fold_data.splitlines()\n",
    "\n",
    "MAX_COORD = 1 + max(chain.from_iterable(points))\n",
    "\n",
    "for fold_string in folds:\n",
    "    coord, value = fold_string.removeprefix(\"fold along \").split(\"=\")\n",
    "    fold_point = (\n",
    "        int(value) if coord == \"x\" else MAX_COORD,\n",
    "        int(value) if coord == \"y\" else MAX_COORD,\n",
    "    )\n",
    "    points = fold(points, fold_point)\n",
    "\n",
    "width = max(x for x, _ in points) + 1\n",
    "height = max(y for _, y in points) + 1\n",
    "result = [[\" \"] * width for _ in range(height)]\n",
    "for x, y in points:\n",
    "    result[y][x] = \"\\u2588\"\n",
    "print(\"\\n\".join(\"\".join(line) for line in result))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "263337ea",
   "metadata": {},
   "source": [
    "# Day 14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "9212149d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3015383850689\n"
     ]
    }
   ],
   "source": [
    "from collections import Counter\n",
    "from itertools import chain\n",
    "from math import ceil\n",
    "from pathlib import Path\n",
    "\n",
    "try:\n",
    "    from itertools import pairwise  # Python 3.10\n",
    "except ImportError:\n",
    "    from itertools import tee\n",
    "    def pairwise(it):\n",
    "        it1, it2 = tee(it, 2)\n",
    "        next(it2)\n",
    "        yield from zip(it1, it2)\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day14.txt\")\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    polymer = f.readline().strip()\n",
    "    f.readline()  # empty line\n",
    "    rules = dict(line.strip().split(\" -> \") for line in f)\n",
    "\n",
    "counter = Counter(\"\".join(item) for item in pairwise(polymer))\n",
    "\n",
    "for _ in range(40):\n",
    "    new_counter = Counter()\n",
    "    for (char1, char2), count in counter.items():\n",
    "        target = rules[char1 + char2]\n",
    "        new_counter[char1 + target] += count\n",
    "        new_counter[target + char2] += count\n",
    "    counter = new_counter\n",
    "\n",
    "element_counter = Counter()\n",
    "for (char1, char2), count in counter.items():\n",
    "    element_counter[char1] += count\n",
    "    element_counter[char2] += count\n",
    "print(ceil(max(element_counter.values()) / 2) - ceil(min(element_counter.values()) / 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "459dd638",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'FNFPPNKPPHSOKFFHOFOC'"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "polymer"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "313e3d88",
   "metadata": {},
   "source": [
    "# Day 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "c1fbf8e1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "508\n",
      "2872\n",
      "2.1289970874786377\n"
     ]
    }
   ],
   "source": [
    "from queue import PriorityQueue\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day15.txt\")\n",
    "\n",
    "def neighbouring_costs(grid, r, c):\n",
    "    return [(grid.get((r_, c_), float(\"+inf\")), (r_, c_)) for r_, c_ in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]]\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    grid = {(r, c): int(n) for r, line in enumerate(f) for c, n in enumerate(line.strip())}\n",
    "\n",
    "def dijkstra(costs, from_, dest_):\n",
    "    visited = {from_}\n",
    "    q = PriorityQueue()\n",
    "    q.put((0, from_))\n",
    "    while True:\n",
    "        cost, current_node = q.get()\n",
    "        if current_node == dest_:\n",
    "            return cost\n",
    "        for tot, pos in neighbouring_costs(costs, *current_node):\n",
    "            if tot < float(\"inf\") and pos not in visited:\n",
    "                visited.add(pos)\n",
    "                q.put((cost + tot, pos))\n",
    "\n",
    "print(dijkstra(grid, (0, 0), (99, 99)))\n",
    "\n",
    "R, C = 1 + max(t[0] for t in grid.keys()), 1 + max(t[1] for t in grid.keys())\n",
    "larger_map = {\n",
    "    (r, c): ((grid[r % R, c % C] - 1 + (r//R) + (c//C)) % 9) + 1 for c in range(5 * C) for r in range(5 * R)\n",
    "}\n",
    "\n",
    "from time import time\n",
    "start = time()\n",
    "print(dijkstra(larger_map, (0,0), (5 * R - 1, 5 * C - 1)))\n",
    "print(time() - start)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2c778b66",
   "metadata": {},
   "source": [
    "# Day 16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "ecf6b68e",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "947\n",
      "660797830937\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "BNF-ish grammar that parses the packets.\n",
    "{n} is used to indicate \"repeat n times\".\n",
    "\n",
    "A literal packet is a tuple (type, version, value)\n",
    "An operator packet is a tuple (type, version, flag, list_of_packets)\n",
    "\n",
    "packet := type (version=\"100\" value | version operator_packets)\n",
    "value := (\"1\" group)* \"0\" group\n",
    "group := D{4}\n",
    "# (Bit) Length of packets read is specified by `bit_length`.\n",
    "# Number of packets read is specified by `packet_length`.\n",
    "operator_packets := (\"0\" bit_length packet* | \"1\" packet_length packet{packet_length})\n",
    "bit_length := D{15}\n",
    "packet_length := D{11}\n",
    "type := D{3}\n",
    "version := D{3}\n",
    "D := \"1\" | \"0\"\n",
    "\"\"\"\n",
    "\n",
    "from functools import partial\n",
    "from itertools import chain\n",
    "from math import prod\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day16.txt\")\n",
    "\n",
    "def parse(hexadecimal_packet):\n",
    "    packet_string = \"\".join(\n",
    "        f\"{int(letter, 16):04b}\" for letter in hexadecimal_packet\n",
    "    )\n",
    "    return parse_packet(packet_string)\n",
    "\n",
    "def parse_packet(packet_string):\n",
    "    type_, packet_string = parse_type(packet_string)\n",
    "    version, packet_string = parse_type(packet_string)\n",
    "    if version == \"100\":\n",
    "        value, packet_string = parse_value(packet_string)\n",
    "        return (int(type_, 2), int(version, 2), int(value, 2)), packet_string\n",
    "    else:\n",
    "        (flag, packets), packet_string = parse_operator_packets(packet_string)\n",
    "        return (int(type_, 2), int(version, 2), int(flag), packets), packet_string\n",
    "\n",
    "def parse_value(packet_string):\n",
    "    parsed = \"\"\n",
    "    while packet_string[0] == \"1\":\n",
    "        group, packet_string = parse_group(packet_string[1:])\n",
    "        parsed += group\n",
    "    expect(packet_string[0], \"0\")\n",
    "    group, packet_string = parse_group(packet_string[1:])\n",
    "    return parsed + group, packet_string\n",
    "\n",
    "def parse_operator_packets(packet_string):\n",
    "    flag, packet_string = parse_D(packet_string)\n",
    "    if flag == \"0\":\n",
    "        length, packet_string = parse_bit_length(packet_string)\n",
    "        bit_length = int(length, 2)\n",
    "        to_parse = packet_string[:bit_length]  # Part of the string to be parsed.\n",
    "        packets = []\n",
    "        while to_parse:\n",
    "            packet, to_parse = parse_packet(to_parse)\n",
    "            packets.append(packet)\n",
    "        packet_string = packet_string[bit_length:]\n",
    "    elif flag == \"1\":\n",
    "        length, packet_string = parse_packet_length(packet_string)\n",
    "        packet_number = int(length, 2)\n",
    "        packets = []\n",
    "        for _ in range(packet_number):\n",
    "            packet, packet_string = parse_packet(packet_string)\n",
    "            packets.append(packet)\n",
    "    return (flag, packets), packet_string\n",
    "\n",
    "### === Basic parsers === ###\n",
    "def parse_Dn(n, packet_string):\n",
    "    parsed = \"\"\n",
    "    for _ in range(n):\n",
    "        D, packet_string = parse_D(packet_string)\n",
    "        parsed += D\n",
    "    return parsed, packet_string\n",
    "\n",
    "def parse_D(packet_string):\n",
    "    expect(packet_string[0], \"01\")\n",
    "    return packet_string[0], packet_string[1:]\n",
    "\n",
    "### --- helper function --- ###\n",
    "def expect(D, values):\n",
    "    if D not in values:\n",
    "        raise ValueError(f\"Expected one of {values}.\")\n",
    "\n",
    "def sum_versions(packet):\n",
    "    sub = 0 if len(packet) == 3 else sum(sum_versions(sub) for sub in packet[3])\n",
    "    return packet[0] + sub\n",
    "\n",
    "parse_group = partial(parse_Dn, 4)\n",
    "parse_bit_length = partial(parse_Dn, 15)\n",
    "parse_packet_length = partial(parse_Dn, 11)\n",
    "parse_type = partial(parse_Dn, 3)\n",
    "parse_version = partial(parse_Dn, 3)\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    hexadecimal_string = \"\".join(f.read().strip().splitlines())\n",
    "\n",
    "transmission, _ = parse(hexadecimal_string)\n",
    "#transmission, _ = parse(\"A0016C880162017C3686B18A3D4780\")\n",
    "\n",
    "print(sum_versions(transmission))\n",
    "\n",
    "eval_dict = {\n",
    "    0: sum,\n",
    "    1: prod,\n",
    "    2: min,\n",
    "    3: max,\n",
    "    5: lambda packets: packets[0] > packets[1],\n",
    "    6: lambda packets: packets[0] < packets[1],\n",
    "    7: lambda packets: packets[0] == packets[1],\n",
    "}\n",
    "\n",
    "def evaluate(packet):\n",
    "    if len(packet) == 3:\n",
    "        return packet[2]\n",
    "\n",
    "    subs = [evaluate(sub) for sub in packet[3]]\n",
    "    return eval_dict[packet[1]](subs)\n",
    "\n",
    "print(evaluate(transmission))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd6b5409",
   "metadata": {},
   "source": [
    "# Day 17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "47cb82a4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4186\n",
      "2709\n"
     ]
    }
   ],
   "source": [
    "from itertools import count\n",
    "from math import ceil, floor\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day17.txt\")\n",
    "\n",
    "def xpos(v0, steps):\n",
    "    delta = min(steps, v0)\n",
    "    return delta * v0 - delta * (delta - 1) // 2\n",
    "\n",
    "def ypos(v0, steps):\n",
    "    return steps * v0 - steps * (steps - 1) // 2\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    xdata, ydata = f.readline().strip().removeprefix(\"target area: \").split(\", \")\n",
    "\n",
    "x_min, x_max = map(int, xdata.removeprefix(\"x=\").split(\"..\"))\n",
    "y_min, y_max = map(int, ydata.removeprefix(\"y=\").split(\"..\"))\n",
    "\n",
    "highest = float(\"-inf\")\n",
    "# Iterate over possible values of vx (velocity along the x axis).\n",
    "count = 0\n",
    "for vx in range(x_max, 0, -1):\n",
    "    for vy in range(min(y_min, 0), 1 + max(abs(y_max), abs(y_min))):\n",
    "        positions = []\n",
    "        on_target = False\n",
    "        while (not positions) or (positions[-1][1] <= x_max and positions[-1][0] >= y_min):\n",
    "            x, y = xpos(vx, len(positions)), ypos(vy, len(positions))\n",
    "            on_target = on_target or x_min <= x <= x_max and y_min <= y <= y_max\n",
    "            positions.append((y, x))\n",
    "        if on_target:\n",
    "            highest = max(highest, max(positions)[0])\n",
    "        count += on_target\n",
    "\n",
    "print(highest)\n",
    "print(count)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "16d49b28",
   "metadata": {},
   "source": [
    "# Day 18"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "59f5d242",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3806\n",
      "4727\n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "from itertools import product\n",
    "from math import ceil, floor\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day18.txt\")\n",
    "\n",
    "def snail_read(snail):\n",
    "    \"\"\"Reads a snail that is assumed to only have 1-digit values.\"\"\"\n",
    "    values, depths, depth = [], [], 0\n",
    "    for char in snail:\n",
    "        if char == \"[\":\n",
    "            depth += 1\n",
    "        elif char == \"]\":\n",
    "            depth -= 1\n",
    "        elif char == \",\":\n",
    "            depths.append(depth)\n",
    "        elif char in \"0123456789\":\n",
    "            values.append(int(char))\n",
    "    return values, depths\n",
    "\n",
    "def snail_print(snail):\n",
    "    \"\"\"Takes a snail and returns its string representation.\"\"\"\n",
    "    values, depths = snail\n",
    "    result, prev_depth = \"\", 0\n",
    "    for idx, depth in enumerate(depths):\n",
    "        if depth > prev_depth:\n",
    "            result += \"[\" * (depth - prev_depth) + str(values[idx]) + \",\"\n",
    "        else:\n",
    "            result += str(values[idx]) + \"]\" * (prev_depth - depth) + \",\"\n",
    "        prev_depth = depth\n",
    "    result += str(values[-1]) + \"]\" * prev_depth\n",
    "    return result\n",
    "\n",
    "def snail_add(left, right):\n",
    "    \"\"\"Adds two snails and returns the result in reduced form.\"\"\"\n",
    "    (lvals, ldepths), (rvals, rdepths) = left, right\n",
    "    snail = (lvals + rvals, [1 + d for d in ldepths] + [1] + [1 + d for d in rdepths])\n",
    "    while True:\n",
    "        snail, flag = snail_explode(snail)\n",
    "        if flag:\n",
    "            continue\n",
    "        snail, flag = snail_split(snail)\n",
    "        if not flag:\n",
    "            break\n",
    "    return snail\n",
    "\n",
    "def snail_explode(snail):\n",
    "    values, depths = snail\n",
    "    try:\n",
    "        idx = depths.index(5)\n",
    "    except ValueError:\n",
    "        return snail, False\n",
    "\n",
    "    new_values = values[::]\n",
    "    if idx > 0:\n",
    "        new_values[idx - 1] += values[idx]\n",
    "    if idx + 2 < len(new_values):\n",
    "        new_values[idx + 2] += values[idx + 1]\n",
    "    new_values = new_values[:idx] + [0] + new_values[idx + 2:]\n",
    "    depths = depths[:idx] + depths[idx + 1:]\n",
    "    return (new_values, depths), True\n",
    "\n",
    "def snail_split(snail):\n",
    "    values, depths = snail\n",
    "    if all((witness := val) < 10 for val in values):\n",
    "        return snail, False\n",
    "\n",
    "    idx = values.index(witness)\n",
    "    new_depth = 1 + max(\n",
    "        depths[idx - 1] if idx > 0 else 0,\n",
    "        depths[idx] if idx < len(depths) else 0,\n",
    "    )\n",
    "    values = values[:idx] + [floor(witness / 2), ceil(witness / 2)] + values[idx + 1:]\n",
    "    depths = depths[:idx] + [new_depth] + depths[idx:]\n",
    "    return (values, depths), True\n",
    "\n",
    "def snail_magnitude(snail):\n",
    "    def combine(stack):\n",
    "        stack.append(2 * stack.pop() + 3 * stack.pop())\n",
    "\n",
    "    values, depths = snail\n",
    "    prev_depth, sub_magnitudes = 0, []\n",
    "    for val, dep in zip(values, depths):\n",
    "        sub_magnitudes.append(val)\n",
    "        for _ in range(prev_depth - dep):\n",
    "            combine(sub_magnitudes)\n",
    "        prev_depth = dep\n",
    "    sub_magnitudes.append(values[-1])\n",
    "    for _ in range(prev_depth):\n",
    "        combine(sub_magnitudes)\n",
    "    return sub_magnitudes[0]\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    snails = [snail_read(line.strip()) for line in f]\n",
    "\n",
    "print(\n",
    "    snail_magnitude(reduce(snail_add, snails))\n",
    ")\n",
    "print(max(\n",
    "    snail_magnitude(snail_add(left, right)) for left, right in product(snails, repeat=2) if left != right\n",
    "))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dae959c4",
   "metadata": {},
   "source": [
    "# Day 19"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "80a34a52",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24 ->  0\n",
      "16 ->  0\n",
      " 5 ->  0\n",
      "18 ->  0\n",
      " 2 ->  0\n",
      "13 ->  0\n",
      " 3 ->  0\n",
      "12 ->  0\n",
      " 8 ->  0\n",
      " 9 ->  0\n",
      "14 ->  0\n",
      "15 ->  0\n",
      "17 ->  0\n",
      "10 ->  0\n",
      " 1 ->  0\n",
      " 6 ->  0\n",
      "11 ->  0\n",
      " 7 ->  0\n",
      "19 ->  0\n",
      "20 ->  0\n",
      "21 ->  0\n",
      " 4 ->  0\n",
      "22 ->  0\n",
      "23 ->  0\n",
      "303\n",
      "9621\n"
     ]
    }
   ],
   "source": [
    "# https://www.reddit.com/r/adventofcode/comments/rjwhdv/2021_day19_i_need_help_understanding_how_to_solve/\n",
    "\n",
    "# To read later:\n",
    "#  - https://www.reddit.com/r/adventofcode/comments/rjpf7f/comment/hp87fkd/?utm_source=share&utm_medium=web2x&context=3\n",
    "#  - https://www.reddit.com/r/adventofcode/comments/rjpf7f/comment/hp86e4k/?utm_source=share&utm_medium=web2x&context=3\n",
    "#  - https://www.reddit.com/r/adventofcode/comments/rjpf7f/comment/hp8599l/?utm_source=share&utm_medium=web2x&context=3\n",
    "\n",
    "from functools import cache\n",
    "from itertools import product\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day19.txt\")\n",
    "MIN_MATCH = 12\n",
    "ROTATIONS = [  # There has to be a nice way of building this decently.\n",
    "    # facing positive x\n",
    "    (1, 2, 3),\n",
    "    (1, -3, 2),\n",
    "    (1, -2, -3),\n",
    "    (1, 3, -2),\n",
    "    # facing negative x\n",
    "    (-1, -2, 3),\n",
    "    (-1, 3, 2),\n",
    "    (-1, 2, -3),\n",
    "    (-1, -3, -2),\n",
    "    # facing positive y\n",
    "    (2, 3, 1),\n",
    "    (2, -1, 3),\n",
    "    (2, -3, -1),\n",
    "    (2, 1, -3),\n",
    "    # facing negative y\n",
    "    (-2, -3, 1),\n",
    "    (-2, 1, 3),\n",
    "    (-2, 3, -1),\n",
    "    (-2, -1, -3),\n",
    "    # facing positive z\n",
    "    (3, 1, 2),\n",
    "    (3, -2, 1),\n",
    "    (3, -1, -2),\n",
    "    (3, 2, -1),\n",
    "    # facing negative z\n",
    "    (-3, -1, 2),\n",
    "    (-3, 2, 1),\n",
    "    (-3, 1, -2),\n",
    "    (-3, -2, -1),\n",
    "]\n",
    "\n",
    "def sign(x):\n",
    "    return (x > 0) - (x < 0)\n",
    "\n",
    "class Point:\n",
    "    \"\"\"Class to represent 2D or 3D points.\"\"\"\n",
    "    def __init__(self, x, y, z=0):\n",
    "        self.x, self.y, self.z = x, y, z\n",
    "\n",
    "    @classmethod\n",
    "    def fromstring(cls, string):\n",
    "        \"\"\"Create a point from a comma-separated string.\"\"\"\n",
    "        return cls(*map(int, string.strip().split(\",\")))\n",
    "\n",
    "    def __add__(self, other):\n",
    "        \"\"\"Adds a point to another point or to a scalar number.\"\"\"\n",
    "        if isinstance(other, Point):\n",
    "            return Point(self.x + other.x, self.y + other.y, self.z + other.z)\n",
    "        else:\n",
    "            return Point(self.x + other, self.y + other, self.z + other)\n",
    "\n",
    "    def __sub__(self, other):\n",
    "        \"\"\"Subtracts a point from another point or scalar number.\"\"\"\n",
    "        return self + (-other)\n",
    "\n",
    "    def __mul__(self, other):\n",
    "        \"\"\"Multiplies a point with a number.\"\"\"\n",
    "        return Point(self.x * other, self.y * other, self.z * other)\n",
    "\n",
    "    def __rmul__(self, other):\n",
    "        return self * other\n",
    "\n",
    "    def __neg__(self):\n",
    "        \"\"\"Negates a point.\"\"\"\n",
    "        return Point(-self.x, -self.y, -self.z)\n",
    "\n",
    "    def __abs__(self):\n",
    "        \"\"\"Returns the sum of the absolute values of the coordinates.\"\"\"\n",
    "        return abs(self.x) + abs(self.y) + abs(self.z)\n",
    "\n",
    "    def __eq__(self, other):\n",
    "        \"\"\"Checks if a point is equal to another point.\"\"\"\n",
    "        return isinstance(other, Point) and (\n",
    "            self.x == other.x and\n",
    "            self.y == other.y and\n",
    "            self.z == other.z\n",
    "        )\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"<{self.x}, {self.y}, {self.z}>\"\n",
    "\n",
    "    def __hash__(self):\n",
    "        \"\"\"Gives a unique hash to each point to allow points to be contained in sets.\"\"\"\n",
    "        return hash((self.x, self.y, self.z))\n",
    "\n",
    "    def __iter__(self):\n",
    "        return iter((self.x, self.y, self.z))\n",
    "\n",
    "    def rotate(self, rot):\n",
    "        coords = [None, self.x, self.y, self.z]\n",
    "        return Point(*[sign(c) * coords[abs(c)] for c in rot])\n",
    "\n",
    "\n",
    "def to_edges(beacons):\n",
    "    \"\"\"Turns a list of beacons into a list of lists of edges.\"\"\"\n",
    "    return [\n",
    "        [y - x for y in beacons]\n",
    "        for x in beacons\n",
    "    ]\n",
    "\n",
    "\n",
    "def orientations(edges):\n",
    "    \"\"\"Yield the 24 possible rotations of the list of edges.\"\"\"\n",
    "    for rot in ROTATIONS:\n",
    "        yield [edge.rotate(rot) for edge in edges]\n",
    "\n",
    "'''\n",
    "def match(reference, others, threshold):\n",
    "    \"\"\"Check if the two structures match geometrically.\n",
    "    \n",
    "    `reference` is a list of edges, and `others` is a list of lists of edges,\n",
    "    seen from the perspective of each point.\n",
    "    A match is defined by an overlap of `threshold` or more points,\n",
    "    which means `threshold - 1` or more edges.\n",
    "    \"\"\"\n",
    "\n",
    "    for idx, oth in enumerate(others):\n",
    "        if len(set(reference) & set(oth)) >= threshold - 1:\n",
    "            return idx\n",
    "    return None\n",
    "'''\n",
    "\n",
    "\n",
    "def match(references, others, threshold):\n",
    "    \"\"\"Check if the two structures match geometrically.\n",
    "\n",
    "    `references` is a list of lists of edges and `others` is a list of lists of edges.\n",
    "    A match is defined by an overlap of `threshold` or more points,\n",
    "    which means `threshold - 1` or more edges.\n",
    "    \"\"\"\n",
    "\n",
    "    it = product(enumerate(references[:-(threshold - 1)]), enumerate(others))\n",
    "    for (r_idx, ref), (o_idx, oth) in it:\n",
    "        if len(set(ref) & set(oth)) >= threshold - 1:\n",
    "            return True, r_idx, o_idx\n",
    "    return False, None, None\n",
    "\n",
    "\n",
    "def transform(reference, others, threshold):\n",
    "    \"\"\"Given two lists of points in 3D, try to transform `others`\n",
    "    into the same coordinate system as `reference`.\n",
    "    \"\"\"\n",
    "\n",
    "    ref_edges = to_edges(reference)\n",
    "    # Try all possible orientations of the other points.\n",
    "    for orientation in orientations(others):\n",
    "        other_edges = to_edges(orientation)\n",
    "        flag, r_idx, o_idx = match(ref_edges, other_edges, threshold)\n",
    "        if not flag:\n",
    "            continue\n",
    "        # If flag is `True`, then reference[r_idx] and orientation[o_idx] match.\n",
    "        vec = reference[r_idx] - orientation[o_idx]\n",
    "        return True, reference, [other + vec for other in orientation], vec\n",
    "    return False, reference, others, None\n",
    "\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    scanners = [\n",
    "        tuple(map(Point.fromstring, scanner.splitlines()[1:]))\n",
    "        for scanner in f.read().split(\"\\n\\n\")\n",
    "    ]\n",
    "\n",
    "scanner_positions = [Point(0, 0, 0) for _ in scanners]\n",
    "to_do = set(range(len(scanners)))\n",
    "no_changes = False\n",
    "while len(to_do) > 1 and not no_changes:\n",
    "    no_changes = True\n",
    "    for ref, oth in product(to_do, to_do):\n",
    "        if ref == oth or len(scanners[ref]) > len(scanners[ref]):\n",
    "            continue\n",
    "        flag, ref_points, oth_points, vec = transform(scanners[ref], scanners[oth], MIN_MATCH)\n",
    "        if flag:\n",
    "            print(f\"{oth:2} -> {ref:2}\")\n",
    "            to_do.remove(oth)\n",
    "            scanners[ref] = tuple(set(ref_points) | set(oth_points))\n",
    "            scanner_positions[oth] -= vec\n",
    "            no_changes = False\n",
    "            break\n",
    "\n",
    "\n",
    "assert not no_changes, \"The algo. failed.\"\n",
    "final = to_do.pop()\n",
    "print(len(scanners[final]))\n",
    "print(max(\n",
    "    abs(x - y) for x, y in product(scanner_positions, repeat=2)\n",
    "))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82142359",
   "metadata": {},
   "source": [
    "# Day 20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "88ab2c0d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18131"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from functools import reduce\n",
    "from itertools import product\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day20.txt\")\n",
    "\n",
    "\n",
    "def get_next(image, pos, algorithm, padding):\n",
    "    x, y = pos\n",
    "    binary = \"\".join(\n",
    "        image.get((x + dx, y + dy), padding)\n",
    "        for dy, dx in product((-1, 0, 1), repeat=2)\n",
    "    )\n",
    "    return algorithm[int(binary, 2)]\n",
    "\n",
    "\n",
    "def enhance(algorithm, image, bounds, padding):\n",
    "    (x_min, x_max), (y_min, y_max) = bounds\n",
    "    img = {}\n",
    "    for pos in product(range(x_min - 1, x_max + 2), range(y_min - 1, y_max + 2)):\n",
    "        img[pos] = get_next(image, pos, algorithm, padding)\n",
    "\n",
    "    new_bounds = ((x_min - 1, x_max + 1), (y_min - 1, y_max +1))\n",
    "    new_padding = algorithm[0] if padding == \"0\" else algorithm[-1]\n",
    "    return img, new_bounds, new_padding\n",
    "\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    algo = [\"1\" if val == \"#\" else \"0\" for val in f.readline().strip()]\n",
    "    f.readline()\n",
    "    image = {\n",
    "        (x, y): \"1\" if val == \"#\" else \"0\"\n",
    "        for y, line in enumerate(f) for x, val in enumerate(line.strip())\n",
    "    }\n",
    "\n",
    "max_x, max_y = max(image.keys())\n",
    "bounds = ((0, max_x), (0, max_y))\n",
    "padding = \"0\"\n",
    "\n",
    "# for _ in range(2):\n",
    "for _ in range(50):\n",
    "    image, bounds, padding = enhance(algo, image, bounds, padding)\n",
    "sum(val == \"1\" for val in image.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "24b09aaf",
   "metadata": {},
   "source": [
    "# Day 21"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "4d2e25b0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "576600\n"
     ]
    }
   ],
   "source": [
    "from itertools import cycle, islice\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day21.txt\")\n",
    "ROLLS = 3\n",
    "SIDES = 100\n",
    "\n",
    "die = cycle(range(1, SIDES + 1))\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    players_start = [int(line.strip().split()[-1]) for line in f]\n",
    "\n",
    "seed = list(range(1, 11))\n",
    "positions = [cycle(seed[p:] + seed[:p]) for p in players_start]\n",
    "scores = [0] * len(positions)\n",
    "\n",
    "p, n = 0, len(positions)\n",
    "while max(scores) < 1000:\n",
    "    positions[p % n] = islice(positions[p % n], sum(islice(die, ROLLS)) - 1, None)\n",
    "    scores[p % n] += next(positions[p % n])\n",
    "    p += 1\n",
    "print(p * ROLLS * min(scores))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "id": "a680bc83",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from functools import cache\n",
    "from itertools import product\n",
    "\n",
    "advances = Counter(sum(perm) for perm in product(range(1, 4), repeat=3))\n",
    "\n",
    "@cache\n",
    "def play(pos, scores, player):\n",
    "    # print(f\"Playing {pos = }, {scores = }, {player = }.\")\n",
    "    pos, scores = list(pos), list(scores)\n",
    "    if max(scores) >= 21:\n",
    "        return [int(sc >= 21) for sc in scores]\n",
    "\n",
    "    outcomes = [0] * len(pos)\n",
    "    for roll, count in advances.items():\n",
    "        pos_, scores_ = pos[::], scores[::]\n",
    "        pos_[player] = (pos_[player] - 1 + roll) % 10 + 1\n",
    "        scores_[player] += pos_[player]\n",
    "        outcomes = [\n",
    "            out + count * win\n",
    "            for out, win in zip(outcomes, play(tuple(pos_), tuple(scores_), 1 - player))\n",
    "        ]\n",
    "    return outcomes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "id": "9087fec6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "131888061854776"
      ]
     },
     "execution_count": 138,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max(play(tuple(players_start), (0, 0), 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a813913c",
   "metadata": {},
   "source": [
    "# Day 22\n",
    "\n",
    "## Part 1 (brute-force)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "aa1ecaf4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "568000\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "from itertools import product\n",
    "from pathlib import Path\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day22.txt\")\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    steps = [line.strip() for line in f.readlines()[:20]]\n",
    "rects = [\n",
    "    [tuple(map(int, bit.split(\"=\")[1].split(\"..\"))) for bit in coords.split(\",\")]\n",
    "    for coords in steps\n",
    "]\n",
    "\n",
    "reactor = defaultdict(int)\n",
    "for step in steps:\n",
    "    target, coords = step.split()\n",
    "    target = target == \"on\"\n",
    "    xr, yr, zr = [tuple(map(int, bit.split(\"=\")[1].split(\"..\"))) for bit in coords.split(\",\")]\n",
    "    for coords in product(range(xr[0], xr[1] + 1), range(yr[0], yr[1] + 1), range(zr[0], zr[1] + 1)):\n",
    "        reactor[coords] = target\n",
    "print(sum(reactor.values()))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5d2f527e",
   "metadata": {},
   "source": [
    "## Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "id": "47ed350b",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product, starmap\n",
    "from math import prod\n",
    "from queue import SimpleQueue\n",
    "\n",
    "def split_interval(reference, other):\n",
    "    \"\"\"Splits the other interval in pieces in or out of the reference interval.\"\"\"\n",
    "\n",
    "    (ref_a, ref_b), (other_a, other_b) = reference, other\n",
    "    if other_b < ref_a or ref_b < other_a or ref_a <= other_a <= other_b <= ref_b:\n",
    "        intervals = [other]\n",
    "    elif other_a <= ref_a <= other_b <= ref_b:\n",
    "        intervals = [(other_a, ref_a - 1), (ref_a, other_b)]\n",
    "    elif ref_a <= other_a <= ref_b <= other_b:\n",
    "        intervals = [(other_a, ref_b), (ref_b + 1, other_b)]\n",
    "    elif other_a <= ref_a <= ref_b <= other_b:\n",
    "        intervals = [\n",
    "            (other_a, ref_a - 1),\n",
    "            (ref_a, ref_b),\n",
    "            (ref_b + 1, other_b),\n",
    "        ]\n",
    "    return [(a, b) for a, b in intervals if b >= a]\n",
    "\n",
    "def split(reference, other):\n",
    "    \"\"\"Splits the other hypercube in pieces in or out of the reference hypercube.\"\"\"\n",
    "\n",
    "    to_handle = SimpleQueue()\n",
    "    to_handle.put((tuple(), reference, other))\n",
    "    final = []\n",
    "\n",
    "    if any(\n",
    "        oth_a > ref_b or ref_a > oth_b\n",
    "        for (ref_a, ref_b), (oth_a, oth_b) in zip(reference, other)\n",
    "    ):\n",
    "        return [other]\n",
    "\n",
    "    return list(product(*starmap(split_interval, zip(reference, other))))\n",
    "\n",
    "def inside(reference, other):\n",
    "    \"\"\"Determine whether or not the other hypercube is contained inside the reference.\n",
    "\n",
    "    Assumes that `other` is either completely contained in, or completely outside of,\n",
    "    the `reference` hypercube.\n",
    "    \"\"\"\n",
    "\n",
    "    vertices = product(*other)\n",
    "    return any(\n",
    "        all(a <= coord <= b for (a, b), coord in zip(reference, vertex))\n",
    "        for vertex in vertices\n",
    "    )\n",
    "\n",
    "def volume(hypercube):\n",
    "    return prod(b - a + 1 for a, b in hypercube)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "id": "cb0bef9f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1177411289280259\n",
      "Finished in 7.44 minutes.\n"
     ]
    }
   ],
   "source": [
    "from itertools import product\n",
    "from pathlib import Path\n",
    "from time import time\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day22.txt\")\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    steps = [line.strip() for line in f.readlines()]\n",
    "\n",
    "rects = [\n",
    "    tuple([tuple(map(int, bit.split(\"=\")[1].split(\"..\"))) for bit in coords.split(\",\")])\n",
    "    for coords in steps\n",
    "]\n",
    "instructions = [step.split()[0] for step in steps]\n",
    "\n",
    "start = time()\n",
    "\n",
    "# `on` is a list of fully disjoint regions where the lights are on.\n",
    "on = set()\n",
    "for rect, instruction in zip(rects, instructions):\n",
    "    if instruction == \"on\":\n",
    "        # Figure out what parts of the region we are handling haven't\n",
    "        # been turned ON yet.\n",
    "        pieces = {rect}\n",
    "        for on_region in on:\n",
    "            pieces = {\n",
    "                p\n",
    "                for piece in pieces for p in split(on_region, piece)\n",
    "                if not inside(on_region, p)\n",
    "            }\n",
    "        on |= pieces\n",
    "    elif instruction == \"off\":\n",
    "        # Figure out what parts of the ON regions are inside the region\n",
    "        # we are handling right now, and drop those.\n",
    "        new_on = set()\n",
    "        for on_region in on:\n",
    "            new_on.update(\n",
    "                piece for piece in split(rect, on_region)\n",
    "                if not inside(rect, piece)\n",
    "            )\n",
    "        on = new_on\n",
    "\n",
    "print(sum(volume(region) for region in on))\n",
    "print(f\"Finished in {(time() - start) / 60:.2f} minutes.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5800254c",
   "metadata": {},
   "source": [
    "# Day 23"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "d2cadb88",
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Let's represent the game as a tuple of pairs.\n",
    "The first element of the pair has the coordinates and the second element has the amphipod (or None).\n",
    "The tuple consists of these pairs, ordered.\n",
    "Therefore, it is easy to check when two game positions match.\n",
    "\n",
    "For example, the game\n",
    "\n",
    "#############\n",
    "#...........#\n",
    "###B#C#B#D###\n",
    "  #A#D#C#A#\n",
    "  #########\n",
    "\n",
    "could be represented as follows:\n",
    "\"\"\"\n",
    "\n",
    "EMPTY = _ = \"X\"\n",
    "game = (\n",
    "    ((0, 0), _), ((0, 1), _), ((0, 3), _), ((0, 5), _), ((0, 7), _), ((0, 9), _), ((0, 10), _),\n",
    "                    ((1, 2), \"B\"), ((1, 4), \"C\"), ((1, 6), \"B\"), ((1, 8), \"D\"),\n",
    "                    ((2, 2), \"A\"), ((2, 4), \"D\"), ((2, 6), \"C\"), ((2, 8), \"A\"),\n",
    ")\n",
    "\n",
    "\"\"\"\n",
    "The first coordinate represents height and the second coordinate represents the horizontal position.\n",
    "\"\"\"\n",
    "\n",
    "from functools import cache\n",
    "from queue import PriorityQueue\n",
    "\n",
    "AMPHS = \"ABCD\"\n",
    "COSTS = {amph: 10 ** AMPHS.index(amph) for amph in AMPHS}\n",
    "CHAMBERS = list(zip(range(2, 9, 2), AMPHS))\n",
    "\n",
    "def movement_cost(from_, to_, amph):\n",
    "    \"\"\"Computes the movement cost of an amphipod between two positions.\"\"\"\n",
    "    ((yf, xf), (yt, xt)) = from_, to_\n",
    "    return COSTS[amph] * (abs(yf - yt) + abs(xf - xt))\n",
    "\n",
    "def is_clear(game, from_, to_):\n",
    "    \"\"\"Checks if an amphipod at `from_` can move freely up to `to_`.\"\"\"\n",
    "    ((yf, xf), (yt, xt)) = from_, to_\n",
    "    return all(\n",
    "        amph == EMPTY for ((y, x), amph) in game\n",
    "        if (  # Only check positions that matter, excluding self.\n",
    "            (y, x) != (yf, xf) and\n",
    "            # Main hallway between from_ and to_:\n",
    "            (min(xf, xt) <= x <= max(xf, xt) and y == 0) or\n",
    "            (x == xf and y < yf) or  # Starting chamber.\n",
    "            (x == xt and y <= yt)  # Finishing chamber.\n",
    "        )\n",
    "    )\n",
    "\n",
    "def move(game, from_, to_):\n",
    "    \"\"\"Moves the amphipod in the given position into the destination.\n",
    "\n",
    "    Assumes the move is legal.\n",
    "    \"\"\"\n",
    "    game = dict(game)\n",
    "    game[to_] = game[from_]\n",
    "    game[from_] = EMPTY\n",
    "    return tuple(game.items())\n",
    "\n",
    "def next_moves(game):\n",
    "    \"\"\"Returns a list of pairs with costs and next possible moves.\"\"\"\n",
    "\n",
    "    game_dict, moves = dict(game), []\n",
    "    free_hallway = [pos for pos, amph in game_dict.items() if pos[0] == 0 and amph == EMPTY]\n",
    "    #print(f\"{free_hallway = }\")\n",
    "    from_chamber = [\n",
    "        (amph, (y, x))\n",
    "        for (y, x), amph in game_dict.items()\n",
    "        if (\n",
    "            amph != EMPTY and (\n",
    "                (x, amph) not in CHAMBERS or\n",
    "                any(x == x_ and y < y_ and (x, amph_) not in CHAMBERS for (y_, x_), amph_ in game_dict.items())\n",
    "            )\n",
    "        )\n",
    "    ]\n",
    "    #print(f\"{want_rellocation = }\")\n",
    "    # What amphipods are in the hallway?\n",
    "    from_hallway = [(amph, (y, x)) for (y, x), amph in game_dict.items() if y == 0 and amph != EMPTY]\n",
    "\n",
    "    # What chambers are looking to receive amphipods?\n",
    "    # Only those that are not full and that contain, at most, one correct amphipod.\n",
    "    accepting_chambers = []\n",
    "    for chamber_x, correct_amph in CHAMBERS:\n",
    "        chamb_slots = [((y, x), amph) for (y, x), amph in game_dict.items() if x == chamber_x]\n",
    "        # Go over the slots, start from the bottom.\n",
    "        for (y, x), amph in reversed(chamb_slots):\n",
    "            if amph == EMPTY:\n",
    "                accepting_chambers.append(((y, x), correct_amph))\n",
    "            elif amph != correct_amph:\n",
    "                break\n",
    "    #print(f\"{accepting_chambers = }\")\n",
    "\n",
    "    # Try to move amphipods into their correct positions.\n",
    "    for to_, correct_amph in accepting_chambers:\n",
    "        # For each occupied position, check if that amphipod can go to its chamber.\n",
    "        for amph, from_ in from_hallway:\n",
    "            # print(f\"\\t{from_ = } {to_ = }\")\n",
    "            if amph != correct_amph or not is_clear(game, from_, to_):\n",
    "                continue\n",
    "            moves.append((movement_cost(from_, to_, amph), from_, to_))\n",
    "    #print(f\"And valid moves, up to now: {moves = }\")\n",
    "\n",
    "    for to_ in free_hallway:\n",
    "        for amph, from_ in from_chamber:\n",
    "            # To move into the hallway, an amphipod can't be in the hallway already.\n",
    "            if from_[0] != 0 and is_clear(game, from_, to_):\n",
    "                moves.append((movement_cost(from_, to_, amph), from_, to_))\n",
    "    #print(f\"final valid moves are {moves = }\")\n",
    "\n",
    "    return sorted(moves)\n",
    "\n",
    "def is_solved(game):\n",
    "    return all(\n",
    "        (y == 0 and amph == EMPTY) or (x, amph) in CHAMBERS\n",
    "        for (y, x), amph in game\n",
    "    )\n",
    "\n",
    "def solve(game):\n",
    "    \"\"\"Find the cheapest way to solve the amphipod puzzle.\"\"\"\n",
    "\n",
    "    visited = set()\n",
    "    queue = PriorityQueue()\n",
    "    queue.put((0, game))\n",
    "    while not queue.empty():\n",
    "        cost, game_ = queue.get()\n",
    "        #print(f\"{cost = }\", end=\", \")\n",
    "        if game_ in visited:\n",
    "            continue\n",
    "        else:\n",
    "            visited.add(game_)\n",
    "        if is_solved(game_):\n",
    "            return cost\n",
    "\n",
    "        moves = next_moves(game_)\n",
    "        for step, from_, to_ in next_moves(game_):\n",
    "            next_game = move(game_, from_, to_)\n",
    "            queue.put((cost + step, next_game))\n",
    "\n",
    "    raise RuntimeError(f\"Couldn't solve {game}.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "00658185",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12521"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve(game)  # test case, should give 12521"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "5d0c933e",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10607\n",
      "Took 0.8655635992685954 minutes.\n",
      "59071\n",
      "Took 1.431675410270691 minutes.\n"
     ]
    }
   ],
   "source": [
    "from pathlib import Path\n",
    "from time import time\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day23.txt\")\n",
    "\n",
    "EMPTY = \".\"\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    data = [line[1:-1] for line in f.read().splitlines()[2:-1]]\n",
    "\n",
    "game = (\n",
    "    tuple(((0, x), EMPTY) for x in [0, 1, 3, 5, 7, 9, 10]) +\n",
    "    tuple(sorted([((1 + y, x), amph) for y, line in enumerate(data) for x, amph in enumerate(line) if amph in AMPHS + EMPTY]))\n",
    ")\n",
    "\n",
    "start = time()\n",
    "print(solve(game))\n",
    "print(f\"Took {(time() - start) / 60} minutes.\")\n",
    "\n",
    "data = (\n",
    "    [data[0]] +\n",
    "    [\" #D#C#B#A#\", \" #D#B#A#C#\"] +\n",
    "    [data[1]]\n",
    ")\n",
    "game = (\n",
    "    tuple(((0, x), EMPTY) for x in [0, 1, 3, 5, 7, 9, 10]) +\n",
    "    tuple(sorted([((1 + y, x), amph) for y, line in enumerate(data) for x, amph in enumerate(line) if amph in AMPHS + EMPTY]))\n",
    ")\n",
    "start = time()\n",
    "print(solve(game))\n",
    "print(f\"Took {(time() - start) / 60} minutes.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "22f2d4d7",
   "metadata": {},
   "source": [
    "# Day 24\n",
    "\n",
    "***Solved by hand!***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "347b2e80",
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m     57\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mtuple\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     58\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 59\u001b[1;33m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfound\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfound\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfound\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfound\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfound\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfound\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfound\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfound\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfound\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfound\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfound\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfound\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     38\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 39\u001b[1;33m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     41\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfound\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp/ipykernel_16856/2304215234.py\u001b[0m in \u001b[0;36msolve\u001b[1;34m(sections, mem)\u001b[0m\n\u001b[0;32m     36\u001b[0m     \u001b[1;32mfor\u001b[0m \u001b[0mdigit\u001b[0m \u001b[1;32min\u001b[0m \u001b[1;34m\"987654321\"\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     37\u001b[0m         \u001b[0mres\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0malu\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msection\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mdigit\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mmem\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 38\u001b[1;33m         \u001b[1;32mif\u001b[0m \u001b[0msections\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     39\u001b[0m             \u001b[0mflag\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mfound\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msolve\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0msections\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mres\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     40\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mflag\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "from functools import cache\n",
    "from itertools import product\n",
    "from pathlib import Path\n",
    "from time import time\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day24.txt\")\n",
    "\n",
    "@cache\n",
    "def alu(program, inp, mem=None):\n",
    "    mem = {\"x\": 0, \"y\": 0, \"z\": 0, \"w\": 0} if mem is None else dict(zip(\"xyzw\", mem))\n",
    "    for command in program:\n",
    "        match command.split():\n",
    "            case [\"inp\", x]:\n",
    "                mem[x] = int(inp[0])\n",
    "                inp = inp[1:]\n",
    "            case [\"add\", x, y]:\n",
    "                rhs = mem[y] if y.isalpha() else int(y)\n",
    "                mem[x] += rhs\n",
    "            case [\"mul\", x, y]:\n",
    "                rhs = mem[y] if y.isalpha() else int(y)\n",
    "                mem[x] *= rhs\n",
    "            case [\"div\", x, y]:\n",
    "                rhs = mem[y] if y.isalpha() else int(y)\n",
    "                mem[x] = int(mem[x] / rhs)\n",
    "            case [\"mod\", x, y]:\n",
    "                rhs = mem[y] if y.isalpha() else int(y)\n",
    "                mem[x] %= rhs\n",
    "            case [\"eql\", x, y]:\n",
    "                rhs = mem[y] if y.isalpha() else int(y)\n",
    "                mem[x] = int(mem[x] == rhs)\n",
    "    return tuple(mem.values())\n",
    "\n",
    "def solve(sections, mem=None):\n",
    "    section, *sections = sections\n",
    "    for digit in \"987654321\":\n",
    "        res = alu(section, digit, mem)\n",
    "        if sections:\n",
    "            flag, found = solve(sections, res)\n",
    "            if flag:\n",
    "                return digit + found\n",
    "        else:\n",
    "            if res[2] == 0:\n",
    "                return True, digit\n",
    "    return False, None\n",
    "            \n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    program = f.read().splitlines()\n",
    "\n",
    "sections, section = [], []\n",
    "for line in program:\n",
    "    if line.startswith(\"inp\") and section:\n",
    "        sections.append(tuple(section))\n",
    "        section = []\n",
    "    section.append(line)\n",
    "sections.append(tuple(section))\n",
    "\n",
    "solve(sections)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f09fb400",
   "metadata": {},
   "outputs": [],
   "source": [
    "@cache\n",
    "def step(A, B, C, w, z):\n",
    "    if B == 1:\n",
    "        return z * 26 + w + C if (z % 26 + A) == w else z\n",
    "    elif B == 26:\n",
    "        return int(z / 26) * (26 + w + C if (z % 26 + A) == w else 1)\n",
    "    else:\n",
    "        raise RuntimeError(\"B should be 1 or 26.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad927e76",
   "metadata": {},
   "source": [
    "# Day 25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "5c9c7c6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "_ = '''from itertools import count\n",
    "from pathlib import Path\n",
    "from time import time\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day25.txt\")\n",
    "\n",
    "east_bound, south_bound = set(), set()\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    for y, line in enumerate(f):\n",
    "        for x, val in enumerate(line.strip()):\n",
    "            if val == \"v\":\n",
    "                south_bound.add((x, y))\n",
    "            elif val == \">\":\n",
    "                east_bound.add((x, y))\n",
    "\n",
    "max_x, max_y = x, y\n",
    "cucumbers = east_bound | south_bound\n",
    "sets = [east_bound, south_bound]\n",
    "directions = [((1, 0), (max_x, max_y + 1)), ((0, 1), (max_x + 1, max_y))]\n",
    "moved = float(\"inf\")\n",
    "for c in count():\n",
    "    \"\"\"\n",
    "    moved = 0\n",
    "    for moving, ((dx, dy), (mx, my)) in zip(cucumbers, directions):\n",
    "        cucs = set()\n",
    "        for x, y in moving:\n",
    "            if (x + dx % mx, y + dy % my) in cucumbers:\n",
    "                cucs.add((x, y))\n",
    "            else:\n",
    "                moved += 1\n",
    "                cucs.add((x + dx % mx, y + dy % my))\n",
    "    \"\"\"\n",
    "    \n",
    "    east_bound_, moved = set(), 0\n",
    "    for (x, y) in east_bound:\n",
    "        if ((x + 1) % max_x, y) not in cucumbers:\n",
    "            east_bound_.add(((x + 1) % max_x, y))\n",
    "            moved += 1\n",
    "        else:\n",
    "            east_bound_.add((x, y))\n",
    "    east_bound = east_bound_\n",
    "    cucumbers = east_bound | south_bound\n",
    "\n",
    "    south_bound_ = set()\n",
    "    for (x, y) in south_bound:\n",
    "        if (x, (y + 1) % max_y) not in cucumbers:\n",
    "            south_bound_.add((x, (y + 1) % max_y))\n",
    "            moved += 1\n",
    "        else:\n",
    "            south_bound_.add((x, y))\n",
    "    sout_bound = south_bound_\n",
    "    cucumbers = east_bound | south_bound\n",
    "\n",
    "    print(c)\n",
    "    if not moved:\n",
    "        break\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "e5c20415",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "456\n",
      "Done in 2.590 seconds.\n"
     ]
    }
   ],
   "source": [
    "from itertools import count\n",
    "from pathlib import Path\n",
    "from time import time\n",
    "\n",
    "INPUT_PATH = Path(\"aoc2021_inputs/day25.txt\")\n",
    "\n",
    "with open(INPUT_PATH, \"r\") as f:\n",
    "    cucumbers = [list(line.strip()) for line in f]\n",
    "\n",
    "start = time()\n",
    "\n",
    "max_x, max_y = len(cucumbers[0]), len(cucumbers)\n",
    "for c in count(1):\n",
    "    will_go_east, will_go_south = set(), set()\n",
    "    for y, row in enumerate(cucumbers):\n",
    "        for x, val in enumerate(row):\n",
    "            if val == \".\":\n",
    "                continue\n",
    "            elif val == \">\" and row[(x + 1) % max_x] == \".\":\n",
    "                will_go_east.add((x, y))\n",
    "            elif val == \"v\" and (\n",
    "                (cucumbers[(y + 1) % max_y][x] == \".\" and cucumbers[(y + 1) % max_y][(x - 1) % max_x] != \">\") or\n",
    "                (cucumbers[(y + 1) % max_y][x] == \">\" and cucumbers[(y + 1) % max_y][(x + 1) % max_x] == \".\")\n",
    "            ):\n",
    "                will_go_south.add((x, y))\n",
    "\n",
    "    if not len(will_go_east) + len(will_go_south):\n",
    "        print(c)\n",
    "        break\n",
    "    for (x, y) in will_go_east:\n",
    "        cucumbers[y][x] = \".\"\n",
    "        cucumbers[y][(x + 1) % max_x] = \">\"\n",
    "    for (x, y) in will_go_south:\n",
    "        cucumbers[y][x] = \".\"\n",
    "        cucumbers[(y + 1) % max_y][x] = \"v\"\n",
    "\n",
    "    # print(\"\\n\".join(\"\".join(row) for row in cucumbers))\n",
    "\n",
    "print(f\"Done in {time() - start:.3f} seconds.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "15a856e3",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.0"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}