aoc2021.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# AOC 2021\n",
    "\n",
    "Welcome to the Advent of Code 2021 !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic configuration\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install aocd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "\n",
    "os.environ['AOC_SESSION'] = open('session.txt').read().strip()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from aocd import submit\n",
    "from aocd.models import Puzzle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 25\n",
    "https://adventofcode.com/2021/day/25\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 25)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lines = puzzle.input_data.split('\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "from matplotlib import pyplot as plt\n",
    "\n",
    "plt.rcParams[\"figure.figsize\"] = (10,10)\n",
    "\n",
    "height, width = len(lines), len(lines[0])\n",
    "\n",
    "cmap = {\n",
    "    '.': 0,\n",
    "    '>': 1,\n",
    "    'v': 2,\n",
    "}\n",
    "\n",
    "def parse_input(lines):\n",
    "    floor = np.zeros((width, height))\n",
    "    for y, line in enumerate(lines):\n",
    "        for x, char in enumerate(line):\n",
    "            floor[x,y] = cmap[char]\n",
    "    return floor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def step(floor):\n",
    "    \n",
    "    for v in [1, 2]:\n",
    "        new_floor = np.zeros((width, height))\n",
    "\n",
    "        for y in range(height):\n",
    "            for x in range(width):\n",
    "                if floor[x, y] == v:\n",
    "                    xn, yn = x, y\n",
    "                    if v == 1 and (floor[(x+1)%width, y] == 0):\n",
    "                        xn = (x+1)%width\n",
    "                    if v == 2 and (floor[x, (y+1)%height] == 0):\n",
    "                        yn = (y+1)%height\n",
    "                    new_floor[xn, yn] = v\n",
    "                    \n",
    "        new_floor[np.where(floor == v%2+1)] = v%2+1\n",
    "        floor = new_floor\n",
    "    return new_floor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "count = 0\n",
    "\n",
    "floor = parse_input(lines)\n",
    "\n",
    "while True:\n",
    "    new_floor = step(floor)\n",
    "    count += 1\n",
    "    if np.all(new_floor == floor):\n",
    "        break\n",
    "    floor = new_floor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.imshow(floor)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_a = count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 24\n",
    "https://adventofcode.com/2021/day/24\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 23\n",
    "https://adventofcode.com/2021/day/23\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hallway = [(x, 0) for x in range(11)]\n",
    "valid_hallway = [(x, 0) for x in range(11) if x not in [2, 4, 6, 8]]\n",
    "\n",
    "weights = {cls: 10**k for cls, k in zip(\"ABCD\", range(4))}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lair = {class_: set((x, y) for y in range(1, 3)) for class_, x in zip(\"ABCD\", [2, 4, 6, 8])}\n",
    "lairs = [(x, y) for x in [2, 4, 6, 8] for y in range(1, 3)]\n",
    "positions = hallway + lairs\n",
    "\n",
    "idx2pos = {idx: pos for idx, pos in enumerate(positions)}\n",
    "pos2idx = {pos: idx for idx, pos in enumerate(positions)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "def get_transitions():\n",
    "\n",
    "    matrix = {}\n",
    "\n",
    "    for class_ in \"ABCD\":\n",
    "        matrix[class_] = defaultdict(set)\n",
    "        for src in lairs:\n",
    "            for dst in lair[class_]:\n",
    "                if src not in lair[class_] or (src in lair[class_] and src[1] < dst[1]):\n",
    "                    matrix[class_][src].add(dst)\n",
    "            for dst in valid_hallway:\n",
    "                matrix[class_][src].add(dst)\n",
    "\n",
    "        for src in valid_hallway:\n",
    "            for dst in lair[class_]:\n",
    "                matrix[class_][src].add(dst)\n",
    "                \n",
    "    return matrix\n",
    "\n",
    "\n",
    "def get_path(src, dst):\n",
    "    x1, y1 = src\n",
    "    x2, y2 = dst\n",
    "        \n",
    "    path = set()\n",
    "\n",
    "    while y1 != 0:\n",
    "        path.add((x1, y1))\n",
    "        y1 -= 1\n",
    "    dx = 1 if x2 > x1 else -1\n",
    "    while x1 != x2:\n",
    "        path.add((x1, y1))\n",
    "        x1 += dx\n",
    "    while y1 != y2:\n",
    "        path.add((x1, y1))\n",
    "        y1 += 1\n",
    "        \n",
    "    path.remove(src)\n",
    "    path.add(dst)\n",
    "        \n",
    "    return path\n",
    "\n",
    "def display(state, large=False):\n",
    "    \n",
    "    state_dict = todict(state)\n",
    "    \n",
    "    for y in range(5 if large else 3):\n",
    "        for x in range(11):\n",
    "            if (x, y) in state_dict:\n",
    "                print(state_dict[(x, y)], end=\"\")\n",
    "            else:\n",
    "                print('#', end=\"\")\n",
    "        print()\n",
    "\n",
    "def update_state(state, src, dst):\n",
    "    idx_dst = pos2idx[dst]\n",
    "    idx_src = pos2idx[src]\n",
    "    new_state = state[:idx_dst] + state[idx_src] + state[idx_dst+1:]\n",
    "    new_state = new_state[:idx_src] + '.' + new_state[idx_src+1:]\n",
    "    return new_state\n",
    "\n",
    "def has_foreigner(state, cls):\n",
    "    return any( (state[pos2idx[pos]] != cls) and (state[pos2idx[pos]] != '.') for pos in lair[cls])\n",
    "\n",
    "def todict(state):\n",
    "    return {pos: state[idx] for idx, pos in enumerate(positions)}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "def run(initial_state, final_state, MAX_COST = 20000, verbose = False):\n",
    "\n",
    "    solutions = []\n",
    "    visited = {initial_state: 0}\n",
    "    queue = deque([(initial_state, [0], [initial_state])])\n",
    "    \n",
    "    transitions = get_transitions()\n",
    "\n",
    "    while queue:\n",
    "        state, cost, history = queue.popleft()\n",
    "\n",
    "        pods = [(pos, state[idx]) for idx, pos in enumerate(positions) if state[idx] != '.']\n",
    "        occupied = set(p[0] for p in pods)\n",
    "\n",
    "        for src_pos, cls in pods:\n",
    "            for dst_pos in transitions[cls][src_pos] - occupied:\n",
    "                if src_pos in lair[cls] and not has_foreigner(state, cls) and dst_pos not in lair[cls]:\n",
    "                    continue\n",
    "                path = get_path(src_pos, dst_pos)\n",
    "\n",
    "                if not (path & occupied):\n",
    "\n",
    "                    if dst_pos in lair[cls] and has_foreigner(state, cls):\n",
    "                        continue\n",
    "\n",
    "                    path_cost = len(path)*weights[cls]\n",
    "\n",
    "                    if sum(cost) + path_cost >= MAX_COST:\n",
    "                        continue\n",
    "\n",
    "                    new_state = update_state(state, src_pos, dst_pos)\n",
    "\n",
    "                    if new_state == final_state:\n",
    "                        if verbose:\n",
    "                            print(\"=\"*40)\n",
    "                            print(sum(cost))\n",
    "                            print(\"=\"*40)\n",
    "                            for c, h in zip(cost, history):\n",
    "                                print(c)\n",
    "                                display(h)\n",
    "                                print('-'*20)\n",
    "                        solutions.append(sum(cost) + path_cost)\n",
    "                    else:\n",
    "                        if new_state not in visited or (sum(cost) + path_cost) < visited[new_state]:\n",
    "                            visited[new_state] = sum(cost) + path_cost\n",
    "                            queue.append((new_state, cost + [path_cost], history + [new_state]))\n",
    "    return solutions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "initial_state = \".\"*11 + \"CBDAADBC\"\n",
    "display(initial_state)\n",
    "\n",
    "final_state = \".\"*11 + \"AABBCCDD\"\n",
    "display(final_state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solutions = run(initial_state, final_state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_a = min(solutions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lair = {class_: set((x, y) for y in range(1, 5)) for class_, x in zip(\"ABCD\", [2, 4, 6, 8])}\n",
    "lairs = [(x, y) for x in [2, 4, 6, 8] for y in range(1, 5)]\n",
    "positions = hallway + lairs\n",
    "\n",
    "idx2pos = {idx: pos for idx, pos in enumerate(positions)}\n",
    "pos2idx = {pos: idx for idx, pos in enumerate(positions)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "initial_state = \".\"*11 + \"CDDBDCBAABADBACC\"\n",
    "display(initial_state, large=True)\n",
    "\n",
    "final_state = \".\"*11 + \"AAAABBBBCCCCDDDD\"\n",
    "display(final_state, large=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solutions = run(initial_state, final_state, MAX_COST=100000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_b = min(solutions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 22\n",
    "https://adventofcode.com/2021/day/22\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 22)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lines = puzzle.input_data.split('\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lines = [line.split() for line in lines]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "def read_input(lines, limit_scale=True):\n",
    "    queue = deque()\n",
    "\n",
    "    for cmd, coords in lines:\n",
    "        x, y, z = coords.split(',')\n",
    "        l = (x[2:].split('..'), y[2:].split('..'), z[2:].split('..'))\n",
    "        if abs(int(l[0][0])) <= 50:\n",
    "            limits = [(l[0][0], int(l[0][1])+1), (l[1][0], int(l[1][1])+1), (l[2][0], int(l[2][1])+1)]\n",
    "            queue.append((cmd, Volume(limits)))\n",
    "            \n",
    "    return queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "class Volume:\n",
    "    def __init__(self, limits):\n",
    "        self.x0 = int(limits[0][0])\n",
    "        self.x1 = int(limits[0][1])\n",
    "        self.y0 = int(limits[1][0])\n",
    "        self.y1 = int(limits[1][1])\n",
    "        self.z0 = int(limits[2][0])\n",
    "        self.z1 = int(limits[2][1])\n",
    "        \n",
    "    def volume(self):\n",
    "        return (self.x1 - self.x0)*(self.y1 - self.y0)*(self.z1 - self.z0)\n",
    "    \n",
    "    def intersect(self, other):\n",
    "        x0 = max(self.x0, other.x0)\n",
    "        x1 = min(self.x1, other.x1)\n",
    "        y0 = max(self.y0, other.y0)\n",
    "        y1 = min(self.y1, other.y1)\n",
    "        z0 = max(self.z0, other.z0)\n",
    "        z1 = min(self.z1, other.z1)\n",
    "        \n",
    "        if x0 >= x1 or y0 >= y1 or z0 >= z1:\n",
    "            return None\n",
    "        \n",
    "        return Volume([(x0, x1), (y0, y1), (z0, z1)])\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"({self.x0},{self.x1}) ({self.y0},{self.y1}) ({self.z0},{self.z1})\"\n",
    "    \n",
    "    def corners(self):\n",
    "        corners = []\n",
    "        for x in [self.x0, self.x1]:\n",
    "            for y in [self.y0, self.y1]:\n",
    "                for z in [self.z0, self.z1]:\n",
    "                    corners.append((x, y, z))\n",
    "        return corners\n",
    "    \n",
    "    def contains(self, pt, strict=True):\n",
    "        x, y, z = pt\n",
    "        if strict:\n",
    "            return (self.x0 < x < self.x1) and (self.y0 < y < self.y1) and (self.z0 < z < self.z1)\n",
    "        else:\n",
    "            return (self.x0 <= x <= self.x1) and (self.y0 <= y <= self.y1) and (self.z0 <= z <= self.z1)\n",
    "\n",
    "    def includes(self, other):\n",
    "        return all(self.contains(pt, False) for pt in other.corners())\n",
    "\n",
    "def linf(p1, p2):\n",
    "    return sum(p1[i] != p2[i] for i in range(3))\n",
    "\n",
    "def split(vol, inter):\n",
    "    case = len(set(inter.corners()) & set(vol.corners()))\n",
    "    subvolumes = []\n",
    "    \n",
    "    if case == 0:\n",
    "        if inter.volume() < vol.volume():\n",
    "            p0 = (vol.x0, vol.y0, vol.z0)\n",
    "            p1 = (vol.x1, inter.y0, vol.z1)\n",
    "            subvolumes.append(Volume(corners_to_limits(p0, p1)))\n",
    "            \n",
    "            p0 = (vol.x0, inter.y0, vol.z0)\n",
    "            p1 = (vol.x1, inter.y1, inter.z0)\n",
    "            subvolumes.append(Volume(corners_to_limits(p0, p1)))\n",
    "            \n",
    "            p0 = (vol.x0, inter.y0, inter.z1)\n",
    "            p1 = (vol.x1, inter.y1, vol.z1)\n",
    "            subvolumes.append(Volume(corners_to_limits(p0, p1)))\n",
    "            \n",
    "            p0 = (vol.x0, inter.y0, inter.z0)\n",
    "            p1 = (inter.x0, inter.y1, inter.z1)\n",
    "            subvolumes.append(Volume(corners_to_limits(p0, p1)))\n",
    "            \n",
    "            p0 = (inter.x1, inter.y0, inter.z0)\n",
    "            p1 = (vol.x1, inter.y1, inter.z1)\n",
    "            subvolumes.append(Volume(corners_to_limits(p0, p1)))\n",
    "            \n",
    "            p0 = (vol.x0, inter.y1, vol.z0)\n",
    "            p1 = (vol.x1, vol.y1, vol.z1)\n",
    "            subvolumes.append(Volume(corners_to_limits(p0, p1)))\n",
    "    \n",
    "    if case == 1:\n",
    "        pivot = [pt for pt in inter.corners() if vol.contains(pt)][0]\n",
    "        for corner in vol.corners():\n",
    "            if corner not in set(inter.corners()):\n",
    "                subvolumes.append(Volume(corners_to_limits(pivot, corner)))\n",
    "    elif case == 2:\n",
    "        anchor = list(set(vol.corners()) & set(inter.corners()))[0]\n",
    "        pivot = [pt for pt in inter.corners() if linf(pt, anchor) == 3][0]\n",
    "        for corner in vol.corners():\n",
    "            if corner not in set(inter.corners()) and linf(pivot, corner) == 3:\n",
    "                subvolumes.append(Volume(corners_to_limits(pivot, corner)))\n",
    "    elif case == 4:\n",
    "        anchor = list(set(vol.corners()) - set(inter.corners()))[0]\n",
    "        pivot = [pt for pt in set(inter.corners()) - set(vol.corners()) if linf(pt, anchor) == 3][0] \n",
    "        subvolumes.append(Volume(corners_to_limits(pivot, anchor)))\n",
    "    return subvolumes\n",
    "\n",
    "def corners_to_limits(c1, c2):\n",
    "    x0 = min(c1[0], c2[0])\n",
    "    x1 = max(c1[0], c2[0])\n",
    "    y0 = min(c1[1], c2[1])\n",
    "    y1 = max(c1[1], c2[1])\n",
    "    z0 = min(c1[2], c2[2])\n",
    "    z1 = max(c1[2], c2[2])\n",
    "    return [(x0, x1), (y0, y1), (z0, z1)]\n",
    "\n",
    "def run(queue):\n",
    "    volumes = [queue.popleft()[1]]\n",
    "\n",
    "    while queue:\n",
    "        cmd, current = queue.popleft()\n",
    "\n",
    "        new_volumes = []\n",
    "\n",
    "        init_volume = sum(v.volume() for v in volumes)\n",
    "\n",
    "        inter_volumes = []\n",
    "\n",
    "        for vol in volumes:\n",
    "            inter = vol.intersect(current)\n",
    "\n",
    "            if inter is None or (cmd == 'on' and vol.includes(current)):\n",
    "                new_volumes.append(vol)\n",
    "            else:\n",
    "                inter_volumes.append(inter.volume())\n",
    "                splitted = split(vol, inter)\n",
    "                new_volumes.extend(splitted)\n",
    "\n",
    "        if cmd == 'on':\n",
    "            new_volumes.append(current)\n",
    "\n",
    "        volumes = new_volumes.copy()\n",
    "    return volumes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "queue = read_input(lines)\n",
    "volumes = run(queue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_a = sum(v.volume() for v in volumes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def read_input(lines, limit_scale=True):\n",
    "    queue = deque()\n",
    "\n",
    "    for cmd, coords in lines:\n",
    "        x, y, z = coords.split(',')\n",
    "        l = (x[2:].split('..'), y[2:].split('..'), z[2:].split('..'))\n",
    "        limits = [(l[0][0], int(l[0][1])+1), (l[1][0], int(l[1][1])+1), (l[2][0], int(l[2][1])+1)]\n",
    "        queue.append((cmd, Volume(limits)))\n",
    "            \n",
    "    return queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "queue = read_input(lines)\n",
    "volumes = run(queue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_b = sum(v.volume() for v in volumes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 21\n",
    "https://adventofcode.com/2021/day/21\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 21)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "p01, p02 = [int(line[-1]) for line in puzzle.input_data.split('\\n')]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Dice:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.dice = 0\n",
    "        self.count = 0\n",
    "        \n",
    "    def roll(self):\n",
    "        self.dice = self.dice % 100 + 1\n",
    "        self.count += 1\n",
    "        return self.dice\n",
    "    \n",
    "class Player:\n",
    "    def __init__(self, p0):\n",
    "        self.pos = p0\n",
    "        self.score = 0\n",
    "\n",
    "    def move(self, amount):\n",
    "        self.pos = (self.pos + amount - 1) % 10 + 1\n",
    "        self.score += self.pos\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return f\"{self.pos} {self.score}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dice = Dice()\n",
    "\n",
    "p1, p2 = Player(p01), Player(p02)\n",
    "\n",
    "win = False\n",
    "while not win:\n",
    "    for p in [p1, p2]:\n",
    "        p.move(sum(dice.roll() for i in range(3)))\n",
    "        if p.score >= 1000:\n",
    "            win = True\n",
    "            break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_a = dice.count * min(p.score for p in [p1, p2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "from collections import Counter\n",
    "table = Counter([sum(p) for p in product([1, 2, 3], repeat=3)])\n",
    "\n",
    "def play(p1, p2, second=False):\n",
    "    n1, n2 = 0, 0\n",
    "    for delta, weight in table.items():\n",
    "        pos, score = p2 if second else p1\n",
    "        new_pos = ((pos+delta - 1) % 10) + 1\n",
    "        score += new_pos\n",
    "        if score >= 21:\n",
    "            n1, n2 = (n1, n2+weight) if second else (n1+weight, n2)\n",
    "        else:\n",
    "            np1, np2 = (p1, (new_pos, score)) if second else ((new_pos, score), p2)\n",
    "            sn1, sn2 = play(np1, np2, not(second))\n",
    "            n1 += (weight*sn1)\n",
    "            n2 += (weight*sn2)\n",
    "    return n1, n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n1, n2 = play((p01, 0), (p02, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_b = max(n1, n2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 20\n",
    "https://adventofcode.com/2021/day/20\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "algo, input_ = puzzle.input_data.split('\\n\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def get_neighbor(x0, y0, carte):\n",
    "    string = ''\n",
    "    for y in range(y0-1, y0+2):\n",
    "        for x in range(x0-1, x0+2):\n",
    "            string = f\"{string}{carte[x][y]}\"\n",
    "    return int(string, 2)\n",
    "\n",
    "def parse_input(img):\n",
    "\n",
    "    carte = defaultdict(lambda : defaultdict( lambda : 0))\n",
    "\n",
    "    for y, line in enumerate(img.split('\\n')):\n",
    "        for x, c in enumerate(line):\n",
    "            if c == '#':\n",
    "                carte[x][y] = 1\n",
    "                \n",
    "    return carte"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib import pyplot as plt\n",
    "\n",
    "plt.rcParams[\"figure.figsize\"] = (20,20)\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "def tonumpy(carte):\n",
    "    ymin, ymax = min(carte.keys()), max(carte.keys())\n",
    "    xmin, xmax = min([min(line.keys()) for line in carte.values()]), max([max(line.keys()) for line in carte.values()])\n",
    "    \n",
    "    img = np.array([[carte[x][y] for x in range(xmin-2, xmax+2)] for y in range(ymin-2, ymax+2)]).astype('int')\n",
    "    return img\n",
    "\n",
    "def expand(carte, default_value):\n",
    "    new_carte = defaultdict(lambda : defaultdict( lambda : default_value))\n",
    "\n",
    "    ymin, ymax = min(carte.keys()), max(carte.keys())\n",
    "    xmin, xmax = min([min(line.keys()) for line in carte.values()]), max([max(line.keys()) for line in carte.values()])\n",
    "\n",
    "    for y in range(ymin-3, ymax+3):\n",
    "        for x in range(xmin-3, xmax+3):\n",
    "            val = get_neighbor(x, y, carte)\n",
    "            new_carte[x][y] = 1 if algo[val] == '#' else 0\n",
    "            \n",
    "    return new_carte"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "carte = parse_input(input_)\n",
    "for i in range(2):\n",
    "    carte = expand(carte, (i+1) % 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_a = np.sum(tonumpy(carte))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.imshow(tonumpy(carte))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "carte = parse_input(input_)\n",
    "for i in range(50):\n",
    "    carte = expand(carte, (i+1) % 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_b = np.sum(tonumpy(carte))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.imshow(tonumpy(carte)[100:320,100:320])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 19\n",
    "https://adventofcode.com/2021/day/19\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 19)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def parse_input(data):\n",
    "    scanners = data.split('\\n\\n')\n",
    "    scanners = [scanner.split('\\n')[1:] for scanner in scanners]\n",
    "    return [ np.array([[int(v) for v in coords.split(',') ] for coords in scan]) for scan in scanners]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "scanners = parse_input(puzzle.input_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "from scipy.spatial.transform import Rotation as R\n",
    "\n",
    "elems = []\n",
    "\n",
    "for axis in ['x', 'y', 'z']:\n",
    "    elems.append([R.from_euler(axis, deg, degrees=True).as_matrix().astype(int) for deg in [0, 90, 180, 270]])\n",
    "        \n",
    "rotations = []\n",
    "\n",
    "for rx in elems[0]:\n",
    "    for ry in elems[1]:\n",
    "        for rz in elems[2]:\n",
    "            rot = np.matmul(np.matmul(rz, ry), rx)\n",
    "            if not any(np.all(rot == mat) for mat in rotations):\n",
    "                rotations.append(rot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "ref = scanners[0]\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "def to_set(array):\n",
    "    return set(tuple(coords) for coords in array)\n",
    "\n",
    "def find_delta(pts_src, pts_dst):\n",
    "    \n",
    "    targets = to_set(pts_dst)\n",
    "    \n",
    "    for src in pts_src:\n",
    "        for dst in pts_dst:\n",
    "            delta = src - dst\n",
    "            if len(set(tuple(coords) for coords in pts_src - delta) & targets) >= 12:\n",
    "                return True, delta\n",
    "    return False, None\n",
    "\n",
    "def get_rotations(scan, rotations):\n",
    "    return [scan.dot(rot) for rot in rotations]\n",
    "\n",
    "def find_match(src, dst):\n",
    "\n",
    "    for scan in get_rotations(src, rotations):\n",
    "        found, delta = find_delta(scan, dst)\n",
    "        if found:\n",
    "            return scan - delta, delta\n",
    "        \n",
    "    return None, None\n",
    "    \n",
    "points = scanners[0]\n",
    "assigned = {0}\n",
    "scanners_pos = {0: (0, 0, 0)}\n",
    "\n",
    "while len(assigned) != len(scanners):\n",
    "\n",
    "    for idx, scan in enumerate(scanners):\n",
    "        if idx in assigned:\n",
    "            continue\n",
    "        match, delta = find_match(scan, points)\n",
    "        if match is not None:\n",
    "            print(f'Success for {idx}')\n",
    "            scanners_pos[idx] = delta\n",
    "            assigned.add(idx)\n",
    "            points = np.array(list(to_set(points) | to_set(match)))\n",
    "            break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_a = len(points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_b = max([np.sum(np.abs(np.array(pt1) - np.array(pt2))) for pt2 in scanners_pos.values() for pt1 in scanners_pos.values() ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 18\n",
    "https://adventofcode.com/2021/day/18\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 18)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lines = puzzle.input_data.split('\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def parse_tree(string, parent=None):\n",
    "    if '[' in string:\n",
    "        return Node(string, parent)\n",
    "    return Leaf(int(string), parent)\n",
    "\n",
    "def split(line):\n",
    "    depth = 0\n",
    "    split_idx = 0\n",
    "    for idx, c in enumerate(line):\n",
    "        if c == '[':\n",
    "            depth += 1\n",
    "        elif c == ']':\n",
    "            depth -= 1\n",
    "        elif c == ',' and depth == 0:\n",
    "            split_idx = idx\n",
    "    return line[:split_idx], line[split_idx+1:]\n",
    "\n",
    "def join(left, right):\n",
    "     return f\"[{left},{right}]\"\n",
    "\n",
    "class Leaf:\n",
    "\n",
    "    def __init__(self, val, parent):\n",
    "        self.val = val\n",
    "        self.parent = parent\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return str(self.val)\n",
    "    \n",
    "    def depth(self):\n",
    "        return 0\n",
    "    \n",
    "    def walk_left(self, origin):\n",
    "        return self\n",
    "    \n",
    "    def walk_right(self, origin):\n",
    "        return self\n",
    "    \n",
    "    def magnitude(self):\n",
    "        return self.val\n",
    "    \n",
    "class Node:\n",
    "    def __init__(self, _input, parent=None):\n",
    "        left, right = split(_input[1:-1])\n",
    "        self.left = parse_tree(left, self)\n",
    "        self.right = parse_tree(right, self)\n",
    "        self.parent = parent\n",
    "        self.val = 0\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return f\"[{self.left},{self.right}]\"\n",
    "    \n",
    "    def is_root(self):\n",
    "        return self.parent is None\n",
    "    \n",
    "    def depth(self):\n",
    "        return max(self.left.depth(), self.right.depth()) + 1\n",
    "    \n",
    "    def height(self):\n",
    "        if self.is_root():\n",
    "            return 0\n",
    "        else:\n",
    "            return self.parent.height() + 1\n",
    "        \n",
    "    def walk_left(self, origin):\n",
    "        if origin == self.right:\n",
    "            return self.left.walk_left(self)\n",
    "        elif origin == self.left:\n",
    "            if self.is_root():\n",
    "                return None\n",
    "            return self.parent.walk_left(self)\n",
    "        elif origin == self.parent:\n",
    "            return self.right.walk_left(self)\n",
    "        \n",
    "    def walk_right(self, origin):\n",
    "        if origin == self.left:\n",
    "            return self.right.walk_right(self)\n",
    "        elif origin == self.right:\n",
    "            if self.is_root():\n",
    "                return None\n",
    "            return self.parent.walk_right(self)\n",
    "        elif origin == self.parent:\n",
    "            return self.left.walk_right(self)\n",
    "        \n",
    "    def is_explodable(self):\n",
    "        return self.height() > 3 and isinstance(self.left, Leaf) and isinstance(self.right, Leaf)\n",
    "    \n",
    "    def explode_leftmost(self):\n",
    "        \n",
    "        changed = False\n",
    "        \n",
    "        for side in ['left', 'right']:\n",
    "            child = getattr(self, side)\n",
    "            if isinstance(child, Node):\n",
    "                if child.is_explodable():\n",
    "                    left_neighbor = self.walk_left(child)\n",
    "                    if left_neighbor:\n",
    "                        left_neighbor.val += child.left.val\n",
    "\n",
    "                    right_neighbor = self.walk_right(child)\n",
    "                    if right_neighbor:\n",
    "                        right_neighbor.val += child.right.val\n",
    "\n",
    "                    setattr(self, side, Leaf(0, self))\n",
    "\n",
    "                    return True\n",
    "                else:\n",
    "                    ret = child.explode_leftmost()\n",
    "                    if ret:\n",
    "                        return True\n",
    "        return False\n",
    "    \n",
    "    def split_leftmost(self):\n",
    "        \n",
    "        changed = False\n",
    "        \n",
    "        for side in ['left', 'right']:\n",
    "            child = getattr(self, side)\n",
    "            if isinstance(child, Leaf):\n",
    "                if child.val >= 10:\n",
    "                    left_val = child.val // 2\n",
    "                    right_val = child.val - left_val\n",
    "                    setattr(self, side, Node(join(left_val, right_val), self))\n",
    "                    \n",
    "                    return True\n",
    "            else:\n",
    "                if not child.is_explodable():\n",
    "                    ret = child.split_leftmost()\n",
    "                    if ret:\n",
    "                        return True\n",
    "        return False\n",
    "    \n",
    "    def reduce(self, return_self=True):\n",
    "        finished = False\n",
    "        while not finished:\n",
    "            count = 0\n",
    "            while self.explode_leftmost():\n",
    "                count += 1\n",
    "            if self.split_leftmost():\n",
    "                count += 1\n",
    "            finished = count == 0\n",
    "        if return_self:\n",
    "            return self\n",
    "            \n",
    "    def magnitude(self):\n",
    "        return 3*self.left.magnitude() + 2*self.right.magnitude()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(lines):\n",
    "    current = lines[0]\n",
    "\n",
    "    for line in lines[1:]:\n",
    "        tree = parse_tree(join(current, line))\n",
    "        tree.reduce()\n",
    "        current = str(tree)\n",
    "        \n",
    "    return tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution = solve(lines)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_a = solution.magnitude()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import permutations\n",
    "\n",
    "pairs = permutations(lines, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_b = max(parse_tree(join(l1, l2)).reduce().magnitude() for l1, l2 in pairs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 17\n",
    "https://adventofcode.com/2021/day/17\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 17)\n",
    "limits = [(coords.split('..')) for coords in puzzle.input_data.replace('target area: ', '').split(', ')]\n",
    "limits = [(int(l[0][2:]), int(l[1])) for l in limits]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def launch(vx, vy):\n",
    "    traj = []\n",
    "    x, y = 0, 0\n",
    "    while x <= limits[0][1] and y >= limits[1][0]:\n",
    "        traj.append((x, y))\n",
    "        x += vx\n",
    "        y += vy\n",
    "        if vx > 0:\n",
    "            vx = int(vx / abs(vx))*max(abs(vx) - 1, 0)\n",
    "        vy -= 1\n",
    "\n",
    "    return traj\n",
    "\n",
    "def valid(traj):\n",
    "    return any((limits[0][0] <= x <= limits[0][1]) and (limits[1][0] <= y <= limits[1][1]) for x, y in traj)\n",
    "\n",
    "t = launch(100, -15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ymax = 0\n",
    "for vx in range(18, 320):\n",
    "    for vy in range(-10, 500):\n",
    "        t = launch(vx, vy)\n",
    "        if valid(t):\n",
    "            ymax = max(ymax, max(p[1] for p in t))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_a = ymax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "count = 0\n",
    "for vx in range(18, 320):\n",
    "    for vy in range(-80, 1000):\n",
    "        t = launch(vx, vy)\n",
    "        if valid(t):\n",
    "            count += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_b = count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 16\n",
    "https://adventofcode.com/2021/day/16\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 16)\n",
    "codes = puzzle.input_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "codes = bin(int(codes, 16))[2:].zfill(len(codes)*4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_version(stream):\n",
    "    return int(stream[:3], 2), stream[3:]\n",
    "\n",
    "def get_type(stream):\n",
    "    return int(stream[:3], 2), stream[3:]\n",
    "\n",
    "def get_type_len(stream):\n",
    "    return int(stream[0], 2), stream[1:]\n",
    "\n",
    "def parse_literal(stream):\n",
    "    cont = True\n",
    "    bits = ''\n",
    "    payload_len = 6\n",
    "    while cont:\n",
    "        cont = bool(int(stream[0]))\n",
    "        bits += stream[1:5]\n",
    "        stream = stream[5:]\n",
    "        payload_len += 5\n",
    "    return int(bits, 2), stream\n",
    "    discard = (((payload_len // 4) + 1) * 4) - payload_len\n",
    "\n",
    "\n",
    "def parse_code(stream):\n",
    "    ver, stream = get_version(stream)\n",
    "    type_id, stream = get_type(stream)\n",
    "    \n",
    "    data = []\n",
    "    \n",
    "    if type_id != 4:\n",
    "        \n",
    "        data.append((ver, type_id, -1))\n",
    "        \n",
    "        type_len, stream = get_type_len(stream)\n",
    "        \n",
    "        if type_len == 0:\n",
    "            len_subpacket = int(stream[:15], 2)\n",
    "            stream = stream[15:]\n",
    "            \n",
    "            substream = stream[:len_subpacket]\n",
    "            while substream:\n",
    "                subdata, substream = parse_code(substream)\n",
    "                data.extend(subdata)\n",
    "            stream = stream[len_subpacket:]\n",
    "        else:\n",
    "            nb_subpacket = int(stream[:11], 2)\n",
    "            stream = stream[11:]\n",
    "            \n",
    "            for i in range(nb_subpacket):\n",
    "                subdata, stream = parse_code(stream)\n",
    "                data.extend(subdata)\n",
    "            \n",
    "    else:\n",
    "        val, stream = parse_literal(stream)\n",
    "        data.append((ver, type_id, val))\n",
    "    return data, stream"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data, _ = parse_code(codes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_a = sum(d[0] for d in data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def compute(type_id, data):\n",
    "    if type_id == 0:\n",
    "        return np.sum(data)\n",
    "    elif type_id == 1:\n",
    "        return np.prod(data)\n",
    "    elif type_id == 2:\n",
    "        return np.min(data)\n",
    "    elif type_id == 3:\n",
    "        return np.max(data)\n",
    "    elif type_id == 5:\n",
    "        return int(data[0] > data[1])\n",
    "    elif type_id == 6:\n",
    "        return int(data[0] < data[1])\n",
    "    elif type_id == 7:\n",
    "        return int(data[0] == data[1])\n",
    "    \n",
    "def parse_code_p2(stream):\n",
    "    ver, stream = get_version(stream)\n",
    "    type_id, stream = get_type(stream)\n",
    "    \n",
    "    if type_id != 4:\n",
    "        \n",
    "        data = []\n",
    "        \n",
    "        type_len, stream = get_type_len(stream)\n",
    "        \n",
    "        if type_len == 0:\n",
    "            len_subpacket = int(stream[:15], 2)\n",
    "            stream = stream[15:]\n",
    "            \n",
    "            substream = stream[:len_subpacket]\n",
    "            while substream:\n",
    "                val, substream = parse_code_p2(substream)\n",
    "                data.append(val)\n",
    "            stream = stream[len_subpacket:]\n",
    "        else:\n",
    "            nb_subpacket = int(stream[:11], 2)\n",
    "            stream = stream[11:]\n",
    "            \n",
    "            for i in range(nb_subpacket):\n",
    "                val, stream = parse_code_p2(stream)\n",
    "                data.append(val)\n",
    "                \n",
    "        return compute(type_id, data), stream \n",
    "    else:\n",
    "        val, stream = parse_literal(stream)\n",
    "        return val, stream"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_b, _ = parse_code_p2(codes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 15\n",
    "https://adventofcode.com/2021/day/15"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "data = np.array([[int(c) for c in line] for line in puzzle.input_data.split('\\n')]).astype('uint8')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "distances = np.zeros(data.shape)\n",
    "distances[:,:] = 10**20\n",
    "distances[0, 0] = 0\n",
    "visited = set()\n",
    "to_visit = {(0, 0)}\n",
    "lattice = set((x, y) for y in range(data.shape[0]) for x in range(data.shape[1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def evaluate(node):\n",
    "    x, y = node\n",
    "    for dx, dy in [(-1, 0), (0, 1), (1, 0), (0, -1)]:\n",
    "        neighbor = x+dx, y+dy\n",
    "        if neighbor in lattice:\n",
    "            distances[neighbor] = min(distances[node] + data[neighbor], distances[neighbor])\n",
    "            if neighbor not in visited:\n",
    "                to_visit.add(neighbor)\n",
    "    visited.add(node)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "while to_visit:\n",
    "    node = min([(x, y, distances[x, y]) for x, y in to_visit], key=lambda t: t[2])[:2]\n",
    "    evaluate(node)\n",
    "    to_visit = to_visit - visited"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_a = int(distances[-1,-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cols = [data]\n",
    "\n",
    "for i in range(4):\n",
    "    cols.append((cols[-1] % 9) + 1)\n",
    "\n",
    "lines = [np.concatenate(cols, axis=1)]\n",
    "\n",
    "for i in range(4):\n",
    "    lines.append((lines[-1] % 9) + 1)\n",
    "data = np.concatenate(lines)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "distances = np.zeros(data.shape)\n",
    "distances[:,:] = 10**20\n",
    "distances[0, 0] = 0\n",
    "visited = set()\n",
    "to_visit = {(0, 0)}\n",
    "lattice = set((x, y) for y in range(data.shape[0]) for x in range(data.shape[1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "while to_visit:\n",
    "    node = min([(x, y, distances[x, y]) for x, y in to_visit], key=lambda t: t[2])[:2]\n",
    "    evaluate(node)\n",
    "    to_visit = to_visit - visited"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_b = int(distances[-1, -1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 14\n",
    "https://adventofcode.com/2021/day/14\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 14)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "base, reactions = puzzle.input_data.split('\\n\\n')\n",
    "reactions = [reac.split(' -> ') for reac in reactions.split('\\n')]\n",
    "reactions = {r[0]: r[1] for r in reactions}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert(base, reactions):\n",
    "    insertions = [reactions[base[i:i+2]] for i in range(len(base) - 1)]\n",
    "    result = \"\".join(c1+c2 for c1, c2 in zip(base[:-1], insertions))\n",
    "    result += base[-1]\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "polymer = f\"{base}\"\n",
    "for i in range(10):\n",
    "    polymer = insert(polymer, reactions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "count = Counter(polymer)\n",
    "answer_a = count.most_common()[0][1] - count.most_common()[-1][1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def react(pairs, reactions):\n",
    "    new_count = Counter()\n",
    "    for pair, count in pairs.items():\n",
    "        insert = reactions[pair]\n",
    "        p1, p2 = pair[0]+insert, insert+pair[1]\n",
    "        new_count[p1] += count\n",
    "        new_count[p2] += count\n",
    "    return new_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pairs = Counter(base[i:i+2] for i in range(len(base) - 1))\n",
    "\n",
    "for i in range(40):\n",
    "    pairs = react(pairs, reactions)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_chars(pairs):\n",
    "    counter = Counter()\n",
    "    for pair, count in pairs.items():\n",
    "        counter[pair[0]] += count\n",
    "        counter[pair[1]] += count\n",
    "    return counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "count = count_chars(pairs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_b = ((count.most_common()[0][1] - count.most_common()[-1][1])) // 2 + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 13\n",
    "https://adventofcode.com/2021/day/13\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "coords, folds = puzzle.input_data.split('\\n\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xc = [int(c.split(',')[0]) for c in coords.split('\\n')]\n",
    "yc = [int(c.split(',')[1]) for c in coords.split('\\n')]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "folding = []\n",
    "for fold in folds.split('\\n'):\n",
    "    ax, coord = fold.split('=')\n",
    "    axis = 0 if ax[-1] == 'x' else 1\n",
    "    folding.append((axis, int(coord)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "width, height = max(xc)+1, max(yc)+1\n",
    "paper = np.zeros((width, height))\n",
    "paper[xc, yc] = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fold(paper, folding):\n",
    "    axis, coord = folding\n",
    "    if axis == 0:\n",
    "        first, second = paper[:coord, :], paper[coord+1:, :]\n",
    "    else:\n",
    "        first, second = paper[:, :coord], paper[:, coord+1:]\n",
    "    \n",
    "    if first.shape != second.shape:\n",
    "        sx, sy = second.shape\n",
    "        padded = np.zeros(first.shape)\n",
    "        padded[:sx, :sy] = second\n",
    "        second = padded\n",
    "    return np.maximum(first, np.flip(second, axis))\n",
    "\n",
    "answer_a = int(np.sum(fold(paper, folding[0])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "folded = paper.copy()\n",
    "for instruction in folding:\n",
    "    folded = fold(folded, instruction)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib import pyplot as plt\n",
    "\n",
    "plt.imshow(folded.T)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 12\n",
    "https://adventofcode.com/2021/day/12\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 12)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges = [edge.split('-') for edge in puzzle.input_data.split('\\n')]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "graph = defaultdict(set)\n",
    "for a, b in edges:\n",
    "    graph[a].add(b)\n",
    "    graph[b].add(a)\n",
    "\n",
    "big_caves = set([node for node in graph.keys()if str.lower(node) != node])\n",
    "nodes = set(graph.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "start = 'start'\n",
    "end = 'end'\n",
    "\n",
    "def recurse(path):\n",
    "    \n",
    "    current = path[-1]\n",
    "    \n",
    "    all_paths = []\n",
    "    \n",
    "    for neighbor in graph[current]:\n",
    "        if neighbor not in path or neighbor in big_caves:\n",
    "            new_path = path.copy()\n",
    "            new_path.append(neighbor)\n",
    "            if neighbor == end:\n",
    "                all_paths.append(new_path)\n",
    "            else:\n",
    "                all_paths.extend(recurse(new_path))\n",
    "    return all_paths\n",
    "    \n",
    "all_paths = recurse([start])\n",
    "answer_a = len(all_paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "small_caves = nodes - big_caves - {start, end}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "start = 'start'\n",
    "end = 'end'\n",
    "\n",
    "def recurse(path):\n",
    "    \n",
    "    current = path[-1]\n",
    "    \n",
    "    all_paths = []\n",
    "    \n",
    "    for neighbor in graph[current]:\n",
    "        count = Counter(path)\n",
    "        if (neighbor not in path) or (neighbor in big_caves) or (neighbor in small_caves and max(count[node] for node in small_caves)== 1):\n",
    "            new_path = path.copy()\n",
    "            new_path.append(neighbor)\n",
    "            if neighbor == end:\n",
    "                all_paths.append(new_path)\n",
    "            else:\n",
    "                all_paths.extend(recurse(new_path))\n",
    "    return all_paths\n",
    "    \n",
    "all_paths = recurse([start])\n",
    "answer_b = len(all_paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 11\n",
    "https://adventofcode.com/2021/day/11\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 11)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "octo = np.array([[int(c) for c in line] for line in puzzle.input_data.split('\\n')]).astype('uint8')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Nest:\n",
    "    def __init__(self, octo):\n",
    "        self.width, self.height = octo.shape\n",
    "        self.area = octo.copy()\n",
    "        \n",
    "    def step(self):\n",
    "        self.area += 1\n",
    "\n",
    "        exploded = set()\n",
    "\n",
    "        while True:\n",
    "            x, y = np.where(self.area >= 10)\n",
    "\n",
    "            if x.size == 0:\n",
    "                break\n",
    "\n",
    "            self.area[x, y] = 0\n",
    "\n",
    "            exploded |= set(zip(x, y))\n",
    "\n",
    "            expanded = [(x+dx,y+dy) for dx, dy in product([-1, 0, 1], repeat=2)]\n",
    "            nx, ny = np.concatenate([n[0] for n in expanded]), np.concatenate([n[1] for n in expanded])\n",
    "            valid = (nx >= 0) & (nx < self.width) & (ny >= 0) & (ny < self.height)\n",
    "\n",
    "            for pos, inc in Counter(zip(nx[valid], ny[valid])).items():\n",
    "                if pos not in exploded:\n",
    "                    self.area[pos] += inc\n",
    "\n",
    "        return len(exploded)\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return \"\\n\".join([\"\".join([str(self.area[y, x]) for x in range(self.width)]) for y in range(self.height)])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nest = Nest(octo)\n",
    "answer_a = sum(nest.step() for i in range(100))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nest = Nest(octo)\n",
    "\n",
    "count = 0\n",
    "while True:\n",
    "    n_flashed = nest.step()\n",
    "    count += 1\n",
    "    if n_flashed == nest.area.size:\n",
    "        break\n",
    "answer_b = count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## For fun"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cv2 as cv\n",
    "import seaborn as sns\n",
    "import numpy as np\n",
    "\n",
    "def draw(frame):\n",
    "    ax = sns.heatmap(frame, vmin=0, vmax=10, cbar=False)\n",
    "    fig = ax.figure\n",
    "    \n",
    "    fig.canvas.draw()\n",
    "\n",
    "    img = np.fromstring(fig.canvas.tostring_rgb(), dtype=np.uint8, sep='')\n",
    "    img = img.reshape(fig.canvas.get_width_height()[::-1] + (3, ))\n",
    "    img = cv.cvtColor(img, cv.COLOR_RGB2BGR)\n",
    "    return img\n",
    "\n",
    "class FunNest:\n",
    "    def __init__(self, octo):\n",
    "        self.width, self.height = octo.shape\n",
    "        self.area = octo.copy()\n",
    "        \n",
    "    def step(self):\n",
    "        self.area += 1\n",
    "\n",
    "        exploded = set()\n",
    "        \n",
    "        frames = [self.area.copy()]\n",
    "\n",
    "        while True:\n",
    "            x, y = np.where(self.area >= 10)\n",
    "\n",
    "            if x.size == 0:\n",
    "                break\n",
    "\n",
    "            self.area[x, y] = 0\n",
    "\n",
    "            exploded |= set(zip(x, y))\n",
    "\n",
    "            expanded = [(x+dx,y+dy) for dx, dy in product([-1, 0, 1], repeat=2)]\n",
    "            nx, ny = np.concatenate([n[0] for n in expanded]), np.concatenate([n[1] for n in expanded])\n",
    "            valid = (nx >= 0) & (nx < self.width) & (ny >= 0) & (ny < self.height)\n",
    "\n",
    "            for pos, inc in Counter(zip(nx[valid], ny[valid])).items():\n",
    "                if pos not in exploded:\n",
    "                    self.area[pos] += inc\n",
    "                    \n",
    "            frames.append(self.area.copy())\n",
    "\n",
    "        return frames"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_steps = answer_b + 60\n",
    "FPS = 25\n",
    "\n",
    "fourcc = cv2.VideoWriter_fourcc(*'mp4v')\n",
    "writer = cv.VideoWriter('media/day11.mp4', fourcc, FPS, (432, 288))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nest = FunNest(octo)\n",
    "\n",
    "all_frames = []\n",
    "for i in range(max_steps):\n",
    "    all_frames.append(nest.step())\n",
    "\n",
    "for curr_frames, next_frames in zip(all_frames[:-1], all_frames[1:]):\n",
    "\n",
    "    curr, next_ = curr_frames[0], next_frames[0]\n",
    "    \n",
    "    if len(curr) == 1:\n",
    "        interp_frames = np.linspace(curr, next_, FPS)\n",
    "\n",
    "        for frame in interp_frames:\n",
    "            img = draw(frame)\n",
    "            writer.write(img)\n",
    "    else:\n",
    "        for frame in curr_frames:\n",
    "            img = draw(frame)\n",
    "            writer.write(img)\n",
    "    \n",
    "\n",
    "writer.release()       "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 10\n",
    "https://adventofcode.com/2021/day/10\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lines = puzzle.input_data.split('\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "line = lines[1]\n",
    "\n",
    "mapping = {\n",
    "    '[': ']',\n",
    "    '{': '}',\n",
    "    '(': ')',\n",
    "    '<': '>',\n",
    "}\n",
    "\n",
    "corrupted_scoring = {\n",
    "    ')': 3,\n",
    "    ']': 57,\n",
    "    '}': 1197,\n",
    "    '>': 25137,\n",
    "}\n",
    "\n",
    "def check_line(line):\n",
    "    stack = deque()\n",
    "    for char in line:\n",
    "        if char in mapping:\n",
    "            stack.append(char)\n",
    "        else:\n",
    "            top = stack.pop()\n",
    "            if mapping[top] != char:\n",
    "                return corrupted_scoring[char]\n",
    "    return 0\n",
    "\n",
    "answer_a = sum(check_line(line) for line in lines)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "incomplete_lines = [line for line in lines if check_line(line) == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "repair_scoring = {\n",
    "    ')': 1,\n",
    "    ']': 2,\n",
    "    '}': 3,\n",
    "    '>': 4,\n",
    "}\n",
    "\n",
    "def repair_line(line):\n",
    "    stack = deque()\n",
    "    for char in line:\n",
    "        if char in mapping:\n",
    "            stack.append(char)\n",
    "        else:\n",
    "            top = stack.pop()\n",
    "    \n",
    "    score = 0\n",
    "    while stack:\n",
    "        top = stack.pop()\n",
    "        score *= 5\n",
    "        score += repair_scoring[mapping[top]]\n",
    "    return score\n",
    "\n",
    "scores = sorted(repair_line(line) for line in incomplete_lines)\n",
    "answer_b = scores[len(scores) // 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 9\n",
    "https://adventofcode.com/2021/day/9\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "!pip install opencv-python matplotlib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cv2 as cv\n",
    "\n",
    "depth = np.array([[int(c) for c in line] for line in puzzle.input_data.split('\\n')]).astype('uint8')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib import pyplot as plt\n",
    "\n",
    "plt.rcParams[\"figure.figsize\"] = (10,10)\n",
    "\n",
    "plt.imshow(depth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "erosion = cv.erode(depth, cv.getStructuringElement(cv.MORPH_CROSS, (3, 3)), borderType=cv.BORDER_REFLECT)\n",
    "\n",
    "delta = depth - erosion\n",
    "minima = np.logical_and(delta == 0, depth != 9)\n",
    "\n",
    "answer_a = np.sum(depth[np.where(minima)] + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Quick and dirty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "from collections import defaultdict, Counter\n",
    "\n",
    "depth = defaultdict(lambda : defaultdict(lambda : 10))\n",
    "\n",
    "for y, line in enumerate(puzzle.input_data.split('\\n')):\n",
    "    for x, char in enumerate(line):\n",
    "        depth[x][y] = int(char)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "W, H = len(depth), len(depth[0])\n",
    "minima = []\n",
    "for x in range(W):\n",
    "    for y in range(H):\n",
    "        val = depth[x][y]\n",
    "        if val < depth[x-1][y] and val < depth[x][y-1] and val < depth[x+1][y] and val < depth[x][y+1]:\n",
    "            minima.append((x, y))\n",
    "\n",
    "answer_a = sum(depth[p[0]][p[1]]+1 for p in minima)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "\n",
    "class Bassin:\n",
    "    \n",
    "    def __init__(self, minimum):\n",
    "        self.points = {minimum}\n",
    "    \n",
    "    def expand(self):\n",
    "        \n",
    "        queue = deque(list(self.points))\n",
    "        \n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            \n",
    "            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                pos = (x+dx, y+dy)\n",
    "                if pos in self.points:\n",
    "                    continue\n",
    "                if depth[pos[0]][pos[1]] < 9 and depth[pos[0]][pos[1]] >= depth[x][y]:\n",
    "                    queue.append(pos)\n",
    "                    self.points.add(pos)\n",
    "    def size(self):\n",
    "        return len(self.points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "bassins = [Bassin(minimum) for minimum in minima]\n",
    "for bassin in bassins:\n",
    "    bassin.expand()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "answer_b = math.prod(sorted([bassin.size() for bassin in bassins], reverse=True)[:3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 8\n",
    "https://adventofcode.com/2021/day/8\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "lines = [line.split('|') for line in puzzle.input_data.split('\\n')]\n",
    "lines = [(s1.split(), s2.split()) for s1, s2 in lines]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "count = Counter()\n",
    "\n",
    "for _, output in lines:\n",
    "    for digit in output:\n",
    "        count[len(digit)] += 1\n",
    "        \n",
    "answer_a = count[2] + count[3] + count[4] + count[7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# I dont have time for this shit solution\n",
    "\n",
    "def outsmart_problem(patterns):\n",
    "    \n",
    "    voc = {}\n",
    "    pos = {}\n",
    "    \n",
    "    voc[1] = [el for el in patterns if len(el) == 2][0]\n",
    "    voc[7] = [el for el in patterns if len(el) == 3][0]\n",
    "    voc[4] = [el for el in patterns if len(el) == 4][0]\n",
    "    voc[8] = [el for el in patterns if len(el) == 7][0]\n",
    "    pos[0] = set(voc[7]) - set(voc[1])\n",
    "    voc[9] = [el for el in patterns if len(el) == 6 and len(set(el) - set(voc[4])) == 2][0]\n",
    "    pos[6] = set(voc[9]) - set(voc[4]) - pos[0]\n",
    "    voc[0] = [el for el in patterns if len(el) == 6 if el != voc[9] and set(voc[7]) <= set(el)][0]\n",
    "    voc[6] = [el for el in patterns if len(el) == 6 if el != voc[9] and el != voc[0]][0]\n",
    "    pos[3] = set(voc[6]) - set(voc[0])\n",
    "    pos[2] = set(voc[0]) - set(voc[6])\n",
    "    voc[5] = [el for el in patterns if len(el) == 5 and not (pos[2] <= set(el))][0]\n",
    "    pos[5] = set(voc[1]) - pos[2]\n",
    "    voc[3] = [el for el in patterns if len(el) == 5 and el != voc[5] and pos[5] <= set(el)][0]\n",
    "    voc[2] = [el for el in patterns if len(el) == 5 and el != voc[5] and not(pos[5] <= set(el))][0]\n",
    "    \n",
    "    code_map = {frozenset(v): k for k, v in voc.items()}\n",
    "    \n",
    "    return code_map\n",
    "\n",
    "def decode_line(line):\n",
    "    patterns, display = line\n",
    "    \n",
    "    code_map = outsmart_problem(patterns)\n",
    "    \n",
    "    nb = 0\n",
    "    for signal in display:\n",
    "        nb = nb*10 + code_map[frozenset(signal)]\n",
    "        \n",
    "    return nb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 7\n",
    "https://adventofcode.com/2021/day/7\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pos = [int(p) for p in puzzle.input_data.split(',')]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "mu = round(np.mean(pos))\n",
    "answer_a = min([sum([abs(mu + delta - p) for p in pos]) for delta in range(-1000, 1000)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cost(start, end):\n",
    "    dist = abs(start - end)\n",
    "    return (dist * (dist + 1)) / 2\n",
    "    \n",
    "answer_b = round(min([sum([cost(mu + delta, p) for p in pos]) for delta in range(-1000, 1000)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 6\n",
    "https://adventofcode.com/2021/day/6\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers = puzzle.input_data.split(',')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "def initialize(numbers):\n",
    "    count = Counter()\n",
    "\n",
    "    for nb in numbers:\n",
    "        count[int(nb)] += 1\n",
    "        \n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_age = 9\n",
    "\n",
    "def simulate(count, nb_days):\n",
    "    for day in range(nb_days):\n",
    "        new_count = Counter()\n",
    "        for age in range(max_age):\n",
    "            new_count[(age-1)%max_age] = count[age]\n",
    "        new_count[6] += count[0]\n",
    "        count = new_count\n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_a = sum(simulate(initialize(numbers), 80).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answer_b = sum(simulate(initialize(numbers), 256).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 5\n",
    "https://adventofcode.com/2021/day/5\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Line:\n",
    "    \n",
    "    def __init__(self, p0, p1):\n",
    "        self.x0 = int(p0[0])\n",
    "        self.y0 = int(p0[1])\n",
    "        self.x1 = int(p1[0])\n",
    "        self.y1 = int(p1[1])\n",
    "        \n",
    "        # not pleased with linf but l2 gives overlapping points due to discretization\n",
    "        self.len = max(abs(self.x1 - self.x0), abs(self.y1 - self.y0))\n",
    "\n",
    "        self.dx = (self.x1 - self.x0) / self.len\n",
    "        self.dy = (self.y1 - self.y0) / self.len\n",
    "        \n",
    "    def is_horizontal(self):\n",
    "        return self.y0 == self.y1\n",
    "    \n",
    "    def is_vertical(self):\n",
    "        return self.x0 == self.x1\n",
    "    \n",
    "    def __iter__(self):\n",
    "        self.__iter_ptr = 0\n",
    "        return self\n",
    "        \n",
    "    def __next__(self):\n",
    "        if self.__iter_ptr <= self.len:\n",
    "            vx = (self.__iter_ptr * self.dx) + self.x0\n",
    "            vy = (self.__iter_ptr * self.dy) + self.y0\n",
    "            self.__iter_ptr += 1\n",
    "            return (round(vx), round(vy))\n",
    "        else:\n",
    "            raise StopIteration\n",
    "            \n",
    "from collections import defaultdict, Counter\n",
    "\n",
    "def create_map(lines):\n",
    "\n",
    "    vents = defaultdict(Counter)\n",
    "\n",
    "    for line in lines:\n",
    "        for pt in line:\n",
    "            vents[pt[0]][pt[1]] += 1\n",
    "    \n",
    "    return vents\n",
    "\n",
    "def create_line(line):\n",
    "    p1, p2 = line.split(' -> ')\n",
    "    return Line(p1.split(','), p2.split(','))\n",
    "\n",
    "raw_lines = puzzle.input_data.split('\\n')\n",
    "lines = list(map(create_line, raw_lines))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "non_diag = list(filter(lambda l : l.is_horizontal() or l.is_vertical(), lines))\n",
    "vents = create_map(non_diag)\n",
    "answer_a = len([val for col in vents.values() for val in col.values() if val > 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vents = create_map(lines)\n",
    "answer_b = len([val for col in vents.values() for val in col.values() if val > 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### For fun"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# For fun\n",
    "!pip install seaborn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import seaborn as sns\n",
    "import numpy as np\n",
    "\n",
    "from matplotlib import pyplot as plt\n",
    "\n",
    "plt.rcParams[\"figure.figsize\"] = (15,15)\n",
    "\n",
    "def visualize(vents):\n",
    "    width = max(vents.keys()) + 10\n",
    "    height = max(max(col) for col in vents.values()) + 10\n",
    "\n",
    "    data = np.array([[vents[x][y] for y in range(height)] for x in range(width)])\n",
    "    \n",
    "    sns.heatmap(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "visualize(create_map(non_diag))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "visualize(create_map(lines))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 4\n",
    "https://adventofcode.com/2021/day/4\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install numpy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = puzzle.input_data.split('\\n\\n')\n",
    "numbers, boards = data[0], data[1:]\n",
    "numbers = [int(nb) for nb in numbers.split(',')]\n",
    "boards = list(map(lambda b: [int(loc.strip()) for loc in b.split()], boards))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "class Board:\n",
    "    def __init__(self, brd):\n",
    "        rows = np.array(brd).reshape(5, -1)\n",
    "        cols = rows.T\n",
    "\n",
    "        self.rows = [set(row) for row in rows]\n",
    "        self.cols = [set(col) for col in cols]\n",
    "        \n",
    "    def play(self, number):\n",
    "        self.rows = [set(row) - {number} for row in self.rows]\n",
    "        self.cols = [set(col) - {number} for col in self.cols]\n",
    "        \n",
    "    def has_won(self):\n",
    "        return any([not any(row) for row in self.rows]) or any([not any(col) for col in self.cols])\n",
    "    \n",
    "    def remaining_sum(self):\n",
    "        return sum(sum(row) for row in self.rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play(board, numbers):\n",
    "    brd = Board(board)\n",
    "    for idx, nb in enumerate(numbers):\n",
    "        brd.play(nb)\n",
    "        if brd.has_won():\n",
    "            break\n",
    "    return idx, brd\n",
    "\n",
    "games = sorted([play(board, numbers) for board in boards], key=lambda t: t[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "idx, board = games[0]\n",
    "answer_a = numbers[idx]*board.remaining_sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "idx, board = games[-1]\n",
    "answer_b = numbers[idx]*board.remaining_sum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 3\n",
    "https://adventofcode.com/2021/day/3\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 3)\n",
    "\n",
    "commands = puzzle.input_data.split('\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "acc = Counter()\n",
    "for cmd in commands:\n",
    "    acc += Counter({idx: int(val) for idx, val in enumerate(cmd)})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N, K = len(commands), len(commands[0])\n",
    "gamma = '0b'+''.join(str(int(acc[i] > N/2)) for i in range(K))\n",
    "gamma = int(gamma, 2)\n",
    "epsilon = (~gamma & 0xFFF)\n",
    "answer_a = gamma*epsilon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def filter_cmds(commands, pos, lcb):\n",
    "    acc = sum(int(cmd[pos]) for cmd in commands)\n",
    "    mc = (acc >= len(commands) / 2)\n",
    "    if lcb:\n",
    "        mc = not mc\n",
    "    mc = int(mc)\n",
    "    return [cmd for cmd in commands if int(cmd[pos]) == mc]\n",
    "\n",
    "def apply(cmds, lcb=False):\n",
    "    for pos in range(K):\n",
    "        cmds = filter_cmds(cmds, pos, lcb)\n",
    "        if len(cmds) == 1:\n",
    "            break\n",
    "    return cmds\n",
    "\n",
    "oxy = int(apply(commands.copy(), lcb=False)[0], 2)\n",
    "co2 = int(apply(commands.copy(), lcb=True)[0], 2)\n",
    "\n",
    "answer_b = oxy*co2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 2\n",
    "https://adventofcode.com/2021/day/2\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "\n",
    "puzzle = Puzzle(2021, 2)\n",
    "\n",
    "commands = puzzle.input_data.split('\\n')\n",
    "\n",
    "global_cmd = Counter()\n",
    "\n",
    "for cmd in commands:\n",
    "    word, amount = cmd.split()\n",
    "    global_cmd[word] += int(amount)\n",
    "    \n",
    "answer_a = global_cmd['forward']*(global_cmd['down'] - global_cmd['up'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "status = Counter()\n",
    "\n",
    "for cmd in commands:\n",
    "    word, amount = cmd.split()\n",
    "    amount = int(amount)\n",
    "    if word == \"forward\":\n",
    "        status['forward'] += amount\n",
    "        status['depth'] += amount*status['aim']\n",
    "    elif word == \"up\":\n",
    "        status['aim'] -= amount\n",
    "    else:\n",
    "        status['aim'] += amount\n",
    "        \n",
    "answer_b = status[\"forward\"]*status[\"depth\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 1\n",
    "https://adventofcode.com/2021/day/1\n",
    "### Part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle = Puzzle(2021, 1)\n",
    "\n",
    "depths = [int(depth) for depth in puzzle.input_data.split()]\n",
    "answer_a = len([d1 for d1, d2 in zip(depths[:-1], depths[1:]) if d2 > d1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_a = answer_a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "moving_average = [d1+d2+d3 for d1, d2, d3 in zip(depths[:-2], depths[1:-1], depths[2:])]\n",
    "answer_b = len([d1 for d1, d2 in zip(moving_average[:-1], moving_average[1:]) if d2 > d1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "puzzle.answer_b = answer_b"
   ]
  }
 ],
 "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}