Advent_of_Code_2020.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Advent of Code 2020",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/panthonies/adventofcode/blob/main/Advent_of_Code_2020.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "H3UxBJaml_9l"
      },
      "source": [
        "import pandas as pd\n",
        "import numpy as np\n",
        "import itertools\n",
        "import re\n",
        "from copy import deepcopy"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5fK4jQVemRg1"
      },
      "source": [
        "## Day 1\n",
        "data = pd.read_csv('day1input.txt', header=None)\n",
        "\n",
        "# Part 1\n",
        "x = list(itertools.combinations(data[0], 2))\n",
        "for combo in x:\n",
        "  if (sum(combo)) == 2020:\n",
        "    print(combo[0]*combo[1])\n",
        "    \n",
        "# Part 2\n",
        "x = list(itertools.combinations(data[0], 3))\n",
        "for combo in x:\n",
        "  if (sum(combo)) == 2020:\n",
        "    print(combo[0]*combo[1]*combo[2])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NVycxuew8tZx",
        "outputId": "cabc0134-07b6-4f84-afd1-de5adcd4c63a"
      },
      "source": [
        "## Day 2\n",
        "data = pd.read_csv('day2input.txt', header=None, names=['raw'])\n",
        "data = data.reindex(columns=['raw', 'min', 'max', 'letter', 'password', 'count'], fill_value='')\n",
        "valid = 0\n",
        "\n",
        "# Part 1\n",
        "for i, row in data.iterrows():\n",
        "  split = re.split('[ -]|: ', row.raw)\n",
        "  min = int(split[0])\n",
        "  max = int(split[1])\n",
        "  letter = split[2]\n",
        "  pwd = split[3]\n",
        "  count = pwd.count(letter)\n",
        "  if (count >= min) & (count <= max):\n",
        "    valid += 1\n",
        "  data.at[i, 'min'] = min\n",
        "  data.at[i, 'max']= max\n",
        "  data.at[i, 'letter'] = letter\n",
        "  data.at[i, 'password'] = pwd\n",
        "  data.at[i, 'count'] = count\n",
        "print(valid)\n",
        "\n",
        "# Part 2\n",
        "valid = 0\n",
        "for i, row in data.iterrows():\n",
        "  match = 0\n",
        "  first = row.password[row['min'] - 1]\n",
        "  last = row.password[row['max'] - 1]\n",
        "  if first == row.letter:\n",
        "    match += 1\n",
        "  if last == row.letter:\n",
        "    match += 1\n",
        "  if match == 1:\n",
        "    valid += 1\n",
        "print(valid)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "556\n",
            "605\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mmwWQjPx7eMO"
      },
      "source": [
        "# Day 3\n",
        "data = pd.read_csv('day3input.txt', header=None)\n",
        "\n",
        "# Part 1\n",
        "x1 = 0\n",
        "trees1 = 0\n",
        "for i, row in data.itertuples():\n",
        "  if row[(x1%31)] == '#':\n",
        "    trees1 += 1\n",
        "  x1 += 3\n",
        "print(trees1)\n",
        "\n",
        "# Part 2\n",
        "trees0, x0, trees2, x2, trees3, x3, trees4, x4 = 0, 0, 0, 0, 0, 0, 0, 0\n",
        "for i, row in data.itertuples():\n",
        "  if row[(x0%31)] == '#':\n",
        "    trees0 += 1\n",
        "  x0 += 1\n",
        "  if row[(x2%31)] == '#':\n",
        "    trees2 += 1\n",
        "  x2 += 5\n",
        "  if row[(x3%31)] == '#':\n",
        "    trees3 += 1\n",
        "  x3 += 7\n",
        "  if i%2 == 0:\n",
        "    if row[(x4%31)] == '#':\n",
        "      trees4 += 1\n",
        "    x4 += 1\n",
        "print(trees0*trees1*trees2*trees3*trees4)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y2JOS5Px7jop",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "96315a98-7ceb-40ee-b1e6-0cfbf3b29105"
      },
      "source": [
        "# Day 4\n",
        "input = pd.read_csv('day4input.txt', header=None, skip_blank_lines=False)\n",
        "rows_list = []\n",
        "index = 0\n",
        "d = {}\n",
        "for i, row in input.itertuples():\n",
        "  if pd.isna(row):\n",
        "    rows_list.append(d)\n",
        "    index += 1\n",
        "    d = {}\n",
        "    continue\n",
        "  fields = row.split()\n",
        "  for field in fields:\n",
        "    key = field.split(':')[0]\n",
        "    value = field.split(':')[1]\n",
        "    d[key] = value\n",
        "data = pd.DataFrame(rows_list, columns=['byr', 'iyr', 'eyr', 'hgt', 'hcl', 'ecl', 'pid', 'cid'])\n",
        "\n",
        "# Part 1\n",
        "valid = 0\n",
        "for i, row in data.iterrows():\n",
        "  if (pd.isna(row.byr) | pd.isna(row.iyr) | pd.isna(row.eyr) | pd.isna(row.hgt) | pd.isna(row.hcl) | pd.isna(row.ecl) | pd.isna(row.pid)):\n",
        "    continue\n",
        "  valid += 1\n",
        "print(valid)\n",
        "\n",
        "# Part 2\n",
        "valid = 0\n",
        "for i, row in data.iterrows():\n",
        "  if (pd.isna(row.byr) | pd.isna(row.iyr) | pd.isna(row.eyr) | pd.isna(row.hgt) | pd.isna(row.hcl) | pd.isna(row.ecl) | pd.isna(row.pid)):\n",
        "    continue\n",
        "  if not (len(row.byr) == 4 and row.byr.isdigit() and int(row.byr) >= 1920 and int(row.byr) <= 2002):\n",
        "    continue\n",
        "  if not (len(row.iyr) == 4 and row.iyr.isdigit() and int(row.iyr) >= 2010 and int(row.iyr) <= 2020):\n",
        "    continue\n",
        "  if not (len(row.eyr) == 4 and row.eyr.isdigit() and int(row.eyr) >= 2020 and int(row.eyr) <= 2030):\n",
        "    continue\n",
        "  if not (re.search('^[0-9]+(cm|in)$',row.hgt)):\n",
        "    continue\n",
        "  num = int(re.findall('[0-9]+', row.hgt)[0])\n",
        "  if not ((re.search('cm$', row.hgt) and num >= 150 and num <= 193) or (re.search('in$', row.hgt) and num >= 59 and num <= 76)):\n",
        "    continue\n",
        "  if not (re.search('#[0-9a-f]{6}', row.hcl)):\n",
        "    continue\n",
        "  if not (row.ecl in ['amb', 'blu', 'brn', 'gry', 'grn', 'hzl', 'oth']):\n",
        "    continue\n",
        "  if not (re.search('^[0-9]{9}$', row.pid)):\n",
        "    continue\n",
        "  valid += 1\n",
        "print(valid)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "237\n",
            "172\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "3NcJ9mCQ7snZ",
        "outputId": "9b90cd7c-4e87-4164-88c0-46afc2ed56bf"
      },
      "source": [
        "# Day 5\n",
        "data = pd.read_csv('day5input.txt', header=None, names=['seat'])\n",
        "data = data.reindex(columns=['seat', 'seat_row', 'seat_col', 'id'], fill_value=0)\n",
        "def get_seat(bin, num):\n",
        "  x = 0\n",
        "  for letter in bin:\n",
        "    if letter == 'B' or letter == 'R':\n",
        "      x = x + num/2\n",
        "      num = num/2\n",
        "    if letter == 'F' or letter == 'L':\n",
        "      num = num/2\n",
        "  return x\n",
        "\n",
        "# Part 1\n",
        "for i, row in data.iterrows():\n",
        "  bin_row = row.seat[0:7]\n",
        "  bin_col = row.seat[7:10]\n",
        "  data.at[i, 'seat_row'] = get_seat(bin_row, 128)\n",
        "  data.at[i, 'seat_col'] = get_seat(bin_col, 8)\n",
        "  data.at[i, 'id'] = data.at[i, 'seat_row'] * 8 + data.at[i, 'seat_col']\n",
        "ids = sorted(data['id'])\n",
        "max = ids[-1]\n",
        "print(max)\n",
        "\n",
        "# Part 2\n",
        "missing = sorted(set(range(ids[0], ids[-1] + 1)).difference(ids))[0]\n",
        "print(missing)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "832\n",
            "517\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7qttTvtiapmj",
        "outputId": "6d67d02b-faee-48f5-d9b1-68c773a90baf"
      },
      "source": [
        "# Day 6\n",
        "input = pd.read_csv('day6input.txt', header=None, skip_blank_lines=False)\n",
        "rows_list = []\n",
        "d = {}\n",
        "people = 0\n",
        "for i, row in input.itertuples():\n",
        "  if pd.isna(row):\n",
        "    d['people'] = people\n",
        "    rows_list.append(d)\n",
        "    d = {}\n",
        "    people = 0 \n",
        "    continue\n",
        "  people += 1\n",
        "  for letter in row:\n",
        "    if letter not in d:\n",
        "      d[letter] = 1\n",
        "    else:\n",
        "      d[letter] += 1\n",
        "  if i == len(input) - 1:\n",
        "    d['people'] = people\n",
        "    rows_list.append(d)\n",
        "\n",
        "# Part 1\n",
        "num = 0\n",
        "for row in rows_list:\n",
        "  num = num + len(row) - 1\n",
        "print(num)\n",
        "\n",
        "# Part 2\n",
        "num = 0\n",
        "for row in rows_list:\n",
        "  for answer in row:\n",
        "    if answer == 'people':\n",
        "      continue\n",
        "    if row['people'] == row[answer]:\n",
        "      num += 1\n",
        "print(num)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "6763\n",
            "3512\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UROIZnSgsNfV",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "24dca575-880f-4869-8cfd-fc487305fd2f"
      },
      "source": [
        "# Day 7\n",
        "with open('day7input.txt','r') as f:\n",
        "    input = f.read().split('\\n')\n",
        "\n",
        "bag_dict = {}\n",
        "for row in input:\n",
        "  split_row = re.split(' bags contain | bag[s]?[,.]{1}[ ]?', row) # 'no other' = none\n",
        "  parent_bag = split_row[0]\n",
        "  child_bags = split_row[1:len(split_row)-1]\n",
        "\n",
        "  if child_bags == ['no other']:\n",
        "    continue\n",
        "  bag_dict[parent_bag] = []\n",
        "  for child_bag in child_bags:\n",
        "    split_child_bag = re.split(' ', child_bag, maxsplit=1)\n",
        "    num = split_child_bag[0]\n",
        "    bag = split_child_bag[1]\n",
        "    bag_dict[parent_bag].append((bag, num))\n",
        "\n",
        "# Part 1\n",
        "def find_shiny_gold(bag):\n",
        "  if bag not in bag_dict:\n",
        "    return 0\n",
        "  running_count = 0\n",
        "  for child_bag in bag_dict[bag]:\n",
        "    if child_bag[0] == 'shiny gold':\n",
        "      return 1\n",
        "    running_count += find_shiny_gold(child_bag[0])\n",
        "  return running_count\n",
        "\n",
        "found = 0\n",
        "for bag in bag_dict:\n",
        "  if find_shiny_gold(bag) > 0:\n",
        "    found += 1\n",
        "print(found)\n",
        "\n",
        "# Part 2\n",
        "def count_bags_inside(bag):\n",
        "  if bag not in bag_dict:\n",
        "    return 0\n",
        "  running_count = 0\n",
        "  for child_bag in bag_dict[bag]:\n",
        "    bags_in_child = int(child_bag[1])\n",
        "    running_count += bags_in_child + bags_in_child * count_bags_inside(child_bag[0])\n",
        "  return running_count\n",
        "\n",
        "print(count_bags_inside('shiny gold'))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "172\n",
            "39645\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6LaHZswZNTXq",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "a77e1e73-c98f-469f-a79c-0493960d66d3"
      },
      "source": [
        "# Day 8\n",
        "data = pd.read_csv('day8input.txt', header=None, names=['raw'])\n",
        "data = data.reindex(columns=['raw', 'command', 'num'], fill_value='')\n",
        "data['repeat'] = 0\n",
        "\n",
        "for i, row in data.iterrows():\n",
        "  split = row.raw.split(\" \")\n",
        "  data.at[i, 'command'] = split[0]\n",
        "  sign = split[1][0]\n",
        "  num = int(split[1][1:len(split[1])])\n",
        "  if sign == \"+\":\n",
        "    data.at[i, 'num'] = num\n",
        "  else:\n",
        "    data.at[i, 'num'] = -num\n",
        "\n",
        "def get_acc_value(input, part1 = False):\n",
        "  data = input.copy()\n",
        "  accumulator = 0\n",
        "  index = 0\n",
        "  while (True):\n",
        "    if index == len(data) - 1:\n",
        "      return accumulator\n",
        "\n",
        "    if data['repeat'][index] == 1:\n",
        "      if part1 == False:\n",
        "        return -99999\n",
        "      else:\n",
        "        return accumulator\n",
        "\n",
        "    if data['command'][index] == \"acc\":\n",
        "      data.at[index, 'repeat'] = 1\n",
        "      accumulator += data['num'][index]\n",
        "      index += 1\n",
        "    elif data['command'][index] == \"jmp\":\n",
        "      data.at[index, 'repeat'] = 1\n",
        "      index += data['num'][index]\n",
        "    else:\n",
        "      data.at[index, 'repeat'] = 1\n",
        "      index += 1\n",
        "\n",
        "# Part 1\n",
        "print(get_acc_value(data, True))\n",
        "\n",
        "# Part 2\n",
        "for i, row in data.iterrows():\n",
        "  acc = 0\n",
        "  test = data.copy()\n",
        "  if row.command == 'jmp':\n",
        "    test.at[i, 'command'] = 'nop'\n",
        "    acc = get_acc_value(test)\n",
        "    if acc != -99999:\n",
        "      print(acc)\n",
        "  if row.command == 'nop':\n",
        "    test.at[i, 'command'] = 'jmp'\n",
        "    acc = get_acc_value(test)\n",
        "    if acc != -99999:\n",
        "      print(acc) "
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1744\n",
            "1174\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "jw3M1mlKxlML",
        "outputId": "cb5746a6-28a8-4872-e18b-dbd9fc30e3dd"
      },
      "source": [
        "# Day 9\n",
        "with open('day9input.txt','r') as f:\n",
        "    input = f.read().split('\\n')\n",
        "    input = [int(line) for line in input[0:len(input)-1]]\n",
        "\n",
        "def get_match(num_list, match):\n",
        "  x = list(itertools.combinations(num_list, 2))\n",
        "  for combo in x:\n",
        "    if (sum(combo)) == match:\n",
        "      return 1\n",
        "  return 0\n",
        "\n",
        "# Part 1\n",
        "preamble = []\n",
        "for i in input:\n",
        "  if len(preamble) == 25:\n",
        "    match = get_match(preamble, i)\n",
        "    if match == 0:\n",
        "      print(i)\n",
        "      break\n",
        "  preamble.append(i)\n",
        "  if len(preamble) < 25:\n",
        "    continue\n",
        "  if len(preamble) > 25:\n",
        "    preamble.pop(0)\n",
        "    \n",
        "# Part 2\n",
        "nums = []\n",
        "j = 0\n",
        "while sum(nums) != i:\n",
        "  if sum(nums) < i:\n",
        "    nums.append(input[j])\n",
        "    j += 1\n",
        "  if sum(nums) > i:\n",
        "    nums.pop(0)\n",
        "print(min(nums) + max(nums))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "556543474\n",
            "67638197\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "EwsYNUvySOWb",
        "outputId": "083f9934-4e9f-4087-bc22-98a637a7cb7d"
      },
      "source": [
        "# Day 10\n",
        "with open('day10input.txt','r') as f:\n",
        "    input = f.read().split('\\n')\n",
        "    input = sorted([int(line) for line in input[0:len(input)-1]])\n",
        "    input.append(max(input)+3)\n",
        "    input.insert(0, 0)\n",
        "  \n",
        "# Part1\n",
        "diff1 = 0\n",
        "diff3 = 0\n",
        "for idx, val in enumerate(input):\n",
        "  prev = input[idx-1]\n",
        "  if idx == 0:\n",
        "    prev = 0\n",
        "  if val - prev == 1:\n",
        "    diff1 += 1\n",
        "  if val - prev == 3:\n",
        "    diff3 += 1\n",
        "print(diff1*diff3)\n",
        "\n",
        "# Part 2\n",
        "def valid(input):\n",
        "  dropout = []\n",
        "  for idx, val in enumerate(input):\n",
        "    prev = input[idx-1]\n",
        "    if idx == 0:\n",
        "      continue\n",
        "    if val - prev > 3:\n",
        "      return 0\n",
        "    return 1\n",
        "  \n",
        "def get_ways(split):\n",
        "  global ways\n",
        "  is_valid = valid(split)\n",
        "  if is_valid == 0:\n",
        "    return 0\n",
        "  if is_valid == 1:\n",
        "    ways.add(tuple(split))\n",
        "\n",
        "  for idx, val in enumerate(split):\n",
        "    if idx == 0:\n",
        "      continue\n",
        "    if idx == len(split)-1:\n",
        "      continue\n",
        "    get_ways(split[:idx] + split[idx+1:])\n",
        "\n",
        "split_input = []\n",
        "first = 0\n",
        "for idx, val in enumerate(input):\n",
        "  prev = input[idx-1]\n",
        "  if idx == 0:\n",
        "    prev = 0\n",
        "  if val - prev == 3:\n",
        "    new = input[first:idx]\n",
        "    first = idx\n",
        "    if len(new) >= 3:\n",
        "      split_input.append(new)\n",
        "\n",
        "x = 1\n",
        "ways = set()\n",
        "for split in split_input:\n",
        "  get_ways(split)\n",
        "  x = x * len(ways)\n",
        "  ways = set()\n",
        "print(x)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2030\n",
            "42313823813632\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "kKDSJOKgcPbO",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "a9f7dc11-0d18-4419-e5c5-763f13bfb90d"
      },
      "source": [
        "# Day 11\n",
        "import hashlib\n",
        "with open('day11input.txt','r') as f:\n",
        "    input = f.read().split('\\n')\n",
        "    input = input[0:len(input)-1]\n",
        "\n",
        "def get_val(input, ix, iy, part=1):\n",
        "    maxrow = len(input)\n",
        "    maxcol = len(input[0])\n",
        "    if (ix) not in range(0, maxrow):\n",
        "        return 0\n",
        "    if (iy) not in range(0, maxcol):\n",
        "        return 0\n",
        "    val = input[ix][iy]\n",
        "    if val == '#':\n",
        "        return 1\n",
        "    if part == 2 and val == 'L':\n",
        "        return -1\n",
        "    else:\n",
        "        return 0\n",
        "\n",
        "def scan(input, threshold=4, part=1):\n",
        "    changes = []\n",
        "    output = input.copy()\n",
        "    for ix, x in enumerate(input):\n",
        "        for iy, y in enumerate(x):\n",
        "            if y == '.':\n",
        "                continue\n",
        "            if part == 1:\n",
        "                occ = get_surrounding(input, ix, iy)\n",
        "            else:\n",
        "                occ = get_surrounding_pt2(input, ix, iy)\n",
        "            if y == 'L' and occ == 0:\n",
        "                changes.append([ix, iy, '#'])\n",
        "            if y == '#' and occ >= threshold:\n",
        "                changes.append([ix, iy, 'L'])\n",
        "    # apply changes\n",
        "    for x in changes:\n",
        "        ix, iy, newval = x[0], x[1], x[2]\n",
        "        maxcol = len(input[0])\n",
        "        output[ix] = output[ix][0:iy] + newval + output[ix][iy+1:maxcol]\n",
        "    return output\n",
        "\n",
        "def count_occupied(input):\n",
        "    count = 0\n",
        "    for x in input:\n",
        "        for y in x:\n",
        "            if y == '#':\n",
        "                count += 1\n",
        "    return count\n",
        "\n",
        "# Part 1\n",
        "def get_surrounding(input, ix, iy):\n",
        "    # return # of occupied adjacent seats\n",
        "    a = get_val(input, ix-1, iy-1)\n",
        "    b = get_val(input, ix  , iy-1)\n",
        "    c = get_val(input, ix+1, iy-1)\n",
        "    d = get_val(input, ix-1, iy)\n",
        "    e = get_val(input, ix+1, iy)\n",
        "    f = get_val(input, ix-1, iy+1)\n",
        "    g = get_val(input, ix  , iy+1)\n",
        "    h = get_val(input, ix+1, iy+1)\n",
        "    return a+b+c+d+e+f+g+h\n",
        "\n",
        "states = {}     \n",
        "while True:\n",
        "    input = scan(input)\n",
        "    hash = hashlib.sha1(str(input).encode()).hexdigest()\n",
        "    if hash in states:\n",
        "        count = count_occupied(input)\n",
        "        print(count)\n",
        "        break\n",
        "    states[hash] = ''\n",
        "\n",
        "# Part 2 - Inefficient...takes a minute to run.\n",
        "with open('day11input.txt','r') as f:\n",
        "    input = f.read().split('\\n')\n",
        "    input = input[0:len(input)-1]\n",
        "\n",
        "def get_idxs(maxrow, maxcol, ix, iy, xop, yop):\n",
        "    while ix in range(0, maxrow) and iy in range(0, maxcol):\n",
        "        ix = ix + xop\n",
        "        iy = iy + yop\n",
        "        val = get_val(input, ix, iy, part=2)\n",
        "        if val == 1:\n",
        "            return 1\n",
        "        if val == -1:\n",
        "            return 0\n",
        "    return 0\n",
        "\n",
        "def get_surrounding_pt2(input, ix, iy):\n",
        "    # return # of occupied visible seats\n",
        "    val = 0\n",
        "    maxrow = len(input)\n",
        "    maxcol = len(input[0])\n",
        "    for x in [(-1, -1),(-1, 0),(-1, 1),(0, -1),(0, 1),(1, -1),(1, 0),(1, 1)]:\n",
        "        val += get_idxs(maxrow, maxcol, ix, iy, x[0], x[1])\n",
        "    return val\n",
        "\n",
        "states = {}     \n",
        "while True:\n",
        "    input = scan(input, threshold=5, part=2)\n",
        "    hash = hashlib.sha1(str(input).encode()).hexdigest()\n",
        "    if hash in states:\n",
        "        count = count_occupied(input)\n",
        "        print(count)\n",
        "        break\n",
        "    states[hash] = ''"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2334\n",
            "2100\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ulFsJwisyV6P",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "7df225f5-be2d-4245-a4bf-b15897f789b9"
      },
      "source": [
        "# Day 12\n",
        "with open('day12input.txt','r') as f:\n",
        "    input = [(line.strip()) for line in f]\n",
        "    input = [(x[0], int(x[1:len(x)])) for x in input]\n",
        "\n",
        "# Part 1\n",
        "x = 0\n",
        "y = 0\n",
        "facing = 'E'\n",
        "forward={'N': ('y', 1),  'E': ('x', 1), 'S': ('y', -1), 'W': ('x', -1)}\n",
        "dir_to_degrees={'N': 90, 'E': 0, 'S': 270, 'W': 180}\n",
        "degrees_to_dir={0: 'E', 90: 'N',180: 'W', 270: 'S'}\n",
        "\n",
        "for cmd in input:\n",
        "  dir, num = cmd[0], cmd[1]\n",
        "  if dir == 'F':\n",
        "    fcmd = forward[facing]\n",
        "    if fcmd[0] == 'y':\n",
        "      y += num * fcmd[1]\n",
        "    if fcmd[0] == 'x':\n",
        "      x += num * fcmd[1]\n",
        "  \n",
        "  if dir == 'L':\n",
        "    current_deg = dir_to_degrees[facing]\n",
        "    current_deg = (current_deg + num + 360)%360\n",
        "    facing = degrees_to_dir[current_deg]\n",
        "  if dir == 'R':\n",
        "    current_deg = dir_to_degrees[facing]\n",
        "    current_deg = (current_deg - num)%360\n",
        "    facing = degrees_to_dir[current_deg]\n",
        "\n",
        "  if dir == 'N':\n",
        "    y += num\n",
        "  if dir == 'S':\n",
        "    y -= num\n",
        "  if dir == 'E':\n",
        "    x += num\n",
        "  if dir == 'W':\n",
        "    x -= num\n",
        "print(abs(x)+abs(y))\n",
        "\n",
        "# Part 2\n",
        "x = 0\n",
        "y = 0\n",
        "wpx = 10\n",
        "wpy = 1\n",
        "facing = 'E'\n",
        "left_rotate={0: (1, 1), 90: (-1, 1),180: (-1, -1), 270: (1, -1)}\n",
        "right_rotate={0: (1, 1), 90: (1, -1),180: (-1, -1), 270: (-1, 1)}\n",
        "\n",
        "def rotate(wpx, wpy, deg, way):\n",
        "  deg = deg%360\n",
        "  if deg == 90 or deg == 270:\n",
        "    wpx, wpy = wpy, wpx\n",
        "  if way == 'L':\n",
        "    wpx = wpx*left_rotate[deg][0]\n",
        "    wpy = wpy*left_rotate[deg][1]\n",
        "  if way == 'R':\n",
        "    wpx = wpx*right_rotate[deg][0]\n",
        "    wpy = wpy*right_rotate[deg][1]\n",
        "  return wpx, wpy\n",
        "\n",
        "for cmd in input:\n",
        "  dir, num = cmd[0], cmd[1]\n",
        "  if dir == 'F':\n",
        "    x = x + wpx*num\n",
        "    y = y + wpy*num\n",
        "  \n",
        "  if dir == 'L':\n",
        "    wpx, wpy = rotate(wpx, wpy, num, 'L')\n",
        "  if dir == 'R':\n",
        "    wpx, wpy = rotate(wpx, wpy, num, 'R')\n",
        "\n",
        "  if dir == 'N':\n",
        "    wpy += num\n",
        "  if dir == 'S':\n",
        "    wpy -= num\n",
        "  if dir == 'E':\n",
        "    wpx += num\n",
        "  if dir == 'W':\n",
        "    wpx -= num\n",
        "print(abs(x)+abs(y))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "636\n",
            "26841\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "9o5JSZN6iBbh",
        "outputId": "844962f4-8c12-499a-8ae8-080d21b74f18"
      },
      "source": [
        "# Day 13\n",
        "with open('day13input.txt','r') as f:\n",
        "    input = [(line.strip()) for line in f]\n",
        "    timestamp = int(input[0])\n",
        "    all_buses = input[1].split(',')\n",
        "    buses = []\n",
        "    for idx, bus in enumerate(all_buses):\n",
        "      if bus.isdigit() == True:\n",
        "        buses.append(int(bus))\n",
        "\n",
        "# Part 1\n",
        "depart_time = timestamp\n",
        "flag = 0\n",
        "while flag == 0:\n",
        "  depart_time += 1  \n",
        "  for bus in buses:\n",
        "    if depart_time%bus == 0:\n",
        "      # print(f'Next bus: {bus} at timestamp {depart_time}')\n",
        "      flag = 1\n",
        "      break\n",
        "print((depart_time-timestamp)*bus)\n",
        "\n",
        "# Part 2\n",
        "bus_tuples = []\n",
        "for idx, bus in enumerate(all_buses):\n",
        "  if bus == 'x':\n",
        "    continue\n",
        "  bus_tuples.append((int(bus), idx%int(bus) if idx != 0 else 0))\n",
        "\n",
        "def is_valid_time(buses, time):\n",
        "  passed = 0\n",
        "  for bus in buses:\n",
        "    mod = time%bus[0] + bus[1]\n",
        "    if mod == bus[0] or mod == 0:\n",
        "      passed += 1\n",
        "  if passed == len(buses):\n",
        "    return True\n",
        "  return False\n",
        "\n",
        "def mini_check(bus_tuples, check, start, mult):\n",
        "  time = start\n",
        "  new_mult = 1\n",
        "  new_start = start\n",
        "\n",
        "  check_buses = []\n",
        "  for i in range(check):\n",
        "    check_buses.append(bus_tuples[i])\n",
        "    new_mult = new_mult * bus_tuples[i][0]\n",
        "  while True:\n",
        "    time += mult\n",
        "    if is_valid_time(check_buses, time):\n",
        "      new_start = time  \n",
        "      break\n",
        "\n",
        "  # print(f'New Start: {new_start}, New Mult: {new_mult}')\n",
        "  return new_start, new_mult\n",
        "\n",
        "new_mult = 1\n",
        "new_start = 0\n",
        "for i in range(2, len(bus_tuples)+1):\n",
        "  new_start, new_mult = mini_check(bus_tuples, check=i, start = new_start, mult=new_mult)\n",
        "print(new_start)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "4808\n",
            "741745043105674\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TpdEEcgS1kM9",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b6dbdedb-e296-4f15-bc4c-9fd9ef05491e"
      },
      "source": [
        "# Day 14\n",
        "with open('day14input.txt','r') as f:\n",
        "    input = [(line.strip()) for line in f]\n",
        "    input_part1 = [{int(re.search('(?<=\\[)[0-9]+(?=\\])', row).group(0)): '{:036b}'.format(int(row.split(' = ')[1]))} \n",
        "             if re.search('mem', row) \n",
        "             else {'1': [m.start(0) for m in re.finditer('1', row.split(' = ')[1])],\n",
        "                   '0': [m.start(0) for m in re.finditer('0', row.split(' = ')[1])]} for row in input]\n",
        "    input_part2 = [{'{:036b}'.format(int(re.search('(?<=\\[)[0-9]+(?=\\])', row).group(0))): int(row.split(' = ')[1])} \n",
        "             if re.search('mem', row) \n",
        "             else {'1': [m.start(0) for m in re.finditer('1', row.split(' = ')[1])],\n",
        "                   'float': [m.start(0) for m in re.finditer('X', row.split(' = ')[1])]} for row in input]\n",
        "# Part 1\n",
        "idx0, idx1 = [], []\n",
        "memory = {}\n",
        "for row in input_part1:\n",
        "    if '0' in row or '1' in row:\n",
        "        idx0, idx1 = row.get('0', []), row.get('1', [])\n",
        "    else:\n",
        "        memkey = list(row.keys())[0]\n",
        "        memval = row[memkey]\n",
        "        for idx in idx0:\n",
        "            memval = memval[:idx] + '0' + memval[idx+1:]\n",
        "        for idx in idx1:\n",
        "            memval = memval[:idx] + '1' + memval[idx+1:]\n",
        "        memory[memkey] = memval\n",
        "sum = 0\n",
        "for key in memory:\n",
        "    sum += int(memory[key], 2)\n",
        "print(sum) # 3059488894985\n",
        "\n",
        "# Part 2\n",
        "idx1, idxfloat = [], []\n",
        "memory = {}\n",
        "for row in input_part2:\n",
        "    if '1' in row or 'float' in row:\n",
        "        idx1, idxfloat = row.get('1', []), row.get('float', [])\n",
        "    else:\n",
        "        memkey = list(row.keys())[0]\n",
        "        memval = row[memkey]\n",
        "        for idx in idx1:\n",
        "            memkey = memkey[:idx] + '1' + memkey[idx+1:]\n",
        "        combos = list(itertools.product(['0', '1'], repeat = len(idxfloat)))\n",
        "        for i in combos:\n",
        "            float_memkey = memkey\n",
        "            for j in range(len(i)):\n",
        "                float_memkey = float_memkey[:idxfloat[j]] + i[j] + float_memkey[idxfloat[j]+1:]\n",
        "            memory[float_memkey] = memval\n",
        "sum = 0\n",
        "for key in memory:\n",
        "    sum += memory[key]\n",
        "print(sum) # 2900994392308"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "3059488894985\n",
            "2900994392308\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "PHEwgN4vXqL7",
        "outputId": "28e7b4f9-f4e7-47b1-c736-3dd5e1567d48"
      },
      "source": [
        "# Day 15\n",
        "def get_answer(input, stop):\n",
        "    round = len(input)\n",
        "    spoken = input[-1]\n",
        "    prev_idx = {}\n",
        "    for idx, val in enumerate(input[:-1]):\n",
        "        prev_idx[val] = idx+1\n",
        "\n",
        "    while True:\n",
        "        if round == stop:\n",
        "            return spoken \n",
        "        if spoken not in prev_idx:\n",
        "            prev_idx[spoken] = round\n",
        "            next_spoken = 0\n",
        "        else:\n",
        "            next_spoken = round-prev_idx[spoken]\n",
        "            prev_idx[spoken] = round\n",
        "        spoken = next_spoken\n",
        "        round += 1\n",
        "\n",
        "# Part 1\n",
        "print(get_answer(input=[14,8,16,0,1,17], stop=2020))\n",
        "\n",
        "# Part 2; ~12 seconds\n",
        "print(get_answer(input=[14,8,16,0,1,17], stop=30000000))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "240\n",
            "505\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "uP0Dc1cbem-y",
        "outputId": "7775db75-acb0-48f7-eecc-bb0dfb7a5a60"
      },
      "source": [
        "# Day 16\n",
        "with open('day16input.txt','r') as f:\n",
        "    input = f.read().split('\\n\\n')\n",
        "    fields = input[0]\n",
        "    fields = re.sub('[a-z| ]*: ', '', fields)\n",
        "    my_ticket = input[1].split(':\\n')[1]\n",
        "    my_ticket = [int(line) for line in my_ticket.split(',')]\n",
        "    nearby = input[2].split(':\\n')[1]\n",
        "\n",
        "# Part 1\n",
        "x = re.split('\\n| or ', fields)\n",
        "x = [(int(line.split('-')[0]), int(line.split('-')[1])) for line in x]\n",
        "\n",
        "y = nearby.split('\\n')\n",
        "y = [line.split(',') for line in y[:len(y)-1]]\n",
        "\n",
        "valid_tix = [my_ticket] # start with my own ticket\n",
        "sum = 0\n",
        "for ticket in y:\n",
        "    valid = True\n",
        "    for fieldval in ticket:\n",
        "        failed = 0\n",
        "        for ranges in x:\n",
        "            if int(fieldval) < ranges[0] or int(fieldval) > ranges[1]:\n",
        "                failed += 1\n",
        "        if failed == len(x):\n",
        "            sum += int(fieldval)\n",
        "            valid = False\n",
        "    if valid == True:\n",
        "        valid_tix.append(ticket)\n",
        "print(sum) # 25788\n",
        "\n",
        "# Part 2\n",
        "def is_valid(item, condition):\n",
        "    min1 = int(condition[0][0]) \n",
        "    max1 = int(condition[0][1]) \n",
        "    min2 = int(condition[1][0]) \n",
        "    max2 = int(condition[1][1]) \n",
        "    if int(item) not in range(min1, max1+1) and int(item) not in range(min2, max2+1):\n",
        "        return False\n",
        "    return True\n",
        "\n",
        "x = re.split('\\n', fields)\n",
        "x = [line.split(' or ') for line in x]\n",
        "x = [[(line[0].split('-')[0], line[0].split('-')[1]), (line[1].split('-')[0], line[1].split('-')[1])]  for line in x]\n",
        "df = pd.DataFrame(valid_tix)\n",
        "valid_cols = {}\n",
        "\n",
        "for idx, condition in enumerate(x):\n",
        "    if idx not in valid_cols:\n",
        "        valid_cols[idx] = []\n",
        "\n",
        "    # for each field, check the values on the ticket for that field\n",
        "    for col, data in df.iteritems():\n",
        "        valid = True\n",
        "        \n",
        "        # for each value, if it is valid for the field, then the ticket is ok\n",
        "        for item in data.values:\n",
        "            if not is_valid(item, condition):\n",
        "                valid = False\n",
        "                break\n",
        "        if valid == True:\n",
        "            valid_cols[idx].append(col)\n",
        "\n",
        "# manually look through the valid_cols dict to match fields with columns\n",
        "# turns out the departure fields 0-6 are for columns 13, 10, 7, 17, 19, 16\n",
        "# multiply the columns matching the six departure fields on my ticket together for the answer\n",
        "print(my_ticket[17]*my_ticket[13]*my_ticket[16]*my_ticket[19]*my_ticket[10]*my_ticket[7])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "25788\n",
            "3902565915559\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nEN87I3GWCSl",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "76d1b050-36cd-4e81-e7e8-6951c7e0605f"
      },
      "source": [
        "# Day 17\n",
        "input = '''####...#\n",
        "......##\n",
        "####..##\n",
        "##......\n",
        "..##.##.\n",
        "#.##...#\n",
        "....##.#\n",
        ".##.#.#.'''.split('\\n')\n",
        "\n",
        "# Part 1\n",
        "world = {\n",
        "    0: input,\n",
        "}\n",
        "\n",
        "def add_new_layer(old_world):\n",
        "    world = old_world.copy()\n",
        "    newrow = '.' * len(world[0][0]) # new row to insert\n",
        "    # Expand Z Axis\n",
        "    newz = [newrow] * len(world[0])\n",
        "    world[max(world) + 1], world[min(world) - 1] = newz, newz\n",
        "    # Expand X Axis\n",
        "    for z in world:\n",
        "         world[z] = [newrow] + world[z] + [newrow]\n",
        "    # Expand Y Axis\n",
        "    for z in world:\n",
        "         for x in range(0, len(world[z])):\n",
        "            world[z][x] = '.' + world[z][x] + '.'\n",
        "    return world\n",
        "\n",
        "def count_adj(z, x, y, world, original):\n",
        "    adj = 0\n",
        "    for z1 in [-1, 0, 1]:\n",
        "        for x1 in [-1, 0, 1]:\n",
        "            for y1 in [-1, 0, 1]:\n",
        "                try:\n",
        "                    if world[z+z1][x+x1][y+y1] == '#':\n",
        "                        adj += 1\n",
        "                except:\n",
        "                    pass\n",
        "    if original == '#':\n",
        "        adj = adj - 1\n",
        "    return adj\n",
        "\n",
        "def count_active_in_world(world):\n",
        "    active = 0\n",
        "    for z in world:\n",
        "        for x in range(0, len(world[z])):\n",
        "            for y in range(0, len(world[z][x])):\n",
        "                if world[z][x][y] == '#':\n",
        "                    active += 1\n",
        "    return active\n",
        "\n",
        "# Repeat for 6 rounds\n",
        "for _ in [0] * 6:\n",
        "    world = add_new_layer(world)\n",
        "    becomes_active = []\n",
        "    becomes_inactive = []\n",
        "    for z in world:\n",
        "        for x in range(0, len(world[z])):\n",
        "            for y in range(0, len(world[z][x])):\n",
        "                original = world[z][x][y]\n",
        "                adj = count_adj(z, x, y, world, original)\n",
        "                if original == '.' and adj == 3:\n",
        "                    becomes_active.append([z, x, y])\n",
        "                if original == '#' and not (adj == 2 or adj == 3):\n",
        "                    becomes_inactive.append([z, x, y])\n",
        "                \n",
        "    for point in becomes_active:\n",
        "        z, x, y = point[0], point[1], point[2]\n",
        "        world[z][x] = world[z][x][:y] + '#' + world[z][x][y+1:]\n",
        "    for point in becomes_inactive:\n",
        "        z, x, y = point[0], point[1], point[2]\n",
        "        world[z][x] = world[z][x][:y] + '.' + world[z][x][y+1:]\n",
        "print(count_active_in_world(world))\n",
        "\n",
        "\n",
        "# Part 2\n",
        "world = {\n",
        "    0: {0: input},\n",
        "}\n",
        "\n",
        "def add_new_layer(old_world): # DIMS: world[w][z][x][y]\n",
        "    world = old_world.copy()\n",
        "    newx = '.' * len(world[0][0][0])\n",
        "    newz = [newx] * len(world[0][0])\n",
        "    neww = {}\n",
        "    \n",
        "    # Expand W Axis\n",
        "    newmax = max(world) + 1\n",
        "    newmin = min(world) - 1\n",
        "    for z in world[0]:\n",
        "        neww[z] = newz\n",
        "    world[newmax], world[newmin] = neww, neww\n",
        "\n",
        "    # Expand Z Axis\n",
        "    newmax = max(world[0]) + 1\n",
        "    newmin = min(world[0]) - 1\n",
        "    for w in world:\n",
        "        world[w][newmax], world[w][newmin] = newz, newz\n",
        "\n",
        "    # Expand X Axis\n",
        "    x_copy = deepcopy(world)\n",
        "    for w in x_copy:\n",
        "        for z in x_copy[w]:\n",
        "            world[w][z] = [newx] + x_copy[w][z] + [newx]\n",
        "\n",
        "    # Expand Y Axis\n",
        "    y_copy = deepcopy(world)\n",
        "    for w in y_copy:\n",
        "        for z in y_copy[w]:\n",
        "            for x in range(0, len(y_copy[w][z])):\n",
        "                world[w][z][x] = '.' + y_copy[w][z][x] + '.'\n",
        "    return world\n",
        "\n",
        "def count_adj(w, z, x, y, world, original):\n",
        "    adj = 0\n",
        "    for w1 in [-1, 0, 1]:\n",
        "        for z1 in [-1, 0, 1]:\n",
        "            for x1 in [-1, 0, 1]:\n",
        "                for y1 in [-1, 0, 1]:\n",
        "                    try:\n",
        "                        if world[w+w1][z+z1][x+x1][y+y1] == '#':\n",
        "                            adj += 1\n",
        "                    except:\n",
        "                        pass\n",
        "    if original == '#':\n",
        "        adj = adj - 1\n",
        "    return adj\n",
        "\n",
        "def count_active_in_world(world):\n",
        "    active = 0\n",
        "    for w in world:\n",
        "        for z in world:\n",
        "            for x in range(0, len(world[w][z])):\n",
        "                for y in range(0, len(world[w][z][x])):\n",
        "                    if world[w][z][x][y] == '#':\n",
        "                        active += 1\n",
        "    return active\n",
        "\n",
        "# Repeat for 6 rounds\n",
        "for _ in [0] * 6:\n",
        "    world = add_new_layer(world)\n",
        "    becomes_active = []\n",
        "    becomes_inactive = []\n",
        "    for w in world:\n",
        "        for z in world[w]:\n",
        "            for x in range(0, len(world[w][z])):\n",
        "                for y in range(0, len(world[w][z][x])):\n",
        "                    original = world[w][z][x][y]\n",
        "                    adj = count_adj(w, z, x, y, world, original)\n",
        "                    if original == '.' and adj == 3:\n",
        "                        becomes_active.append([w, z, x, y])\n",
        "                    if original == '#' and not (adj == 2 or adj == 3):\n",
        "                        becomes_inactive.append([w, z, x, y])\n",
        "                \n",
        "    for point in becomes_active:\n",
        "        w, z, x, y = point[0], point[1], point[2], point[3]\n",
        "        world[w][z][x] = world[w][z][x][:y] + '#' + world[w][z][x][y+1:]\n",
        "    for point in becomes_inactive:\n",
        "        w, z, x, y = point[0], point[1], point[2], point[3]\n",
        "        world[w][z][x] = world[w][z][x][:y] + '.' + world[w][z][x][y+1:]\n",
        "print(count_active_in_world(world)) # 2448"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "237\n",
            "2448\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "gSseg1A_lZfJ",
        "outputId": "6037aeb6-3f0a-43e0-cf96-ef41486e13ba"
      },
      "source": [
        "# Day 18\n",
        "with open('day18input.txt','r') as f:\n",
        "    input = [(line.strip()) for line in f]\n",
        "    \n",
        "def eval_no_parens(state):\n",
        "    try:\n",
        "        state = state.group()\n",
        "    except:\n",
        "        pass\n",
        "    state = re.sub('\\(|\\)', '', state)\n",
        "    split = state.split(\" \")\n",
        "    while len(split) > 2:\n",
        "        first_op = str(eval(''.join(split[0:3])))\n",
        "        split = [first_op] + split[3:]\n",
        "    return ''.join(split)\n",
        "\n",
        "def get_solution(input):\n",
        "    while '(' in input:\n",
        "        input = re.sub(r'\\([^()]*\\)', eval_no_parens, input)\n",
        "    input = eval_no_parens(input)\n",
        "    return input\n",
        "\n",
        "sum = 0\n",
        "for line in input:\n",
        "    solution = get_solution(line)\n",
        "    sum += int(solution)\n",
        "print(sum)\n",
        "\n",
        "# Part 2\n",
        "def solve_part_two(input):\n",
        "    input = '(' + input + ')'\n",
        "    input = re.sub('\\*', ') * (', input)\n",
        "    ans = eval(input)\n",
        "    return ans\n",
        "\n",
        "sum = 0\n",
        "for line in input:\n",
        "    solution = solve_part_two(line)\n",
        "    sum += int(solution)\n",
        "    count += 1\n",
        "print(sum)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "30753705453324\n",
            "244817530095503\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "97750-3p_bvx"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "MRy6LsWb_xzD",
        "outputId": "e1a15dd9-eae3-42f3-8456-298ff39575f3"
      },
      "source": [
        "# Day 19\n",
        "with open('day19input.txt','r') as f:\n",
        "    input = f.read().split('\\n\\n')\n",
        "    rules = input[0].split('\\n')\n",
        "    messages = input[1].split('\\n')\n",
        "    messages = messages[:len(messages)-1]\n",
        "\n",
        "r = {}\n",
        "for row in rules:\n",
        "    s = row.split(': ')\n",
        "    key = (s[0])\n",
        "    if 'a' in row:\n",
        "        r[key] = 'a'\n",
        "        continue\n",
        "    if 'b' in row:\n",
        "        r[key] = 'b'\n",
        "        continue\n",
        "    val = s[1].split(' | ')\n",
        "    val = [t.split(' ') for t in val]\n",
        "    r[key] = val\n",
        "\n",
        "# Check to see if a string matches a specific rule option\n",
        "def run_seq(r, rule, string):\n",
        "    if not rule:\n",
        "        yield string\n",
        "    else:\n",
        "        k, *rule = rule\n",
        "        for string in run(r, k, string):\n",
        "            yield from run_seq(r, rule, string) \n",
        "\n",
        "\n",
        "# Check each option that produces a valid output\n",
        "def run_alt(r, rule_options, string):\n",
        "    for rule in rule_options:\n",
        "        yield from run_seq(r, rule, string)\n",
        "\n",
        "\n",
        "# Top-level check\n",
        "# If rule is a list, then move on to the next step. \n",
        "# Otherwise, return string leftovers.\n",
        "def run(r, rule, string):\n",
        "    if isinstance(r[rule], list):\n",
        "        yield from run_alt(r, r[rule], string)\n",
        "    else:\n",
        "        if string and (string[0] == r[rule]):\n",
        "            yield string[1:]\n",
        "\n",
        "# Check if a string matches rule 0\n",
        "def match(r, string):\n",
        "    return(any(m == '' for m in run(r, '0', string)))\n",
        "\n",
        "\n",
        "# Part 1\n",
        "sum = 0 \n",
        "for m in messages:\n",
        "    if match(r, m):\n",
        "        sum += 1\n",
        "print(sum)\n",
        "\n",
        "# Part 2\n",
        "r['8'] = [['42'], ['42', '8']]\n",
        "r['11'] = [['42', '31'], ['42', '11', '31']]\n",
        "sum = 0 \n",
        "for m in messages:\n",
        "    if match(r, m):\n",
        "        sum += 1\n",
        "print(sum)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "200\n",
            "407\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0QvLZ3VlN_Oi",
        "outputId": "bb9924c4-8306-4a79-8e5f-11994a082c7d"
      },
      "source": [
        "# Day 20\n",
        "with open('day20input.txt','r') as f:\n",
        "    input = f.read().split('\\n\\n')\n",
        "    input = input[:len(input)-1]\n",
        "\n",
        "tiles = {}\n",
        "positions = {}\n",
        "\n",
        "for tile in input:\n",
        "    tile_num = re.findall('(?<= )[0-9]{4}(?=:)', tile)[0]\n",
        "    tile_content = tile.split(':\\n')[1].split('\\n')\n",
        "    \n",
        "    top = tile_content[0]\n",
        "    bottom = tile_content[-1]\n",
        "    left = ''.join([x[0] for x in tile_content])\n",
        "    right = ''.join([x[-1] for x in tile_content])\n",
        "\n",
        "    tiles[tile_num] = {\n",
        "        'full': tile_content,\n",
        "        'sides': [top, bottom, left, right, top[::-1], bottom[::-1], left[::-1], right[::-1]]\n",
        "    }\n",
        "    positions[tile_num] = set()\n",
        "\n",
        "# Part 1\n",
        "for t1 in tiles:\n",
        "    for t2 in tiles:\n",
        "        # don't check against itself\n",
        "        if tiles[t1]['full'] == tiles[t2]['full']: \n",
        "            continue\n",
        "        for side1 in tiles[t1]['sides']:\n",
        "            for side2 in tiles[t2]['sides']:\n",
        "                if side1 == side2:\n",
        "                    positions[t1].add(t2)\n",
        "                    continue\n",
        "\n",
        "solution = 1\n",
        "edges = {}\n",
        "middle = {}\n",
        "start = ''\n",
        "for tile in positions:\n",
        "    if len(positions[tile]) == 2:\n",
        "        solution = solution * int(tile)\n",
        "        start = tile\n",
        "\n",
        "    if len(positions[tile]) <= 3:\n",
        "        edges[tile] = positions[tile]\n",
        "    else:\n",
        "        middle[tile] = positions[tile]\n",
        "print(solution)\n",
        "\n",
        "# Part 2\n",
        "def get_side_contents(row, positions, completed=[]):\n",
        "    done = False\n",
        "    while done == False:\n",
        "        # check the last tile\n",
        "        current_tile = row[-1]\n",
        "\n",
        "        for tile in positions[current_tile]:\n",
        "            \n",
        "            num_borders = len(positions[tile]) if tile in positions else None\n",
        "            if not num_borders:\n",
        "                continue\n",
        "            # end of row\n",
        "            if num_borders == 2 and tile not in row:\n",
        "                row.append(tile)\n",
        "                done = True\n",
        "                break\n",
        "            if num_borders == 3 and tile not in completed and tile not in row:\n",
        "                row.append(tile)\n",
        "                break\n",
        "    return row\n",
        "\n",
        "# Get edges of picture\n",
        "top_row = get_side_contents([start], edges)\n",
        "left_col = get_side_contents([top_row[0]], edges, completed = top_row)\n",
        "right_col = get_side_contents([top_row[-1]], edges, completed = top_row + left_col)\n",
        "bottom_row = get_side_contents([left_col[-1]], edges, completed = top_row + left_col + right_col)\n",
        "\n",
        "# Form edges of picture\n",
        "picture = [[0] * len(top_row)] * len(left_col)\n",
        "picture[0], picture[-1] = top_row, bottom_row\n",
        "\n",
        "picture = pd.DataFrame(picture)\n",
        "picture[0] = left_col\n",
        "picture[(len(picture)-1)] = right_col\n",
        "\n",
        "# Fill in middle of picture\n",
        "delete_these = []\n",
        "for i, row in picture.iterrows():\n",
        "    if i == 0 or i == len(picture) - 1:\n",
        "        continue\n",
        "    for j in [1, 10, 2, 9, 3, 8, 4, 7, 5, 6]: \n",
        "        surrounding_vals = [picture[i+1][j], picture[i-1][j], picture[i][j+1], picture[i][j-1]]\n",
        "        surrounding_vals = [x for x in surrounding_vals if x != 0]\n",
        "        # check all middle tiles for match\n",
        "        for middle_tile in middle:\n",
        "            match = 0\n",
        "            for middle_tile_border in middle[middle_tile]:\n",
        "                if middle_tile_border in surrounding_vals:\n",
        "                    match += 1\n",
        "            if match >= len(surrounding_vals):\n",
        "                picture.loc[j, i] = middle_tile\n",
        "                delete_these.append(middle_tile)\n",
        "    for i in delete_these:\n",
        "        try:\n",
        "            middle.pop(i)\n",
        "        except:\n",
        "            pass\n",
        "\n",
        "# picture ## This is the orientation of tile indexes\n",
        "\n",
        "# ----------------------------------------------------\n",
        "# Change all tiles to correct orientation\n",
        "def flip_horizontal(tile):\n",
        "    return [x[::-1] for x in tile]\n",
        "\n",
        "def rotate_90(tile):\n",
        "    return [''.join(x) for x in list(zip(*reversed(tile)))]\n",
        "\n",
        "def find_match(right_side, tile_pic):\n",
        "    # rotate until we find a match\n",
        "    for _ in [0] * 5:\n",
        "        left_side = ''.join([x[0] for x in tile_pic])\n",
        "        if left_side == right_side:\n",
        "            return tile_pic\n",
        "        tile_pic = rotate_90(tile_pic)\n",
        "\n",
        "    tile_pic = flip_horizontal(tile_pic)\n",
        "    for _ in [0] * 5:\n",
        "        left_side = ''.join([x[0] for x in tile_pic])\n",
        "        if left_side == right_side:\n",
        "            return tile_pic\n",
        "        tile_pic = rotate_90(tile_pic)\n",
        "    print(\"No Match\")\n",
        "    return \n",
        "\n",
        "def find_match_2(bottom_side, tile_pic):\n",
        "    # rotate until we find a match\n",
        "    for _ in [0] * 5:\n",
        "        top_side = tile_pic[0]\n",
        "        if top_side == bottom_side:\n",
        "            return tile_pic\n",
        "        tile_pic = rotate_90(tile_pic)\n",
        "\n",
        "    tile_pic = flip_horizontal(tile_pic)\n",
        "    for _ in [0] * 5:\n",
        "        top_side = tile_pic[0]\n",
        "        if top_side == bottom_side:\n",
        "            return tile_pic\n",
        "        tile_pic = rotate_90(tile_pic)\n",
        "    print(\"No Match\")\n",
        "    return \n",
        "\n",
        "# Go through all tiles, and change orientation in the tiles dictionary\n",
        "for row in range(0, len(picture)):\n",
        "    for col in range(0, len(picture)):\n",
        "        n = picture[col][row]\n",
        "        \n",
        "        # for the first column, check it with the one above\n",
        "        if col == 0:\n",
        "            if row == 0:\n",
        "                # getting orientation of first tile - not generalizable to other inputs\n",
        "                tiles[n]['full'] = flip_horizontal(tiles[n]['full']) \n",
        "                continue\n",
        "            else:\n",
        "                prev_pic = tiles[picture[col][row-1]]['full']\n",
        "                bottom_side = prev_pic[-1]\n",
        "                tile_pic = tiles[n]['full']\n",
        "                tile_pic = find_match_2(bottom_side, tile_pic)\n",
        "                tiles[n]['full'] = tile_pic\n",
        "                continue\n",
        "        \n",
        "        # for all other columns\n",
        "        prev_pic = tiles[picture[col-1][row]]['full']\n",
        "        right_side = ''.join([x[-1] for x in prev_pic])\n",
        "        tile_pic = tiles[n]['full']\n",
        "        tile_pic = find_match(right_side, tile_pic)\n",
        "\n",
        "        tiles[n]['full'] = tile_pic\n",
        "\n",
        "# Remove borders \n",
        "def remove_borders(tile): # tile is a list of strings\n",
        "    tile = [x[1:len(x)-1] for x in tile]\n",
        "    tile.pop(0)\n",
        "    tile.pop(len(tile)-1)\n",
        "    return tile\n",
        "\n",
        "for t in tiles:\n",
        "    tiles[t]['full'] = remove_borders(tiles[t]['full'])\n",
        "\n",
        "# Combine all tiles\n",
        "full_picture = []\n",
        "for row in range(0, len(picture)):\n",
        "    full_picture_row = [''] * 8\n",
        "    for col in range(0, len(picture)):\n",
        "        n = picture[col][row]\n",
        "        for idx, line in enumerate(tiles[n]['full']):\n",
        "            full_picture_row[idx] += line\n",
        "\n",
        "    full_picture = full_picture + full_picture_row\n",
        "\n",
        "# Rotate picture until we see monsters (not generalizable to other inputs)\n",
        "full_picture = rotate_90(rotate_90(full_picture))\n",
        "# full_picture ## This is the full picture\n",
        "\n",
        "# ----------------------------------------\n",
        "# Find the number of monsters\n",
        "monster = [(0,0), (1,-1), (4,-1), (5,0), (6,0), (7,-1), (10,-1), (11,0), (12,0), (13,-1), (16,-1), (17,0), (18,0), (19,0), (18,1)]\n",
        "num_monsters = 0\n",
        "for rowix, row in enumerate(full_picture):\n",
        "    for charix, char in enumerate(row):\n",
        "        count = 0\n",
        "        for i, j in monster:\n",
        "            try:\n",
        "                if full_picture[charix+i][rowix+j] == '#':\n",
        "                    count += 1\n",
        "            except:\n",
        "                pass\n",
        "        if count and count == len(monster):\n",
        "            # print(\"MONSTER FOUND\")\n",
        "            num_monsters += 1\n",
        "\n",
        "# Count the number of #'s that aren't part of sea monsters\n",
        "waves = 0\n",
        "for line in full_picture:\n",
        "    waves += line.count('#')\n",
        "print(waves - 15 * len(monster))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "54755174472007\n",
            "1692\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "TBovSgFVGxEg",
        "outputId": "624c1c8f-73af-477f-ba56-247c25e7c1ba"
      },
      "source": [
        "# Day 21\n",
        "with open('day21input.txt','r') as f:\n",
        "    input = [(line.strip()) for line in f]\n",
        "    ingredients = [x.split(' (')[0] for x in input]\n",
        "    allergens = [re.search('(?<=\\(contains ).+?(?=\\))', x).group(0) for x in input]\n",
        "\n",
        "# Identify potential ingredients for each allergen\n",
        "r = {}\n",
        "for i in range(0, len(input)):\n",
        "    food_list      = ingredients[i].split(' ')\n",
        "    allergens_list = allergens[i].split(', ')\n",
        "\n",
        "    for allerg in allergens_list:\n",
        "        if allerg not in r:\n",
        "            r[allerg] = food_list\n",
        "        else:\n",
        "            r[allerg] = list(set(r[allerg]) & set(food_list))\n",
        "\n",
        "# Create a list of all potential allergens\n",
        "potential_allergens = []\n",
        "for allergen in r:\n",
        "    for potential_ingredient in r[allergen]:\n",
        "        potential_allergens.append(potential_ingredient)\n",
        "\n",
        "# Part 1: Count the total number of non-allergen ingredients\n",
        "count = 0\n",
        "for recipe in ingredients:\n",
        "    recipe = recipe.split(' ')\n",
        "    for x in recipe:\n",
        "        if x not in potential_allergens:\n",
        "            count += 1\n",
        "print(count)\n",
        "\n",
        "# Part 2: List ingredients in alphabetical order\n",
        "map = { # since the list is short, we can create the map just by looking at 'r', the potential ingredients for each allergen\n",
        "    'nuts': 'kfxr',\n",
        "    'peanuts': 'xmhsbd',\n",
        "    'soy': 'chbtp',\n",
        "    'shellfish': 'xzhxj',\n",
        "    'wheat': 'cqvc',\n",
        "    'eggs': 'ntft',\n",
        "    'fish': 'nhx',\n",
        "    'sesame': 'rrjb'\n",
        "}\n",
        "all_allergens = ['nuts', 'peanuts', 'soy', 'shellfish', 'wheat', 'eggs', 'fish', 'sesame']\n",
        "all_allergens = sorted(all_allergens)\n",
        "\n",
        "solution = ''\n",
        "for x in all_allergens:\n",
        "    solution += map[x] + ','\n",
        "solution = solution[:len(solution)-1]\n",
        "print(solution)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1685\n",
            "ntft,nhx,kfxr,xmhsbd,rrjb,xzhxj,chbtp,cqvc\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Roj7LJZH0HZb",
        "outputId": "ee1d4d33-ba6f-4193-ca45-8d541e70f345"
      },
      "source": [
        "# Day 22\n",
        "with open('day22input.txt','r') as f:\n",
        "    input = f.read().split('\\n\\n')\n",
        "\n",
        "# Part 1\n",
        "player_one = [int(x) for x in input[0].split(':\\n')[1].split('\\n')]\n",
        "player_two = [int(x) for x in input[1][:-1].split(':\\n')[1].split('\\n')]\n",
        "\n",
        "def play_one_round(p1, p2):\n",
        "    card1 = p1.pop(0)\n",
        "    card2 = p2.pop(0)\n",
        "    if card1 > card2:\n",
        "        p1 += [card1] + [card2]\n",
        "    else:\n",
        "        p2 += [card2] + [card1]\n",
        "    return p1, p2\n",
        "\n",
        "def get_score(p1, p2):\n",
        "    score = 0\n",
        "    p = p1 if len(p1) > 0 else p2\n",
        "    for idx, x in enumerate(p):\n",
        "        score += x * (len(p) - idx)\n",
        "    return score\n",
        "\n",
        "while len(player_one) > 0 and len(player_two) > 0:\n",
        "    player_one, player_two = play_one_round(player_one, player_two)\n",
        "print(get_score(player_one, player_two))\n",
        "\n",
        "\n",
        "# Part 2 - takes a couple secs to run\n",
        "player_one = [int(x) for x in input[0].split(':\\n')[1].split('\\n')]\n",
        "player_two = [int(x) for x in input[1][:-1].split(':\\n')[1].split('\\n')]\n",
        "\n",
        "def play_one_round(p1, p2, prev_rounds):\n",
        "    # Check if this has been played before\n",
        "    cards = str(p1) + str(p2)\n",
        "    if cards in prev_rounds:\n",
        "        return p1, [], prev_rounds # give p1 the win\n",
        "    \n",
        "    prev_rounds.add(cards)\n",
        "    card1 = p1.pop(0)\n",
        "    card2 = p2.pop(0)\n",
        "\n",
        "    # Do a recursive combat\n",
        "    recursive, recursive_p2_win = False, False\n",
        "    if card1 <= len(p1) and card2 <=len(p2):\n",
        "        recursive = True\n",
        "        xp1, _, _ = play_game(p1[:card1], p2[:card2], prev_rounds = set())\n",
        "        if len(xp1) == 0:\n",
        "            recursive_p2_win = True\n",
        "\n",
        "    # Continue with game\n",
        "    if recursive and recursive_p2_win:\n",
        "        p2 += [card2] + [card1]\n",
        "    elif recursive and not recursive_p2_win:\n",
        "        p1 += [card1] + [card2]\n",
        "    elif (card1 > card2):\n",
        "        p1 += [card1] + [card2]\n",
        "    else:\n",
        "        p2 += [card2] + [card1]\n",
        "    return p1, p2, prev_rounds\n",
        "    \n",
        "\n",
        "def get_score(p1, p2):\n",
        "    score = 0\n",
        "    p = p1 if len(p1) > 0 else p2\n",
        "    for idx, x in enumerate(p):\n",
        "        score += x * (len(p) - idx)\n",
        "    return score\n",
        "\n",
        "\n",
        "def play_game(p1, p2, prev_rounds=set()):\n",
        "    while len(p1) > 0 and len(p2) > 0:\n",
        "        p1, p2, prev_rounds = play_one_round(p1, p2, prev_rounds)\n",
        "    return p1, p2, prev_rounds\n",
        "\n",
        "player_one, player_two, _ = play_game(player_one, player_two)\n",
        "print(get_score(player_one, player_two))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "31754\n",
            "35436\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "tL9ERoMijlvF",
        "outputId": "61a95774-0255-4d9f-e52c-25e38c2f11ae"
      },
      "source": [
        "# Day 23\n",
        "input = [5,3,8,9,1,4,7,6,2]\n",
        "#input = [3,8,9,1,2,5,4,6,7]\n",
        "\n",
        "# Part 1\n",
        "def get_cups(crab, input):\n",
        "    x = input.pop((input.index(crab) + 1) % len(input))\n",
        "    y = input.pop((input.index(crab) + 1) % len(input))\n",
        "    z = input.pop((input.index(crab) + 1) % len(input))\n",
        "    return x, y, z, input\n",
        "\n",
        "def find_dest_idx(crab, input):\n",
        "    dest = crab - 1\n",
        "    xmin, xmax = min(input), max(input)\n",
        "    while dest not in input:\n",
        "        dest = dest - 1\n",
        "        if dest < xmin:\n",
        "            dest = xmax\n",
        "    return input.index(dest)\n",
        "\n",
        "def score(input):\n",
        "    one = input.index(1)\n",
        "    s = input[one+1:] + input[:one]\n",
        "    s = [str(x) for x in s]\n",
        "    return ''.join(s)\n",
        "\n",
        "crab = input[0]\n",
        "moves = 0\n",
        "while moves < 100:\n",
        "    x, y, z, input = get_cups(crab, input)\n",
        "    dest_idx = find_dest_idx(crab, input)\n",
        "    input = input[:dest_idx + 1] + [x] + [y] + [z] + input[dest_idx + 1:]\n",
        "    crab = input[(input.index(crab)+1)%len(input)]\n",
        "    moves += 1\n",
        "print(score(input))\n",
        "\n",
        "# Part 2 Solution, taken from https://github.com/sophiebits/adventofcode/blob/main/2020/day23.py\n",
        "\n",
        "line = [5,3,8,9,1,4,7,6,2]\n",
        "line.extend(range(10, 10 ** 6 + 1))\n",
        "\n",
        "class Node:\n",
        "    __slots__ = ('value', 'next')\n",
        "    def __init__(self, value):\n",
        "        self.value = value\n",
        "        self.next = None\n",
        "\n",
        "def run(line, steps=100):\n",
        "    nodes = {num: Node(num) for num in line}\n",
        "    for num, num2 in zip(line, line[1:] + line[:1]):\n",
        "        nodes[num].next = nodes[num2]\n",
        "    front = nodes[line[0]]\n",
        "    for stepno in range(steps):\n",
        "        a = front.next\n",
        "        b = a.next\n",
        "        c = b.next\n",
        "\n",
        "        look = front.value\n",
        "        while True:\n",
        "            look -= 1\n",
        "            if look == 0:\n",
        "                look = len(line)\n",
        "            if look not in (a.value, b.value, c.value):\n",
        "                break\n",
        "\n",
        "        after = nodes[look]\n",
        "        front.next, front, after.next, c.next = c.next, c.next, a, after.next\n",
        "\n",
        "        if stepno % 1000000 == 0:\n",
        "            print(stepno)\n",
        "\n",
        "    print(nodes[1].next.value * nodes[1].next.next.value)\n",
        "\n",
        "run(line, 10 ** 7)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "54327968\n",
            "0\n",
            "1000000\n",
            "2000000\n",
            "3000000\n",
            "4000000\n",
            "5000000\n",
            "6000000\n",
            "7000000\n",
            "8000000\n",
            "9000000\n",
            "157410423276\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zRo_9cohiqby"
      },
      "source": [
        "# Day 23 Part 2 - Failed Attempt\n",
        "input = [3,8,9,1,2,5,4,6,7]\n",
        "labelslen = len(input)\n",
        "r = [0] * (labelslen+1)\n",
        "r[0] = input[0]\n",
        "for idx, x in enumerate(input):\n",
        "    if idx < len(input) - 1:\n",
        "        r[x] = input[idx+1]\n",
        "    else:\n",
        "        r[x] = 0\n",
        "        last_label = x\n",
        "\n",
        "def move(crab, r, labelslen, last_label):\n",
        "    print(\"Starting game...\", build(r))\n",
        "    print(f\"Linked: {r}\")\n",
        "    # get next 3 values\n",
        "    x = r[crab] if r[crab] != 0 else r[0]\n",
        "    y = r[x]    if r[x] != 0 else r[0]\n",
        "    z = r[y]    if r[y] != 0 else r[0]\n",
        "    if last_label in [x, y, z]:\n",
        "        r[last_label] = r[z]\n",
        "        last_label = XXXXXXX # NEEDS TO BE FIXED\n",
        "    # \"remove\" from the list\n",
        "    r[crab] = r[z] if r[z] != 0 else r[0]\n",
        "    print(f\"Removed {x}, {y}, {z} from r, which is now {r}\")\n",
        "\n",
        "    # find destination\n",
        "    dest = crab - 1\n",
        "    while dest in [x, y, z] or dest <= 0: \n",
        "        print(dest)   \n",
        "        if dest == 0:\n",
        "            dest = labelslen\n",
        "        else:\n",
        "            dest = dest - 1\n",
        "    if dest == 0:\n",
        "        dest = r[dest]\n",
        "    print(f\"Destination found at {dest}\")\n",
        "    # insert values at destination\n",
        "    dest_next = r[dest] if r[dest] != 0 else r[0]\n",
        "    if r[dest] != 0:\n",
        "        r[dest] = x\n",
        "    else:\n",
        "        r[r[dest]] = x\n",
        "    if r[z] != 0:\n",
        "        r[z] = dest_next\n",
        "    else:\n",
        "        r[r[z]] = dest_next\n",
        "    # new crab cup\n",
        "    crab = r[crab] if r[crab] != 0 else r[0]\n",
        "    #print(f'New crab at {crab}, in list {build(r)}, linked list {r}')\n",
        "    return crab, r\n",
        "\n",
        "# Part 2\n",
        "crab = input[0]\n",
        "moves = 0\n",
        "while moves < 100:\n",
        "    crab, r = move(crab, r, labelslen, last_label)\n",
        "    if len(r) != len(set(r)):\n",
        "        print(f\"YEET, {moves}\")\n",
        "        break\n",
        "    moves += 1"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "uHnsVE4TUAT8",
        "outputId": "1572333b-d5b8-4523-93b9-7160dc5965d5"
      },
      "source": [
        "# Day 24\n",
        "with open('day24input.txt','r') as f:\n",
        "    input = [(line.strip()) for line in f]\n",
        "    \n",
        "# Part 1\n",
        "r = []\n",
        "locs = []\n",
        "for tile in input:\n",
        "    loc = [0,0,0]\n",
        "\n",
        "    ne = re.findall('ne', tile)\n",
        "    tile = re.sub('ne', '', tile)\n",
        "\n",
        "    nw = re.findall('nw', tile)\n",
        "    tile = re.sub('nw', '', tile)\n",
        "\n",
        "    se = re.findall('se', tile)\n",
        "    tile = re.sub('se', '', tile)\n",
        "\n",
        "    sw = re.findall('sw', tile)\n",
        "    tile = re.sub('sw', '', tile)\n",
        "\n",
        "    e = re.findall('e', tile)\n",
        "    w = re.findall('w', tile)\n",
        "\n",
        "    for i in ne + nw + se + sw + e + w:\n",
        "        if i == 'e':\n",
        "            loc[0] += 1\n",
        "            loc[1] += -1\n",
        "        if i == 'w':\n",
        "            loc[0] += -1\n",
        "            loc[1] += +1\n",
        "        if i == 'ne':\n",
        "            loc[0] += 1\n",
        "            loc[2] += -1\n",
        "        if i == 'nw':\n",
        "            loc[1] += 1\n",
        "            loc[2] += -1\n",
        "        if i == 'se':\n",
        "            loc[1] += -1\n",
        "            loc[2] += 1\n",
        "        if i == 'sw':\n",
        "            loc[0] += -1\n",
        "            loc[2] += 1\n",
        "    locs.append(tuple(loc))\n",
        "locs = [x for x in locs if locs.count(x) == 1]\n",
        "print(len(locs)) # 287\n",
        "\n",
        "# Part 2\n",
        "world = {\n",
        "    (0,0,0): 1\n",
        "}\n",
        "\n",
        "def expand_world(world):\n",
        "    new_world = deepcopy(world)\n",
        "    for tile in world:\n",
        "        for x in [(0,-1,1),(1,-1,0),(1,0,-1),(0,1,-1),(-1,1,0),(-1,0,1)]:\n",
        "            border = (tile[0]+x[0], tile[1]+x[1], tile[2]+x[2])\n",
        "            if border not in world:\n",
        "                new_world[border] = 0\n",
        "    return new_world\n",
        "\n",
        "def count_black_tiles(world):\n",
        "    num = 0\n",
        "    for tile in world:\n",
        "        num += world[tile]\n",
        "    return num\n",
        "\n",
        "def num_adjacent_black(world, tile):\n",
        "    num = 0\n",
        "    for x in [(0,-1,1),(1,-1,0),(1,0,-1),(0,1,-1),(-1,1,0),(-1,0,1)]:\n",
        "        border = (tile[0]+x[0], tile[1]+x[1], tile[2]+x[2])\n",
        "        try:\n",
        "            num += world[border]\n",
        "        except:\n",
        "            pass\n",
        "    return num\n",
        "\n",
        "def day(world):\n",
        "    world = expand_world(world)\n",
        "    to_white = []\n",
        "    to_black = []\n",
        "    for tile in world:\n",
        "        num_adj = num_adjacent_black(world, tile)\n",
        "        if (world[tile] == 1 and num_adj == 0) or (world[tile] == 1 and num_adj > 2):\n",
        "            to_white.append(tile)\n",
        "        if world[tile] == 0 and num_adj == 2:\n",
        "            to_black.append(tile)\n",
        "\n",
        "    for x in to_white:\n",
        "        world[x] = 0\n",
        "    for x in to_black:\n",
        "        world[x] = 1\n",
        "    return world\n",
        "\n",
        "# Create initial world on Day 0 - black tiles\n",
        "for x in locs:\n",
        "    world[x] = 1\n",
        "\n",
        "# Repeat for 100 days - takes ~10 seconds\n",
        "for _ in [0]*100:\n",
        "    world = day(world)\n",
        "print(count_black_tiles(world))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "287\n",
            "3636\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "iGEYEpqBURnz",
        "outputId": "f636897a-79c5-499d-cee1-b3baed417f81"
      },
      "source": [
        "# Day 25!\n",
        "public_key_door = 9033205\n",
        "public_key_card = 9281649\n",
        "\n",
        "subject = 7\n",
        "big_number = 20201227\n",
        "\n",
        "# Get loop size of door\n",
        "val = 1\n",
        "door_loop_size = 0\n",
        "while val != public_key_door:\n",
        "    val = val * subject\n",
        "    val = val % big_number\n",
        "    door_loop_size += 1\n",
        "\n",
        "# Get loop size of card\n",
        "val = 1\n",
        "card_loop_size = 0\n",
        "while val != public_key_card:\n",
        "    val = val * subject\n",
        "    val = val % big_number\n",
        "    card_loop_size += 1\n",
        "\n",
        "# Get encryption key via door\n",
        "val = 1\n",
        "for _ in [0] * door_loop_size:\n",
        "    val = val * public_key_card\n",
        "    val = val % big_number\n",
        "print(val)\n",
        "\n",
        "# Get encryption key via card\n",
        "val = 1\n",
        "for _ in [0] * card_loop_size:\n",
        "    val = val * public_key_door\n",
        "    val = val % big_number\n",
        "print(val)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "9714832\n",
            "9714832\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}