benchmarks.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 27,
   "outputs": [],
   "source": [
    "import math\n",
    "import re\n",
    "from dataclasses import dataclass, asdict\n",
    "from itertools import combinations\n",
    "from typing import Tuple, Type, TypeVar\n",
    "from collections import defaultdict, deque\n",
    "from functools import lru_cache\n",
    "from lark import Lark, LarkError\n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Imports\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "outputs": [],
   "source": [
    "searched_sum = 2020"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 01 Setup\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "212 µs ± 9.17 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_01_input.txt\") as input_data:\n",
    "    for i, pair in enumerate(combinations(sorted((int(x) for x in input_data)), 2)):\n",
    "        if sum(pair) == searched_sum:\n",
    "            day_01_p1 = math.prod(pair)\n",
    "            break"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 01 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8.99 ms ± 686 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_01_input.txt\") as input_data:\n",
    "    for i, triple in enumerate(combinations(sorted((int(x) for x in input_data)), 3)):\n",
    "        if sum(triple) == searched_sum:\n",
    "            day_01_p2 = math.prod(triple)\n",
    "            break"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 01 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "outputs": [],
   "source": [
    "parse_expression = re.compile(r\"^(\\d+)-(\\d+)\\s+(\\w):\\s+(.*)$\")\n",
    "\n",
    "def parse_entry(entry: str) -> Tuple:\n",
    "    g = parse_expression.match(entry).groups()\n",
    "    return *map(int, g[:2]), *g[2:]"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 02 Setup\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.24 ms ± 17.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_02_input.txt\") as input_data:\n",
    "    day_02_p1 = sum(f <= p.count(c) <= s for f, s, c, p in map(parse_entry, input_data))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 02 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.16 ms ± 33.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_02_input.txt\") as input_data:\n",
    "    day_02_p2 = sum(\n",
    "        (p[f - 1] == c) != (p[s - 1] == c)\n",
    "        for f, s, c, p in map(parse_entry, input_data)\n",
    "    )"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 02 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "outputs": [],
   "source": [
    "slopes = [(1, 1), (3, 1), (5, 1), (7, 1), (1, 2)]"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 03 Setup\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.34 ms ± 43.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_03_input.txt\") as input_data:\n",
    "    tree_map = np.array(\n",
    "        [np.array([c == \"#\" for c in row.strip()], dtype=bool) for row in input_data]\n",
    "    )\n",
    "height, width = tree_map.shape\n",
    "\n",
    "day_03_p1 = np.sum(tree_map[(np.arange(height), np.arange(0, height * 3, 3) % width)])"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 03 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.44 ms ± 118 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_03_input.txt\") as input_data:\n",
    "    tree_map = np.array(\n",
    "        [np.array([c == \"#\" for c in row.strip()], dtype=bool) for row in input_data]\n",
    "    )\n",
    "height, width = tree_map.shape\n",
    "\n",
    "slope_index_generator = (\n",
    "    (np.arange(0, height, d), np.arange(0, math.ceil(height / d) * r, r) % width)\n",
    "    for r, d in slopes\n",
    ")\n",
    "day_03_p2 = math.prod(np.sum(tree_map[s]) for s in slope_index_generator)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 03 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "outputs": [],
   "source": [
    "# noinspection PyTypeChecker\n",
    "T = TypeVar(\"T\", bound=\"Passport\")\n",
    "\n",
    "@dataclass\n",
    "class Passport:\n",
    "    byr: str = \"\"\n",
    "    iyr: str = \"\"\n",
    "    eyr: str = \"\"\n",
    "    hgt: str = \"\"\n",
    "    hcl: str = \"\"\n",
    "    ecl: str = \"\"\n",
    "    pid: str = \"\"\n",
    "    cid: str = \"\"\n",
    "\n",
    "    @classmethod\n",
    "    def from_string(cls: Type[T], info: str) -> T:\n",
    "        # I guess this an IDE bug as creating a dict from a generator should be valid\n",
    "        # noinspection PyTypeChecker\n",
    "        return Passport(\n",
    "            **dict(p.split(\":\") for p in info.strip().replace(\"\\n\", \" \").split())\n",
    "        )\n",
    "\n",
    "    def is_valid(self, excludes: list[str] = (\"cid\",), strict: bool = False) -> bool:\n",
    "        def check_year_bounds(year: str, min_bound: int, max_bound: int) -> bool:\n",
    "            return year.isdigit() and min_bound <= int(year) <= max_bound\n",
    "\n",
    "        # noinspection PyShadowingNames\n",
    "        def check_height(height: str) -> bool:\n",
    "            match = re.match(r\"^(\\d{2,3})(cm|in)$\", height)\n",
    "            if match:\n",
    "                value, unit = match.groups()\n",
    "                value = int(value)\n",
    "                return 150 <= value <= 193 if unit == \"cm\" else 59 <= value <= 76\n",
    "            return False\n",
    "\n",
    "        complete = all(v != \"\" for k, v in asdict(self).items() if k not in excludes)\n",
    "        if strict:\n",
    "            return (\n",
    "                complete\n",
    "                and check_year_bounds(self.byr, 1920, 2002)\n",
    "                and check_year_bounds(self.iyr, 2010, 2020)\n",
    "                and check_year_bounds(self.eyr, 2020, 2030)\n",
    "                and check_height(self.hgt)\n",
    "                and bool(re.match(r\"^#[0-9a-f]{6}$\", self.hcl))\n",
    "                and self.ecl in [\"amb\", \"blu\", \"brn\", \"gry\", \"grn\", \"hzl\", \"oth\"]\n",
    "                and bool(re.match(r\"^\\d{9}$\", self.pid))\n",
    "            )\n",
    "\n",
    "        return complete"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 04 Setup\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.96 ms ± 127 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_04_input.txt\") as input_data:\n",
    "    passport_infos = input_data.read().strip().split(\"\\n\\n\")\n",
    "\n",
    "day_04_p1 = sum(Passport.from_string(s).is_valid() for s in passport_infos)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 04 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5.92 ms ± 73.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_04_input.txt\") as input_data:\n",
    "    passport_infos = input_data.read().strip().split(\"\\n\\n\")\n",
    "\n",
    "day_04_p2 = sum(Passport.from_string(s).is_valid(strict=True) for s in passport_infos)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 04 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "outputs": [],
   "source": [
    "def seat_id(input_string: str) -> int:\n",
    "    return int(input_string.translate(str.maketrans(\"FLBR\", \"0011\")), 2)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 05 Setup\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "636 µs ± 29.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_05_input.txt\") as input_data:\n",
    "    seat_ids = sorted(map(seat_id, input_data))\n",
    "day_05_p1 = seat_ids[-1]"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 05 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "702 µs ± 29.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_05_input.txt\") as input_data:\n",
    "    seat_ids = sorted(map(seat_id, input_data))\n",
    "day_05_p2 = seat_ids[np.nonzero(np.diff(seat_ids) == 2)[0][0]] + 1"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 05 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "814 µs ± 9.05 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_06_input.txt\") as input_data:\n",
    "    groups = [{q for q in g.replace(\"\\n\", \"\")} for g in input_data.read().split(\"\\n\\n\")]\n",
    "day_06_p1 = sum(len(x) for x in groups)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 06 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.67 ms ± 78.7 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_06_input.txt\") as input_data:\n",
    "    groups = [[set(q) for q in g.split(\"\\n\")] for g in input_data.read().split(\"\\n\\n\")]\n",
    "day_06_p2 = sum(len(set.intersection(*[y for y in x])) for x in groups)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 06 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "outputs": [],
   "source": [
    "bag_regex = r\"^(\\w+ \\w+)\"\n",
    "contained_regex = r\"(\\d+) (\\w+ \\w+)\"\n",
    "\n",
    "\n",
    "def parse_rule(input_string: str) -> tuple:\n",
    "    bag_match = re.match(bag_regex, input_string).group(1)\n",
    "    contained_match = [m.groups() for m in re.finditer(contained_regex, input_string)]\n",
    "    return bag_match, [(int(m[0]), m[1]) for m in contained_match]"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 07 Setup\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7.6 ms ± 146 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_07_input.txt\") as input_data:\n",
    "    bag_map = dict(map(parse_rule, input_data))\n",
    "\n",
    "@lru_cache()\n",
    "def contains_bag(query_bag: str, bag_to_check: str) -> bool:\n",
    "    contained_bags = {b for _, b in bag_map[bag_to_check]}\n",
    "    if not contained_bags:\n",
    "        return False\n",
    "    if query_bag in contained_bags:\n",
    "        return True\n",
    "    return any(contains_bag(query_bag, b) for b in contained_bags)\n",
    "\n",
    "\n",
    "day_07_p1 = sum(contains_bag(\"shiny gold\", s) for s in bag_map)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 07 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.02 ms ± 9.83 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_07_input.txt\") as input_data:\n",
    "    bag_map = dict(map(parse_rule, input_data))\n",
    "\n",
    "lookup_dict = defaultdict(set)\n",
    "for bag, contained_bags in bag_map.items():\n",
    "    for _, contained_bag in contained_bags:\n",
    "        lookup_dict[contained_bag].add(bag)\n",
    "\n",
    "bags_containing_shiny_gold = lookup_dict[\"shiny gold\"]\n",
    "bags_to_process = bags_containing_shiny_gold.copy()\n",
    "while bags_to_process:\n",
    "    new_bags = lookup_dict[bags_to_process.pop()]\n",
    "    bags_containing_shiny_gold |= new_bags\n",
    "    bags_to_process |= new_bags\n",
    "\n",
    "day_07_p1 = len(bags_containing_shiny_gold)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 07 Part 1 alternative\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.49 ms ± 37.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_07_input.txt\") as input_data:\n",
    "    bag_map = dict(map(parse_rule, input_data))\n",
    "\n",
    "def get_sub_bag_count(count: int, bag: str) -> int:\n",
    "    if not bag_map[bag]:\n",
    "        return count\n",
    "    return count + count * sum(get_sub_bag_count(c, b) for c, b in bag_map[bag])\n",
    "\n",
    "\n",
    "day_07_p1 = get_sub_bag_count(1, 'shiny gold') - 1"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 07 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "outputs": [],
   "source": [
    "position = 0\n",
    "visited = set()\n",
    "accumulator = 0\n",
    "\n",
    "class LoopException(Exception):\n",
    "    pass\n",
    "\n",
    "\n",
    "def noop(*args) -> None:\n",
    "    global position\n",
    "    if position in visited:\n",
    "        raise LoopException\n",
    "    visited.add(position)\n",
    "    position += 1\n",
    "\n",
    "\n",
    "def acc(value: int) -> None:\n",
    "    global position\n",
    "    global accumulator\n",
    "    if position in visited:\n",
    "        raise LoopException\n",
    "    visited.add(position)\n",
    "    accumulator += value\n",
    "    position += 1\n",
    "\n",
    "\n",
    "def jmp(value: int) -> None:\n",
    "    global position\n",
    "    if position in visited:\n",
    "        raise LoopException\n",
    "    visited.add(position)\n",
    "    position += value\n",
    "\n",
    "\n",
    "op_map = {\n",
    "    \"nop\": noop,\n",
    "    \"acc\": acc,\n",
    "    \"jmp\": jmp\n",
    "}"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 08 Setup\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "140 µs ± 5.15 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_08_input.txt\") as input_data:\n",
    "    op_codes = [x.strip().split() for x in input_data]\n",
    "\n",
    "callstack = []\n",
    "while True:\n",
    "    callstack.append(position)\n",
    "    op, arg = op_codes[position]\n",
    "    try:\n",
    "        op_map[op](int(arg))\n",
    "    except LoopException:\n",
    "        day_08_p1 = accumulator\n",
    "        break"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 08 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "154 µs ± 8.27 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_08_input.txt\") as input_data:\n",
    "    op_codes = [x.strip().split() for x in input_data]\n",
    "\n",
    "position = 0\n",
    "visited = set()\n",
    "accumulator = 0\n",
    "callstack = []\n",
    "while True:\n",
    "    callstack.append(position)\n",
    "    op, arg = op_codes[position]\n",
    "    try:\n",
    "        op_map[op](int(arg))\n",
    "    except LoopException:\n",
    "        break\n",
    "\n",
    "position_to_check = [x for x in callstack[:-1] if op_codes[x][0] in [\"nop\", \"jmp\"]]\n",
    "\n",
    "terminated = False\n",
    "for corruption_candidate in position_to_check:\n",
    "    if terminated:\n",
    "        break\n",
    "    position = 0\n",
    "    visited = set()\n",
    "    accumulator = 0\n",
    "    altered_op_codes = op_codes.copy()\n",
    "    old_op, arg = altered_op_codes[corruption_candidate]\n",
    "    altered_op_codes[corruption_candidate] = (\"nop\", arg) if old_op == \"jmp\" else (\"jmp\", arg)\n",
    "    while True:\n",
    "        if position >= len(altered_op_codes):\n",
    "            day_08_p2 = accumulator\n",
    "            terminated = True\n",
    "            break\n",
    "        op, arg = altered_op_codes[position]\n",
    "        try:\n",
    "            op_map[op](int(arg))\n",
    "        except LoopException:\n",
    "            break"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 08 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.53 ms ± 569 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "offset = 25\n",
    "with open(\"day_09_input.txt\") as input_data:\n",
    "    numbers = np.array([int(x) for x in input_data])\n",
    "\n",
    "x = np.lib.stride_tricks.as_strided(numbers, (len(numbers) - offset, offset), (numbers.strides[0], numbers.strides[0]))\n",
    "\n",
    "for c, p in zip(numbers[25:], np.expand_dims(x, axis=1)):\n",
    "    if not (p + p.T == c).any():\n",
    "        day_09_p1 = c\n",
    "        break"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 09 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6.22 ms ± 101 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_09_input.txt\") as input_data:\n",
    "    numbers = np.array([int(x) for x in input_data])\n",
    "\n",
    "offset = 25\n",
    "x = np.lib.stride_tricks.as_strided(numbers, (len(numbers) - offset, offset), (numbers.strides[0], numbers.strides[0]))\n",
    "\n",
    "for c, p in zip(numbers[25:], x):\n",
    "    if not (p.reshape(-1, 1) + p.reshape(1, -1) == c).any():\n",
    "        day_09_p1 = c\n",
    "        break\n",
    "\n",
    "accumulated = numbers.cumsum().reshape(1, -1)\n",
    "for left, right in zip(*np.nonzero((accumulated - accumulated.T) == day_09_p1)):\n",
    "    if right - left > 2:\n",
    "        involved = numbers[left + 1:right + 1]\n",
    "        day_09_p2 = min(involved) + max(involved)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 09 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "84.6 µs ± 6.78 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_10_input.txt\") as input_data:\n",
    "    adapters = np.sort(np.array([int(x) for x in input_data]))\n",
    "\n",
    "differences = np.diff(np.hstack(([0], adapters, [adapters[-1] + 3])))\n",
    "day_10_p1 = np.sum(differences == 1) * (np.sum(differences == 3))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 10 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "117 µs ± 8.82 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_10_input.txt\") as input_data:\n",
    "    adapters = np.sort(np.array([int(x) for x in input_data]))\n",
    "\n",
    "differences = np.diff(np.hstack(([0], adapters, [adapters[-1] + 3])))\n",
    "run_diffs = np.diff(np.hstack(([0], differences == 1, [0])))\n",
    "run_starts, = np.nonzero(run_diffs > 0)\n",
    "run_ends, = np.nonzero(run_diffs < 0)\n",
    "\n",
    "lookup = {2: 2, 3: 4, 4: 7}\n",
    "\n",
    "day_10_p2 = math.prod(lookup[width] for start, end in zip(run_starts, run_ends) if (width := end - start) > 1)\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 10 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.19 ms ± 23.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "lookup = {\"L\": 0, \"#\": 1, \".\": np.nan}"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 11 Setup\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "39.6 ms ± 1.19 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_11_input.txt\") as input_data:\n",
    "    seat_map = np.array([[lookup[c] for c in line.strip()] for line in input_data])\n",
    "\n",
    "floor = np.isnan(seat_map)\n",
    "height, width = seat_map.shape\n",
    "\n",
    "seat_map = np.zeros((height + 2, width + 2), dtype=bool)\n",
    "seat_view = seat_map[1:-1, 1:-1]\n",
    "\n",
    "neighbour_map = np.lib.stride_tricks.as_strided(\n",
    "    seat_map,\n",
    "    shape=(height, width, 3, 3),\n",
    "    strides=seat_map.strides + seat_map.strides,\n",
    ")\n",
    "\n",
    "day_11_p1 = -1\n",
    "while day_11_p1 != (current_value := np.sum(seat_view, dtype=int)):\n",
    "    neighbour_sums = np.sum(neighbour_map, axis=(2, 3), dtype=np.uint8)\n",
    "    seat_view[(neighbour_sums == 0) & ~floor] = True\n",
    "    seat_view[(neighbour_sums > 4) & seat_view & ~floor] = False\n",
    "    day_11_p1 = current_value"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 11 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.45 ms ± 9.64 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_12_input.txt\") as input_data:\n",
    "    directions = [(line[0], int(line[1:].strip())) for line in input_data]\n",
    "\n",
    "position = np.array([0, 0])\n",
    "direction = np.array([0, 1])\n",
    "\n",
    "direction_lookup = {\n",
    "    \"N\": np.array([-1, 0]),\n",
    "    \"E\": np.array([0, 1]),\n",
    "    \"S\": np.array([1, 0]),\n",
    "    \"W\": np.array([0, -1]),\n",
    "}\n",
    "# [[cos a, -sin a], [sin a, cos a]]\n",
    "rotation_lookup = {\n",
    "    90: np.array([[0, -1], [1, 0]]),\n",
    "    180: np.array([[-1, 0], [0, -1]]),\n",
    "    270: np.array([[0, 1], [-1, 0]]),\n",
    "}\n",
    "\n",
    "for command, value in directions:\n",
    "    if command in \"NESW\":\n",
    "        position += value * direction_lookup[command]\n",
    "    elif command in \"RL\":\n",
    "        rotation_value = value if command == \"R\" else 360 - value\n",
    "        direction = np.matmul(direction, rotation_lookup[rotation_value])\n",
    "    elif command == \"F\":\n",
    "        position += value * direction\n",
    "    else:\n",
    "        print(\"Unsupported command\", command)\n",
    "\n",
    "\n",
    "day_12_p1 = np.sum(np.abs(position))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 12 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.36 ms ± 28.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_12_input.txt\") as input_data:\n",
    "    directions = [(line[0], int(line[1:].strip())) for line in input_data]\n",
    "\n",
    "direction_lookup = {\n",
    "    \"N\": np.array([-1, 0]),\n",
    "    \"E\": np.array([0, 1]),\n",
    "    \"S\": np.array([1, 0]),\n",
    "    \"W\": np.array([0, -1]),\n",
    "}\n",
    "# [[cos a, -sin a], [sin a, cos a]]\n",
    "rotation_lookup = {\n",
    "    90: np.array([[0, -1], [1, 0]]),\n",
    "    180: np.array([[-1, 0], [0, -1]]),\n",
    "    270: np.array([[0, 1], [-1, 0]]),\n",
    "}\n",
    "\n",
    "position = np.array([0, 0])\n",
    "waypoint = np.array([-1, 10])\n",
    "\n",
    "for command, value in directions:\n",
    "    if command in \"NESW\":\n",
    "        waypoint += value * direction_lookup[command]\n",
    "    elif command in \"RL\":\n",
    "        rotation_value = value if command == \"R\" else 360 - value\n",
    "        waypoint = np.matmul(waypoint, rotation_lookup[rotation_value])\n",
    "    elif command == \"F\":\n",
    "        position += value * waypoint\n",
    "    else:\n",
    "        print(\"Unsupported command\", command)\n",
    "\n",
    "day_12_p2 = np.sum(np.abs(position))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 12 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "23.8 µs ± 3.88 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_13_input.txt\") as input_data:\n",
    "    earliest_arrival = int(input_data.readline().strip())\n",
    "    bus_ids = [int(x) for x in input_data.readline().split(\",\") if x != \"x\"]\n",
    "\n",
    "wait_time, bus_id = sorted((bus_id - earliest_arrival % bus_id, bus_id) for bus_id in bus_ids)[0]\n",
    "\n",
    "day_13_p1 = wait_time * bus_id"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 13 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "62.6 µs ± 2.44 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_13_input.txt\") as input_data:\n",
    "    input_data.readline()\n",
    "    bus_ids = [(offset, int(x)) for offset, x in enumerate(input_data.readline().split(\",\")) if x != \"x\"]\n",
    "\n",
    "step_size = bus_ids.pop(0)[1]\n",
    "position = step_size\n",
    "while bus_ids:\n",
    "    offset, bus_id = bus_ids.pop(0)\n",
    "    while (position + offset) % bus_id != 0:\n",
    "        position += step_size\n",
    "    step_size *= bus_id\n",
    "\n",
    "day_13_p2 =position"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 13 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "780 µs ± 50.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "mask_regex = re.compile(r\"^mask\\s+=\\s+([X10]+)\")\n",
    "mem_regex = re.compile(r\"^mem\\[(\\d+)\\]\\s=\\s(\\d+)\")\n",
    "\n",
    "result = {}\n",
    "with open(\"day_14_input.txt\") as input_data:\n",
    "    for line in input_data:\n",
    "        if mask_match := mask_regex.match(line):\n",
    "            and_pattern = int(mask_match.group(1).replace(\"1\", \"0\").replace(\"X\", \"1\"), 2)\n",
    "            or_pattern = int(mask_match.group(1).replace(\"X\", \"0\"), 2)\n",
    "        else:\n",
    "            position, value = map(int, mem_regex.match(line).groups())\n",
    "            result[position] = value & and_pattern | or_pattern\n",
    "\n",
    "day_14_p1 = sum(result.values())"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 14 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "36 ms ± 212 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "mask_regex = re.compile(r\"^mask\\s+=\\s+([X10]+)\")\n",
    "mem_regex = re.compile(r\"^mem\\[(\\d+)\\]\\s=\\s(\\d+)\")\n",
    "result = {}\n",
    "with open(\"day_14_input.txt\") as input_data:\n",
    "    for line in input_data:\n",
    "        if mask_match := mask_regex.match(line):\n",
    "            and_pattern = int(mask_match.group(1).replace(\"0\", \"1\").replace(\"X\", \"0\"), 2)\n",
    "            or_template = mask_match.group(1)\n",
    "            or_patterns = []\n",
    "            x_count = line.count(\"X\")\n",
    "            for x in range(2**x_count):\n",
    "                or_pattern = or_template\n",
    "                for c in bin(x)[2:].zfill(x_count):\n",
    "                    or_pattern = or_pattern.replace(\"X\", c, 1)\n",
    "                or_patterns.append(int(or_pattern, 2))\n",
    "        else:\n",
    "            position, value = map(int, mem_regex.match(line).groups())\n",
    "            for or_pattern in or_patterns:\n",
    "                result[position & and_pattern | or_pattern] = value\n",
    "\n",
    "day_14_p2 = sum(result.values())\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 14 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "373 µs ± 72.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "input_data = [6, 3, 15, 13, 1, 0]\n",
    "\n",
    "history = {x: i + 1 for i, x in enumerate(input_data[:-1])}\n",
    "last_value = input_data[-1]\n",
    "turn = len(input_data) + 1\n",
    "last_turn = 2020\n",
    "while turn <= last_turn:\n",
    "    if last_value not in history:\n",
    "        current_value = 0\n",
    "    else:\n",
    "        current_value = turn - history[last_value] - 1\n",
    "    history[last_value] = turn - 1\n",
    "    last_value = current_value\n",
    "    turn += 1\n",
    "\n",
    "day_14_p1 = last_value"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 15 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9.36 s ± 437 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "input_data = [6, 3, 15, 13, 1, 0]\n",
    "\n",
    "history = {x: i + 1 for i, x in enumerate(input_data[:-1])}\n",
    "last_value = input_data[-1]\n",
    "turn = len(input_data) + 1\n",
    "last_turn = 30000000\n",
    "while turn <= last_turn:\n",
    "    if last_value not in history:\n",
    "        current_value = 0\n",
    "    else:\n",
    "        current_value = turn - history[last_value] - 1\n",
    "    history[last_value] = turn - 1\n",
    "    last_value = current_value\n",
    "    turn += 1\n",
    "\n",
    "day_15_p2 = last_value"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 15 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7.18 ms ± 998 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_16_input.txt\") as input_data:\n",
    "    rules_dict = {}\n",
    "    while match := re.match(r\"^((?:\\w+\\s?)+):\\s(\\d+-\\d+)\\sor\\s(\\d+-\\d+)\", input_data.readline()):\n",
    "        rules_dict[match.group(1)] = [pd.Interval(*map(int, g.split(\"-\")), closed=\"both\") for g in match.groups()[1:]]\n",
    "    while \"your ticket:\" not in input_data.readline():\n",
    "        pass\n",
    "    my_ticket = list(map(int, input_data.readline().split(\",\")))\n",
    "    while \"nearby tickets:\" not in input_data.readline():\n",
    "        pass\n",
    "    nearby_tickets = [list(map(int, x.split(\",\"))) for x in input_data]\n",
    "\n",
    "\n",
    "def check_valid(ticket: list[int]) -> tuple[bool, int]:\n",
    "    valid = True\n",
    "    error_rate = 0\n",
    "    for value in ticket:\n",
    "        if not any(value in rule for name, rules in rules_dict.items() for rule in rules):\n",
    "            valid = False\n",
    "            error_rate += value\n",
    "    return valid, error_rate\n",
    "\n",
    "\n",
    "day_16_p1 = sum(check_valid(ticket)[1] for ticket in nearby_tickets)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 16 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "66.5 ms ± 599 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_16_input.txt\") as input_data:\n",
    "    rules_dict = {}\n",
    "    while match := re.match(r\"^((?:\\w+\\s?)+):\\s(\\d+-\\d+)\\sor\\s(\\d+-\\d+)\", input_data.readline()):\n",
    "        rules_dict[match.group(1)] = [pd.Interval(*map(int, g.split(\"-\")), closed=\"both\") for g in match.groups()[1:]]\n",
    "    while \"your ticket:\" not in input_data.readline():\n",
    "        pass\n",
    "    my_ticket = list(map(int, input_data.readline().split(\",\")))\n",
    "    while \"nearby tickets:\" not in input_data.readline():\n",
    "        pass\n",
    "    nearby_tickets = [list(map(int, x.split(\",\"))) for x in input_data]\n",
    "\n",
    "\n",
    "def check_valid(ticket: list[int]) -> tuple[bool, int]:\n",
    "    valid = True\n",
    "    error_rate = 0\n",
    "    for value in ticket:\n",
    "        if not any(value in rule for name, rules in rules_dict.items() for rule in rules):\n",
    "            valid = False\n",
    "            error_rate += value\n",
    "    return valid, error_rate\n",
    "\n",
    "valid_tickets = [ticket for ticket in nearby_tickets if check_valid(ticket)[0]]\n",
    "\n",
    "\n",
    "def map_fields(ticket: list[int]) -> list[set]:\n",
    "    possible_fields = [set() for _ in range(len(ticket))]\n",
    "    for i, value in enumerate(ticket):\n",
    "        possible_fields[i] = {name for name, rules in rules_dict.items() for rule in rules if value in rule}\n",
    "\n",
    "    return possible_fields\n",
    "\n",
    "\n",
    "candidates = {i: f[0].intersection(*f) for i, f in enumerate(zip(*[map_fields(ticket) for ticket in valid_tickets]))}\n",
    "candidates_sorted = {k: v for k, v in sorted(candidates.items(), key=lambda item: len(item[1]))}\n",
    "\n",
    "assigned = {}\n",
    "for i, fields in candidates_sorted.items():\n",
    "    fields = fields - assigned.keys()\n",
    "    if len(fields) == 1:\n",
    "        field, = fields\n",
    "        assigned[field] = i\n",
    "    else:\n",
    "        print(\"Should not happen\")\n",
    "\n",
    "day_16_p2 = math.prod(my_ticket[v] for k, v in assigned.items() if k.startswith('departure'))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 16 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7.66 ms ± 1.59 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_17_input.txt\") as input_data:\n",
    "    initial_plane = np.array(\n",
    "        [[c == \"#\" for c in line.strip()] for line in input_data], dtype=bool\n",
    "    )[np.newaxis, :, :]\n",
    "\n",
    "space = np.pad(initial_plane, 7, constant_values=False)\n",
    "\n",
    "depth, height, width = [x - 2 for x in space.shape]\n",
    "\n",
    "space_view = space[1 : depth + 1, 1 : height + 1, 1 : width + 1]\n",
    "\n",
    "neighbour_map = np.lib.stride_tricks.as_strided(\n",
    "    space,\n",
    "    shape=(depth, height, width, 3, 3, 3),\n",
    "    strides=space.strides + space.strides,\n",
    ")\n",
    "\n",
    "for i in range(6):\n",
    "    swap_space = space_view.copy()\n",
    "    neighbour_sums = np.sum(neighbour_map, axis=(3, 4, 5), dtype=np.uint8)\n",
    "\n",
    "    swap_space[~((neighbour_sums == 3) | (neighbour_sums == 4)) & space_view] = False\n",
    "    swap_space[(neighbour_sums == 3) & ~space_view] = True\n",
    "\n",
    "    space_view[:, :, :] = swap_space\n",
    "\n",
    "day_17_p1 = np.sum(space_view)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 17 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "249 ms ± 3.63 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_17_input.txt\") as input_data:\n",
    "    initial_plane = np.array(\n",
    "        [[c == \"#\" for c in line.strip()] for line in input_data], dtype=bool\n",
    "    )[np.newaxis, np.newaxis, :, :]\n",
    "\n",
    "space = np.pad(initial_plane, 7, constant_values=False)\n",
    "\n",
    "time, depth, height, width = [x - 2 for x in space.shape]\n",
    "\n",
    "space_view = space[1 : time + 1, 1 : depth + 1, 1 : height + 1, 1 : width + 1]\n",
    "\n",
    "neighbour_map = np.lib.stride_tricks.as_strided(\n",
    "    space,\n",
    "    shape=(time, depth, height, width, 3, 3, 3, 3),\n",
    "    strides=space.strides + space.strides,\n",
    ")\n",
    "\n",
    "for i in range(6):\n",
    "    swap_space = space_view.copy()\n",
    "    neighbour_sums = np.sum(neighbour_map, axis=(4, 5, 6, 7), dtype=np.uint8)\n",
    "\n",
    "    swap_space[~((neighbour_sums == 3) | (neighbour_sums == 4)) & space_view] = False\n",
    "    swap_space[(neighbour_sums == 3) & ~space_view] = True\n",
    "\n",
    "    space_view[:, :, :, :] = swap_space\n",
    "\n",
    "day_17_p2 = np.sum(space_view)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 17 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "outputs": [],
   "source": [
    "from antlr4 import InputStream, CommonTokenStream, ParseTreeVisitor\n",
    "from Day18Part1Lexer import Day18Part1Lexer\n",
    "from Day18Part1Parser import Day18Part1Parser\n",
    "from Day18Part1Visitor import Day18Part1Visitor\n",
    "from Day18Part2Lexer import Day18Part2Lexer\n",
    "from Day18Part2Parser import Day18Part2Parser\n",
    "from Day18Part2Visitor import Day18Part2Visitor"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 18 Setup\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "603 ms ± 92.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "class Day18Part1ExprVisitor(Day18Part1Visitor):\n",
    "    def visitOpExpr(self, ctx: Day18Part1Parser.OpExprContext):\n",
    "        left = self.visit(ctx.expr(0))\n",
    "        right = self.visit(ctx.expr(1))\n",
    "        op = ctx.op.text\n",
    "        if op == \"+\":\n",
    "            return left + right\n",
    "        elif op == \"-\":\n",
    "            return left - right\n",
    "        elif op == \"*\":\n",
    "            return left * right\n",
    "\n",
    "    def visitAtomExpr(self, ctx: Day18Part1Parser.AtomExprContext):\n",
    "        return int(ctx.getText())\n",
    "\n",
    "    def visitBraceExpr(self, ctx: Day18Part1Parser.BraceExprContext):\n",
    "        return self.visit(ctx.expr())\n",
    "\n",
    "\n",
    "lexer = Day18Part1Lexer()\n",
    "parser = Day18Part1Parser(CommonTokenStream(lexer))\n",
    "visitor = Day18Part1ExprVisitor()\n",
    "\n",
    "with open(\"day_18_input.txt\") as input_data:\n",
    "    result = []\n",
    "    for line in input_data:\n",
    "        lexer.inputStream = InputStream(line.strip())\n",
    "        parser.setTokenStream(CommonTokenStream(lexer))\n",
    "        result.append(visitor.visit(parser.expr()))\n",
    "\n",
    "day_18_p1 = sum(result)\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 18 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "628 ms ± 61.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "# Before using this you have to run `antlr4 -Dlanguage=Python3 -no-listener -visitor Day18Part2.g4`\n",
    "class Day18Part2ExprVisitor(Day18Part2Visitor):\n",
    "    def visitOpExpr(self, ctx: Day18Part2Parser.OpExprContext):\n",
    "        left = self.visit(ctx.expr(0))\n",
    "        right = self.visit(ctx.expr(1))\n",
    "        op = ctx.op.text\n",
    "        if op == \"+\":\n",
    "            return left + right\n",
    "        elif op == \"-\":\n",
    "            return left - right\n",
    "        elif op == \"*\":\n",
    "            return left * right\n",
    "\n",
    "    def visitAtomExpr(self, ctx: Day18Part2Parser.AtomExprContext):\n",
    "        return int(ctx.getText())\n",
    "\n",
    "    def visitBraceExpr(self, ctx: Day18Part2Parser.BraceExprContext):\n",
    "        return self.visit(ctx.expr())\n",
    "\n",
    "\n",
    "lexer = Day18Part2Lexer()\n",
    "parser = Day18Part2Parser(CommonTokenStream(lexer))\n",
    "visitor = Day18Part2ExprVisitor()\n",
    "\n",
    "with open(\"day_18_input.txt\") as input_data:\n",
    "    result = []\n",
    "    for line in input_data:\n",
    "        lexer.inputStream = InputStream(line.strip())\n",
    "        parser.setTokenStream(CommonTokenStream(lexer))\n",
    "        result.append(visitor.visit(parser.expr()))\n",
    "\n",
    "day_18_p2 = sum(result)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 18 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13 ms ± 1.97 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_19_input.txt\") as input_data:\n",
    "    rules = {}\n",
    "    while match := re.match(r'^(\\d+): \"?([^\"]+)\"?$', input_data.readline().strip()):\n",
    "        rule_id = match.group(1)\n",
    "        rule = [f\"({x.strip()})\" for x in match.group(2).split(\"|\")]\n",
    "        rules[rule_id] = f\"({'|'.join(rule)})\"\n",
    "    for key in sorted(rules, key=lambda x: -int(x)):\n",
    "        current_rule = rules[key]\n",
    "        for sub_key in rules:\n",
    "            rules[sub_key] = rules[sub_key].replace(key, current_rule)\n",
    "    rule_zero = f'^{rules[\"0\"].replace(\" \", \"\")}$'\n",
    "    day_19_p1 = sum(bool(re.match(rule_zero, line)) for line in input_data)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 19 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.58 s ± 74.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_19_input.txt\") as input_data:\n",
    "    rules = [\"start: x0\"]\n",
    "    while line := input_data.readline().strip():\n",
    "        if line.startswith(\"8:\"):\n",
    "            line = \"8: 42 | 42 8\"\n",
    "        elif line.startswith(\"11:\"):\n",
    "            line = \"11: 42 31 | 42 11 31\"\n",
    "\n",
    "        rules.append(re.sub(r\"(\\d+)\", r\"x\\1\", line))\n",
    "    patterns = [x.strip() for x in input_data]\n",
    "\n",
    "\n",
    "parser = Lark(\"\\n\".join(rules))\n",
    "\n",
    "\n",
    "def check_valid(pattern: str) -> bool:\n",
    "    try:\n",
    "        parser.parse(pattern)\n",
    "    except LarkError:\n",
    "        return False\n",
    "    return True\n",
    "\n",
    "\n",
    "day_19_p2 = sum(check_valid(x) for x in patterns)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 19 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "outputs": [],
   "source": [
    "import math\n",
    "from collections import defaultdict\n",
    "from typing import Iterator\n",
    "\n",
    "import numpy as np\n",
    "import re\n",
    "import networkx as nx\n",
    "from dataclasses import dataclass\n",
    "\n",
    "\n",
    "@dataclass\n",
    "class ImageTile:\n",
    "    data: np.ndarray\n",
    "\n",
    "    _border_slices: list[tuple] = (\n",
    "        (0, slice(None)),\n",
    "        (-1, slice(None)),\n",
    "        (slice(None), 0),\n",
    "        (slice(None), -1),\n",
    "        (0, slice(None, None, -1)),\n",
    "        (-1, slice(None, None, -1)),\n",
    "        (slice(None, None, -1), 0),\n",
    "        (slice(None, None, -1), -1),\n",
    "    )\n",
    "\n",
    "    def borders(self) -> list[str]:\n",
    "        return [\"\".join(map(str, self.data[x, y])) for x, y in self._border_slices]\n",
    "\n",
    "    def rotate(self) -> None:\n",
    "        self.data = np.rot90(self.data)\n",
    "\n",
    "    def flip(self) -> None:\n",
    "        self.data = np.flipud(self.data)\n",
    "\n",
    "    def match_right(self, right_border: str) -> None:\n",
    "        borders = self.borders()\n",
    "        right_index = borders.index(right_border)\n",
    "        if right_index == 0:\n",
    "            self.data = np.rot90(self.data, k=-1)\n",
    "        elif right_index == 1:\n",
    "            self.data = np.flipud(np.rot90(self.data, k=1))\n",
    "        elif right_index == 2:\n",
    "            self.data = np.fliplr(self.data)\n",
    "        elif right_index == 4:\n",
    "            self.data = np.flipud(np.rot90(self.data, k=-1))\n",
    "        elif right_index == 5:\n",
    "            self.data = np.rot90(self.data, k=1)\n",
    "        elif right_index == 6:\n",
    "            self.data = np.flipud(np.fliplr(self.data))\n",
    "        elif right_index == 7:\n",
    "            self.data = np.flipud(self.data)\n",
    "\n",
    "    def match_left(self, left_border: str) -> None:\n",
    "        self.match_right(left_border)\n",
    "        self.data = np.fliplr(self.data)\n",
    "\n",
    "    def match_top(self, top_border: str) -> None:\n",
    "        self.match_right(top_border)\n",
    "        self.data = np.rot90(self.data)\n",
    "\n",
    "\n",
    "def tile_generator(filename: str) -> Iterator[tuple[int, ImageTile]]:\n",
    "    with open(filename) as input_data:\n",
    "        text = input_data.read()\n",
    "\n",
    "    for tile_string in text.strip().split(\"\\n\\n\"):\n",
    "        _id, *data = tile_string.split(\"\\n\")\n",
    "        _id = int(re.search(r\"\\d+\", _id).group())\n",
    "        data = np.array([[c == \"#\" for c in row] for row in data], dtype=np.uint8)\n",
    "        yield _id, ImageTile(data)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 20 Setup\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12 ms ± 642 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "tile_connections = defaultdict(set)\n",
    "tiles = dict(tile_generator(\"day_20_input.txt\"))\n",
    "\n",
    "for tile_id, tile in tiles.items():\n",
    "    for border in tile.borders():\n",
    "        tile_connections[border].add(tile_id)\n",
    "\n",
    "G = nx.from_edgelist(\n",
    "    [\n",
    "        (*tile_ids, {\"border\": border})\n",
    "        for border, tile_ids in tile_connections.items()\n",
    "        if len(tile_ids) == 2\n",
    "    ]\n",
    ")\n",
    "\n",
    "corner_tiles = [n[0] for n in G.degree() if n[1] == 2]\n",
    "\n",
    "day_20_p1 = math.prod(corner_tiles)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 20 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "436 ms ± 128 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "tile_connections = defaultdict(set)\n",
    "tiles = dict(tile_generator(\"day_20_input.txt\"))\n",
    "\n",
    "for tile_id, tile in tiles.items():\n",
    "    for border in tile.borders():\n",
    "        tile_connections[border].add(tile_id)\n",
    "\n",
    "G = nx.from_edgelist(\n",
    "    [\n",
    "        (*tile_ids, {\"border\": border})\n",
    "        for border, tile_ids in tile_connections.items()\n",
    "        if len(tile_ids) == 2\n",
    "    ]\n",
    ")\n",
    "\n",
    "corner_tiles = [n[0] for n in G.degree() if n[1] == 2]\n",
    "visited = {corner_tiles[0]}\n",
    "\n",
    "\n",
    "def tile_score(x: int) -> int:\n",
    "    return visited.add(x) or -sum(n in visited for n in G.neighbors(x))\n",
    "\n",
    "\n",
    "c0 = corner_tiles[0]\n",
    "tile_ids = [c0] + [v for _, v in nx.bfs_beam_edges(G, c0, tile_score, 4)]\n",
    "\n",
    "tile_map = np.zeros((12, 12), dtype=int)\n",
    "idx = np.argsort(np.add.outer(np.arange(12), np.arange(12)).ravel(), kind=\"stable\")\n",
    "tile_map.ravel()[idx] = np.array(tile_ids)\n",
    "\n",
    "result = np.zeros((12*8, 12*8), dtype=int)\n",
    "\n",
    "top_left_tile: ImageTile = tiles[tile_map[0, 0]]\n",
    "top_left_tile.match_right(G.get_edge_data(tile_map[0, 0], tile_map[0, 1])[\"border\"])\n",
    "if top_left_tile.borders()[1] != G.get_edge_data(tile_map[0, 0], tile_map[1, 0])[\"border\"]:\n",
    "    top_left_tile.flip()\n",
    "result[0:8, 0:8] = top_left_tile.data[1:9, 1:9]\n",
    "for y in range(1, 12):\n",
    "    tile_above: ImageTile = tiles[tile_map[y-1, 0]]\n",
    "    tile: ImageTile = tiles[tile_map[y, 0]]\n",
    "    tile.match_top(tile_above.borders()[1])\n",
    "    result[y*8:y*8+8, 0:8] = tile.data[1:9, 1:9]\n",
    "\n",
    "for y in range(0, 12):\n",
    "    for x in range(1, 12):\n",
    "        tile_left: ImageTile = tiles[tile_map[y, x - 1]]\n",
    "        tile: ImageTile = tiles[tile_map[y, x]]\n",
    "        tile.match_left(tile_left.borders()[3])\n",
    "        result[y * 8:y * 8 + 8, x*8:x*8+8] = tile.data[1:9, 1:9]\n",
    "\n",
    "\n",
    "monster = \"\"\"                  #\n",
    "#    ##    ##    ###\n",
    " #  #  #  #  #  #   \"\"\"\n",
    "monster = np.array([[c == \"#\" for c in row] for row in monster.split(\"\\n\")], dtype=np.uint8)\n",
    "\n",
    "monster_height, monster_length = monster.shape\n",
    "monster_points = np.sum(monster)\n",
    "height, width = result.shape\n",
    "\n",
    "result_map = np.lib.stride_tricks.as_strided(\n",
    "    result,\n",
    "    (height - monster_height, width - monster_length, monster_height, monster_length),\n",
    "    result.strides + result.strides\n",
    ")\n",
    "\n",
    "for _ in range(2):\n",
    "    result = np.flipud(result)\n",
    "    for _ in range(4):\n",
    "        result = np.rot90(result)\n",
    "        result_map = np.lib.stride_tricks.as_strided(\n",
    "            result,\n",
    "            (height - monster_height, width - monster_length, monster_height, monster_length),\n",
    "            result.strides + result.strides\n",
    "        )\n",
    "        counter = 0\n",
    "        for y in range(result_map.shape[0]):\n",
    "            for x in range(result_map.shape[1]):\n",
    "                if np.sum(result_map[y, x] & monster) == 15:\n",
    "                    counter += 1\n",
    "\n",
    "        if counter > 0:\n",
    "            day_20_p2 = int(np.sum(result) - monster_points * counter)\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 20 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.6 ms ± 710 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "pattern = re.compile(r\"^((?:\\w+\\s)+)\\(contains ((?:\\w+(?:,\\s)?)+)\\)$\")\n",
    "with open(\"day_21_input.txt\") as input_data:\n",
    "    foods = [pattern.match(line).groups() for line in input_data]\n",
    "\n",
    "food_ingredients = [i.split() for i, _ in foods]\n",
    "\n",
    "allergens_dict = defaultdict(list)\n",
    "for ingredients, allergens in foods:\n",
    "    for allergen in allergens.split(\", \"):\n",
    "        allergens_dict[allergen].append(set(ingredients.split()))\n",
    "\n",
    "for allergen, ingredients in allergens_dict.items():\n",
    "    allergens_dict[allergen] = ingredients[0].intersection(*ingredients[1:])\n",
    "\n",
    "allergens_dict = {\n",
    "    k: v for k, v in sorted(allergens_dict.items(), key=lambda x: len(x[1]))\n",
    "}\n",
    "\n",
    "seen = set()\n",
    "while len(seen) < len(allergens_dict):\n",
    "    for allergen, ingredients in allergens_dict.items():\n",
    "        if len(ingredients) == 1:\n",
    "            seen.update(ingredients)\n",
    "        else:\n",
    "            allergens_dict[allergen] = ingredients - seen\n",
    "\n",
    "ingredients_with_allergens = [y for x in allergens_dict.values() for y in x]\n",
    "day_21_p1 = sum(\n",
    "        sum(x not in ingredients_with_allergens for x in ingredients)\n",
    "        for ingredients in food_ingredients\n",
    "    )"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 21 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.07 ms ± 17.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "pattern = re.compile(r\"^((?:\\w+\\s)+)\\(contains ((?:\\w+(?:,\\s)?)+)\\)$\")\n",
    "with open(\"day_21_input.txt\") as input_data:\n",
    "    foods = [pattern.match(line).groups() for line in input_data]\n",
    "\n",
    "food_ingredients = [i.split() for i, _ in foods]\n",
    "\n",
    "allergens_dict = defaultdict(list)\n",
    "for ingredients, allergens in foods:\n",
    "    for allergen in allergens.split(\", \"):\n",
    "        allergens_dict[allergen].append(set(ingredients.split()))\n",
    "\n",
    "for allergen, ingredients in allergens_dict.items():\n",
    "    allergens_dict[allergen] = ingredients[0].intersection(*ingredients[1:])\n",
    "\n",
    "allergens_dict = {\n",
    "    k: v for k, v in sorted(allergens_dict.items(), key=lambda x: len(x[1]))\n",
    "}\n",
    "\n",
    "seen = set()\n",
    "while len(seen) < len(allergens_dict):\n",
    "    for allergen, ingredients in allergens_dict.items():\n",
    "        if len(ingredients) == 1:\n",
    "            seen.update(ingredients)\n",
    "        else:\n",
    "            allergens_dict[allergen] = ingredients - seen\n",
    "\n",
    "ingredients_with_allergens = [y for x in allergens_dict.values() for y in x]\n",
    "day_21_p2 = \",\".join(y for x in dict(sorted(allergens_dict.items())).values() for y in x)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 21 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "404 µs ± 113 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_22_input.txt\") as input_data:\n",
    "    deck1, deck2 = input_data.read().strip().split(\"\\n\\n\")\n",
    "deck1 = deque(map(int, deck1.split(\"\\n\")[1:]))\n",
    "deck2 = deque(map(int, deck2.split(\"\\n\")[1:]))\n",
    "\n",
    "\n",
    "def play():\n",
    "    card1, card2 = deck1.popleft(), deck2.popleft()\n",
    "    if card1 > card2:\n",
    "        deck1.extend([card1, card2])\n",
    "    elif card2 > card1:\n",
    "        deck2.extend([card2, card1])\n",
    "    else:\n",
    "        print(\"draw - should not happen\")\n",
    "\n",
    "\n",
    "while deck1 and deck2:\n",
    "    play()\n",
    "\n",
    "winner = np.array(deck1 if deck1 else deck2)\n",
    "\n",
    "day_22_p1 = np.sum(winner * np.arange(len(winner), 0, -1))\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 22 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.4 s ± 15.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "with open(\"day_22_input.txt\") as input_data:\n",
    "    deck1, deck2 = input_data.read().strip().split(\"\\n\\n\")\n",
    "deck1 = deque(map(int, deck1.split(\"\\n\")[1:]))\n",
    "deck2 = deque(map(int, deck2.split(\"\\n\")[1:]))\n",
    "\n",
    "\n",
    "def play_recursive(deck1: deque[int], deck2: deque[int]):\n",
    "    play_recursive.counter += 1\n",
    "    game_history = set()\n",
    "    while deck1 and deck2:\n",
    "        if (tuple(deck1), tuple(deck2)) in game_history:\n",
    "            return True\n",
    "        else:\n",
    "            game_history.add((tuple(deck1), tuple(deck2)))\n",
    "        card1, card2 = deck1.popleft(), deck2.popleft()\n",
    "\n",
    "        if card1 <= len(deck1) and card2 <= len(deck2):\n",
    "            winner = play_recursive(deque(list(deck1)[:card1]), deque(list(deck2)[:card2]))\n",
    "            if winner:\n",
    "                deck1.extend([card1, card2])\n",
    "            else:\n",
    "                deck2.extend([card2, card1])\n",
    "        elif card1 > card2:\n",
    "            deck1.extend([card1, card2])\n",
    "        elif card2 > card1:\n",
    "            deck2.extend([card2, card1])\n",
    "        else:\n",
    "            print(\"draw - should not happen\")\n",
    "    return bool(deck1)\n",
    "\n",
    "play_recursive.counter = 0\n",
    "play_recursive(deck1, deck2)\n",
    "\n",
    "winner = np.array(deck1 if deck1 else deck2)\n",
    "\n",
    "day_22_p2 = np.sum(winner * np.arange(len(winner), 0, -1))\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 22 Part 2\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "119 µs ± 1.5 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "from collections import deque\n",
    "from tqdm import tqdm\n",
    "input_data = deque(int(x) for x in \"389547612\")\n",
    "\n",
    "\n",
    "def play(start_cups, moves):\n",
    "    num_cups = len(start_cups)\n",
    "    for _ in range(moves):\n",
    "        current_cup = start_cups[0]\n",
    "        start_cups.rotate(-1)\n",
    "        destination = (current_cup - 2) % num_cups + 1\n",
    "        while (idx := start_cups.index(destination)) < 3:\n",
    "            destination = (destination - 2) % num_cups + 1\n",
    "        taken = [start_cups.popleft() for _ in range(3)]\n",
    "        start_cups.rotate(2 - idx)\n",
    "        start_cups.extend(taken)\n",
    "        start_cups.rotate(idx + 1)\n",
    "    return start_cups\n",
    "\n",
    "\n",
    "cups = play(input_data, 100)\n",
    "cups.rotate(-cups.index(1))\n",
    "day_23_p1 = \"\".join(map(str, list(cups)[1:]))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 23 Part 1\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8.09 s ± 288 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "input_data = [int(x) for x in \"389547612\"]\n",
    "input_data.extend(range(10, 1000001))\n",
    "\n",
    "\n",
    "def play_fast(start_cups, moves):\n",
    "    num_cups = len(start_cups)\n",
    "    lookup = dict(zip(start_cups, start_cups[1:] + start_cups[:1]))\n",
    "    current_cup = start_cups[-1]\n",
    "    for _ in range(moves):\n",
    "        current_cup = lookup[current_cup]\n",
    "\n",
    "        pick_up = [lookup[current_cup]]\n",
    "        for _ in range(2):\n",
    "            pick_up.append(lookup[pick_up[-1]])\n",
    "        lookup[current_cup] = lookup[pick_up[-1]]\n",
    "\n",
    "        destination = (current_cup - 2) % num_cups + 1\n",
    "        while destination in pick_up:\n",
    "            destination = (destination - 2) % num_cups + 1\n",
    "\n",
    "        lookup[destination] = pick_up[0]\n",
    "        lookup[pick_up[-1]] = lookup[destination]\n",
    "\n",
    "    return lookup\n",
    "\n",
    "\n",
    "result = play_fast(input_data, 10000000)\n",
    "cup_1 = result[1]\n",
    "cup_2 = result[cup_1]\n",
    "\n",
    "day_23_p2 = cup_1 * cup_2"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% Day 23 Part 2\n"
    }
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "python38364bit97431240191747c1a13d006b5208ec49",
   "language": "python",
   "display_name": "Python 3.8.3 64-bit"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}