Advent of Code 2021.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "eed93b5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import aocd\n",
    "import re\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.image as mpimg\n",
    "\n",
    "from PIL import Image \n",
    "%matplotlib inline\n",
    "\n",
    "def get_as_ints(l):\n",
    "    return list(map(lambda x: int(x), l))\n",
    "\n",
    "def get_lines(day):\n",
    "    return aocd.get_data(year=2021, day=day).split(\"\\n\")\n",
    "\n",
    "def get_csv(day):\n",
    "    return aocd.get_data(year=2021, day=day).split(\",\")\n",
    "                \n",
    "def get_lines_as_ints(day):\n",
    "    return get_as_ints(get_lines(day))\n",
    "\n",
    "def get_csv_as_ints(day):\n",
    "    return get_as_ints(get_csv(day))\n",
    "\n",
    "def get_csv_lines(day):\n",
    "    return list(map(lambda s: s.split(\",\"), get_as_lines(day)))\n",
    "\n",
    "def get_csv_lines_as_ints(day):\n",
    "    return list(map(lambda s: get_as_ints(s.split(\",\")), get_as_lines(day)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "486b0031",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1521\n"
     ]
    }
   ],
   "source": [
    "# Day 1: part 1\n",
    "\n",
    "data = get_lines_as_ints(1)\n",
    "\n",
    "larger = 0\n",
    "for i in range(len(data) - 1):\n",
    "    if data[i] < data[i + 1]:\n",
    "        larger += 1\n",
    "        \n",
    "print(larger)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "6f2d91fb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1543\n"
     ]
    }
   ],
   "source": [
    "# Day 1: part 2\n",
    "\n",
    "data = get_lines_as_ints(1)\n",
    "\n",
    "larger = 0\n",
    "for i in range(len(data) - 3):\n",
    "    if data[i] < data[i + 3]:\n",
    "        larger += 1\n",
    "        \n",
    "print(larger)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ad16cf6c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1654760\n"
     ]
    }
   ],
   "source": [
    "# Day 2: part 1\n",
    "\n",
    "data = get_lines(2)\n",
    "\n",
    "depth = 0\n",
    "forward = 0\n",
    "\n",
    "for datum in data:\n",
    "    instruction = datum.split(\" \")\n",
    "    val = int(instruction[1])\n",
    "    if instruction[0] == \"forward\":\n",
    "        forward += val\n",
    "    elif instruction[0] == \"up\":\n",
    "        depth -= val\n",
    "    else:\n",
    "        depth += val\n",
    "\n",
    "print(forward * depth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "04909bbb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1956047400\n"
     ]
    }
   ],
   "source": [
    "# Day 2: part 2\n",
    "\n",
    "data = get_lines(2)\n",
    "\n",
    "depth = 0\n",
    "forward = 0\n",
    "aim = 0\n",
    "\n",
    "for datum in data:\n",
    "    instruction = datum.split(\" \")\n",
    "    val = int(instruction[1])\n",
    "    if instruction[0] == \"forward\":\n",
    "        forward += val\n",
    "        depth += aim * val\n",
    "    elif instruction[0] == \"up\":\n",
    "        aim -= val\n",
    "    else:\n",
    "        aim += val\n",
    "\n",
    "print(forward * depth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5b21fd50",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2954600\n"
     ]
    }
   ],
   "source": [
    "# Day 3: part 1\n",
    "\n",
    "data = get_lines(3)\n",
    "\n",
    "new_data = np.zeros((len(data), len(data[0])))\n",
    "\n",
    "counter = 0\n",
    "for datum in data:\n",
    "    for bit in datum:\n",
    "        new_data[counter // len(data[0])][counter % len(data[0])] += int(bit)\n",
    "        counter += 1\n",
    "\n",
    "one_is_max = np.sum(new_data, axis = 0) > (len(new_data) / 2)\n",
    "\n",
    "num_one = 0\n",
    "num_two = 0\n",
    "\n",
    "for i in range(len(data[0])):\n",
    "    num_one += pow(2, i) * one_is_max[len(data[0]) - i - 1]\n",
    "    num_two += pow(2, i) * (1 - one_is_max[len(data[0]) - i - 1])\n",
    "    \n",
    "print(int(num_one * num_two))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "1520a0b4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1662846\n"
     ]
    }
   ],
   "source": [
    "# Day 3: part 2\n",
    "\n",
    "data = get_lines(3)\n",
    "\n",
    "new_data = np.zeros((len(data), len(data[0])))\n",
    "\n",
    "counter = 0\n",
    "for datum in data:\n",
    "    for bit in datum:\n",
    "        new_data[counter // len(data[0])][counter % len(data[0])] += int(bit)\n",
    "        counter += 1\n",
    "\n",
    "        \n",
    "oxygen = np.copy(new_data)\n",
    "co2 = np.copy(new_data)\n",
    "index = 0\n",
    "while len(oxygen) > 1 and index < len(data[0]):\n",
    "    one_is_max = np.sum(oxygen, axis = 0)[index] >= (len(oxygen) / 2)\n",
    "    oxygen = oxygen[oxygen[:, index] == (1 if one_is_max else 0)]\n",
    "    index += 1\n",
    "\n",
    "index = 0\n",
    "while len(co2) > 1 and index < len(data[0]):\n",
    "    one_is_max = np.sum(co2, axis = 0)[index] >= (len(co2) / 2)\n",
    "    co2 = co2[co2[:, index] == (0 if one_is_max else 1)]\n",
    "    index += 1\n",
    "\n",
    "num_one = 0\n",
    "num_two = 0\n",
    "\n",
    "for i in range(len(data[0])):\n",
    "    num_one += pow(2, i) * oxygen[0][len(data[0]) - i - 1]\n",
    "    num_two += pow(2, i) * (co2[0][len(data[0]) - i - 1])\n",
    "    \n",
    "print(int(num_one * num_two))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "fbed7780",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "49860\n"
     ]
    }
   ],
   "source": [
    "# Day 4: Part 1\n",
    "\n",
    "data = get_lines(4)\n",
    "numbers = data[0].split(\",\")\n",
    "\n",
    "boards = np.zeros(((len(data) - 1) // 6, 5, 5))\n",
    "selected = np.copy(boards)\n",
    "\n",
    "for i in range(2, len(data)):\n",
    "    if len(data[i]) < 10:\n",
    "        continue\n",
    "    else:\n",
    "        j = 0\n",
    "        for num in re.split(\"\\\\s+\", data[i].strip()):\n",
    "            boards[(i - 2) // 6, (i - 2) % 6, j] = int(num)\n",
    "            j+=1\n",
    "            \n",
    "for number in numbers:\n",
    "    number = int(number)\n",
    "    selected[boards[:,:,:] == number] = 1\n",
    "    \n",
    "    rows = np.logical_or.reduce(np.sum(selected, 2)[:, :] == 5, axis = 1)\n",
    "    cols = np.logical_or.reduce(np.sum(selected, 1)[:, :] == 5, axis = 1)\n",
    "    \n",
    "    row = np.logical_or.reduce(rows)\n",
    "    col = np.logical_or.reduce(cols)\n",
    "    \n",
    "    if row:\n",
    "        print(int(np.sum(boards[rows][selected[rows] == False]) * number))\n",
    "        break\n",
    "    if col:\n",
    "        print(int(np.sum(boards[cols][selected[cols] == False]) * number))\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "b1da12c4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "24628\n"
     ]
    }
   ],
   "source": [
    "# Day 4: Part 2\n",
    "\n",
    "data = get_lines(4)\n",
    "numbers = data[0].split(\",\")\n",
    "\n",
    "boards = np.zeros(((len(data) - 1) // 6, 5, 5))\n",
    "selected = np.copy(boards)\n",
    "\n",
    "for i in range(2, len(data)):\n",
    "    if len(data[i]) < 10:\n",
    "        continue\n",
    "    else:\n",
    "        j = 0\n",
    "        for num in re.split(\"\\\\s+\", data[i].strip()):\n",
    "            boards[(i - 2) // 6, (i - 2) % 6, j] = int(num)\n",
    "            j+=1\n",
    "\n",
    "found = False\n",
    "index = -1\n",
    "for number in numbers:\n",
    "    number = int(number)\n",
    "    selected[boards[:,:,:] == number] = 1\n",
    "    \n",
    "    rows = np.logical_or.reduce(np.sum(selected, 2)[:, :] == 5, axis = 1)\n",
    "    cols = np.logical_or.reduce(np.sum(selected, 1)[:, :] == 5, axis = 1)\n",
    "    \n",
    "    solved = np.logical_or(rows, cols)\n",
    "    \n",
    "    if len(solved[solved == False]) == 1:\n",
    "        found = True\n",
    "        index = solved == False\n",
    "        \n",
    "    if found and len(solved[solved == False]) == 0:\n",
    "        print(int(np.sum(boards[index][selected[index] == 0]) * number))\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e3b7fd77",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7297\n"
     ]
    }
   ],
   "source": [
    "# Day 5: Part 1\n",
    "\n",
    "data = get_lines(5)\n",
    "\n",
    "new_data = np.zeros((len(data), 2, 2))\n",
    "\n",
    "for i in range(len(data)):\n",
    "    d = data[i].split(\" -> \")\n",
    "    d = list(map(lambda x: x.split(\",\"), d))\n",
    "    new_data[i] = [[int(d[0][0]), int(d[0][1])], [int(d[1][0]), int(d[1][1])]]\n",
    "    \n",
    "grid = np.zeros((1000,1000))\n",
    "\n",
    "for line in new_data:\n",
    "    if line[0][0] == line[1][0]:\n",
    "        start = int(min(line[0][1], line[1][1]))\n",
    "        end = int(max(line[0][1], line[1][1]))\n",
    "        for j in range(start, end + 1): \n",
    "            grid[int(line[0][0]), int(j)] += 1\n",
    "            \n",
    "    elif line[0][1] == line[1][1]:\n",
    "        start = int(min(line[0][0], line[1][0]))\n",
    "        end = int(max(line[0][0], line[1][0]))\n",
    "        for j in range(start, end + 1): \n",
    "            grid[int(j), int(line[0][1])] += 1\n",
    "            \n",
    "print(len(grid[grid >= 2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "a9468cd2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "21038\n"
     ]
    }
   ],
   "source": [
    "# Day 5: Part 2\n",
    "\n",
    "data = get_lines(5)\n",
    "\n",
    "new_data = np.zeros((len(data), 2, 2))\n",
    "\n",
    "for i in range(len(data)):\n",
    "    d = data[i].split(\" -> \")\n",
    "    d = list(map(lambda x: x.split(\",\"), d))\n",
    "    new_data[i] = [[int(d[0][0]), int(d[0][1])], [int(d[1][0]), int(d[1][1])]]\n",
    "    \n",
    "grid = np.zeros((1000,1000))\n",
    "\n",
    "for line in new_data:\n",
    "    if line[0][0] == line[1][0]:\n",
    "        start = int(min(line[0][1], line[1][1]))\n",
    "        end = int(max(line[0][1], line[1][1]))\n",
    "        for j in range(start, end + 1): \n",
    "            grid[int(line[0][0]), int(j)] += 1\n",
    "        continue\n",
    "            \n",
    "    elif line[0][1] == line[1][1]:\n",
    "        start = int(min(line[0][0], line[1][0]))\n",
    "        end = int(max(line[0][0], line[1][0]))\n",
    "        for j in range(start, end + 1): \n",
    "            grid[int(j), int(line[0][1])] += 1\n",
    "        continue\n",
    "\n",
    "    delta = line[0] - line[1]\n",
    "    \n",
    "    if delta[0] == 0 or delta[1] == 0:\n",
    "        continue\n",
    "    \n",
    "    x_range = range(int(delta[0]) + 1) if delta[0] > 0 else range(0, int(delta[0] - 1), -1)\n",
    "    y_range = range(int(delta[1]) + 1) if delta[1] > 0 else range(0, int(delta[1] - 1), -1)\n",
    "    \n",
    "    for x,y in zip(x_range, y_range):\n",
    "        grid[int(line[1][0] + x), int(line[1][1] + y)] +=1\n",
    "\n",
    "print(len(grid[grid >= 2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "b98afd95",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "351188\n"
     ]
    }
   ],
   "source": [
    "# Day 6: part 1\n",
    "\n",
    "data = get_csv_as_ints(6)\n",
    "\n",
    "for i in range(80):\n",
    "    count = 0\n",
    "    for j in range(len(data)):\n",
    "        if data[j] != 0:\n",
    "            data[j] -= 1\n",
    "        else:\n",
    "            count += 1\n",
    "            data[j] = 6\n",
    "    for new in range(count):\n",
    "        data.append(8)\n",
    "\n",
    "print(len(data))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "4e21c04e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1595779846729\n"
     ]
    }
   ],
   "source": [
    "# Day 6: part 2\n",
    "\n",
    "data = get_csv_as_ints(6)\n",
    "\n",
    "bins = np.zeros((9))\n",
    "for day in data:\n",
    "    bins[day] +=1\n",
    "    \n",
    "for i in range(256):\n",
    "    zeros = bins[0]\n",
    "    bins = np.roll(bins, -1)\n",
    "    bins[6] += zeros\n",
    "\n",
    "print(int(bins.sum()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "58464361",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "336701\n"
     ]
    }
   ],
   "source": [
    "# Day 7: part 1\n",
    "\n",
    "data = np.array(get_csv_as_ints(7))\n",
    "\n",
    "print(np.frompyfunc(lambda i: np.frompyfunc(lambda x: abs(x - i), 1, 1)(data).sum(), 1, 1)(np.arange(data.min(), data.max() + 1)).min())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "67bef9e8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "95167302\n"
     ]
    }
   ],
   "source": [
    "# Day 7: part 2\n",
    "\n",
    "data = np.array(get_csv_as_ints(7))\n",
    "\n",
    "def sum_fact(val):\n",
    "    val = abs(val)\n",
    "    return val * (val + 1) // 2\n",
    "\n",
    "print(np.frompyfunc(lambda i: np.frompyfunc(lambda x: sum_fact(x-i), 1, 1)(data).sum(), 1, 1)(np.arange(data.min(), data.max() + 1)).min())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "7c44634c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "449\n"
     ]
    }
   ],
   "source": [
    "# Day 8: part 1\n",
    "\n",
    "data = np.array(get_lines(8))\n",
    "data = np.array(list(map(lambda s: np.array(s.split(\" | \")[1].split(\" \")), data)))\n",
    "\n",
    "one = ['c', 'f']\n",
    "four = ['b', 'c', 'd', 'f']\n",
    "seven = ['a','c','f']\n",
    "eight = ['a','b','c','d','e','f','g']\n",
    "\n",
    "nums = [one, four, seven, eight]\n",
    "\n",
    "counter = 0\n",
    "for d in data:\n",
    "    for d2 in d:\n",
    "        length = len(d2)\n",
    "        if length == 2 or length == 3 or length == 4 or length == 7:\n",
    "            counter += 1\n",
    "print(counter)\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "973d9c2a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "968175\n"
     ]
    }
   ],
   "source": [
    "from itertools import permutations\n",
    "\n",
    "data = np.array(get_lines(8))\n",
    "data = list(map(lambda s: list(map(lambda n: n.split(\" \"), s.split(\" | \"))), data))\n",
    "\n",
    "total = 0\n",
    "for d in data:\n",
    "    output = 0\n",
    "    \n",
    "    vals = [\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\",\"\"]\n",
    "    \n",
    "    \n",
    "    for d1 in d[0]:\n",
    "        length = len(d1)\n",
    "        if length == 2:\n",
    "            vals[1] = d1\n",
    "        elif length == 3: \n",
    "            vals[7] = d1\n",
    "        elif length == 4:\n",
    "            vals[4] = d1\n",
    "        elif length == 7:\n",
    "            vals[8] = d1\n",
    "    \n",
    "    for d1 in d[0]:\n",
    "        if d1 in vals:\n",
    "            continue\n",
    "        \n",
    "        length = len(d1)\n",
    "        if length == 5:\n",
    "            if vals[1][0] in d1 and vals[1][1] in d1:\n",
    "                vals[3] = d1\n",
    "            else:\n",
    "                common = 0\n",
    "                for c in vals[4]:\n",
    "                    if c in d1:\n",
    "                        common += 1\n",
    "                \n",
    "                if common == 2:\n",
    "                    vals[2] = d1\n",
    "                else:\n",
    "                    vals[5] = d1\n",
    "        elif length == 6:\n",
    "            common = 0\n",
    "            for c in vals[1]:\n",
    "                if c in d1:\n",
    "                    common += 1\n",
    "            \n",
    "            if common == 1:\n",
    "                vals[6] = d1\n",
    "            else:\n",
    "                common = 0\n",
    "                for c in vals[4]:\n",
    "                    if c in d1:\n",
    "                        common += 1\n",
    "                if common == 4:\n",
    "                    vals[9] = d1\n",
    "                else:\n",
    "                    vals[0] = d1\n",
    "    \n",
    "    for d2 in d[1]:\n",
    "        output *= 10\n",
    "        perms = [''.join(p) for p in set(permutations(d2))]\n",
    "        for perm in perms:\n",
    "            if perm in vals:\n",
    "                output += vals.index(perm)\n",
    "                \n",
    "    total += output\n",
    "    \n",
    "print(total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "13819bae",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "603\n"
     ]
    }
   ],
   "source": [
    "# Day 9: Part 1\n",
    "\n",
    "data = np.array(get_lines(9))\n",
    "\n",
    "total = 0\n",
    "for i in range(len(data)):\n",
    "    for j in range(len(data[i])):\n",
    "        val = int(data[i][j])\n",
    "        bad = False\n",
    "        if not i - 1 == -1:\n",
    "            if int(data[i - 1][j]) <= val:\n",
    "                bad = True\n",
    "        if not i + 1 == len(data):\n",
    "            if int(data[i + 1][j]) <= val:\n",
    "                bad = True\n",
    "        if not j - 1 == -1:\n",
    "            if int(data[i][j - 1]) <= val:\n",
    "                bad = True\n",
    "        if not j + 1 == len(data[i]):\n",
    "            if int(data[i][j + 1]) <= val:\n",
    "                bad = True\n",
    "        if not bad:\n",
    "            total += val + 1\n",
    "\n",
    "print(total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "fabe0286",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "786780\n"
     ]
    }
   ],
   "source": [
    "# Day 9: Part 2\n",
    "\n",
    "data = np.array(get_lines(9))\n",
    "\n",
    "low_points = []\n",
    "for i in range(len(data)):\n",
    "    for j in range(len(data[i])):\n",
    "        val = int(data[i][j])\n",
    "        bad = False\n",
    "        if not i - 1 == -1:\n",
    "            if int(data[i - 1][j]) <= val:\n",
    "                bad = True\n",
    "        if not i + 1 == len(data):\n",
    "            if int(data[i + 1][j]) <= val:\n",
    "                bad = True\n",
    "        if not j - 1 == -1:\n",
    "            if int(data[i][j - 1]) <= val:\n",
    "                bad = True\n",
    "        if not j + 1 == len(data[i]):\n",
    "            if int(data[i][j + 1]) <= val:\n",
    "                bad = True\n",
    "        if not bad:\n",
    "            low_points.append([i,j])\n",
    "            \n",
    "basin_sizes = []\n",
    "def search_basin(cur, past, visited):\n",
    "    if cur in visited:\n",
    "        return\n",
    "    \n",
    "    if int(data[cur[0]][cur[1]]) > int(data[past[0]][past[1]]):\n",
    "        if not int(data[cur[0]][cur[1]]) == 9:\n",
    "            visited.append(cur)\n",
    "        else:\n",
    "            return\n",
    "    else:\n",
    "        return\n",
    "    \n",
    "    if cur[0] > 0:\n",
    "        search_basin([cur[0] - 1, cur[1]], cur, visited)\n",
    "    if cur[0] < len(data) - 1:\n",
    "        search_basin([cur[0] + 1, cur[1]], cur, visited)\n",
    "    if cur[1] > 0:\n",
    "        search_basin([cur[0], cur[1] - 1], cur, visited)\n",
    "    if cur[1] < len(data[cur[0]]) - 1:\n",
    "        search_basin([cur[0], cur[1]  + 1], cur, visited)\n",
    "    \n",
    "for low_point in low_points:\n",
    "    visited = []\n",
    "    if low_point[0] > 0:\n",
    "        search_basin([low_point[0] - 1, low_point[1]], low_point, visited)\n",
    "        \n",
    "    if low_point[0] < len(data) - 1:\n",
    "        search_basin([low_point[0] + 1, low_point[1]], low_point, visited)\n",
    "        \n",
    "    if low_point[1] > 0:\n",
    "        search_basin([low_point[0], low_point[1] - 1], low_point, visited)\n",
    "        \n",
    "    if low_point[1] < len(data[low_point[0]]) - 1:\n",
    "        search_basin([low_point[0], low_point[1] + 1], low_point, visited)\n",
    "        \n",
    "    basin_sizes.append(len(visited) + 1)\n",
    "    \n",
    "print(np.multiply.reduce(np.array(basin_sizes)[np.array(basin_sizes).argsort()[-3::]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "3111c5e1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "362271\n"
     ]
    }
   ],
   "source": [
    "# Day 10: Part 1\n",
    "data = get_lines(10)\n",
    "\n",
    "new_lines = []\n",
    "for line in data:\n",
    "    past_line = \"\"\n",
    "    while line != past_line:\n",
    "        past_line = line\n",
    "        line = line.replace(\"()\", \"\")\n",
    "        line = line.replace(\"<>\", \"\")\n",
    "        line = line.replace(\"{}\", \"\")\n",
    "        line = line.replace(\"[]\", \"\")\n",
    "    \n",
    "    if \")\" in line or \"]\" in line or \"}\" in line or \">\" in line:\n",
    "        new_lines.append(line)\n",
    "        \n",
    "total = 0\n",
    "for line in new_lines:\n",
    "    found = False\n",
    "    for c in line:\n",
    "        if found:\n",
    "            continue\n",
    "        \n",
    "        if c == \")\":\n",
    "            total += 3\n",
    "            found = True\n",
    "        elif c == \"]\":\n",
    "            total += 57\n",
    "            found = True\n",
    "        elif c == \"}\":\n",
    "            total += 1197\n",
    "            found = True\n",
    "        elif c == \">\":\n",
    "            total += 25137\n",
    "            found = True\n",
    "        \n",
    "print(total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "d157eae8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1698395182\n"
     ]
    }
   ],
   "source": [
    "# Day 10: Part 2\n",
    "data = get_lines(10)\n",
    "\n",
    "new_lines = []\n",
    "for line in data:\n",
    "    past_line = \"\"\n",
    "    while line != past_line:\n",
    "        past_line = line\n",
    "        line = line.replace(\"()\", \"\")\n",
    "        line = line.replace(\"<>\", \"\")\n",
    "        line = line.replace(\"{}\", \"\")\n",
    "        line = line.replace(\"[]\", \"\")\n",
    "    \n",
    "    if not (\")\" in line or \"]\" in line or \"}\" in line or \">\" in line):\n",
    "        new_lines.append(line)\n",
    "        \n",
    "totals = []\n",
    "for line in new_lines:\n",
    "    total = 0\n",
    "    for c in line[::-1]:\n",
    "        total *= 5\n",
    "        if c == \"(\":\n",
    "            total += 1\n",
    "        elif c == \"[\":\n",
    "            total += 2\n",
    "        elif c == \"{\":\n",
    "            total += 3\n",
    "        elif c == \"<\":\n",
    "            total += 4\n",
    "    totals.append(total)\n",
    "        \n",
    "totals = np.array(totals)\n",
    "args = np.argsort(totals)\n",
    "print(totals[args][(len(totals) // 2)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "6939d729",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1723\n"
     ]
    }
   ],
   "source": [
    "# Day 11: Part 1\n",
    "data = get_lines(11)\n",
    "\n",
    "new_data = np.zeros((10,10))\n",
    "\n",
    "index = 0\n",
    "for line in data:\n",
    "    for n in line:\n",
    "        new_data[index // 10][index % 10] = int(n)\n",
    "        index += 1\n",
    "\n",
    "def flash(x, y, flashed):\n",
    "    if new_data[x, y] > 9 and flashed[x, y] == 0:\n",
    "        sub_flashes = 1\n",
    "        flashed[x, y] = 1\n",
    "        \n",
    "        for i in range(-1, 2):\n",
    "            for j in range(-1, 2):\n",
    "                if not i == 0 or not j == 0:\n",
    "                    if not(x + i < 0 or y + j < 0 or x + i == 10 or y + j == 10):\n",
    "                        new_data[x + i,y + j] += 1\n",
    "                        sub_flashes += flash(x + i, y + j, flashed)\n",
    "\n",
    "        return sub_flashes\n",
    "    else:\n",
    "        return 0\n",
    "\n",
    "flashes = 0\n",
    "for i in range(100):\n",
    "    flashed = np.zeros((10, 10))\n",
    "    for x in range(10):\n",
    "       for y in range(10):\n",
    "           new_data[x, y] += 1\n",
    "    \n",
    "    for x in range(10):\n",
    "        for y in range(10):\n",
    "            flashes += flash(x, y, flashed)\n",
    "    new_data[new_data > 9] = 0\n",
    "print(flashes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "1ac07e33",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "327\n"
     ]
    }
   ],
   "source": [
    "# Day 11: Part 2\n",
    "data = get_lines(11)\n",
    "\n",
    "new_data = np.zeros((10,10))\n",
    "\n",
    "index = 0\n",
    "for line in data:\n",
    "    for n in line:\n",
    "        new_data[index // 10][index % 10] = int(n)\n",
    "        index += 1\n",
    "\n",
    "def flash(x, y, flashed):\n",
    "    if new_data[x, y] > 9 and flashed[x, y] == 0:\n",
    "        flashed[x, y] = 1\n",
    "        \n",
    "        for i in range(-1, 2):\n",
    "            for j in range(-1, 2):\n",
    "                if not i == 0 or not j == 0:\n",
    "                    if not(x + i < 0 or y + j < 0 or x + i == 10 or y + j == 10):\n",
    "                        new_data[x + i,y + j] += 1\n",
    "                        flash(x + i, y + j, flashed)\n",
    "                        \n",
    "i = 0\n",
    "while True:\n",
    "    flashed = np.zeros((10, 10))\n",
    "    for x in range(10):\n",
    "       for y in range(10):\n",
    "           new_data[x, y] += 1\n",
    "    \n",
    "    for x in range(10):\n",
    "        for y in range(10):\n",
    "           flash(x, y, flashed)\n",
    "    new_data[new_data > 9] = 0\n",
    "    \n",
    "    i += 1\n",
    "    if new_data.sum() == 0:\n",
    "        print(i)\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "5c6e29b5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    }
   ],
   "source": [
    "# Day 12: Part 1\n",
    "data = get_lines(12)\n",
    "\n",
    "data = \"\"\"start-A\n",
    "start-b\n",
    "A-c\n",
    "A-b\n",
    "b-d\n",
    "A-end\n",
    "b-end\"\"\".split(\"\\n\")\n",
    "\n",
    "data = list(map(lambda s: s.split(\"-\"), data))\n",
    "\n",
    "caves = []\n",
    "isLarge = []\n",
    "\n",
    "for pair in data:\n",
    "    for cave in pair:\n",
    "        if not cave in caves:\n",
    "            caves.append(cave)\n",
    "            isLarge.append(cave.lower() != cave)\n",
    "\n",
    "caves = np.array(caves)            \n",
    "            \n",
    "pairs = np.zeros((len(caves), len(caves)))\n",
    "\n",
    "for pair in data:\n",
    "    pairs[caves == pair[0], caves == pair[1]] += 1\n",
    "    pairs[caves == pair[1], caves == pair[0]] += 1\n",
    "    \n",
    "    \n",
    "start = np.where(caves == \"start\")[0][0]\n",
    "end = np.where(caves == \"end\")[0][0]\n",
    "\n",
    "def search(index, visited):\n",
    "    if (not len(visited) == 0) and caves[index] == \"start\":\n",
    "        return 0\n",
    "    \n",
    "    if not isLarge[index] and index in visited:\n",
    "        return 0\n",
    "    \n",
    "    if caves[index] == \"end\":\n",
    "        return 1\n",
    "    \n",
    "    total = 0\n",
    "    \n",
    "    visited.append(index)\n",
    "    for i in range(len(pairs[index])):\n",
    "        if pairs[index][i] == 1:\n",
    "            total += search(i, visited)\n",
    "    visited.pop()\n",
    "    return total\n",
    "    \n",
    "print(search(start, []))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "59ebb0f9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "96988\n"
     ]
    }
   ],
   "source": [
    "# Day 12: Part 1\n",
    "data = get_lines(12)\n",
    "\n",
    "data = list(map(lambda s: s.split(\"-\"), data))\n",
    "\n",
    "caves = []\n",
    "isLarge = []\n",
    "\n",
    "for pair in data:\n",
    "    for cave in pair:\n",
    "        if not cave in caves:\n",
    "            caves.append(cave)\n",
    "            isLarge.append(cave.lower() != cave)\n",
    "\n",
    "caves = np.array(caves)            \n",
    "            \n",
    "pairs = np.zeros((len(caves), len(caves)))\n",
    "\n",
    "for pair in data:\n",
    "    pairs[caves == pair[0], caves == pair[1]] += 1\n",
    "    pairs[caves == pair[1], caves == pair[0]] += 1\n",
    "    \n",
    "    \n",
    "start = np.where(caves == \"start\")[0][0]\n",
    "end = np.where(caves == \"end\")[0][0]\n",
    "\n",
    "def hasSmallTwice(visited):\n",
    "    total = np.zeros(len(caves))\n",
    "    for i in range(len(caves)):\n",
    "        if not isLarge[i]:\n",
    "            for j in visited:\n",
    "                if j == i:\n",
    "                    total[i] += 1\n",
    "                    if total[i] == 2:\n",
    "                        return True\n",
    "    return False\n",
    "\n",
    "def search(index, visited):\n",
    "    if (not len(visited) == 0) and caves[index] == \"start\":\n",
    "        return 0\n",
    "    \n",
    "    if not isLarge[index] and index in visited and hasSmallTwice(visited):\n",
    "        return 0\n",
    "    \n",
    "    if caves[index] == \"end\":\n",
    "        return 1\n",
    "    \n",
    "    total = 0\n",
    "    \n",
    "    visited.append(index)\n",
    "    for i in range(len(pairs[index])):\n",
    "        if pairs[index][i] == 1:\n",
    "            total += search(i, visited)\n",
    "    visited.pop()\n",
    "    return total\n",
    "    \n",
    "print(search(start, []))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "60e98a79",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "675\n"
     ]
    }
   ],
   "source": [
    "# Day 13: Part 1\n",
    "\n",
    "data = get_lines(13)\n",
    "\n",
    "split = data.index(\"\")\n",
    "\n",
    "grid = np.zeros((split, 2))\n",
    "\n",
    "for i in range(split):\n",
    "    p = get_as_ints(data[i].split(\",\"))\n",
    "    grid[i] = [p[0], p[1]]\n",
    "    \n",
    "folds = np.zeros((len(data) - 1 - split))\n",
    "j = 0\n",
    "\n",
    "for i in range(split + 1, len(data)):\n",
    "    if \"x\" in data[i]:\n",
    "        folds[j] = 1\n",
    "    j += 1\n",
    "    \n",
    "new_grid = []\n",
    "    \n",
    "size = 1310\n",
    "\n",
    "for i in grid:\n",
    "    if folds[0] and i[0] >= size // 2:\n",
    "        i[0] = size - i[0]\n",
    "    elif not folds[0] and i[1] >= size // 2:\n",
    "        i[1] = size - i[1]\n",
    "    \n",
    "    if not (str(i[0]) + \",\" + str(i[1])) in new_grid:\n",
    "        new_grid.append(str(i[0]) + \",\" + str(i[1]))\n",
    "\n",
    "print(len(new_grid))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "65dec165",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.image.AxesImage at 0x17dd8980d90>"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWoAAABRCAYAAAD7Euw5AAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAHBklEQVR4nO3cT6hcdxnG8e/jNaVaBds0LTVJbZW6KjXKJZuKVLAa3UQFpVnVVVxYqDvFjVUQiqjoSogaqKKWQq1mUYxBFHXTJi2x/1JjKNFeU5JqkDaKhqaPizlXx3T+5d5zZt6TPB8Id+bMyZxn3pnz3nN/8ztHtomIiLpet+gAERExWRp1RERxadQREcWlUUdEFJdGHRFRXBp1RERxr59lJUk7gG8BS8B3bd87af2rr1ryDVs3jH386BNvvJCMI73zln9OfHyWbUx7jnloI2df6lkhZ4X3HC6enG1o47VeDPX8F//grP+tUY9p2jxqSUvAUeB2YAU4COyy/cy4/7P8rsv96P6tY5/zQ2/dNnGbs9h/4vDEx2fZxrTnmIc2cvalnhVyVnjP4eLJ2YY2XuvFUM9H/Ete8umRjXqWoY/twDHbz9k+C9wP7FxLyIiIuHCzNOrNwPND91eaZRERMQezNOpRh+KvGS+RtFvSIUmHXvzbufUni4gIYLZGvQIMDzhvAU6cv5LtPbaXbS9v2rjUVr6IiEveLI36IHCTpBslXQbcAezrNlZERKyaOj3P9iuS7gL2M5iet9f2050nm4O+fKM9jwzzqEVf9KUWfck5zTxmbPR9X59pHrXth4GHO0sRERFj5czEiIji0qgjIopLo46IKC6NOiKiuDTqiIji0qgjIopLo46IKG6medRtq3ASSFvmcWnPPmSYRV/e90vlBIsqn4u+WOR+liPqiIji0qgjIopLo46IKC6NOiKiuDTqiIji0qgjIopLo46IKG4h86jbmG84jzm5fbngfhsXXp/H6+jL+17hPZ1FX3L2QZV9ZJwcUUdEFJdGHRFRXBp1RERxadQREcWlUUdEFJdGHRFRXBp1RERxadQREcUt5ISXKvpywf2IqqqfKLKq7/t6jqgjIopLo46IKC6NOiKiuDTqiIji0qgjIopLo46IKC6NOiKiuEt6HvU0F8tF6mfZRt/nmV6KKnw+2/hsrTdDG+ZRS1j7a5mpUUs6DrwMnANesb28pq1FRMQFu5Aj6vfb/mtnSSIiYqSMUUdEFDdrozbwC0mPSdrdZaCIiPh/sw593Gr7hKRrgAOSnrX9m+EVmga+G+D6zfmOMiKiLTMdUds+0fw8BTwEbB+xzh7by7aXN21cajdlRMQlbGqjlnSFpDev3gY+CDzVdbCIiBiYZYziWuAhSavr/8j2zztNFRER/yXb7T+p9CLwp6FFVwN9mNrXh5x9yAjJ2bbkbFfFnG+zvWnUA5006tdsRDrUh5Nk+pCzDxkhOduWnO3qS85VmUcdEVFcGnVERHHzatR75rSd9epDzj5khORsW3K2qy85gTmNUUdExNpl6CMiorhOG7WkHZL+IOmYpM93ua31kHRc0pOSDks6tOg8qyTtlXRK0lNDy66SdEDSH5ufVy4yY5NpVM57JP2lqelhSR9ZZMYm01ZJv5J0RNLTku5ulpep6YSMpeop6XJJj0r6fZPzS83yMrWckrNUPafpbOhD0hJwFLgdWAEOArtsP9PJBtehud72crXLuEp6H3AG+L7tm5tlXwVO2763+eV3pe3PFcx5D3DG9tcWmW2YpOuA62w/3pxt+xjwUeBTFKnphIyfpFA9NTgD7grbZyRtAH4H3A18nCK1nJJzB4XqOU2XR9TbgWO2n7N9Frgf2Nnh9i46zYWvTp+3eCdwX3P7PgY78UKNyVmO7RdsP97cfhk4AmymUE0nZCzFA2eauxuaf6ZQLWFizl7pslFvBp4fur9CwQ9co0+Xcb3W9gsw2KmBaxacZ5K7JD3RDI0sfIhmmKQbgHcDj1C0pudlhGL1lLQk6TBwCjhgu2Qtx+SEYvWcpMtGrRHLqv4mu9X2e4APA59p/pSP9fk28A5gG/AC8PWFphki6U3Ag8Bnbb+06DyjjMhYrp62z9neBmwBtku6ecGRRhqTs1w9J+myUa8AW4fubwFOdLi9NZvlMq6FnGzGMVfHM08tOM9Itk82O8irwHcoUtNmnPJB4Ie2f9IsLlXTURmr1hPA9t+BXzMY9y1Vy2HDOSvXc5QuG/VB4CZJN0q6DLgD2Nfh9tZE/buM6z7gzub2ncDPFphlrNWdtfExCtS0+WLpe8AR298YeqhMTcdlrFZPSZskvaW5/QbgA8CzFKoljM9ZrZ7TdHrCSzPl5ZvAErDX9lc629gaSXo7g6No+N9lXEvklPRj4DYGV/o6CXwR+CnwAHA98GfgE7YX+kXemJy3Mfiz0sBx4NOrY5eLIum9wG+BJ4FXm8VfYDAGXKKmEzLuolA9Jd3C4MvCJQYHfA/Y/rKkjRSp5ZScP6BQPafJmYkREcXlzMSIiOLSqCMiikujjogoLo06IqK4NOqIiOLSqCMiikujjogoLo06IqK4/wDymhIlmoxTwgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Day 13: Part 2\n",
    "\n",
    "data = get_lines(13)\n",
    "\n",
    "split = data.index(\"\")\n",
    "\n",
    "grid = []\n",
    "\n",
    "for i in range(split):\n",
    "    p = get_as_ints(data[i].split(\",\"))\n",
    "    grid.append([p[0], p[1]])\n",
    "    \n",
    "folds = []\n",
    "\n",
    "for i in range(split + 1, len(data)):\n",
    "    folds.append(\"x\" in data[i])\n",
    "   \n",
    "grid_size = [1311, 895]\n",
    "\n",
    "for foldX in folds:\n",
    "    size = grid_size[0] if foldX else grid_size[1]\n",
    "\n",
    "    if foldX:\n",
    "        grid_size[0] //= 2\n",
    "    else:\n",
    "        grid_size[1] //= 2\n",
    "    \n",
    "    new_grid = []\n",
    "    for i in grid:\n",
    "        if foldX and i[0] >= size // 2:\n",
    "            i[0] = size - 1 - i[0]\n",
    "        elif not foldX and i[1] >= size // 2:\n",
    "            i[1] = size - 1 - i[1]\n",
    "                \n",
    "        if not i in new_grid:\n",
    "            new_grid.append(i)\n",
    "\n",
    "    grid = new_grid\n",
    "\n",
    "display = np.zeros((6, 40))\n",
    "for p in grid:\n",
    "    display[p[1], p[0]] = 1\n",
    "\n",
    "plt.imshow(display, vmin = 0, vmax = 1)     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "ffd09de6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2712\n"
     ]
    }
   ],
   "source": [
    "# Day 14: Part 1\n",
    "data = get_lines(14)\n",
    "\n",
    "vals = {}\n",
    "\n",
    "for i in range(2, len(data)):\n",
    "    s = data[i].split(\" -> \")\n",
    "    vals[s[0]] = s[1]\n",
    "\n",
    "string = data[0]\n",
    "for i in range(10):\n",
    "    new_string = string[0]\n",
    "    for i in range(0, len(string) - 1):\n",
    "        key = string[i: i+2]\n",
    "        val = vals[key]\n",
    "        \n",
    "        new_string += val + key[1]\n",
    "    string = new_string\n",
    "\n",
    "chars = []\n",
    "counts = []\n",
    "\n",
    "for c in string:\n",
    "    if c in chars:\n",
    "        counts[chars.index(c)] += 1\n",
    "    else:\n",
    "        chars.append(c)\n",
    "        counts.append(1)\n",
    "        \n",
    "print(np.array(counts)[np.argsort(counts)][len(counts) - 1] - np.array(counts)[np.argsort(counts)][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "id": "9f60a98c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8336623059567\n"
     ]
    }
   ],
   "source": [
    "# Day 14: Part 2\n",
    "data = get_lines(14)\n",
    "\n",
    "vals = {}\n",
    "pairs = {}\n",
    "\n",
    "for i in range(2, len(data)):\n",
    "    s = data[i].split(\" -> \")\n",
    "    vals[s[0]] = s[1]\n",
    "    pairs[s[0]] = 0\n",
    "\n",
    "string = data[0]\n",
    "        \n",
    "for i in range(0, len(string) - 1):\n",
    "    pairs[string[i: i + 2:]] += 1\n",
    "          \n",
    "for i in range(40):\n",
    "    new_pairs = {}\n",
    "    for pair in pairs.keys():\n",
    "        new_pairs[pair] = 0\n",
    "    \n",
    "    for pair in pairs.keys():        \n",
    "        val = vals[pair]\n",
    "        new_pairs[pair[0] + val] += pairs[pair]\n",
    "        new_pairs[val + pair[1]] += pairs[pair]\n",
    "    pairs = new_pairs\n",
    "    \n",
    "chars = []\n",
    "counts = []\n",
    "\n",
    "for pair in pairs.keys():\n",
    "    if pair[0] in chars:\n",
    "        counts[chars.index(pair[0])] += pairs[pair]\n",
    "    else:\n",
    "        chars.append(pair[0])\n",
    "        counts.append(pairs[pair])\n",
    "\n",
    "counts[chars.index(string[::-1][0])] +=1\n",
    "        \n",
    "print(np.array(counts)[np.argsort(counts)][len(counts) - 1] - np.array(counts)[np.argsort(counts)][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "id": "3a5cb023",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "390\n"
     ]
    }
   ],
   "source": [
    "# Day 15: Part 1\n",
    "data = get_lines(15)\n",
    "\n",
    "size = len(data)\n",
    "\n",
    "grid = np.zeros((size, size))\n",
    "i = 0\n",
    "for line in data:\n",
    "    for c in line:\n",
    "        grid[i // size][i % size] = int(c)\n",
    "        i += 1\n",
    "        \n",
    "path = [[0, 0, 0]]\n",
    "explored = np.zeros((size, size))\n",
    "explored[0, 0] = 1\n",
    "min_path = None\n",
    "\n",
    "neighbors = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "\n",
    "def search():\n",
    "    global min_path, size\n",
    "    while len(path):\n",
    "        path.sort(key = lambda x: x[2])\n",
    "        x, y, cost = path.pop(0)\n",
    "        if min_path is None or cost < min_path:\n",
    "            for direction in neighbors:\n",
    "                new_pos = np.add([x, y], direction)\n",
    "                if not -1 in new_pos and not size in new_pos:\n",
    "                    if new_pos[0] == size - 1 and new_pos[1] ==  size - 1:\n",
    "                        cost += grid[new_pos[0], new_pos[1]]\n",
    "                        if min_path is None or cost < best:\n",
    "                            min_path = cost\n",
    "                            return\n",
    "                    if not explored[new_pos[0], new_pos[1]]:\n",
    "                        explored[new_pos[0], new_pos[1]] = 1\n",
    "                        path.append((new_pos[0], new_pos[1], cost + grid[new_pos[0], new_pos[1]]))\n",
    "\n",
    "search()\n",
    "print(int(min_path))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "id": "bc00deba",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2814\n"
     ]
    }
   ],
   "source": [
    "# Day 15: Part 2\n",
    "data = get_lines(15)\n",
    "\n",
    "size = len(data) * 5\n",
    "\n",
    "grid = np.zeros((size, size))\n",
    "i = 0\n",
    "for line in data:\n",
    "    for c in line:\n",
    "        grid[i // (size // 5)][i % (size // 5)] = int(c)\n",
    "        i += 1\n",
    "        \n",
    "pts = [(pt // len(data), pt % len(data), grid[pt // len(data), pt % len(data)]) for pt in range(len(data) * len(data))]\n",
    "\n",
    "for ox, oy in [(x // 5, x % 5) for x in range(1, 25)]:\n",
    "    for x, y, val in pts:\n",
    "        grid[x + ox * len(data), y + oy * len(data)] = (val - 1 + ox + oy) % 9 + 1\n",
    "\n",
    "path = [[0, 0, 0]]\n",
    "explored = np.zeros((size, size))\n",
    "explored[0, 0] = 1\n",
    "min_path = None\n",
    "\n",
    "neighbors = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "\n",
    "def search():\n",
    "    global min_path, size\n",
    "    while len(path):\n",
    "        path.sort(key = lambda x: x[2])\n",
    "        x, y, cost = path.pop(0)\n",
    "        if min_path is None or cost < min_path:\n",
    "            for direction in neighbors:\n",
    "                new_pos = np.add([x, y], direction)\n",
    "                if not -1 in new_pos and not size in new_pos:\n",
    "                    if new_pos[0] == size - 1 and new_pos[1] ==  size - 1:\n",
    "                        cost += grid[new_pos[0], new_pos[1]]\n",
    "                        if min_path is None or cost < best:\n",
    "                            min_path = cost\n",
    "                            return\n",
    "                    if not explored[new_pos[0], new_pos[1]]:\n",
    "                        explored[new_pos[0], new_pos[1]] = 1\n",
    "                        path.append((new_pos[0], new_pos[1], cost + grid[new_pos[0], new_pos[1]]))\n",
    "\n",
    "# search()\n",
    "print(int(min_path))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 297,
   "id": "b8b45eff",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "895\n"
     ]
    }
   ],
   "source": [
    "# Day 16: Part 1\n",
    "data = get_lines(16)[0]\n",
    "\n",
    "hex_to_bin = {\n",
    "    \"0\": \"0000\",\n",
    "    \"1\": \"0001\",\n",
    "    \"2\": \"0010\",\n",
    "    \"3\": \"0011\",\n",
    "    \"4\": \"0100\",\n",
    "    \"5\": \"0101\",\n",
    "    \"6\": \"0110\",\n",
    "    \"7\": \"0111\",\n",
    "    \"8\": \"1000\",\n",
    "    \"9\": \"1001\",\n",
    "    \"A\": \"1010\",\n",
    "    \"B\": \"1011\",\n",
    "    \"C\": \"1100\",\n",
    "    \"D\": \"1101\",\n",
    "    \"E\": \"1110\",\n",
    "    \"F\": \"1111\",\n",
    "}\n",
    "\n",
    "decoded = \"\"\n",
    "\n",
    "for c in data:\n",
    "    decoded += hex_to_bin[c]\n",
    "    \n",
    "version_sum = 0\n",
    "\n",
    "def parse_packet(start):\n",
    "    global version_sum\n",
    "    \n",
    "    value = None\n",
    "    v = int(decoded[start: start + 3], 2)\n",
    "    t = int(decoded[start + 3: start + 6], 2)\n",
    "\n",
    "    version_sum += v\n",
    "    \n",
    "    if t == 4:\n",
    "        start += 6\n",
    "        value = 0\n",
    "        while True:\n",
    "            value *= 16\n",
    "            value += int(decoded[start + 1: start + 5], 2)\n",
    "            start += 5\n",
    "            if decoded[start - 5] == \"0\":\n",
    "                break\n",
    "    else:\n",
    "        i = int(decoded[start + 6], 2)\n",
    "        l = int(decoded[start + 7: start + 7 + (15 if i == 0 else 11)], 2)\n",
    "        \n",
    "        start += 7\n",
    "        start += 15 if i == 0 else 11\n",
    "        \n",
    "        if i == 0: # length of subpackets\n",
    "            start_start = start\n",
    "            while True:\n",
    "                _, next_start = parse_packet(start)\n",
    "                start = next_start\n",
    "                \n",
    "                assert next_start > i\n",
    "                assert next_start - start_start <= l\n",
    "                \n",
    "                if next_start - start_start == l:\n",
    "                    break\n",
    "        else: # number of subpackets\n",
    "            for _ in range(l):\n",
    "                _, next_start = parse_packet(start)\n",
    "\n",
    "                assert next_start > start\n",
    "                start = next_start\n",
    "    return (v, start)\n",
    "\n",
    "parse_packet(0)\n",
    "print(version_sum)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 298,
   "id": "0d593524",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1148595959144\n"
     ]
    }
   ],
   "source": [
    "# Day 16: Part 1\n",
    "data = get_lines(16)[0]\n",
    "\n",
    "hex_to_bin = {\n",
    "    \"0\": \"0000\",\n",
    "    \"1\": \"0001\",\n",
    "    \"2\": \"0010\",\n",
    "    \"3\": \"0011\",\n",
    "    \"4\": \"0100\",\n",
    "    \"5\": \"0101\",\n",
    "    \"6\": \"0110\",\n",
    "    \"7\": \"0111\",\n",
    "    \"8\": \"1000\",\n",
    "    \"9\": \"1001\",\n",
    "    \"A\": \"1010\",\n",
    "    \"B\": \"1011\",\n",
    "    \"C\": \"1100\",\n",
    "    \"D\": \"1101\",\n",
    "    \"E\": \"1110\",\n",
    "    \"F\": \"1111\",\n",
    "}\n",
    "\n",
    "decoded = \"\"\n",
    "\n",
    "for c in data:\n",
    "    decoded += hex_to_bin[c]\n",
    "    \n",
    "version_sum = 0\n",
    "\n",
    "def parse_packet(start):\n",
    "    global version_sum\n",
    "    \n",
    "    value = None\n",
    "    v = int(decoded[start: start + 3], 2)\n",
    "    t = int(decoded[start + 3: start + 6], 2)\n",
    "\n",
    "    version_sum += v\n",
    "    \n",
    "    if t == 4:\n",
    "        start += 6\n",
    "        value = 0\n",
    "        while True:\n",
    "            value *= 16\n",
    "            value += int(decoded[start + 1: start + 5], 2)\n",
    "            start += 5\n",
    "            if decoded[start - 5] == \"0\":\n",
    "                break\n",
    "    else:\n",
    "        i = int(decoded[start + 6], 2)\n",
    "        l = int(decoded[start + 7: start + 7 + (15 if i == 0 else 11)], 2)\n",
    "        \n",
    "        start += 7\n",
    "        start += 15 if i == 0 else 11\n",
    "        \n",
    "        values = []\n",
    "        \n",
    "        if i == 0: # length of subpackets\n",
    "            start_start = start\n",
    "            while True:\n",
    "                _v, __v, next_start = parse_packet(start)\n",
    "                values.append(__v)\n",
    "                start = next_start\n",
    "                \n",
    "                assert next_start > i\n",
    "                assert next_start - start_start <= l\n",
    "                \n",
    "                if next_start - start_start == l:\n",
    "                    break\n",
    "        else: # number of subpackets\n",
    "            for _ in range(l):\n",
    "                _v, __v, next_start = parse_packet(start)\n",
    "                values.append(__v)\n",
    "                assert next_start > start\n",
    "                start = next_start\n",
    "                \n",
    "        if t == 0:\n",
    "            value = np.sum(values)\n",
    "        elif t == 1:\n",
    "            value = 1\n",
    "            for _v in values:\n",
    "                value *= _v\n",
    "        elif t == 2:\n",
    "            value = values[np.argsort(values)[0]]\n",
    "        elif t == 3: \n",
    "            value = values[np.argsort(values)[::-1][0]]\n",
    "        elif t == 5:\n",
    "            value = 1 if values[0] > values [1] else 0\n",
    "        elif t == 6:\n",
    "            value = 1 if values[0] < values [1] else 0\n",
    "        elif t == 7:\n",
    "            value = 1 if values[0] == values [1] else 0\n",
    "        \n",
    "    return (v, value, start)\n",
    "\n",
    "print(parse_packet(0)[1])\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 531,
   "id": "fcb81b40",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12246\n"
     ]
    }
   ],
   "source": [
    "# Day 17: Part 1\n",
    "data = get_lines(17)[0]\n",
    "\n",
    "start = [0, 0]\n",
    "\n",
    "pos = data[13:]\n",
    "# x min max, y min max\n",
    "points = get_as_ints(re.findall(\"-?\\\\d+\", pos))\n",
    "\n",
    "max_y_vel = points[2] * -1 - 1\n",
    "\n",
    "print(max_y_vel * (max_y_vel + 1) // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 532,
   "id": "879b1ed5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3528\n"
     ]
    }
   ],
   "source": [
    "# Day 17: Part 2\n",
    "data = get_lines(17)[0]\n",
    "\n",
    "pos_data = data[13:]\n",
    "# x min max, y min max\n",
    "points = get_as_ints(re.findall(\"-?\\\\d+\", pos_data))\n",
    "\n",
    "x_vel_min = 0\n",
    "\n",
    "while x_vel_min * (x_vel_min + 1) // 2 < points[0]:\n",
    "    x_vel_min+=1\n",
    "    \n",
    "y_vel_max = points[2] * -1 - 1\n",
    "\n",
    "x_vel_max = points[1]\n",
    "y_vel_min = points[2]\n",
    "\n",
    "total = 0\n",
    "\n",
    "for x_vel in range(x_vel_min, x_vel_max + 1):\n",
    "    for y_vel in range(y_vel_min, y_vel_max + 1):\n",
    "        pos = [0, 0]\n",
    "        \n",
    "        x_vel_run = x_vel\n",
    "        y_vel_run = y_vel\n",
    "        \n",
    "        while pos[0] <= points[1] and pos[1] >= points[2]:\n",
    "            pos[0] += x_vel_run\n",
    "            pos[1] += y_vel_run\n",
    "            \n",
    "            if x_vel_run > 0:\n",
    "                x_vel_run -= 1\n",
    "                \n",
    "            y_vel_run -= 1\n",
    "            \n",
    "            if pos[0] <= points[1] and pos[1] >= points[2]:\n",
    "                if pos[0] >= points[0] and pos[1] <= points[3]:\n",
    "                    total += 1\n",
    "                    break\n",
    "print(total)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 520,
   "id": "c923c7fc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3647\n"
     ]
    }
   ],
   "source": [
    "# Day 18: Part 1\n",
    "data = get_lines(18)\n",
    "\n",
    "numbers = []\n",
    "\n",
    "for line in data:\n",
    "    index = 0\n",
    "    array = []\n",
    "    for char in line:\n",
    "        if char == \"[\":\n",
    "            index += 1\n",
    "        elif char == \"]\":\n",
    "            index -= 1\n",
    "        elif char != \",\":\n",
    "            array.append([int(char), index])\n",
    "            \n",
    "    numbers.append(array)\n",
    "\n",
    "def add(n1, n2):\n",
    "    arr = n1 + n2\n",
    "    for val in arr:\n",
    "        val[1] += 1\n",
    "    return reduce(arr)\n",
    "\n",
    "def reduce(arr):\n",
    "    ex = explode(arr)\n",
    "    if ex != None:\n",
    "        return reduce(ex)\n",
    "    else:\n",
    "        sp = split(arr)\n",
    "        if sp != None:\n",
    "            return reduce(sp)\n",
    "        return arr\n",
    "    \n",
    "def explode(arr):\n",
    "    for i in range(len(arr) - 1):\n",
    "        if arr[i][1] >= 5 and arr[i + 1][1] == arr[i][1]:\n",
    "            if i > 0:\n",
    "                arr[i - 1][0] += arr[i][0]\n",
    "            if i + 2 < len(arr):\n",
    "                arr[i + 2][0] += arr[i + 1][0]\n",
    "            del arr[i + 1]\n",
    "            arr[i] = [0, arr[i][1] - 1]\n",
    "            \n",
    "            return arr\n",
    "            \n",
    "    return None\n",
    "\n",
    "def split(arr):\n",
    "    for i in range(len(arr)):\n",
    "        if arr[i][0] >= 10:\n",
    "            val = arr[i][0]\n",
    "            arr[i] = [val // 2, arr[i][1] + 1]\n",
    "            arr.insert(i + 1, [val - val // 2, arr[i][1]])\n",
    "            return arr\n",
    "    return None\n",
    "\n",
    "def mag(arr):\n",
    "    while len(arr) > 1:\n",
    "        for i in range(len(arr) - 1):\n",
    "            if arr[i][1] == arr[i + 1][1]:\n",
    "                arr[i][0] *= 3\n",
    "                arr[i][0] += 2 * arr[i + 1][0]\n",
    "                arr[i][1] -= 1\n",
    "                del arr[i + 1]\n",
    "                break\n",
    "    return arr[0][0]\n",
    "\n",
    "total = add(numbers[0], numbers[1])\n",
    "\n",
    "for i in range(2, len(numbers)):\n",
    "    total = add(total, numbers[i])\n",
    "\n",
    "print(mag(total))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 533,
   "id": "9a9f1dcb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4600\n"
     ]
    }
   ],
   "source": [
    "# Day 18: Part 2\n",
    "data = get_lines(18)\n",
    "\n",
    "numbers = []\n",
    "\n",
    "for line in data:\n",
    "    index = 0\n",
    "    array = []\n",
    "    for char in line:\n",
    "        if char == \"[\":\n",
    "            index += 1\n",
    "        elif char == \"]\":\n",
    "            index -= 1\n",
    "        elif char != \",\":\n",
    "            array.append([int(char), index])\n",
    "            \n",
    "    numbers.append(array)\n",
    "\n",
    "def add(n1, n2):\n",
    "    arr = n1 + n2\n",
    "    for val in arr:\n",
    "        val[1] += 1\n",
    "    return reduce(arr)\n",
    "\n",
    "def reduce(arr):\n",
    "    ex = explode(arr)\n",
    "    if ex != None:\n",
    "        return reduce(ex)\n",
    "    else:\n",
    "        sp = split(arr)\n",
    "        if sp != None:\n",
    "            return reduce(sp)\n",
    "        return arr\n",
    "    \n",
    "def explode(arr):\n",
    "    for i in range(len(arr) - 1):\n",
    "        if arr[i][1] >= 5 and arr[i + 1][1] == arr[i][1]:\n",
    "            if i > 0:\n",
    "                arr[i - 1][0] += arr[i][0]\n",
    "            if i + 2 < len(arr):\n",
    "                arr[i + 2][0] += arr[i + 1][0]\n",
    "            del arr[i + 1]\n",
    "            arr[i] = [0, arr[i][1] - 1]\n",
    "            \n",
    "            return arr\n",
    "            \n",
    "    return None\n",
    "\n",
    "def split(arr):\n",
    "    for i in range(len(arr)):\n",
    "        if arr[i][0] >= 10:\n",
    "            val = arr[i][0]\n",
    "            arr[i] = [val // 2, arr[i][1] + 1]\n",
    "            arr.insert(i + 1, [val - val // 2, arr[i][1]])\n",
    "            return arr\n",
    "    return None\n",
    "\n",
    "def mag(arr):\n",
    "    while len(arr) > 1:\n",
    "        for i in range(len(arr) - 1):\n",
    "            if arr[i][1] == arr[i + 1][1]:\n",
    "                arr[i][0] *= 3\n",
    "                arr[i][0] += 2 * arr[i + 1][0]\n",
    "                arr[i][1] -= 1\n",
    "                del arr[i + 1]\n",
    "                break\n",
    "    return arr[0][0]\n",
    "\n",
    "maximum = -1\n",
    "for i in range(0, len(numbers)):\n",
    "    for j in range(0, len(numbers)):\n",
    "        if i == j:\n",
    "            continue\n",
    "        _mag = mag(add(eval(repr(numbers[i])), eval(repr(numbers[j]))))\n",
    "        if _mag > maximum:\n",
    "            maximum = _mag\n",
    "\n",
    "print(maximum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 980,
   "id": "599cf77e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Day 19: Part 1/2 Data gathering\n",
    "data = get_lines(19)\n",
    "\n",
    "points = []\n",
    "scanner_points = []\n",
    "for i in range(1, len(data)):\n",
    "    if \"---\" in data[i]:\n",
    "        points.append(scanner_points)\n",
    "        scanner_points = []\n",
    "    elif \",\" in data[i]:\n",
    "        scanner_points.append(np.array(re.findall(\"-?\\\\d+\", data[i])).astype(np.int32))\n",
    "points.append(scanner_points)\n",
    "        \n",
    "def rotations():\n",
    "    vectors = [\n",
    "        (1, 0, 0),\n",
    "        (-1, 0, 0),\n",
    "        (0, 1, 0),\n",
    "        (0, -1, 0),\n",
    "        (0, 0, 1),\n",
    "        (0, 0, -1),\n",
    "    ]\n",
    "    vectors = list(map(np.array, vectors))\n",
    "    rotations = []\n",
    "    for vi in vectors:\n",
    "        for vj in vectors:\n",
    "            if vi.dot(vj) == 0:\n",
    "                vk = np.cross(vi, vj)\n",
    "                rotations.append(np.array([vi, vj, vk]))\n",
    "    return rotations\n",
    "\n",
    "rotations = list(rotations())\n",
    "\n",
    "# x, y, z, rotation_index (0 - 24)\n",
    "scanners = np.zeros((len(points), len(points), 4))\n",
    "scanners[:, :, 3] = -1\n",
    "\n",
    "def try_solve(i, j):\n",
    "    scanner_i_points = points[i]\n",
    "    scanner_j_points = points[j]\n",
    "    \n",
    "    for rot in range(len(rotations)):\n",
    "        delta_counts = {}\n",
    "        for start_i in scanner_i_points:\n",
    "            deltas = start_i - scanner_j_points @ rotations[rot]\n",
    "            for delta in deltas:\n",
    "                if not str(delta) in delta_counts.keys():\n",
    "                    delta_counts[str(delta)] = 1\n",
    "                else: \n",
    "                    delta_counts[str(delta)] += 1\n",
    "\n",
    "        for key in delta_counts.keys():\n",
    "            if delta_counts[key] >= 12:\n",
    "                delta = re.findall(\"-?\\\\d+\", key)\n",
    "                scanners[j][i] = [delta[0], delta[1], delta[2], rot]\n",
    "                return\n",
    "\n",
    "for i in range(len(scanners)):\n",
    "    for j in range(len(scanners)):\n",
    "        try_solve(i, j)\n",
    "\n",
    "scanners = np.array(scanners)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 976,
   "id": "117dda3d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "332\n"
     ]
    }
   ],
   "source": [
    "# Day 19: Part 1 Half 2\n",
    "pairs = [(0, 0)]\n",
    "\n",
    "stack = [0]\n",
    "completed = []\n",
    "while len(stack) != 0:\n",
    "    i = stack.pop()\n",
    "    for j in range(len(scanners)):\n",
    "        if j in completed or j in stack:\n",
    "            continue\n",
    "        if scanners[i,j,3] != -1 and not i == j:\n",
    "            pairs.append((j, i))\n",
    "            stack.insert(0, j)\n",
    "    completed.append(i)\n",
    "    \n",
    "seen_points = set()\n",
    "\n",
    "for i in range(len(scanners)):\n",
    "    pair = None\n",
    "    translated = points[i]\n",
    "    \n",
    "    while pair == None or pair[0] != 0:\n",
    "        for p in pairs:\n",
    "            if (pair == None and p[0] == i) or (pair != None and p[0] == pair[1]):\n",
    "                pair = p\n",
    "                break\n",
    "\n",
    "        rotation = rotations[int(scanners[pair[0], pair[1], 3])]\n",
    "        translated = translated @ rotation + scanners[pair[0], pair[1], 0:3]\n",
    "        \n",
    "    for point in translated:\n",
    "        seen_points.add(str(point))\n",
    "\n",
    "print(len(seen_points))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 979,
   "id": "8d45442a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8507.0\n"
     ]
    }
   ],
   "source": [
    "# Day 19: Part 2 Half 2\n",
    "\n",
    "locations = []\n",
    "\n",
    "for i in range(len(scanners)):\n",
    "    pair = None\n",
    "    translated = np.array([0,0,0])\n",
    "    \n",
    "    while pair == None or pair[0] != 0:\n",
    "        for p in pairs:\n",
    "            if (pair == None and p[0] == i) or (pair != None and p[0] == pair[1]):\n",
    "                pair = p\n",
    "                break\n",
    "\n",
    "        rotation = rotations[int(scanners[pair[0], pair[1], 3])]\n",
    "        translated = translated @ rotation + scanners[pair[0], pair[1], 0:3]\n",
    "    locations.append(translated)\n",
    "\n",
    "m = 0\n",
    "\n",
    "for a in locations:\n",
    "    for b in locations:\n",
    "        s = a - b\n",
    "        s = abs(s)\n",
    "        s = s.sum()\n",
    "        \n",
    "        if s > m:\n",
    "            m = s\n",
    "    \n",
    "print(int(m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 810,
   "id": "4d4c12b3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5846\n"
     ]
    }
   ],
   "source": [
    "# Day 20: Part 1\n",
    "data = get_lines(20)\n",
    "\n",
    "alg = data[0]\n",
    "\n",
    "start_img = np.zeros((len(data) - 2, len(data[2])))\n",
    "\n",
    "for i in range(2, len(data)):\n",
    "    for j in range(len(data[i])):\n",
    "        start_img[i - 2][j] = 1 if data[i][j] == \"#\" else 0\n",
    "\n",
    "def get_value(i, j, arr, default):\n",
    "    if i < 0 or i >= len(arr) or j < 0 or j >= len(arr[i]):\n",
    "        return 1 - default if alg[0] == \"#\" else 0\n",
    "    return arr[i, j]\n",
    "\n",
    "def run_step(img, step):\n",
    "    new_img = np.zeros((len(img) + 2, len(img) + 2))\n",
    "    for x in range(len(new_img)):\n",
    "        for y in range(len(new_img[x])):\n",
    "            n = 0\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    n *= 2\n",
    "                    n += get_value(x + i - 2, y + j - 2, img, step % 2)\n",
    "            new_img[x, y] = 1 if alg[int(n)] == \"#\" else 0\n",
    "    return new_img\n",
    "\n",
    "print(int(run_step(run_step(start_img, 1), 2).sum()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 981,
   "id": "b55c6c02",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "21149\n"
     ]
    }
   ],
   "source": [
    "# Day 20: Part 2\n",
    "data = get_lines(20)\n",
    "\n",
    "# data = \"\"\"..#.#..#####.#.#.#.###.##.....###.##.#..###.####..#####..#....#..#..##..###..######.###...####..#..#####..##..#.#####...##.#.#..#.##..#.#......#.###.######.###.####...#.##.##..#..#..#####.....#.#....###..#.##......#.....#..#..#..##..#...##.######.####.####.#.#...#.......#..#.#.#...####.##.#......#..#...##.#.##..#...##.#.##..###.#......#.#.......#.#.#.####.###.##...#.....####.#..#..#.##.#....##..#.####....##...##..#...#......#.#.......#.......##..####..#...#.#.#...##..#.#..###..#####........#..####......#..#\n",
    "\n",
    "# #..#.\n",
    "# #....\n",
    "# ##..#\n",
    "# ..#..\n",
    "# ..###\"\"\".split(\"\\n\")\n",
    "\n",
    "alg = data[0]\n",
    "\n",
    "start_img = np.zeros((len(data) - 2, len(data[2])))\n",
    "\n",
    "for i in range(2, len(data)):\n",
    "    for j in range(len(data[i])):\n",
    "        start_img[i - 2][j] = 1 if data[i][j] == \"#\" else 0\n",
    "\n",
    "def get_value(i, j, arr, default):\n",
    "    if i < 0 or i >= len(arr) or j < 0 or j >= len(arr[i]):\n",
    "        return 1 - default if alg[0] == \"#\" else 0\n",
    "    return arr[i, j]\n",
    "\n",
    "def run_step(img, step):\n",
    "    new_img = np.zeros((len(img) + 2, len(img) + 2))\n",
    "    for x in range(len(new_img)):\n",
    "        for y in range(len(new_img[x])):\n",
    "            n = 0\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    n *= 2\n",
    "                    n += get_value(x + i - 2, y + j - 2, img, step % 2)\n",
    "            new_img[x, y] = 1 if alg[int(n)] == \"#\" else 0\n",
    "    return new_img\n",
    "\n",
    "img = start_img\n",
    "\n",
    "for i in range(0, 50):\n",
    "    img = run_step(img, i + 1)\n",
    "print(int(img.sum()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1010,
   "id": "7e84b52e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "929625\n"
     ]
    }
   ],
   "source": [
    "# Day 21: Part 1\n",
    "data = get_lines(21)\n",
    "\n",
    "dice_roll = 0\n",
    "\n",
    "def get_roll():\n",
    "    global dice_roll\n",
    "    roll = dice_roll + 1\n",
    "    dice_roll += 1\n",
    "    dice_roll %= 100\n",
    "    return roll\n",
    "    \n",
    "players = [[int(data[0][::-1][0]),0],[int(data[1][::-1][0]),0]]\n",
    "\n",
    "def roll_and_add(player):\n",
    "    player[0] += get_roll() + get_roll() + get_roll() - 1\n",
    "    player[0] %= 10\n",
    "    player[0] += 1\n",
    "    player[1] += player[0]\n",
    "\n",
    "turn = 0\n",
    "while players[0][1] < 1000 and players[1][1] < 1000:\n",
    "    player = turn % 2\n",
    "    roll_and_add(players[player])\n",
    "    turn += 1\n",
    "\n",
    "print(turn * 3 * (players[0][1] if players[0][1] < players[1][1] else players[1][1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1053,
   "id": "bcfdc3fc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "175731756652760\n"
     ]
    }
   ],
   "source": [
    "# Day 21: Part 2\n",
    "data = get_lines(21)\n",
    "\n",
    "players = [[int(data[0][::-1][0]),0],[int(data[1][::-1][0]),0]]\n",
    "\n",
    "already_seen = {}\n",
    "\n",
    "def find_wins(players, turn, roll = 0):\n",
    "    turn_str = ((tuple(players[0]), tuple(players[1])), turn, roll)\n",
    "    if turn_str in already_seen.keys():\n",
    "        return already_seen[turn_str]\n",
    "    \n",
    "    player = turn % 2\n",
    "    new_players = [[players[0][0], players[0][1]], [players[1][0], players[1][1]]]\n",
    "    if not roll == 0:\n",
    "        new_players[player][0] += roll - 1\n",
    "        new_players[player][0] %= 10\n",
    "        new_players[player][0] += 1\n",
    "        new_players[player][1] += new_players[player][0]\n",
    "        \n",
    "        ret = None\n",
    "        if new_players[0][1] >= 21:\n",
    "            ret = (1, 0)\n",
    "        elif new_players[1][1] >= 21:\n",
    "            ret = (0, 1)\n",
    "            \n",
    "        if ret != None:\n",
    "            already_seen[turn_str] = ret\n",
    "            return ret\n",
    "        \n",
    "    one_wins = 0\n",
    "    two_wins = 0\n",
    "    for a in range(1, 4):\n",
    "        for b in range(1, 4):\n",
    "            for c in range(1, 4):\n",
    "                o, t = find_wins(new_players, turn + 1, a + b + c)\n",
    "                one_wins += o\n",
    "                two_wins += t\n",
    "                \n",
    "    ret = (one_wins, two_wins)\n",
    "    already_seen[turn_str] = ret\n",
    "    return ret\n",
    "\n",
    "one, two = find_wins(players, -1)\n",
    "print(one if one > two else two)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1119,
   "id": "0050502f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "474140\n",
      "intersects\n",
      "[[-5, 48, -31, 23, -19, 34], []]\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "# Day 22: Part 1\n",
    "data = get_lines(22)\n",
    "\n",
    "data = \"\"\"on x=-5..47,y=-31..22,z=-19..33\n",
    "on x=-44..5,y=-27..21,z=-14..35\n",
    "on x=-49..-1,y=-11..42,z=-10..38\n",
    "on x=-20..34,y=-40..6,z=-44..1\n",
    "off x=26..39,y=40..50,z=-2..11\n",
    "on x=-41..5,y=-41..6,z=-36..8\n",
    "off x=-43..-33,y=-45..-28,z=7..25\n",
    "on x=-33..15,y=-32..19,z=-34..11\n",
    "off x=35..47,y=-46..-34,z=-11..5\n",
    "on x=-14..36,y=-6..44,z=-16..29\n",
    "on x=-57795..-6158,y=29564..72030,z=20435..90618\n",
    "on x=36731..105352,y=-21140..28532,z=16094..90401\n",
    "on x=30999..107136,y=-53464..15513,z=8553..71215\n",
    "on x=13528..83982,y=-99403..-27377,z=-24141..23996\n",
    "on x=-72682..-12347,y=18159..111354,z=7391..80950\n",
    "on x=-1060..80757,y=-65301..-20884,z=-103788..-16709\n",
    "on x=-83015..-9461,y=-72160..-8347,z=-81239..-26856\n",
    "on x=-52752..22273,y=-49450..9096,z=54442..119054\n",
    "on x=-29982..40483,y=-108474..-28371,z=-24328..38471\n",
    "on x=-4958..62750,y=40422..118853,z=-7672..65583\n",
    "on x=55694..108686,y=-43367..46958,z=-26781..48729\n",
    "on x=-98497..-18186,y=-63569..3412,z=1232..88485\n",
    "on x=-726..56291,y=-62629..13224,z=18033..85226\n",
    "on x=-110886..-34664,y=-81338..-8658,z=8914..63723\n",
    "on x=-55829..24974,y=-16897..54165,z=-121762..-28058\n",
    "on x=-65152..-11147,y=22489..91432,z=-58782..1780\n",
    "on x=-120100..-32970,y=-46592..27473,z=-11695..61039\n",
    "on x=-18631..37533,y=-124565..-50804,z=-35667..28308\n",
    "on x=-57817..18248,y=49321..117703,z=5745..55881\n",
    "on x=14781..98692,y=-1341..70827,z=15753..70151\n",
    "on x=-34419..55919,y=-19626..40991,z=39015..114138\n",
    "on x=-60785..11593,y=-56135..2999,z=-95368..-26915\n",
    "on x=-32178..58085,y=17647..101866,z=-91405..-8878\n",
    "on x=-53655..12091,y=50097..105568,z=-75335..-4862\n",
    "on x=-111166..-40997,y=-71714..2688,z=5609..50954\n",
    "on x=-16602..70118,y=-98693..-44401,z=5197..76897\n",
    "on x=16383..101554,y=4615..83635,z=-44907..18747\n",
    "off x=-95822..-15171,y=-19987..48940,z=10804..104439\n",
    "on x=-89813..-14614,y=16069..88491,z=-3297..45228\n",
    "on x=41075..99376,y=-20427..49978,z=-52012..13762\n",
    "on x=-21330..50085,y=-17944..62733,z=-112280..-30197\n",
    "on x=-16478..35915,y=36008..118594,z=-7885..47086\n",
    "off x=-98156..-27851,y=-49952..43171,z=-99005..-8456\n",
    "off x=2032..69770,y=-71013..4824,z=7471..94418\n",
    "on x=43670..120875,y=-42068..12382,z=-24787..38892\n",
    "off x=37514..111226,y=-45862..25743,z=-16714..54663\n",
    "off x=25699..97951,y=-30668..59918,z=-15349..69697\n",
    "off x=-44271..17935,y=-9516..60759,z=49131..112598\n",
    "on x=-61695..-5813,y=40978..94975,z=8655..80240\n",
    "off x=-101086..-9439,y=-7088..67543,z=33935..83858\n",
    "off x=18020..114017,y=-48931..32606,z=21474..89843\n",
    "off x=-77139..10506,y=-89994..-18797,z=-80..59318\n",
    "off x=8476..79288,y=-75520..11602,z=-96624..-24783\n",
    "on x=-47488..-1262,y=24338..100707,z=16292..72967\n",
    "off x=-84341..13987,y=2429..92914,z=-90671..-1318\n",
    "off x=-37810..49457,y=-71013..-7894,z=-105357..-13188\n",
    "off x=-27365..46395,y=31009..98017,z=15428..76570\n",
    "off x=-70369..-16548,y=22648..78696,z=-1892..86821\n",
    "on x=-53470..21291,y=-120233..-33476,z=-44150..38147\n",
    "off x=-93533..-4276,y=-16170..68771,z=-104985..-24507\"\"\".split(\"\\n\")\n",
    "\n",
    "new_data = []\n",
    "\n",
    "for line in data:\n",
    "    new_data.append(('f' not in line, get_as_ints(re.findall(\"-?\\\\d+\", line))))\n",
    "    bounds = new_data[::-1][0][1]\n",
    "    bounds[1] += 1\n",
    "    bounds[3] += 1\n",
    "    bounds[5] += 1\n",
    "    \n",
    "grid = np.zeros((101, 101, 101))\n",
    "for i in range(20):\n",
    "    on = 1 if new_data[i][0] else 0\n",
    "    vs = new_data[i][1]\n",
    "    grid[vs[0] + 50: vs[1] + 50:, vs[2] + 50: vs[3] + 50:, vs[4] + 50: vs[5] + 50:] = on\n",
    "\n",
    "print(int(grid.sum()))\n",
    "\n",
    "\n",
    "\n",
    "def intersects(range0, range1):\n",
    "    return range0[0] <= range1[0] <= range0[1] or range0[0] <= range1[1] <= range0[1] or range1[0] <= range0[0] <= range1[1] or range1[0] <= range0[1] <= range0[1]\n",
    "\n",
    "# new bounds for this, new generic bounds, union\n",
    "def union_of(bounds_a, bounds_b):\n",
    "    if intersects(bounds_a[0:2], bounds_b[0:2]) and intersects(bounds_a[2:4], bounds_b[2:4]) and intersects(bounds_a[4:6], bounds_b[4:6]):\n",
    "            print(\"intersects\")\n",
    "            return ([], [], [])\n",
    "    else:\n",
    "        print(\"doesnt intersect\")\n",
    "        return ([bounds_a], [bounds_b], [])\n",
    "    \n",
    "on_points = 0\n",
    "completed = 0\n",
    "unions = []\n",
    "for on, bounds in new_data:\n",
    "    if len(unions) == 0 and on == 1:\n",
    "        unions.append(bounds)\n",
    "    \n",
    "    my_bounds = [bounds]\n",
    "    ui = 0\n",
    "    new_unions_step = []\n",
    "    for union in unions:\n",
    "        new_my_bounds = []\n",
    "        for my_bound in my_bounds:\n",
    "            new_bounds, new_unions, new_union = union_of(my_bound, union)\n",
    "            new_unions_step.append(new_unions)\n",
    "            if on == 1 and len(new_union) == 0:\n",
    "                new_my_bounds.append(new_union)\n",
    "        my_bounds = new_my_bounds\n",
    "    \n",
    "    for new_union_step in new_unions_step:\n",
    "        unions.append(new_union_step)\n",
    "    print(unions)\n",
    "    completed += 1\n",
    "    if completed == 1:\n",
    "        break\n",
    "print(on_points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "df63bd53",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}