aoc2020.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# AOC 2020\n",
    "\n",
    "Welcome to the Advent of Code 2020 !"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Basic configuration\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "! pip install -U advent-of-code-data numpy pandas"
   ]
  },
  {
   "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.models import Puzzle\n",
    "from collections import Counter, defaultdict\n",
    "from itertools import chain, product, combinations\n",
    "from numpy.typing import ArrayLike\n",
    "from pprint import pprint\n",
    "from queue import PriorityQueue\n",
    "from statistics import median\n",
    "from typing import Callable, Dict, Iterator, Mapping, Tuple\n",
    "import functools\n",
    "import math\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import sys\n",
    "import copy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from helpers.functions import *\n",
    "\n",
    "DIR = \"data/2020/\"\n",
    "load_day = functools.partial(load, DIR)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 1\n",
    "\n",
    "http://adventofcode.com/2020/day/1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = [int(x) for x in load_day(1)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for elem in content:\n",
    "    rest = 2020 - elem\n",
    "    if rest in content:\n",
    "        total = rest * elem\n",
    "        break\n",
    "    \n",
    "print(f'Answer 1: {total}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = len(content)\n",
    "done = False\n",
    "\n",
    "for idx, elem in enumerate(content):\n",
    "    if done:\n",
    "        break\n",
    "    for jdx in range(idx + 1, N):\n",
    "        if done:\n",
    "            break\n",
    "            \n",
    "        rest = 2020 - elem - content[jdx]\n",
    "        if rest in content:\n",
    "            total = rest * elem * content[jdx]\n",
    "            done = True\n",
    "            \n",
    "print(f\"Answer 2: {total}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 2\n",
    "\n",
    "http://adventofcode.com/2020/day/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nb_valids = 0\n",
    "\n",
    "rule = re.compile(r\"^(\\d+)-(\\d+) (\\w): (\\w+)$\")\n",
    "\n",
    "for entry in content:\n",
    "    g = rule.match(entry)\n",
    "    minimum, maximum, character, password = g.groups()\n",
    "    count = collections.Counter(password)\n",
    "\n",
    "    if int(minimum) <= count[character] <= int(maximum):\n",
    "        nb_valids += 1\n",
    "        \n",
    "print(f\"Answer 1: {nb_valids}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nb_valids = 0\n",
    "\n",
    "rule = re.compile(r\"^(\\d+)-(\\d+) (\\w): (\\w+)$\")\n",
    "\n",
    "for entry in content:\n",
    "    g = rule.match(entry)\n",
    "    pos1, pos2, character, password = g.groups()\n",
    "\n",
    "    if (password[int(pos1) - 1] == character) ^ (password[int(pos2) - 1] == character):\n",
    "        nb_valids += 1\n",
    "        \n",
    "print(f\"Answer 2: {nb_valids}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 3\n",
    "\n",
    "http://adventofcode.com/2020/day/3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(3)\n",
    "N, M = np.array([list(c) for c in content]).shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pos_x, pos_y = 0, 0\n",
    "tree_counter = 0\n",
    "\n",
    "while pos_y < N:\n",
    "    tree_counter += 1 if content[pos_y][pos_x % M] == \"#\" else 0\n",
    "    pos_x += 3\n",
    "    pos_y += 1\n",
    "\n",
    "print(f\"Answer 1: {tree_counter}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "slopes = [(1, 1), (3, 1), (5, 1), (7, 1), (1, 2)]\n",
    "tree_counters = np.zeros(5)\n",
    "\n",
    "for idx, slope in enumerate(slopes):\n",
    "    pos_x, pos_y = 0, 0\n",
    "    tree_counter = 0\n",
    "\n",
    "    while pos_y < N:\n",
    "        tree_counters[idx] += 1 if content[pos_y][pos_x % M] == \"#\" else 0\n",
    "        pos_x += slope[0]\n",
    "        pos_y += slope[1]\n",
    "    \n",
    "print(f\"Answer 2: {functools.reduce(lambda a, b: a * b, tree_counters):.0f}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 4\n",
    "\n",
    "http://adventofcode.com/2020/day/4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nb_valid = 0\n",
    "passport = set()\n",
    "\n",
    "for line in content:\n",
    "\n",
    "    if line.strip():\n",
    "        passport |= set([elem.split(\":\")[0] for elem in line.split(\" \")])\n",
    "    \n",
    "    else:\n",
    "        if len(passport) == 8 or len(passport) == 7 and \"cid\" not in passport:\n",
    "            nb_valid += 1\n",
    "        passport = set()\n",
    "\n",
    "print(f\"Answer 1: {nb_valid}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nb_valid = 0\n",
    "passport = set()\n",
    "\n",
    "for line in content:\n",
    "\n",
    "    if line.strip():\n",
    "        for key, val in [elem.split(\":\") for elem in line.split(\" \")]:\n",
    "            if key == \"byr\" and 1920 <= int(val) <= 2002:\n",
    "                passport.add(key)\n",
    "            elif key == \"iyr\" and 2010 <= int(val) <= 2020:\n",
    "                passport.add(key)\n",
    "            elif key == \"eyr\" and 2020 <= int(val) <= 2030:\n",
    "                passport.add(key)\n",
    "            elif key == \"hcl\" and re.match(r\"^#[0-9a-f]{6}$\", val):\n",
    "                passport.add(key)\n",
    "            elif key == \"ecl\" and val in [\"amb\", \"blu\", \"brn\", \"gry\", \"grn\", \"hzl\", \"oth\"]:\n",
    "                passport.add(key)\n",
    "            elif key == \"pid\" and re.match(r\"^[0-9]{9}$\", val):\n",
    "                passport.add(key)\n",
    "            elif key == \"hgt\":\n",
    "                rule = re.compile(r\"^(\\d+)(in|cm)$\")\n",
    "                m = rule.match(val)\n",
    "                if m and ((m.group(2) == \"cm\" and 150 <= int(m.group(1)) <= 193) or (m.group(2) == \"in\" and 59 <= int(m.group(1)) <= 76)):\n",
    "                    passport.add(key)\n",
    "    \n",
    "    else:\n",
    "        if len(passport) == 8 or len(passport) == 7 and \"cid\" not in passport:\n",
    "            nb_valid += 1\n",
    "        passport = set()\n",
    "\n",
    "print(f\"Answer 2: {nb_valid}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 5\n",
    "\n",
    "http://adventofcode.com/2020/day/5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "seats = []\n",
    "\n",
    "for line in content:\n",
    "    seats.append(int(line.replace('F', \"0\").replace('B', \"1\").replace('L', \"0\"). replace('R', \"1\"), 2))\n",
    "        \n",
    "seats.sort()\n",
    "print(f\"Answer 1: {seats[-1]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for idx, s in enumerate(seats):\n",
    "    if idx and s != seats[idx - 1] + 1:\n",
    "        print(f\"Answer 2: {s - 1}\")\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 6\n",
    "\n",
    "http://adventofcode.com/2020/day/6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "total = 0\n",
    "\n",
    "answers = set()\n",
    "\n",
    "for line in content:\n",
    "    if line:\n",
    "        answers |= set(list(line))\n",
    "    else:\n",
    "        total += len(answers)\n",
    "        answers = set()\n",
    "        \n",
    "total += len(answers)\n",
    "print(f\"Answer 1: {total}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "total = 0\n",
    "\n",
    "answers = None\n",
    "\n",
    "for line in content:\n",
    "    if line:\n",
    "        if answers is not None: \n",
    "            answers &= set(list(line))\n",
    "        else:\n",
    "            answers = set(list(line))\n",
    "    else:\n",
    "        total += len(answers)\n",
    "        answers = None\n",
    "        \n",
    "total += len(answers)\n",
    "print(f\"Answer 2: {total}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 7\n",
    "\n",
    "http://adventofcode.com/2020/day/7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rules = collections.defaultdict(dict)\n",
    "inverse_rules = collections.defaultdict(dict)\n",
    "\n",
    "for line in content:\n",
    "    key, val = line.split(\"contain\")\n",
    "    key = key[:-6]  # remove \" bags\"\n",
    "\n",
    "    if \"no other bags\" not in val:\n",
    "        for elem in val[1:-1].split(\", \"):\n",
    "            nb, *color, bags = elem.split(\" \")\n",
    "            rules[key][\" \".join(color)] = int(nb)\n",
    "            inverse_rules[\" \".join(color)][key] = 1/int(nb)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "possibilities = set()\n",
    "queue = [\"shiny gold\"]\n",
    "\n",
    "while queue:\n",
    "    elem = queue.pop(0)\n",
    "    pot = list(inverse_rules[elem].keys())\n",
    "    possibilities |= set(pot)\n",
    "    queue += pot\n",
    "    \n",
    "print(f\"Answer 1: {len(possibilities)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nb_bags = -1\n",
    "\n",
    "queue = [(1, \"shiny gold\")]\n",
    "\n",
    "while queue:\n",
    "    quantity, color = queue.pop(0)\n",
    "    nb_bags += quantity\n",
    "    \n",
    "    for pk, pv in rules[color].items():\n",
    "        queue.append((quantity * pv, pk))\n",
    "        \n",
    "print(f\"Answer 2: {nb_bags}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 8\n",
    "\n",
    "http://adventofcode.com/2020/day/8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def machine(modify=None):\n",
    "    read_lines = []\n",
    "    to_read = 0\n",
    "\n",
    "    accumulator = 0\n",
    "\n",
    "    while to_read not in read_lines and to_read < len(content):\n",
    "        action, value = content[to_read].split(\" \")\n",
    "        read_lines.append(to_read)\n",
    "\n",
    "        if action == \"acc\":\n",
    "            accumulator += int(value)\n",
    "            to_read += 1\n",
    "\n",
    "        elif action == \"jmp\":\n",
    "             to_read += int(value) if modify != to_read else 1\n",
    "\n",
    "        elif action == \"nop\":\n",
    "            to_read += 1 if modify != to_read else int(value)\n",
    "\n",
    "        else:\n",
    "            print(action)\n",
    "            break\n",
    "            \n",
    "    return to_read == len(content), accumulator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "_, score = machine()\n",
    "print(f\"Answer 1: {score}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for attempt in range(len(content)):\n",
    "    success, score = machine(modify=attempt)\n",
    "    \n",
    "    if success:\n",
    "        break\n",
    "        \n",
    "print(f\"Answer 2: {score}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 9\n",
    "\n",
    "http://adventofcode.com/2020/day/9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = list(map(int, load_day(9)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "idx = 25\n",
    "\n",
    "preamble = content[:idx]\n",
    "sum_cand = [preamble[i] + preamble[j] for i in range(idx) for j in range(i + 1, idx)]\n",
    "\n",
    "\n",
    "\n",
    "while True:\n",
    "    elem = content[idx]\n",
    "    \n",
    "    if elem not in sum_cand:\n",
    "        break\n",
    "    \n",
    "    preamble.pop(0)\n",
    "    sum_cand = sum_cand[24:]  # those related to the removed preamble\n",
    "    pos = -1\n",
    "    for i, p in enumerate(preamble):\n",
    "        pos += 24 - i\n",
    "        sum_cand.insert(pos, p + elem)\n",
    "\n",
    "    preamble.append(elem)\n",
    "    idx += 1\n",
    "\n",
    "print(f\"Answer 1: {elem}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "first_idx, last_idx, cur_sum = 0, 0, content[0]  # sum from first to last (inc.)\n",
    "first_too_much = False\n",
    "\n",
    "while cur_sum != elem:\n",
    "    if cur_sum < elem:  # if sum is not enough, add next element\n",
    "        last_idx += 1\n",
    "        cur_sum += content[last_idx]\n",
    "        first_too_much = True\n",
    "        \n",
    "    elif cur_sum > elem:  # otherwise, if just crossed the target, remove the first element\n",
    "        if first_too_much:\n",
    "            cur_sum -= content[first_idx]\n",
    "            first_idx += 1\n",
    "            first_too_much = False\n",
    "        else:  # if still too much, remove the last element next time\n",
    "            cur_sum -= content[last_idx]\n",
    "            last_idx -= 1\n",
    "            \n",
    "print(f\"Answer 2: {min(content[first_idx:last_idx + 1]) + max(content[first_idx:last_idx + 1])}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 10\n",
    "\n",
    "http://adventofcode.com/2020/day/10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = list(map(int, load_day(10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ordered = sorted(content)\n",
    "\n",
    "# Add 0 and the output joltage (max + 3)\n",
    "diffs = collections.Counter([y - x for (x, y) in zip([0] + ordered, ordered + [ordered[-1] + 3])])\n",
    "\n",
    "print(f\"Answer 1: {diffs[1] * diffs[3]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "paths = collections.defaultdict(int)\n",
    "paths[0] = 1\n",
    "\n",
    "for target in ordered:\n",
    "    paths[target] = paths[target - 1] + paths[target - 2] + paths[target - 3]\n",
    "    \n",
    "print(f\"Answer 2: {paths[ordered[-1]]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 11\n",
    "\n",
    "http://adventofcode.com/2020/day/11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(11)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "seats = collections.defaultdict(dict)\n",
    "seats_l = []\n",
    "\n",
    "class Seat:\n",
    "    pos_x, pos_y = None, None\n",
    "    previous_state, next_state = False, None\n",
    "    \n",
    "    def __init__(self, pos_x, pos_y):\n",
    "        self.pos_x = pos_x\n",
    "        self.pos_y = pos_y\n",
    "        self.neighbors = []\n",
    "        self.visible_neighbors = []\n",
    "        \n",
    "        seats[pos_x][pos_y] = self\n",
    "        seats_l.append(self)\n",
    "        \n",
    "        # Set neighbors\n",
    "        for (cand_x, cand_y) in [(pos_x + 1, pos_y - 1), (pos_x, pos_y - 1), (pos_x - 1, pos_y - 1), (pos_x - 1, pos_y)]:\n",
    "            other_seat = seats[cand_x].get(cand_y)\n",
    "            if other_seat:\n",
    "                self.neighbors.append(other_seat)\n",
    "                other_seat.neighbors.append(self)\n",
    "                \n",
    "        # Set visible neighbors\n",
    "        for (delta_x, delta_y) in [(1, -1), (0, -1), (-1, -1), (-1, 0)]:\n",
    "            found_something = False\n",
    "            cand_x, cand_y = pos_x, pos_y\n",
    "            while not found_something and cand_x + delta_x >= 0 and cand_y + delta_y >= 0:\n",
    "                cand_x += delta_x\n",
    "                cand_y += delta_y\n",
    "                \n",
    "                other_seat = seats[cand_x].get(cand_y)\n",
    "                \n",
    "                if other_seat:\n",
    "                    found_something = True\n",
    "                    self.visible_neighbors.append(other_seat)\n",
    "                    other_seat.visible_neighbors.append(self)\n",
    "        \n",
    "    def nb_occupied_neighbors(self):\n",
    "        nb_occupied = 0\n",
    "        for s in self.neighbors:\n",
    "            nb_occupied += 1 if s.previous_state else 0\n",
    "        return nb_occupied\n",
    "    \n",
    "    def nb_occupied_visible_neighbors(self):\n",
    "        nb_occupied = 0\n",
    "        for s in self.visible_neighbors:\n",
    "            nb_occupied += 1 if s.previous_state else 0\n",
    "        return nb_occupied\n",
    "    \n",
    "    def __str__(self):\n",
    "        return f\"SEAT ({self.pos_x}, {self.pos_y}): #{len(self.neighbors)}, #{len(self.visible_neighbors)}\"\n",
    "\n",
    "def nb_occupied_seats():\n",
    "    nb_occupied = 0\n",
    "    for seat in seats_l:\n",
    "        nb_occupied += 1 if seat.previous_state else 0\n",
    "            \n",
    "    return nb_occupied\n",
    "\n",
    "def print_seats():\n",
    "    for i in range(10):\n",
    "        for j in range(10):\n",
    "            if i not in seats[j]:\n",
    "                print(\".\", end=\"\")\n",
    "            else:\n",
    "                print(\"#\" if seats[j][i].previous_state else \"L\", end=\"\")\n",
    "                \n",
    "        print()\n",
    "\n",
    "for pos_y, line in enumerate(content):\n",
    "    for pos_x, elem in enumerate(line):\n",
    "        if elem == \"L\":\n",
    "            s = Seat(pos_x, pos_y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def step():\n",
    "    changes = False\n",
    "    \n",
    "    for seat in seats_l:\n",
    "        if seat.previous_state and seat.nb_occupied_neighbors() >= 4:\n",
    "            seat.next_state = False\n",
    "            changes = True\n",
    "        elif not seat.previous_state and seat.nb_occupied_neighbors() == 0:\n",
    "            seat.next_state = True\n",
    "            changes = True\n",
    "        else:\n",
    "            seat.next_state = seat.previous_state\n",
    "\n",
    "    for seat in seats_l:\n",
    "        seat.previous_state = seat.next_state\n",
    "        seat.next_state = None\n",
    "        \n",
    "    return changes\n",
    "\n",
    "changes = True\n",
    "\n",
    "while changes:    \n",
    "    changes = step()\n",
    "    \n",
    "print(f\"Answer 1: {nb_occupied_seats()}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# If you ran step(), reinitialize\n",
    "\n",
    "def step2():\n",
    "    changes = False\n",
    "    \n",
    "    for seat in seats_l:\n",
    "        if seat.previous_state and seat.nb_occupied_visible_neighbors() >= 5:\n",
    "            seat.next_state = False\n",
    "            changes = True\n",
    "        elif not seat.previous_state and seat.nb_occupied_visible_neighbors() == 0:\n",
    "            seat.next_state = True\n",
    "            changes = True\n",
    "        else:\n",
    "            seat.next_state = seat.previous_state\n",
    "\n",
    "    for seat in seats_l:\n",
    "        seat.previous_state = seat.next_state\n",
    "        seat.next_state = None\n",
    "        \n",
    "    return changes\n",
    "\n",
    "changes = True\n",
    "\n",
    "while changes:\n",
    "    changes = step2()\n",
    "    \n",
    "print(f\"Answer 2: {nb_occupied_seats()}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 12\n",
    "\n",
    "http://adventofcode.com/2020/day/12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pos = [0, 0]\n",
    "direct = \"E\"\n",
    "\n",
    "DIRECTIONS = [\"E\", \"S\", \"W\", \"N\"]\n",
    "\n",
    "def manathan_dist(point):\n",
    "    return abs(point[0]) + abs(point[1])\n",
    "\n",
    "\n",
    "for line in content:\n",
    "    task, amount = line[0], int(line[1:])\n",
    "    if task == \"F\":\n",
    "        task = direct\n",
    "        \n",
    "    if task == \"N\":\n",
    "        pos[1] += amount\n",
    "    elif task == \"S\":\n",
    "        pos[1] -= amount\n",
    "    elif task == \"E\":\n",
    "        pos[0] += amount\n",
    "    elif task == \"W\":\n",
    "        pos[0] -= amount\n",
    "    elif task == \"L\":\n",
    "        idx = (DIRECTIONS.index(direct) - amount // 90) % len(DIRECTIONS)\n",
    "        direct = DIRECTIONS[idx]\n",
    "    elif task == \"R\":\n",
    "        idx = (DIRECTIONS.index(direct) + amount // 90) % len(DIRECTIONS)\n",
    "        direct = DIRECTIONS[idx]\n",
    "        \n",
    "print(f\"Answer 1: {manathan_dist(pos)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pos = [0, 0]\n",
    "waypoint = [10, 1]\n",
    "\n",
    "def turn_clockwise90():\n",
    "    tmp = -waypoint[0]\n",
    "    waypoint[0] = waypoint[1]\n",
    "    waypoint[1] = tmp\n",
    "    \n",
    "\n",
    "for line in content:\n",
    "    task, amount = line[0], int(line[1:])\n",
    "        \n",
    "    if task == \"N\":\n",
    "        waypoint[1] += amount\n",
    "    elif task == \"S\":\n",
    "        waypoint[1] -= amount\n",
    "    elif task == \"E\":\n",
    "        waypoint[0] += amount\n",
    "    elif task == \"W\":\n",
    "        waypoint[0] -= amount\n",
    "    elif task == \"L\":\n",
    "        for i in range((-amount % 360) // 90):\n",
    "            turn_clockwise90()\n",
    "    elif task == \"R\":\n",
    "        for i in range(amount // 90):\n",
    "            turn_clockwise90()\n",
    "    elif task == \"F\":\n",
    "        pos[0] += amount * waypoint[0]\n",
    "        pos[1] += amount * waypoint[1]\n",
    "        \n",
    "print(f\"Answer 2: {manathan_dist(pos)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 13\n",
    "\n",
    "http://adventofcode.com/2020/day/13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(13)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "arrival_time = int(content[0])\n",
    "buses = set([int(x) for x in content[1].split(\",\") if x != \"x\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "min_time, bus_id = None, None\n",
    "\n",
    "for bus in buses:\n",
    "    waiting_time = -arrival_time % bus\n",
    "    \n",
    "    if not min_time or waiting_time < min_time:\n",
    "        min_time = waiting_time\n",
    "        bus_id = bus\n",
    "\n",
    "print(f\"Answer 1: {bus_id * min_time}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n = functools.reduce(lambda x, y: x * y, buses, 1)\n",
    "constraints = [(idx, int(bus)) for idx, bus in enumerate(content[1].split(\",\")) if bus != \"x\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def euclid(a, b):\n",
    "    \"\"\"Return gcd(a, b), u, v such tht au + bv = gcd(a, b)\"\"\"\n",
    "    def eucl(r, u, v, r_prim, u_prim, v_prim):\n",
    "        return (r, u, v) if r_prim == 0 else eucl(r_prim, u_prim, v_prim, r - (r // r_prim) * r_prim, u - (r // r_prim) * u_prim, v - (r // r_prim) * v_prim)\n",
    "\n",
    "    return eucl(a, 1, 0, b, 0, 1)\n",
    "\n",
    "res = 0\n",
    "for c in constraints:\n",
    "    n_hat = n // c[1]\n",
    "    *_, v = euclid(c[1], n_hat)\n",
    "    res -= c[0] * v * n_hat\n",
    "\n",
    "    \n",
    "print(f\"Answer 2: {res % n}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 14\n",
    "\n",
    "http://adventofcode.com/2020/day/14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(14)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mask_rule = re.compile(r\"^mask = (.+)$\")\n",
    "mem_rule = re.compile(r\"^mem\\[(\\d+)\\] = (\\d+)$\")\n",
    "\n",
    "mem = collections.defaultdict(int)\n",
    "\n",
    "def get_masked_value(mask, val):\n",
    "    res = [val[idx] if char == \"X\" else char for idx, char in enumerate(mask)]\n",
    "        \n",
    "    return int(\"\".join(res), 2)\n",
    "\n",
    "for line in content:\n",
    "    mask_m = mask_rule.match(line)\n",
    "    mem_m = mem_rule.match(line)\n",
    "    \n",
    "    if mask_m:\n",
    "        mask = mask_m.group(1)\n",
    "    elif mem_m:\n",
    "        idx, val = [int(x) for x in rule.match(line).groups()]\n",
    "        mem[idx] = get_masked_value(mask, f\"{val:036b}\")\n",
    "      \n",
    "sum = functools.reduce(lambda x, y: x + y, mem.values(), 0)\n",
    "print(f\"Answer 1: {sum}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mem = collections.defaultdict(int)\n",
    "\n",
    "def get_masked_value(mask, val):    \n",
    "    indices = []\n",
    "\n",
    "    res = [val[idx] if char == \"0\" else char for idx, char in enumerate(mask)]\n",
    "    \n",
    "    nb_x = res.count('X')\n",
    "    \n",
    "    for i in range(pow(2, nb_x)):\n",
    "        x_substitutes = ('0' * nb_x + f\"{i:b}\")[-nb_x:]\n",
    "        elem = \"\".join(res)\n",
    "        \n",
    "        for c in x_substitutes:\n",
    "            elem = elem.replace(\"X\", c, 1)\n",
    "        \n",
    "        indices.append(elem)\n",
    "    return indices\n",
    "\n",
    "\n",
    "for line in content:\n",
    "    mask_m = mask_rule.match(line)\n",
    "    mem_m = mem_rule.match(line)\n",
    "    \n",
    "    if mask_m:\n",
    "        mask = mask_m.group(1)\n",
    "    elif mem_m:\n",
    "        idx, val = [int(x) for x in rule.match(line).groups()]\n",
    "        for ix in get_masked_value(mask, f\"{idx:036b}\"):\n",
    "            mem[ix] = val\n",
    "    else:\n",
    "        raise\n",
    "      \n",
    "functools.reduce(lambda x, y: x + y, mem.values(), 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 15\n",
    "\n",
    "http://adventofcode.com/2020/day/15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def init():\n",
    "    last_occurance = collections.defaultdict(int)\n",
    "\n",
    "    last_occurance[18] = 1\n",
    "    last_occurance[11] = 2\n",
    "    last_occurance[9] = 3\n",
    "    last_occurance[0] = 4\n",
    "    last_occurance[5] = 5\n",
    "\n",
    "    last_number = 1\n",
    "    nth_number = 6\n",
    "    \n",
    "    return last_occurance, last_number, nth_number\n",
    "\n",
    "\n",
    "def challenge(last_occurance, last_number, nth_number, stop=2020):\n",
    "\n",
    "    while nth_number < stop:\n",
    "        next_number = nth_number - last_occurance[last_number] if last_occurance[last_number] else 0\n",
    "        last_occurance[last_number] = nth_number\n",
    "        nth_number += 1\n",
    "        last_number = next_number\n",
    "    \n",
    "    return next_number\n",
    "\n",
    "print(f\"Anwser 1: {challenge(*init())}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(f\"Anwser 2: {challenge(*init(), 30000000)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 16\n",
    "\n",
    "http://adventofcode.com/2020/day/16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rule = re.compile(r\"^([a-z\\s]+): (\\d+)-(\\d+) or (\\d+)-(\\d+)$\")\n",
    "section = 0\n",
    "\n",
    "count = 0\n",
    "rules = []\n",
    "valid_tickets = []\n",
    "min_val, max_val = None, None\n",
    "\n",
    "for line in content:\n",
    "    if section == 0:\n",
    "        m = rule.match(line)\n",
    "        if m:\n",
    "            rules.append([int(x) for x in m.groups()[1:]])\n",
    "        \n",
    "        if \"your ticket\" in line:\n",
    "            section = 1\n",
    "\n",
    "            min_val = min([elem[0] for elem in rules])\n",
    "            max_val = max([elem[-1] for elem in rules])\n",
    "        \n",
    "    elif section == 1:    \n",
    "        if \"nearby tickets\" in line:\n",
    "            section = 2\n",
    "        elif line:\n",
    "            valid_tickets.append(line)\n",
    "        \n",
    "    elif section == 2:\n",
    "        invalid_values = [int(x) for x in line.split(\",\") if int(x) < min_val or int(x) > max_val]\n",
    "        \n",
    "        if invalid_values:\n",
    "            count = functools.reduce(lambda x, y: x + y, invalid_values, count)\n",
    "        else:\n",
    "            valid_tickets.append(line)\n",
    "\n",
    "print(f\"Answer 1: {count}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rules_fullfiled = []\n",
    "\n",
    "for i in range(20):\n",
    "    rules_fullfiled.append(set(range(20)))\n",
    "\n",
    "for ticket in valid_tickets:\n",
    "    for idx, x in enumerate(ticket.split(\",\")):\n",
    "        rules_broken = set()\n",
    "        value = int(x)\n",
    "        for rule_idx in rules_fullfiled[idx]:\n",
    "            if value < rules[rule_idx][0] or value > rules[rule_idx][3] or rules[rule_idx][1] < value < rules[rule_idx][2]:\n",
    "                rules_broken.add(rule_idx)\n",
    "        rules_fullfiled[idx] -= rules_broken\n",
    "\n",
    "mappings = {k:rules_fullfiled[k] for k in range(20)}\n",
    "mappings = dict(sorted(mappings.items(), key=lambda x: len(x[1])))\n",
    "\n",
    "mapping, used = {}, set()\n",
    "\n",
    "for k, v in mappings.items():\n",
    "    mapping[k] = next(iter(v - used))\n",
    "    used.add(mapping[k])\n",
    "\n",
    "my_ticket = [int(x) for x in valid_tickets[0].split(\",\")]\n",
    "prod = 1\n",
    "for k, v in mapping.items():\n",
    "    if v < 6:\n",
    "        prod *= my_ticket[k]\n",
    "\n",
    "print(f\"Answer 2: {prod}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 17\n",
    "\n",
    "http://adventofcode.com/2020/day/17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(17)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cubes = collections.defaultdict(bool)\n",
    "\n",
    "min_x = max_x = min_y = max_y = min_z = max_z = 0\n",
    "max_y = len(content)\n",
    "max_x = len(content[0])\n",
    "\n",
    "def compute_value(cubes, x, y, z):\n",
    "    count = 0\n",
    "    for z_idx in range(z - 1, z + 2):\n",
    "        for y_idx in range(y - 1, y + 2):\n",
    "            for x_idx in range(x - 1, x + 2):\n",
    "                if z != z_idx or y != y_idx or x != x_idx:\n",
    "                    count += 1 if cubes[(x_idx, y_idx, z_idx)] else 0\n",
    "    return count == 3 or (count == 2 and cubes[(x, y, z)])\n",
    "\n",
    "def print_cubes(cubes):\n",
    "    for z in range(min_z, max_z + 1):\n",
    "        print(f\"Z = {z}\")\n",
    "        \n",
    "        for y in range(min_y, max_y + 1):\n",
    "            for x in range(min_x, max_x + 1):\n",
    "                print(\"#\" if cubes[(x, y, z)] else \".\", end=\"\")\n",
    "            print()\n",
    "\n",
    "for y, line in enumerate(content):\n",
    "    for x, char in enumerate(line):\n",
    "        cubes[(x, y, 0)] = char == \"#\"\n",
    "        \n",
    "for loop in range(6):\n",
    "    next_cubes = collections.defaultdict(bool)\n",
    "\n",
    "    for z in range(min_z - 1, max_z + 2):\n",
    "        for y in range(min_y - 1, max_y + 2):\n",
    "            for x in range(min_x - 1, max_x + 2):\n",
    "                value = compute_value(cubes, x, y, z)\n",
    "                if value:\n",
    "                    if x < min_x:\n",
    "                        min_x = x\n",
    "                    elif x > max_x:\n",
    "                        max_x = x\n",
    "                    if y < min_y:\n",
    "                        min_y = y\n",
    "                    elif y > max_y:\n",
    "                        max_y = y\n",
    "                    if z < min_z:\n",
    "                        min_z = z\n",
    "                    elif z > max_z:\n",
    "                        max_z = z\n",
    "                next_cubes[(x, y, z)] = value\n",
    "    cubes = next_cubes\n",
    "\n",
    "total = 0\n",
    "for v in next_cubes.values():\n",
    "    total += 1 if v else 0\n",
    "    \n",
    "print(f\"Answer 1: {total}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cubes = collections.defaultdict(bool)\n",
    "\n",
    "min_x = max_x = min_y = max_y = min_z = max_z = min_w = max_w = 0\n",
    "max_y = len(content)\n",
    "max_x = len(content[0])\n",
    "\n",
    "def compute_value(cubes, x, y, z, w):\n",
    "    count = 0\n",
    "    for w_idx in range(w - 1, w + 2):\n",
    "        for z_idx in range(z - 1, z + 2):\n",
    "            for y_idx in range(y - 1, y + 2):\n",
    "                for x_idx in range(x - 1, x + 2):\n",
    "                    if w != w_idx or z != z_idx or y != y_idx or x != x_idx:\n",
    "                        count += 1 if cubes[(x_idx, y_idx, z_idx, w_idx)] else 0\n",
    "    return count == 3 or (count == 2 and cubes[(x, y, z, w)])\n",
    "\n",
    "def print_cubes(cubes):\n",
    "    for w in range(min_w, max_w + 1):\n",
    "        for z in range(min_z, max_z + 1):\n",
    "            print(f\"z = {z}, w = {w}\")\n",
    "\n",
    "            for y in range(min_y, max_y + 1):\n",
    "                for x in range(min_x, max_x + 1):\n",
    "                    print(\"#\" if cubes[(x, y, z, w)] else \".\", end=\"\")\n",
    "                print()\n",
    "\n",
    "for y, line in enumerate(content):\n",
    "    for x, char in enumerate(line):\n",
    "        cubes[(x, y, 0, 0)] = char == \"#\"\n",
    "        \n",
    "for loop in range(6):\n",
    "    next_cubes = collections.defaultdict(bool)\n",
    "\n",
    "    for w in range(min_w - 1, max_w + 2):\n",
    "        for z in range(min_z - 1, max_z + 2):\n",
    "            for y in range(min_y - 1, max_y + 2):\n",
    "                for x in range(min_x - 1, max_x + 2):\n",
    "                    value = compute_value(cubes, x, y, z, w)\n",
    "                    if value:\n",
    "                        if x < min_x:\n",
    "                            min_x = x\n",
    "                        elif x > max_x:\n",
    "                            max_x = x\n",
    "                        if y < min_y:\n",
    "                            min_y = y\n",
    "                        elif y > max_y:\n",
    "                            max_y = y\n",
    "                        if z < min_z:\n",
    "                            min_z = z\n",
    "                        elif z > max_z:\n",
    "                            max_z = z\n",
    "                        if w < min_w:\n",
    "                            min_w = w\n",
    "                        elif w > max_w:\n",
    "                            max_w = w\n",
    "                    next_cubes[(x, y, z, w)] = value\n",
    "    cubes = next_cubes\n",
    "\n",
    "total = 0\n",
    "for v in next_cubes.values():\n",
    "    total += 1 if v else 0\n",
    "    \n",
    "print(f\"Answer 2: {total}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 18\n",
    "\n",
    "http://adventofcode.com/2020/day/18"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(18)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def left_compute(line, pointer=0, accums=None, ops=None):\n",
    "    if accums is None:\n",
    "        return left_compute(line, pointer, [0], ops)\n",
    "    \n",
    "    if ops is None:\n",
    "        return left_compute(line, pointer, accums, [])\n",
    "        \n",
    "    if pointer >= len(line):\n",
    "        return accums[0]\n",
    "    \n",
    "    if line[pointer] == \"(\":\n",
    "        accums.append(0)\n",
    "        ops.append(\"+\")\n",
    "        return left_compute(line, pointer+1, accums, ops)\n",
    "        \n",
    "    elif line[pointer] == \"+\":\n",
    "        try:\n",
    "            accums[-1] += int(line[pointer + 1])\n",
    "            return left_compute(line, pointer+2, accums, ops)\n",
    "        except ValueError:\n",
    "            ops.append(\"+\")\n",
    "            accums.append(0)\n",
    "            return left_compute(line, pointer+2, accums, ops)\n",
    "        \n",
    "    elif line[pointer] == \"*\":\n",
    "        try:\n",
    "            accums[-1] *= int(line[pointer + 1])\n",
    "            return left_compute(line, pointer+2, accums, ops)\n",
    "        except ValueError:\n",
    "            ops.append(\"*\")\n",
    "            accums.append(0)\n",
    "            return left_compute(line, pointer+2, accums, ops)\n",
    "        \n",
    "    elif line[pointer] == \")\":\n",
    "        accums[-2] = eval(f\"{accums[-2]}{ops.pop()}{accums[-1]}\")\n",
    "        accums.pop()\n",
    "        return left_compute(line, pointer+1, accums, ops)\n",
    "        \n",
    "    else:\n",
    "        if accums[-1] == 0:\n",
    "            accums[-1] = int(line[pointer])\n",
    "            return left_compute(line, pointer+1, accums, ops)\n",
    "\n",
    "    \n",
    "\n",
    "total = 0\n",
    "for line in content:\n",
    "    total += left_compute(line.replace(\" \", \"\"))\n",
    "\n",
    "print(f\"Answer 1: {total}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Integer(int):\n",
    "    \n",
    "    def __add__(self, other):\n",
    "        return Integer(int(self) * int(other))\n",
    "\n",
    "    def __mul__(self, other):\n",
    "        return Integer(int(self) + int(other))\n",
    "\n",
    "total = 0\n",
    "for line in content:\n",
    "    line = re.sub(r'(\\d)', r'Integer(\\1)', line.replace(\"*\", \"&&\").replace(\"+\", \"*\").replace(\"&&\", \"+\"))\n",
    "    total += int(eval(line))\n",
    "\n",
    "print(f\"Answer 2: {total}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 19\n",
    "\n",
    "http://adventofcode.com/2020/day/19"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rules = defaultdict(set)\n",
    "queue = []\n",
    "\n",
    "content = \"\"\"42: 9 14 | 10 1\n",
    "9: 14 27 | 1 26\n",
    "10: 23 14 | 28 1\n",
    "1: \"a\"\n",
    "11: 42 31\n",
    "5: 1 14 | 15 1\n",
    "19: 14 1 | 14 14\n",
    "12: 24 14 | 19 1\n",
    "16: 15 1 | 14 14\n",
    "31: 14 17 | 1 13\n",
    "6: 14 14 | 1 14\n",
    "2: 1 24 | 14 4\n",
    "0: 8 11\n",
    "13: 14 3 | 1 12\n",
    "15: 1 | 14\n",
    "17: 14 2 | 1 7\n",
    "23: 25 1 | 22 14\n",
    "28: 16 1\n",
    "4: 1 1\n",
    "20: 14 14 | 1 15\n",
    "3: 5 14 | 16 1\n",
    "27: 1 6 | 14 18\n",
    "14: \"b\"\n",
    "21: 14 1 | 1 14\n",
    "25: 1 1 | 1 14\n",
    "22: 14 14\n",
    "8: 42\n",
    "26: 14 22 | 1 20\n",
    "18: 15 15\n",
    "7: 14 5 | 1 21\n",
    "24: 14 1\n",
    "\n",
    "abbbbbabbbaaaababbaabbbbabababbbabbbbbbabaaaa\n",
    "bbabbbbaabaabba\n",
    "babbbbaabbbbbabbbbbbaabaaabaaa\n",
    "aaabbbbbbaaaabaababaabababbabaaabbababababaaa\n",
    "bbbbbbbaaaabbbbaaabbabaaa\n",
    "bbbababbbbaaaaaaaabbababaaababaabab\n",
    "ababaaaaaabaaab\n",
    "ababaaaaabbbaba\n",
    "baabbaaaabbaaaababbaababb\n",
    "abbbbabbbbaaaababbbbbbaaaababb\n",
    "aaaaabbaabaaaaababaa\n",
    "aaaabbaaaabbaaa\n",
    "aaaabbaabbaaaaaaabbbabbbaaabbaabaaa\n",
    "babaaabbbaaabaababbaabababaaab\n",
    "aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba\n",
    "\"\"\"\n",
    "content = content.split(\"\\n\")\n",
    "content = load_day(19)\n",
    "\n",
    "while True:\n",
    "    rule = content.pop(0)\n",
    "    \n",
    "    if not rule:\n",
    "        break\n",
    "\n",
    "    idx, elems = rule.split(\": \")\n",
    "\n",
    "    if '\"' in elems:\n",
    "        rules[int(idx)] = {elems[1]}\n",
    "        queue.append(int(idx))\n",
    "    else:\n",
    "        rules[int(idx)] = {tuple(int(x) for x in path.split(\" \")) for path in elems.split(\" | \")}\n",
    "        \n",
    "texts = content"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "while queue:\n",
    "    q_idx = queue[0]\n",
    "    \n",
    "    # print(\"Q\", q_idx)\n",
    "\n",
    "    for idx, rule_set in rules.items():\n",
    "        # print(\"RS\", idx, rule_set)\n",
    "        new_rules_set = set()\n",
    "        for rule in rule_set:\n",
    "            # print(\"R\", rule)\n",
    "            new_rule_possibilities = set()\n",
    "            indices_to_replace = [i for i, x in enumerate(rule) if x == q_idx]\n",
    "            \n",
    "            # print(\"ITR\", indices_to_replace)\n",
    "            \n",
    "            for combination in product(rules[q_idx], repeat=len(indices_to_replace)):\n",
    "                # print(\"C\", combination)\n",
    "                \n",
    "                new_rule = list(rule)\n",
    "                for i, repl_idx in enumerate(indices_to_replace):\n",
    "                    new_rule[repl_idx] = combination[i]\n",
    "                    \n",
    "                new_rule_possibilities.add(tuple(new_rule))\n",
    "            \n",
    "            for nrp in new_rule_possibilities:\n",
    "                to_add = \"\".join(list(nrp)) if all([isinstance(elem, str) for elem in list(nrp)]) else nrp\n",
    "                new_rules_set.add(to_add)\n",
    "        \n",
    "        \n",
    "        if all([isinstance(nrs, str) for nrs in new_rules_set]) and idx not in queue:\n",
    "            # print(\"QUEUED\", idx)\n",
    "            queue.append(idx)\n",
    "            \n",
    "        rules[idx] = new_rules_set\n",
    "        # print(\"NR\", rules[idx])\n",
    "    \n",
    "    if q_idx == 0:\n",
    "        break\n",
    "\n",
    "    del rules[q_idx]\n",
    "    queue.pop(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "total = 0\n",
    "for text in texts:\n",
    "    if text in list(rules[0]):\n",
    "        total += 1\n",
    "print(total)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "max_length = max([len(text) for text in texts])  # max length is 96, rule 0 can be written as \"42 42 42* 31 31*\"\n",
    "\n",
    "while queue:\n",
    "    q_idx = queue[0]\n",
    "    \n",
    "    # print(\"Q\", q_idx)\n",
    "\n",
    "    for idx, rule_set in rules.items():\n",
    "        # print(\"RS\", idx, rule_set)\n",
    "        new_rules_set = set()\n",
    "        for rule in rule_set:\n",
    "            # print(\"R\", rule)\n",
    "            new_rule_possibilities = set()\n",
    "            indices_to_replace = [i for i, x in enumerate(rule) if x == q_idx]\n",
    "            \n",
    "            # print(\"ITR\", indices_to_replace)\n",
    "            \n",
    "            for combination in product(rules[q_idx], repeat=len(indices_to_replace)):\n",
    "                # print(\"C\", combination)\n",
    "                \n",
    "                new_rule = list(rule)\n",
    "                for i, repl_idx in enumerate(indices_to_replace):\n",
    "                    new_rule[repl_idx] = combination[i]\n",
    "                    \n",
    "                new_rule_possibilities.add(tuple(new_rule))\n",
    "            \n",
    "            for nrp in new_rule_possibilities:\n",
    "                to_add = \"\".join(list(nrp)) if all([isinstance(elem, str) for elem in list(nrp)]) else nrp\n",
    "                new_rules_set.add(to_add)\n",
    "        \n",
    "        \n",
    "        if all([isinstance(nrs, str) for nrs in new_rules_set]) and idx not in queue:\n",
    "            # print(\"QUEUED\", idx)\n",
    "            queue.append(idx)\n",
    "            \n",
    "        rules[idx] = new_rules_set\n",
    "        # print(\"NR\", rules[idx])\n",
    "\n",
    "    if q_idx == 31:\n",
    "        break\n",
    "        \n",
    "    del rules[q_idx]\n",
    "    queue.pop(0)\n",
    "\n",
    "for x in [0, 8, 11]:\n",
    "    del rules[x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rules[42].intersection(rules[31])  # they have no common intersection !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for r in rules[42]:\n",
    "    bloc_size = len(r)\n",
    "    break\n",
    "print(bloc_size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "total = 0\n",
    "\n",
    "for i, text in enumerate(texts):\n",
    "    original = text\n",
    "    nb_42, nb_31 = 2, 1\n",
    "    \n",
    "    # at least 2 applications of rule 42 and 1 of rule 31\n",
    "    if not (text[:bloc_size] in rules[42] and text[bloc_size:2*bloc_size] in rules[42] and text[-bloc_size:] in rules[31]):\n",
    "        continue\n",
    "        \n",
    "    text = text[2*bloc_size:-bloc_size]\n",
    "    \n",
    "    while text[:bloc_size] in rules[42]:\n",
    "        nb_42 += 1\n",
    "        text = text[bloc_size:]\n",
    "        \n",
    "    while text[:bloc_size] in rules[31]:\n",
    "        nb_31 += 1\n",
    "        text = text[bloc_size:]\n",
    "    \n",
    "    if not text and nb_42 > nb_31:\n",
    "        total += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "total"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 20\n",
    "\n",
    "http://adventofcode.com/2020/day/20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "DEBUG = False\n",
    "if DEBUG:\n",
    "    content = \"\"\"Tile 2311:\n",
    "..##.#..#.\n",
    "##..#.....\n",
    "#...##..#.\n",
    "####.#...#\n",
    "##.##.###.\n",
    "##...#.###\n",
    ".#.#.#..##\n",
    "..#....#..\n",
    "###...#.#.\n",
    "..###..###\n",
    "\n",
    "Tile 1951:\n",
    "#.##...##.\n",
    "#.####...#\n",
    ".....#..##\n",
    "#...######\n",
    ".##.#....#\n",
    ".###.#####\n",
    "###.##.##.\n",
    ".###....#.\n",
    "..#.#..#.#\n",
    "#...##.#..\n",
    "\n",
    "Tile 1171:\n",
    "####...##.\n",
    "#..##.#..#\n",
    "##.#..#.#.\n",
    ".###.####.\n",
    "..###.####\n",
    ".##....##.\n",
    ".#...####.\n",
    "#.##.####.\n",
    "####..#...\n",
    ".....##...\n",
    "\n",
    "Tile 1427:\n",
    "###.##.#..\n",
    ".#..#.##..\n",
    ".#.##.#..#\n",
    "#.#.#.##.#\n",
    "....#...##\n",
    "...##..##.\n",
    "...#.#####\n",
    ".#.####.#.\n",
    "..#..###.#\n",
    "..##.#..#.\n",
    "\n",
    "Tile 1489:\n",
    "##.#.#....\n",
    "..##...#..\n",
    ".##..##...\n",
    "..#...#...\n",
    "#####...#.\n",
    "#..#.#.#.#\n",
    "...#.#.#..\n",
    "##.#...##.\n",
    "..##.##.##\n",
    "###.##.#..\n",
    "\n",
    "Tile 2473:\n",
    "#....####.\n",
    "#..#.##...\n",
    "#.##..#...\n",
    "######.#.#\n",
    ".#...#.#.#\n",
    ".#########\n",
    ".###.#..#.\n",
    "########.#\n",
    "##...##.#.\n",
    "..###.#.#.\n",
    "\n",
    "Tile 2971:\n",
    "..#.#....#\n",
    "#...###...\n",
    "#.#.###...\n",
    "##.##..#..\n",
    ".#####..##\n",
    ".#..####.#\n",
    "#..#.#..#.\n",
    "..####.###\n",
    "..#.#.###.\n",
    "...#.#.#.#\n",
    "\n",
    "Tile 2729:\n",
    "...#.#.#.#\n",
    "####.#....\n",
    "..#.#.....\n",
    "....#..#.#\n",
    ".##..##.#.\n",
    ".#.####...\n",
    "####.#.#..\n",
    "##.####...\n",
    "##..#.##..\n",
    "#.##...##.\n",
    "\n",
    "Tile 3079:\n",
    "#.#.#####.\n",
    ".#..######\n",
    "..#.......\n",
    "######....\n",
    "####.#..#.\n",
    ".#...#.##.\n",
    "#.#####.##\n",
    "..#.###...\n",
    "..#.......\n",
    "..#.###...\n",
    "\"\"\"\n",
    "    content = content.split(\"\\n\")\n",
    "else:\n",
    "    content = load_day(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content[12:24]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tiles = defaultdict(list)\n",
    "borders = {}\n",
    "\n",
    "tile_idx = None\n",
    "left_border, right_border = \"\", \"\"\n",
    "\n",
    "for line in content:\n",
    "    if \"Tile\" in line:\n",
    "        tile_idx = int(line[5:9])\n",
    "    elif line:\n",
    "        tiles[tile_idx].append(line)\n",
    "        left_border += line[0]\n",
    "        right_border += line[-1]\n",
    "    else:\n",
    "        borders[tile_idx] = [tiles[tile_idx][0], right_border, tiles[tile_idx][-1][::-1], left_border[::-1]]\n",
    "        left_border = right_border = \"\"\n",
    "\n",
    "# print(borders)\n",
    "        \n",
    "couples = {}\n",
    "\n",
    "for tile_id, bords in borders.items():\n",
    "    for idx, border in enumerate(bords):\n",
    "        if border in couples.keys():\n",
    "            couples[border].append((tile_id, idx, 1))\n",
    "        elif border[::-1] in couples.keys():\n",
    "            couples[border[::-1]].append((tile_id, idx, -1))\n",
    "        else:\n",
    "            couples[border] = [(tile_id, idx, 1)]\n",
    "\n",
    "# print(couples)\n",
    "\n",
    "missing_neighbors = Counter()\n",
    "for border, coupled_tiles in couples.items():\n",
    "    if len(coupled_tiles) == 1:\n",
    "        missing_neighbors[coupled_tiles[0][0]] += 1\n",
    "\n",
    "# print(missing_neighbors)\n",
    "\n",
    "answer1 = functools.reduce(lambda x, y: x * y, [v[0] for v in missing_neighbors.most_common(4)], 1)\n",
    "print(f\"Answer 1: {answer1}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grid = defaultdict(lambda: defaultdict(tuple))\n",
    "grid[0][0] = (1951, 2, -1) if DEBUG else (3187, 0, 1)\n",
    "\n",
    "for row_idx in range(3 if DEBUG else 12):\n",
    "    col_idx = 0\n",
    "    queue = [grid[row_idx][0]]\n",
    "    \n",
    "    while queue:\n",
    "        elem = queue.pop(0)\n",
    "        print(\"E\", elem)\n",
    "        for c in couples.values():\n",
    "            val = None\n",
    "            for i, x in enumerate(c):\n",
    "                if x[0] == elem[0] and x[1] == (elem[1] + elem[2]) % 4:\n",
    "                    val = i\n",
    "            \n",
    "            if val is not None:\n",
    "                print(c)\n",
    "                right_elem_in_couple = c.pop(val)\n",
    "                print(c)\n",
    "                if len(c):\n",
    "                    col_idx += 1\n",
    "                    delta_flip = - elem[2] * c[0][2] * right_elem_in_couple[2]\n",
    "                    grid[row_idx][col_idx] = (c[0][0], (c[0][1] + delta_flip) % 4, delta_flip)\n",
    "                    queue.append((c[0][0], (c[0][1] + delta_flip) % 4, + delta_flip))\n",
    "                break\n",
    "\n",
    "    elem = grid[row_idx][0]\n",
    "    print(\"L\", elem)\n",
    "    \n",
    "    for c in couples.values():\n",
    "        val = None\n",
    "        for i, x in enumerate(c):\n",
    "            if x[0] == elem[0] and x[1] == (elem[1] + 2) % 4:\n",
    "                val = i\n",
    "            \n",
    "        if val is not None:\n",
    "            print(c)\n",
    "            prox_elem = c.pop(val)\n",
    "            print(c)\n",
    "            if len(c):\n",
    "                grid[row_idx + 1][0] = (c[0][0], c[0][1], -elem[2] * prox_elem[2] * c[0][2])\n",
    "            break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def manage_tile(tile, orient, flip, cut=False):  # tile: list(str)\n",
    "    new_tile = []\n",
    "\n",
    "    if flip == -1:\n",
    "        tile = [t[::-1] for t in tile]\n",
    "        if orient % 2:\n",
    "            orient = (orient + 2) % 4\n",
    "\n",
    "    if orient == 1:\n",
    "        for c_idx in range(-1-int(cut), -len(tile[0])-1+int(cut), -1):\n",
    "            new_row = \"\"\n",
    "            for r_idx in range(int(cut), len(tile)-int(cut)):\n",
    "                new_row += tile[r_idx][c_idx]\n",
    "            new_tile.append(new_row)\n",
    "\n",
    "    elif orient == 2:\n",
    "        for row in reversed(tile[1:-1] if cut else tile):\n",
    "            new_tile.append(reversed(row[1:-1] if cut else row))\n",
    "\n",
    "    elif orient == 3:\n",
    "        for c_idx in range(int(cut), len(tile[0])-int(cut)):\n",
    "            new_row = \"\"\n",
    "            for r_idx in range(-1-int(cut), -len(tile[0])-1+int(cut), -1):\n",
    "                new_row += tile[r_idx][c_idx]\n",
    "            new_tile.append(new_row)\n",
    "\n",
    "    else:\n",
    "        for row in tile[1:-1] if cut else tile:\n",
    "            new_tile.append(row[1:-1] if cut else row)\n",
    "\n",
    "    return new_tile"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "new_tiles = defaultdict(dict)\n",
    "\n",
    "for row_idx, row in grid.items():\n",
    "    for col_idx, data in row.items():\n",
    "        tile_idx, orient, flip = data\n",
    "        # print(data)\n",
    "        \n",
    "        tile = tiles[tile_idx]\n",
    "        if flip == -1:\n",
    "            tile = [t[::-1] for t in tile]\n",
    "            if orient % 2:\n",
    "                orient = (orient + 2) % 4\n",
    "\n",
    "        new_tile = []\n",
    "        if orient == 1:\n",
    "            for c_idx in range(-2, -len(tile[0]), -1):\n",
    "                new_row = \"\"\n",
    "                for r_idx in range(1, len(tile)-1):\n",
    "                    new_row += tile[r_idx][c_idx]\n",
    "                new_tile.append(new_row)\n",
    "\n",
    "        elif orient == 2:\n",
    "            for row in tile[-2:0:-1]:\n",
    "                new_tile.append(row[-2:0:-1])\n",
    "                \n",
    "        elif orient == 3:\n",
    "            for c_idx in range(1, len(tile[0])-1):\n",
    "                new_row = \"\"\n",
    "                for r_idx in range(-2, -len(tile), -1):\n",
    "                    new_row += tile[r_idx][c_idx]\n",
    "                new_tile.append(new_row)\n",
    "                \n",
    "        else:\n",
    "            for row in tile[1:-1]:\n",
    "                new_tile.append(row[1:-1])\n",
    "                \n",
    "        new_tiles[row_idx][col_idx] = new_tile\n",
    "\n",
    "# print(new_tiles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "total_grid = defaultdict(lambda: defaultdict(str))\n",
    "\n",
    "for row_idx, row in new_tiles.items():\n",
    "    for col_idx, tile in row.items():\n",
    "        for ri, tile_row in enumerate(tile):\n",
    "            for ci, val in enumerate(tile_row):\n",
    "                total_grid[row_idx * 8 + ri][col_idx * 8 + ci] = val\n",
    "                \n",
    "total_tile = []\n",
    "for row in total_grid.values():\n",
    "    tile_row = \"\".join(row.values())\n",
    "    total_tile.append(tile_row)\n",
    "    print(tile_row)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pattern = \"\"\"\n",
    "                  # \n",
    "#    ##    ##    ###\n",
    " #  #  #  #  #  #   \n",
    "\"\"\"\n",
    "arr_pattern = pattern.strip(\"\\n\").split(\"\\n\")\n",
    "size_pattern = (3, 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pattern_delta = []\n",
    "for ri in range(3):\n",
    "    for ci in range(20):\n",
    "        if arr_pattern[ri][ci] == \"#\":\n",
    "            pattern_delta.append((ri, ci))\n",
    "max_corr = len(pattern_delta)\n",
    "print(pattern_delta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "monster_coord = set()\n",
    "\n",
    "for orient in range(4):\n",
    "    for flip in [-1, 1]:\n",
    "        print(\"=\" * 30)\n",
    "        print (\"O\", orient, \"F\", flip)\n",
    "        new_tile = manage_tile(total_tile, orient, flip, cut=False)\n",
    "        # print(new_tile)\n",
    "\n",
    "        total_grid = defaultdict(lambda: defaultdict(str))\n",
    "        for idx, row_tile in enumerate(new_tile):\n",
    "            for ci, val in enumerate(row_tile):\n",
    "                total_grid[idx][ci] = val\n",
    "\n",
    "        total_copy_grid = copy.deepcopy(total_grid)\n",
    "\n",
    "        for row_idx, row in total_copy_grid.items():\n",
    "            for col_idx in row.keys():\n",
    "                arrrr = [total_grid[row_idx + d[0]][col_idx + d[1]] == \"#\" for d in pattern_delta]\n",
    "                corr = sum(arrrr)\n",
    "                if corr == max_corr:\n",
    "                    print(row_idx, col_idx, corr) #, arrrr)\n",
    "                    for delta in pattern_delta:\n",
    "                        monster_coord.add((row_idx + delta[0], col_idx + delta[1], orient, flip))\n",
    "                \n",
    "print(len(monster_coord))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 21\n",
    "\n",
    "http://adventofcode.com/2020/day/21"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(21)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "allergens = collections.defaultdict(set)\n",
    "all_components = collections.Counter()\n",
    "\n",
    "for line in content:\n",
    "    elements = line.replace(\")\", \"\").replace(\",\", \"\").split(\" \")\n",
    "    boundary = elements.index(\"(contains\")\n",
    "    \n",
    "    components = set(elements[:boundary])\n",
    "    all_components += collections.Counter(components)\n",
    "    \n",
    "    for i in range(boundary + 1, len(elements)):\n",
    "        if allergens[elements[i]]:\n",
    "            allergens[elements[i]] &= copy.deepcopy(components)\n",
    "        else:\n",
    "            allergens[elements[i]] = copy.deepcopy(components)\n",
    "\n",
    "for allergen_components in allergens.values():\n",
    "    for component in allergen_components:\n",
    "        del all_components[component]\n",
    "\n",
    "print(f\"Answer 1: {sum(all_components.values())}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mappings = [[k, v] for k, v in allergens.items()]\n",
    "\n",
    "N = len(allergens.keys())\n",
    "\n",
    "final_mapping, used = {}, set()\n",
    "\n",
    "while mappings:\n",
    "    mappings = sorted(mappings, key=lambda x: len(x[1]))\n",
    "\n",
    "    key, values = mappings.pop(0)\n",
    "    value = next(iter(values))\n",
    "    \n",
    "    final_mapping[key] = value\n",
    "    \n",
    "    for m in mappings:\n",
    "        m[1] -= set([value])\n",
    "\n",
    "final_mapping = [v for k, v in sorted(final_mapping.items(), key=lambda x: x[0])]\n",
    "\n",
    "print(f\"Answer 2: {','.join(final_mapping)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 22\n",
    "\n",
    "http://adventofcode.com/2020/day/22"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(22)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def init_decks():\n",
    "    decks = [[], []]\n",
    "    add_to_deck = None\n",
    "\n",
    "    for line in content:\n",
    "        if line and line.startswith(\"Player\"):\n",
    "            add_to_deck = int(line[7]) - 1\n",
    "\n",
    "        elif line:\n",
    "            decks[add_to_deck].append(int(line))\n",
    "    return decks\n",
    "\n",
    "def results(decks):\n",
    "    deck = decks[0] if decks[0] else decks[1]\n",
    "    return sum([elem[0] * elem[1] for elem in zip(deck, range(len(deck), 0, -1))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "decks = init_decks()\n",
    "\n",
    "while decks[0] and decks[1]:\n",
    "    play0 = decks[0].pop(0)\n",
    "    play1 = decks[1].pop(0)\n",
    "    \n",
    "    if play0 > play1:\n",
    "        decks[0] += [play0, play1]\n",
    "    else:\n",
    "        decks[1] += [play1, play0]\n",
    "        \n",
    "print(f\"Answer 1: {results(decks)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def game(decks):\n",
    "    previous_decks = []\n",
    "    \n",
    "    while decks[0] and decks[1]:\n",
    "        if decks in previous_decks:\n",
    "            return 0\n",
    "        \n",
    "        previous_decks.append(copy.deepcopy(decks))\n",
    "        \n",
    "        play0 = decks[0].pop(0)\n",
    "        play1 = decks[1].pop(0)\n",
    "        \n",
    "        if len(decks[0]) >= play0 and len(decks[1]) >= play1:\n",
    "            winner = game([decks[0][:play0], decks[1][:play1]])\n",
    "            if winner:\n",
    "                decks[1] += [play1, play0]\n",
    "            else:\n",
    "                decks[0] += [play0, play1]\n",
    "            \n",
    "        else:\n",
    "            if play0 > play1:\n",
    "                decks[0] += [play0, play1]\n",
    "            else:\n",
    "                decks[1] += [play1, play0]\n",
    "\n",
    "    return 0 if decks[0] else 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "decks = init_decks()\n",
    "\n",
    "game(decks)\n",
    "        \n",
    "print(f\"Answer 2: {results(decks)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 23\n",
    "\n",
    "http://adventofcode.com/2020/day/23"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = list(map(int, \"476138259\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def play(successors, current, pickups=[], dest=None, N=100):\n",
    "    \n",
    "    M = max(successors.keys()) + 1\n",
    "    \n",
    "    for loop in range(N):\n",
    "        pickups = [successors[current]]\n",
    "        for i in range(2):\n",
    "            pickups.append(successors[pickups[-1]])\n",
    "\n",
    "        cand_dest = (current - 1) % M\n",
    "        while dest is None:\n",
    "            if cand_dest and cand_dest not in pickups:\n",
    "                dest = cand_dest\n",
    "            else:\n",
    "                cand_dest = (cand_dest - 1) % M\n",
    "\n",
    "        new_current = successors[pickups[-1]]\n",
    "\n",
    "        successors[current] = new_current\n",
    "        current = new_current\n",
    "\n",
    "        successors[pickups[-1]] = successors[dest]\n",
    "        successors[dest] = pickups[0]\n",
    "\n",
    "        dest = None\n",
    "    \n",
    "    return successors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "successors = dict(zip(content, content[1:] + [content[0]]))\n",
    "\n",
    "successors = play(successors, content[0])\n",
    "\n",
    "next_elem = successors[1]\n",
    "print(\"Answer 1:\", end=\" \")\n",
    "while next_elem != 1:\n",
    "    print(next_elem, end=\"\")\n",
    "    next_elem = successors[next_elem]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "successors = dict(zip(range(9, 1000000), range(10, 1000001)))\n",
    "successors[1000000] = content[0]\n",
    "for k,v in zip(content, content[1:] + [10]):\n",
    "    successors[k] = v\n",
    "\n",
    "successors = play(successors, content[0], N=10000000)\n",
    "\n",
    "next_elem = successors[1]\n",
    "print(f\"Answer 2: {next_elem * successors[next_elem]}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 24\n",
    "\n",
    "http://adventofcode.com/2020/day/24"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(24)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def init_grid():\n",
    "    grid = collections.defaultdict(bool)\n",
    "\n",
    "    for line in content:\n",
    "        coords = [0, 0]\n",
    "        while line:\n",
    "            char = line[0]\n",
    "            line = line[1:]\n",
    "            if char == \"e\":\n",
    "                coords = [coords[0], coords[1] + 1]\n",
    "            elif char == \"w\":\n",
    "                coords = [coords[0], coords[1] - 1]\n",
    "            else:\n",
    "                char = f\"{char}{line[0]}\"\n",
    "                line = line[1:]\n",
    "                if char == \"ne\":\n",
    "                    coords = [coords[0] + 1, coords[1] + (1 if coords[0] % 2 else 0)]\n",
    "                elif char == \"nw\":\n",
    "                    coords = [coords[0] + 1, coords[1] - (0 if coords[0] % 2 else 1)]\n",
    "                elif char == \"se\":\n",
    "                    coords = [coords[0] - 1, coords[1] + (1 if coords[0] % 2 else 0)]\n",
    "                elif char == \"sw\":\n",
    "                    coords = [coords[0] - 1, coords[1] - (0 if coords[0] % 2 else 1)]\n",
    "\n",
    "        grid[(coords[0], coords[1])] = not grid[(coords[0], coords[1])]\n",
    "        \n",
    "    return grid\n",
    "        \n",
    "grid = init_grid()\n",
    "print(sum([1 for x in grid.values() if x]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_neighbors(pos):\n",
    "    neighbors = [(pos[0], pos[1] + 1), (pos[0], pos[1] - 1)]\n",
    "    neighbors.append((pos[0] + 1, pos[1] + (1 if pos[0] % 2 else 0))) \n",
    "    neighbors.append((pos[0] + 1, pos[1] - (0 if pos[0] % 2 else 1)))\n",
    "    neighbors.append((pos[0] - 1, pos[1] + (1 if pos[0] % 2 else 0)))\n",
    "    neighbors.append((pos[0] - 1, pos[1] - (0 if pos[0] % 2 else 1)))\n",
    "        \n",
    "    return neighbors\n",
    "\n",
    "\n",
    "grid = init_grid()\n",
    "\n",
    "for day in range(100):\n",
    "    new_grid = collections.defaultdict(bool)\n",
    "    \n",
    "    min_x = min(x[0] for x in grid.keys())\n",
    "    max_x = max(x[0] for x in grid.keys())\n",
    "    min_y = min(x[1] for x in grid.keys())\n",
    "    max_y = max(x[1] for x in grid.keys())\n",
    "        \n",
    "    for x in range(min_x - 1, max_x + 2):\n",
    "        for y in range(min_y - 1, max_y + 2):\n",
    "            coords = (x, y)\n",
    "            color = grid[coords]\n",
    "\n",
    "            nb_black_neighbors = sum([int(grid[n_pos]) for n_pos in get_neighbors(coords)])\n",
    "\n",
    "            if color and 1 <= nb_black_neighbors <= 2:\n",
    "                new_grid[coords] = True\n",
    "            elif not color and nb_black_neighbors == 2:\n",
    "                new_grid[coords] = True\n",
    "        \n",
    "    grid = new_grid\n",
    "    \n",
    "print(sum([1 for x in grid.values() if x]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Day 25\n",
    "\n",
    "http://adventofcode.com/2020/day/25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "content = load_day(25)\n",
    "card_public = int(content[0])\n",
    "door_public = int(content[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 1__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "loop = 0\n",
    "value = 1\n",
    "\n",
    "while value != card_public:\n",
    "    value = (7 * value) % 20201227\n",
    "    loop += 1\n",
    "\n",
    "value = 1\n",
    "for i in range(loop):\n",
    "    value = (door_public * value) % 20201227\n",
    "    \n",
    "print(f\"Answer 1: {value}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Part 2__"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}