2020/aoc2020.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyP1RAnZ2V/Jq3dZ00Wlonx/",
      "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/mgerlach/advent_of_code/blob/main/2020/aoc2020.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "62blI_vduSMW"
      },
      "source": [
        "Day 6\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "V-87NpbTuWMJ",
        "outputId": "3d78bfef-586f-4db7-9c65-eda30a24b936"
      },
      "source": [
        "letters = 'abcdefghijklmnopqrstuvwxyz'\n",
        "\n",
        "def groupsum(g):\n",
        "  hits_per_letter = list(map(lambda c: sum([(1 if c in f else 0) for f in g]), letters))\n",
        "  return len(list(filter(lambda h: h == len(g), hits_per_letter)))\n",
        "\n",
        "group = []\n",
        "sum = 0\n",
        "for l in open('input.txt'):\n",
        "  line = l.strip('\\n ')\n",
        "  if not line:\n",
        "    sum = sum + groupsum(group)\n",
        "    group = []\n",
        "  else:\n",
        "    for c in line:\n",
        "      group.append(line)\n",
        "\n",
        "sum + groupsum(group)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3360"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 21
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jx6fMmjPEjuK"
      },
      "source": [
        "Day 7"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ocF1lvsPCD1c"
      },
      "source": [
        "# vibrant indigo bags contain 3 vibrant turquoise bags, 4 faded magenta bags, 4 pale red bags, 4 mirrored turquoise bags.\n",
        "# ^([a-z ]+?) bags contain (.*)\\.$\n",
        "# (\\d+?) ([a-z ]+?) bags"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1zoxkApI-FmA"
      },
      "source": [
        "class Bag:\n",
        "  def __init__(self):\n",
        "    self.contained_in = [] # Bag\n",
        "    self.contains = [] # (Bag, n)\n",
        "    self.color = None\n",
        "  def __str__(self):\n",
        "    return f'{self.color} contains: {list(map(lambda c: f\"{c[1]}*{c[0].color}\", self.contains))}, contained in: {list(map(lambda c: f\"{c.color}\", self.contained_in))}'\n",
        "  __repr__ = __str__"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2v73sIwJNHnI"
      },
      "source": [
        "import re\n",
        "from functools import reduce\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-iyfgqCDNyTX"
      },
      "source": [
        "def lookup(color: str):\n",
        "  bag = index.get(color)\n",
        "  if bag is None:\n",
        "    bag = Bag()\n",
        "    bag.color = color\n",
        "    index[color] = bag\n",
        "  return bag"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "h0Rya3TTMrSA"
      },
      "source": [
        "index = {}\n",
        "for rule in open('input.txt'):\n",
        "  main_m = re.match('^([a-z ]+?) bags contain (.*)\\.$', rule)\n",
        "  main_color = main_m.group(1)\n",
        "  main_bag = lookup(main_color)\n",
        "  main_contains_rule = main_m.group(2)\n",
        "  for r in main_contains_rule.split(','):\n",
        "    m = re.match('(\\d+?) ([a-z ]+?) bags?', r.strip())\n",
        "    if (m is not None):\n",
        "      n = int(m.group(1))\n",
        "      color = m.group(2)\n",
        "      bag = lookup(color)\n",
        "      bag.contained_in.append(main_bag)\n",
        "      main_bag.contains.append((bag, n))\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "uLBYGKFbS-IR",
        "outputId": "84fd45f3-0d40-4ab5-82e9-0bad34c2d36b"
      },
      "source": [
        "index['shiny gold']\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "shiny gold contains: ['4*striped yellow', '3*drab olive', '1*bright purple'], contained in: ['dark cyan', 'dull coral', 'clear gold']"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 121
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "O9zGkVgOoPKU",
        "outputId": "d59277ba-44f2-47f7-b431-b454942b0558"
      },
      "source": [
        "index['striped yellow']"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "striped yellow contains: ['4*dark red', '3*vibrant crimson', '4*vibrant maroon', '1*mirrored lavender'], contained in: ['dull beige', 'mirrored salmon', 'dim silver', 'light turquoise', 'shiny green', 'dim bronze', 'shiny plum', 'mirrored silver', 'faded teal', 'dotted magenta', 'striped tomato', 'shiny gold', 'striped blue']"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 122
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ruAc9MPHRZEm",
        "outputId": "f48aa66b-7c8e-47ea-adeb-8874e93570a8"
      },
      "source": [
        "def collect_contained_in(bag: Bag, current: set):\n",
        "  return set((bag.color, )) | reduce(lambda s1, s2: s1 | s2, [collect_contained_in(b, current) for b in bag.contained_in], set())\n",
        "\n",
        "len(collect_contained_in(index['shiny gold'], set())) - 1\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "115"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 139
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Y5xLeiIsrtAJ",
        "outputId": "88614645-f6ba-4bb3-b030-e4abbb3c9a6b"
      },
      "source": [
        "def count_contains(bag):\n",
        "  return 1 + sum([b[1] * count_contains(b[0]) for b in bag.contains]) # bag.contains is a list of tupels (bag, n)\n",
        "\n",
        "count_contains(index['shiny gold']) - 1\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1250"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 128
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wGMhYSLWcs_L"
      },
      "source": [
        "Day 8"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EfGFxMc0dodw"
      },
      "source": [
        "import re"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "58H_26FmPOGS",
        "outputId": "c591ac3d-cf8e-4f29-c079-5336b46059c2"
      },
      "source": [
        "mem=[]\n",
        "for line in open('input08.txt'):\n",
        "  m = re.match('([a-z]+) ([0-9+-]+)', line)\n",
        "  mem.append((m.group(1), int(m.group(2))))\n",
        "\n",
        "queue = []\n",
        "queue.append((0, 0, set(), False)) # pc, acc, visited, nop/jmp flipped\n",
        "done = False\n",
        "while queue and not done:\n",
        "  (pc, acc, visited, flipped) = queue.pop(0)\n",
        "  if pc >= len(mem):\n",
        "    done = True\n",
        "    print(acc)\n",
        "  elif pc not in visited:\n",
        "    (cmd, arg) = mem[pc]\n",
        "    if (cmd == 'acc'):\n",
        "      queue.append((pc + 1, acc + arg, visited | { pc }, flipped))\n",
        "    elif cmd == 'nop':\n",
        "      queue.append((pc + 1, acc, visited | { pc }, flipped)) # nop\n",
        "      if not flipped:\n",
        "         queue.append((pc + arg, acc, visited | { pc }, True)) # jmp\n",
        "    elif cmd == 'jmp':\n",
        "      queue.append((pc + arg, acc, visited | { pc }, flipped)) # jmp\n",
        "      if not flipped:\n",
        "         queue.append((pc + 1, acc, visited | { pc }, True)) # nop\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "2060\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "fjS30aUcWWi6"
      },
      "source": [
        "Day 9"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "naCqDXZzWYjf",
        "outputId": "990bad36-0177-4515-a032-fe04e874bc8b"
      },
      "source": [
        "input=[int(l.strip('\\n ')) for l in open('input.txt')]\n",
        "preamble=25\n",
        "for i in range(preamble, len(input)):\n",
        "  found=False\n",
        "  for j in range(i-preamble, i):\n",
        "    if input[j] < input[i]:\n",
        "      for k in range(j+1, i):\n",
        "        if input[i] == input[j] + input[k]:\n",
        "          found=True\n",
        "          break\n",
        "      if found:\n",
        "        break\n",
        "  if not found:\n",
        "    print(f'{i}: {input[i]}')\n",
        "    invalid_index=i\n",
        "    invalid=input[i]\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "631: 776203571\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "YG_0sPRnWkcA",
        "outputId": "d7eabfef-67a9-4972-daa3-3d7a9705b71a"
      },
      "source": [
        "i=0\n",
        "window=[input[i]]\n",
        "while sum(window) != invalid and i < invalid_index:\n",
        "  window.append(input[i])\n",
        "  i = i + 1\n",
        "  while sum(window) > invalid:\n",
        "    window.pop(0)\n",
        "\n",
        "min(window) + max(window)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "104800569"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 16
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qqF2zbT4w2zf"
      },
      "source": [
        "Day 10"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LA7TTf8Mwx3h"
      },
      "source": [
        "input=sorted([int(l.strip('\\n ')) for l in open('input.txt')])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ErbXkxsa2vm8"
      },
      "source": [
        "input=sorted([int(l.strip('\\n ')) for l in open('input_short.txt')])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ey9I14Hav5jD"
      },
      "source": [
        "input=sorted([16,10,15,5,1,11,7,19,6,12,4])"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kR_6D8zGvzjT",
        "outputId": "cefce7c3-e643-444c-b467-5b9cbf84b3fb"
      },
      "source": [
        "# 1\n",
        "diffs = list(map(lambda pair: pair[1]-pair[0], zip([0] + input, input + [input[len(input)-1] + 3])))\n",
        "diffs.count(1) * diffs.count(3)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1876"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 53
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ZKe26jDsAXoo",
        "outputId": "2a0d526c-4c1d-45f9-948f-ce04fa6d9b67"
      },
      "source": [
        "# 2 attempt #1 brute force - too slow for large inputs\n",
        "inputx=[0] + input + [input[len(input)-1] + 3]\n",
        "counts=[0] * len(inputx)\n",
        "\n",
        "def count(index, counts):\n",
        "  if index == len(inputx) - 1:\n",
        "    counts[0] = counts[0] + 1\n",
        "    if(counts[0] % 1000000 == 0):\n",
        "      print(counts[0])\n",
        "  else:\n",
        "    step=1\n",
        "    while((index+step < len(inputx)) and (inputx[index+step]-inputx[index] <= 3)):\n",
        "      count(index+step, counts)\n",
        "      step = step + 1\n",
        "\n",
        "c = [0]\n",
        "count(0, c)\n",
        "c[0]\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "19208"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 44
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "HTxRpxFA_RrS",
        "outputId": "946bc771-13b9-4cb7-ef1e-8ac2ba99c41b"
      },
      "source": [
        "print(input)\n",
        "print(diffs)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[1, 2, 3, 6, 7, 10, 11, 12, 13, 16, 17, 18, 19, 20, 23, 24, 25, 26, 27, 30, 31, 32, 33, 34, 37, 38, 39, 40, 41, 44, 47, 50, 53, 54, 55, 58, 61, 62, 63, 64, 65, 68, 69, 70, 71, 72, 75, 76, 77, 78, 79, 82, 83, 86, 89, 90, 91, 92, 95, 96, 97, 98, 101, 102, 103, 104, 105, 108, 109, 110, 111, 112, 115, 116, 119, 120, 121, 124, 125, 126, 127, 128, 131, 132, 133, 134, 135, 138, 141, 142, 143, 144, 145, 148]\n",
            "[1, 1, 1, 3, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 3, 3, 3, 1, 1, 3, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 3, 3, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 3, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 3, 3]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0f6RG3LBsnL6",
        "outputId": "24000821-421b-4ce0-b254-09c5d268b93a"
      },
      "source": [
        "# 2 better: for each groups of sequences of diff 1, multiply number of possibilities for ommitting adapters (including none)\n",
        "# e. g. any adapter before diff=3 cannot be ommitted, out of n diff-1 adapters, only 2 consecutive adapters can be ommitted, etc.\n",
        "groups_of_ones_combinations=[1, 1, 2, 4, 7] # read: for a group of 4 consecutive diff-1 adapters there are 7 valid arrangements (tribonacci numbers)\n",
        "ones=0\n",
        "combinations=1\n",
        "for i in range(0, len(diffs)):\n",
        "  if diffs[i]==1:\n",
        "    ones=ones+1\n",
        "  else: # 3\n",
        "    combinations=combinations*groups_of_ones_combinations[ones]\n",
        "    ones=0\n",
        "\n",
        "combinations"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "14173478093824"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 69
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tgKJM9WdtRtI"
      },
      "source": [
        "Day 11"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-uW4NoJqtWJd"
      },
      "source": [
        "# 1\n",
        "current = [list(l.strip('\\n ')) for l in open('input_short.txt')]\n",
        "ylen = len(current) # y = rows, top->down\n",
        "xlen = len(current[0]) # x = cols, left->right\n",
        "deltas = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)] # (dy,dx), clockwise\n",
        "\n",
        "def p(cells):\n",
        "  for row in cells:\n",
        "    print(''.join(row))\n",
        "  print()\n",
        "\n",
        "def count_all_occ(cells):\n",
        "  return ''.join([''.join(row) for row in cells]).count('#')\n",
        "\n",
        "def iterate(cells):\n",
        "  next=[]\n",
        "  for y in range(0, ylen):\n",
        "    row = []\n",
        "    next.append(row)\n",
        "    for x in range(0, xlen):\n",
        "      cell = cells[y][x]\n",
        "      if cell != '.':\n",
        "        occ = len(list(filter(lambda c: c == '#', map(lambda d: cells[y+d[0]][x+d[1]] if y+d[0] in range(0,ylen) and x+d[1] in range(0,xlen) else '.', deltas))))\n",
        "        if (cell == 'L'):\n",
        "          if (occ == 0):\n",
        "            row.append('#')\n",
        "          else:\n",
        "            row.append('L')\n",
        "        else: #\n",
        "          if (occ >= 4):\n",
        "            row.append('L')\n",
        "          else:\n",
        "            row.append('#')\n",
        "      else:\n",
        "        row.append('.')\n",
        "  return next\n",
        "\n",
        "next = iterate(current)\n",
        "while next != current:\n",
        "  p(current)\n",
        "  current = next\n",
        "  next = iterate(current)\n",
        "\n",
        "#p(next)\n",
        "count_all_occ(current)\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "50zy6p8d9-QP"
      },
      "source": [
        "# 2\n",
        "current = [list(l.strip('\\n ')) for l in open('input.txt')]\n",
        "ylen = len(current) # y = rows, top->down\n",
        "xlen = len(current[0]) # x = cols, left->right\n",
        "deltas = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)] # (dy,dx), clockwise\n",
        "\n",
        "def p(cells):\n",
        "  for row in cells:\n",
        "    print(''.join(row))\n",
        "  print()\n",
        "\n",
        "def flatten_to_str(cells):\n",
        "  return ''.join([''.join(row) for row in cells])\n",
        "\n",
        "def count_all_occ(cells):\n",
        "  return flatten_to_str(cells).count('#')\n",
        "\n",
        "def count_occ(cells, y, x, d):\n",
        "  yy = y+d[0]\n",
        "  xx = x+d[1]\n",
        "  while yy in range(0, ylen) and xx in range(0, xlen):\n",
        "    c = cells[yy][xx]\n",
        "    if c != '.':\n",
        "      return 1 if c == '#' else 0 # return on first seat seen from (y,x) in direction d\n",
        "    yy = yy+d[0]\n",
        "    xx = xx+d[1]\n",
        "  return 0\n",
        "\n",
        "def iterate(cells):\n",
        "  next=[]\n",
        "  for y in range(0, ylen):\n",
        "    row = []\n",
        "    next.append(row)\n",
        "    for x in range(0, xlen):\n",
        "      cell = cells[y][x]\n",
        "      if cell != '.':\n",
        "        occ = sum(map(lambda d: count_occ(cells, y, x, d), deltas))\n",
        "        if (cell == 'L'):\n",
        "          if (occ == 0):\n",
        "            row.append('#')\n",
        "          else:\n",
        "            row.append('L')\n",
        "        elif cell == '#':\n",
        "          if (occ >= 5):\n",
        "            row.append('L')\n",
        "          else:\n",
        "            row.append('#')\n",
        "      else:\n",
        "        row.append('.')\n",
        "  return next\n",
        "\n",
        "next = iterate(current)\n",
        "while next != current:\n",
        "  p(current)\n",
        "  current = next\n",
        "  next = iterate(current)\n",
        "\n",
        "count_all_occ(current)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jULdbuOtj_DF"
      },
      "source": [
        "Day 12"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "tsxAYcCkj-wp",
        "outputId": "1ba6c1d7-8804-4652-c2c2-23bc74d9f0bf"
      },
      "source": [
        "# 1 move/rotate ship\n",
        "from numpy import array as a\n",
        "from functools import reduce\n",
        "\n",
        "# numpy arrays denote (y, x), i. e. (N/S, E/W) with N & E positive, S & W negative\n",
        "\n",
        "directions = [a([1,0]), a([0,1]), a([-1,0]), a([0,-1])]\n",
        "# index into directions to be multiplied with factor and added to the current position\n",
        "moves = {\n",
        "    'N': 0,\n",
        "    'E': 1,\n",
        "    'S': 2,\n",
        "    'W': 3\n",
        "}\n",
        "# with facing an index into directions, in order to turn right or left by given angle\n",
        "# new facing = (facing + turns['R' or 'L'] * angles[angle] + 4) % 4\n",
        "# + 4 to make positive, % (mod) 4 to limit to 0..3\n",
        "turns = {\n",
        "    'R':1,\n",
        "    'L':-1\n",
        "}\n",
        "angles = {\n",
        "    '0': 0,\n",
        "    '90': 1,\n",
        "    '180': 2,\n",
        "    '270': 3,\n",
        "    '360': 0\n",
        "}\n",
        "\n",
        "navigation=[l.strip('\\n ') for l in open('input.txt')]\n",
        "#navigation=\"F10 N3 F7 R90 F11\".split()\n",
        "\n",
        "start = {\n",
        "    'pos': a([0,0]),\n",
        "    'facing': 1   # index into directions for 'F'orward command\n",
        "}\n",
        "\n",
        "def apply(ship, instruction):\n",
        "  cmd = instruction[0]\n",
        "  param = instruction[1:]\n",
        "  pos = ship['pos']\n",
        "  facing = ship['facing']\n",
        "  if (cmd in moves):\n",
        "    return { 'pos': pos + directions[moves[cmd]] * int(param), 'facing': facing }\n",
        "  if (cmd in turns):\n",
        "    return { 'pos': pos, 'facing': (facing + turns[cmd] * angles[param] + 4) % 4 }\n",
        "  if (cmd == 'F'):\n",
        "    return { 'pos': pos + directions[facing] * int(param), 'facing': facing }\n",
        "  raise(f\"Unknown instruction {instruction}\")\n",
        "\n",
        "end = reduce(lambda ship, instruction: apply(ship, instruction), navigation, start)\n",
        "print(end)\n",
        "\n",
        "abs(end['pos'][0]) + abs(end['pos'][1])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "{'pos': array([-824,  658]), 'facing': 2}\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1482"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 32
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5tnpEVQ2tZxB",
        "outputId": "344205ec-90ad-4d35-84f6-d83327eb642e"
      },
      "source": [
        "# 2 move/rotate waypoint, only F actually moves the ship n times in the direction of the waypoint\n",
        "from numpy import array as a\n",
        "from functools import reduce\n",
        "\n",
        "# numpy arrays denote (y, x), i. e. (N/S, E/W) with N & E positive, S & W negative\n",
        "\n",
        "directions = [a([1,0]), a([0,1]), a([-1,0]), a([0,-1])]\n",
        "# index into directions to be multiplied with factor and added to the current position\n",
        "moves = {\n",
        "    'N': 0,\n",
        "    'E': 1,\n",
        "    'S': 2,\n",
        "    'W': 3\n",
        "}\n",
        "# matrices for rotating the waypoint a([y,x]): new waypoint = rotations[rotation].dot(waypoint)\n",
        "rotations = [\n",
        "     a([[1, 0], [0, 1]]),   # 0\n",
        "     a([[0, -1], [1, 0]]),  # R90 = L270\n",
        "     a([[-1, 0], [0, -1]]), # 180\n",
        "     a([[0, 1], [-1, 0]])   # R270 = L90\n",
        "]\n",
        "# to find the correct rotation (0..3, index into rotations), for commands like R90 or L180:\n",
        "# rotation = (turns['R' or 'L'] * angles[angle] + 4) % 4\n",
        "# + 4 to make positive, % (mod) 4 to limit to 0..3\n",
        "turns = {\n",
        "    'R':1,\n",
        "    'L':-1\n",
        "}\n",
        "angles = {\n",
        "    '0': 0,\n",
        "    '90': 1,\n",
        "    '180': 2,\n",
        "    '270': 3,\n",
        "    '360': 0\n",
        "}\n",
        "\n",
        "navigation=[l.strip('\\n ') for l in open('input.txt')]\n",
        "#navigation=\"F10 N3 F7 R90 F11\".split()\n",
        "\n",
        "start = {\n",
        "    'pos': a([0,0]),\n",
        "    'waypoint': a([1,10])\n",
        "}\n",
        "\n",
        "def apply(ship, instruction):\n",
        "  cmd = instruction[0]\n",
        "  param = instruction[1:]\n",
        "  pos = ship['pos']\n",
        "  waypoint = ship['waypoint']\n",
        "  if (cmd in moves):\n",
        "    return { 'pos': pos, 'waypoint': waypoint + directions[moves[cmd]] * int(param) }\n",
        "  if (cmd in turns):\n",
        "    return { 'pos': pos, 'waypoint': rotations[(turns[cmd] * angles[param] + 4) % 4].dot(waypoint) }\n",
        "  if (cmd == 'F'):\n",
        "    return { 'pos': pos + waypoint * int(param), 'waypoint':waypoint }\n",
        "  raise(f\"Unknown instruction {instruction}\")\n",
        "\n",
        "end = reduce(lambda ship, instruction: apply(ship, instruction), navigation, start)\n",
        "print(end)\n",
        "\n",
        "abs(end['pos'][0]) + abs(end['pos'][1])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "{'pos': array([-47410,  -1329]), 'waypoint': array([-25, -38])}\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "48739"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 48
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "q2zbszALv2li",
        "outputId": "cb144edb-6b1f-488b-ae13-d91a1b1c6f60"
      },
      "source": [
        "from numpy import array as a\n",
        "a([[0, -1], [1, 0]]).dot(a([4, 10])) # rotate (y,x) 90 deg clockwise(R), or (x,y) 90 deg counter-clockwise(L)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([-10,   4])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 49
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ZASyOJE01UI1"
      },
      "source": [
        "Day 13"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "bNFn0_mX1YNi",
        "outputId": "c2cc31f0-16b4-4275-8098-584e55e6f9bf"
      },
      "source": [
        "# 1\n",
        "input_lines=[l.strip('\\n ') for l in open('input.txt')]\n",
        "earliest = int(input_lines[0])\n",
        "buses = list(map(lambda id: int(id), filter(lambda id: id != 'x', input_lines[1].split(','))))\n",
        "#earliest = 939\n",
        "#buses = [7,13,59,31,19]\n",
        "print(earliest)\n",
        "print(buses)\n",
        "m = min(map(lambda b: (b, b - earliest % b), buses), key=lambda b: b[1])\n",
        "print(f\"bus {m[0]} wait {m[1]}\")\n",
        "m[0] * m[1]"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1000390\n",
            "[13, 41, 997, 23, 19, 29, 619, 37, 17]\n",
            "bus 17 wait 9\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "153"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 105
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "jMTI3LeuRlvh",
        "outputId": "bca625bc-f28f-4167-b5c0-ac232156df7c"
      },
      "source": [
        "def gcd(x, y):\n",
        "  while(y):\n",
        "    x, y = y, x % y\n",
        "  return x\n",
        "\n",
        "def lcm(x, y):\n",
        "  return (x*y)//gcd(x,y)\n",
        "\n",
        "lcm(91,19)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "1729"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 198
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "bu6TJ3C3BU00",
        "outputId": "d3a22e43-aa0c-4ce7-df50-90a094e8b514"
      },
      "source": [
        "# 2\n",
        "input_lines=[l.strip('\\n ') for l in open('input.txt')]\n",
        "input_buses = input_lines[1].split(',')\n",
        "# input_buses = ['7','13','x','x','59','x','31','19']\n",
        "\n",
        "# buses defined as pairs (id/interval, column/required offset)\n",
        "buses = list(map(lambda bus: (int(bus[0]), bus[1]), filter(lambda bus: bus[0] != 'x', zip(input_buses, range(0, len(input_buses))))))\n",
        "print(f'buses (id/interval, required offset): {buses}')\n",
        "\n",
        "def find_t(t0, step, buses):\n",
        "  found = False\n",
        "  t = t0-step\n",
        "  while not found:\n",
        "    t += step\n",
        "    found = len(list(filter(lambda bus: (t + bus[1]) % bus[0] == 0, buses))) == len(buses)\n",
        "  return t\n",
        "\n",
        "t = 0\n",
        "step = buses[0][0]  # interval of first bus\n",
        "for i in range(2, len(buses) + 1):\n",
        "  print(f'buses {buses[:i]}: t={t}, searching with step size {step}')\n",
        "  t = find_t(t, step, buses[:i])\n",
        "  step *= buses[i-1][0]  # for non-primes, would have to use step = lcm(step, buses[i-1][0])\n",
        "\n",
        "t"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "buses (id/interval, required offset): [(13, 0), (41, 3), (997, 13), (23, 21), (19, 32), (29, 42), (619, 44), (37, 50), (17, 61)]\n",
            "buses [(13, 0), (41, 3)]: t=0, searching with step size 13\n",
            "buses [(13, 0), (41, 3), (997, 13)]: t=325, searching with step size 533\n",
            "buses [(13, 0), (41, 3), (997, 13), (23, 21)]: t=25909, searching with step size 531401\n",
            "buses [(13, 0), (41, 3), (997, 13), (23, 21), (19, 32)]: t=11716731, searching with step size 12222223\n",
            "buses [(13, 0), (41, 3), (997, 13), (23, 21), (19, 32), (29, 42)]: t=97272292, searching with step size 232222237\n",
            "buses [(13, 0), (41, 3), (997, 13), (23, 21), (19, 32), (29, 42), (619, 44)]: t=5206161506, searching with step size 6734444873\n",
            "buses [(13, 0), (41, 3), (997, 13), (23, 21), (19, 32), (29, 42), (619, 44), (37, 50)]: t=739260652663, searching with step size 4168621376387\n",
            "buses [(13, 0), (41, 3), (997, 13), (23, 21), (19, 32), (29, 42), (619, 44), (37, 50), (17, 61)]: t=9076503405437, searching with step size 154238990926319\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "471793476184394"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 211
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Mfo5M_5xYz_P"
      },
      "source": [
        "Day 14"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8Atrg_ccY1r5",
        "outputId": "5f9bba09-5740-4f80-9f41-bbda1168e36a"
      },
      "source": [
        "# 1\n",
        "import re\n",
        "program=[l.strip('\\n ') for l in open('input.txt')]\n",
        "mem = dict()\n",
        "for l in program:\n",
        "  m = re.match('mask = ([01X]{36})', l)\n",
        "  if (m is not None):\n",
        "    mask = m.group(1)\n",
        "    mask0 = int(mask.replace('X', '1'), 2) # 1. bitwise AND: Set 0 where mask is 0\n",
        "    mask1 = int(mask.replace('X', '0'), 2) # 2. bitwise OR:  Set 1 where mask is 1\n",
        "  else:\n",
        "    m = re.match('mem\\[(\\d+)\\] = (\\d+)', l)\n",
        "    if (m is not None):\n",
        "      addr = m.group(1)\n",
        "      val = int(m.group(2))\n",
        "      mem[addr] = val & mask0 | mask1\n",
        "    else:\n",
        "      raise(f'unknown instruction {l}')\n",
        "\n",
        "sum(mem.values())\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4297467072083"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 55
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "S0dSzSbLslgv"
      },
      "source": [],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "V-1zpUWndcOz",
        "outputId": "9a97a176-0b6e-4be7-d389-9852ec8b09cd"
      },
      "source": [
        "# 2\n",
        "import re\n",
        "from functools import reduce\n",
        "program=[l.strip('\\n ') for l in open('input.txt')]\n",
        "#program=['mask = 00000000000000000000000000000000X0XX', 'mem[26] = 1']\n",
        "mem = dict()\n",
        "for l in program:\n",
        "  m = re.match('mask = ([01X]{36})', l)\n",
        "  if (m is not None):\n",
        "    mask = m.group(1)\n",
        "    float_count = mask.count('X')\n",
        "    masks1=[]\n",
        "    masks0=[]\n",
        "    for x in range(0, 1<<float_count):\n",
        "      msk0 = mask.replace('0', '1') # 1. bitwise AND: Do not change non X positions, for X=0 set 0,     for X=1 don't change\n",
        "      msk1 = mask                   # 2. bitwise OR:  1->1, 0->unchanged for non X,  for X=0 leave 0,   for X=1 set 1\n",
        "      for b in range(0, float_count):\n",
        "        bit_set = (x & (1<<b)) != 0\n",
        "        msk0 = msk0.replace('X', '1' if bit_set else '0', 1)\n",
        "        msk1 = msk1.replace('X', '1' if bit_set else '0', 1)\n",
        "      masks0.append(int(msk0, 2))\n",
        "      masks1.append(int(msk1, 2))\n",
        "  else:\n",
        "    m = re.match('mem\\[(\\d+)\\] = (\\d+)', l)\n",
        "    if (m is not None):\n",
        "      addr = int(m.group(1))\n",
        "      val = int(m.group(2))\n",
        "      for i in range(0, 1<<float_count):\n",
        "        #print(f'{addr & masks0[i] | masks1[i]}')\n",
        "        mem[addr & masks0[i] | masks1[i]] = val\n",
        "    else:\n",
        "      raise(f'unknown instruction {l}')\n",
        "\n",
        "sum(mem.values())"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "5030603328768"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 53
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mtnqsVxJ50GR"
      },
      "source": [
        "Day 15"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WVC6olKz5zwp"
      },
      "source": [
        "input=[2,15,0,9,1,20]\n",
        "mentions=dict()\n",
        "for i in range(0, len(input)):\n",
        "  mentions[input[i]] = (None, i)\n",
        "index=len(input)-1\n",
        "while index<30000000:\n",
        "  if (index % 100000 == 0):\n",
        "    print(index)\n",
        "  n = input[index]\n",
        "  last_mentioned = mentions[n]\n",
        "  next = 0 if last_mentioned[0] is None else last_mentioned[1] - last_mentioned[0]\n",
        "  input.append(next)\n",
        "  #print(input)\n",
        "  mentions[next] = (mentions[next][1], index+1) if next in mentions else (None, index+1)\n",
        "  index += 1\n",
        "\n",
        "input[29999999]\n",
        "\n",
        ""
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "xJuZS5E2VKKg"
      },
      "source": [
        "Day 16\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "VussVA7_VO85",
        "outputId": "f5060697-6b75-4bb8-99bf-dfafa2e94795"
      },
      "source": [
        "import re\n",
        "f = open('input.txt')\n",
        "rules = {}\n",
        "l = f.readline().strip('\\n ')\n",
        "while (l):\n",
        "  m = re.match('([a-z ]+): (\\d+)-(\\d+) or (\\d+)-(\\d+)', l)\n",
        "  rules[m.group(1)] = (range(int(m.group(2)), int(m.group(3))+1), range(int(m.group(4)), int(m.group(5))+1))\n",
        "  l = f.readline().strip('\\n ')\n",
        "\n",
        "while(not l):\n",
        "  l = f.readline().strip('\\n ')\n",
        "\n",
        "if (l == 'your ticket:'):\n",
        "  my_ticket = list(map(lambda s: int(s), f.readline().strip('\\n ').split(',')))\n",
        "else:\n",
        "  raise(Exception('parse error'))\n",
        "\n",
        "l = f.readline().strip('\\n ')\n",
        "while(not l):\n",
        "  l = f.readline().strip('\\n ')\n",
        "\n",
        "tickets = []\n",
        "\n",
        "if (l == 'nearby tickets:'):\n",
        "  l = f.readline().strip('\\n ')\n",
        "  while(l):\n",
        "    tickets.append(list(map(lambda s: int(s), l.split(','))))\n",
        "    l = f.readline().strip('\\n ')\n",
        "else:\n",
        "  raise(Exception('parse error'))\n",
        "\n",
        "print(rules)\n",
        "print(my_ticket)\n",
        "print(tickets)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "{'departure location': (range(30, 829), range(839, 972)), 'departure station': (range(38, 340), range(352, 959)), 'departure platform': (range(39, 906), range(921, 969)), 'departure track': (range(36, 571), range(586, 973)), 'departure date': (range(48, 191), range(196, 958)), 'departure time': (range(29, 484), range(491, 964)), 'arrival location': (range(28, 780), range(803, 960)), 'arrival station': (range(27, 222), range(238, 967)), 'arrival platform': (range(28, 733), range(741, 964)), 'arrival track': (range(41, 753), range(767, 968)), 'class': (range(27, 438), range(452, 973)), 'duration': (range(38, 94), range(107, 959)), 'price': (range(36, 197), range(213, 975)), 'route': (range(48, 859), range(880, 957)), 'row': (range(36, 60), range(73, 975)), 'seat': (range(39, 424), range(431, 975)), 'train': (range(38, 500), range(518, 959)), 'type': (range(45, 563), range(569, 962)), 'wagon': (range(28, 162), range(171, 960)), 'zone': (range(44, 76), range(83, 965))}\n",
            "[139, 113, 127, 181, 53, 149, 131, 239, 137, 241, 89, 151, 109, 73, 157, 59, 107, 83, 173, 179]\n",
            "[[475, 649, 830, 432, 685, 476, 743, 278, 558, 283, 496, 337, 83, 313, 153, 139, 405, 522, 648, 894], [888, 593, 683, 820, 389, 319, 405, 559, 465, 948, 359, 270, 811, 842, 555, 704, 542, 485, 255, 472], [371, 457, 149, 561, 468, 267, 459, 849, 482, 925, 281, 368, 222, 809, 700, 822, 612, 393, 90, 108], [179, 422, 138, 361, 55, 597, 825, 158, 395, 768, 403, 158, 807, 417, 282, 269, 708, 780, 549, 148], [731, 113, 414, 421, 904, 93, 133, 456, 59, 616, 640, 478, 521, 352, 804, 238, 132, 891, 568, 306], [572, 806, 150, 654, 768, 534, 635, 621, 891, 900, 56, 468, 552, 673, 372, 376, 463, 92, 493, 390], [461, 394, 305, 569, 371, 825, 684, 824, 187, 591, 262, 363, 935, 935, 730, 752, 885, 104, 434, 826], [834, 663, 318, 632, 668, 940, 670, 400, 633, 354, 399, 744, 630, 521, 684, 821, 640, 74, 748, 74], [335, 637, 199, 594, 687, 940, 904, 530, 262, 664, 642, 895, 398, 642, 648, 187, 372, 335, 592, 480], [531, 624, 844, 686, 943, 541, 853, 377, 731, 948, 416, 267, 668, 699, 182, 630, 94, 339, 137, 267], [468, 278, 300, 267, 292, 924, 386, 338, 556, 671, 813, 640, 448, 535, 283, 607, 627, 857, 363, 335], [287, 810, 492, 289, 313, 905, 180, 296, 535, 78, 363, 118, 554, 148, 743, 858, 881, 359, 221, 812], [696, 219, 221, 241, 180, 778, 672, 479, 320, 570, 538, 707, 360, 751, 273, 401, 943, 226, 283, 310], [147, 650, 794, 291, 849, 57, 182, 361, 300, 452, 89, 87, 804, 559, 748, 744, 591, 417, 107, 292], [264, 247, 243, 109, 541, 161, 724, 15, 265, 301, 528, 161, 773, 746, 810, 182, 378, 303, 847, 721], [769, 688, 172, 425, 946, 90, 244, 522, 173, 539, 282, 744, 357, 182, 691, 270, 498, 559, 727, 719], [741, 413, 520, 902, 157, 481, 937, 53, 549, 828, 407, 117, 681, 903, 691, 565, 327, 661, 824, 402], [465, 141, 385, 366, 520, 985, 634, 526, 149, 51, 539, 931, 220, 725, 613, 933, 161, 556, 403, 377], [215, 687, 634, 550, 411, 388, 612, 350, 245, 303, 768, 307, 54, 675, 770, 741, 465, 617, 827, 137], [632, 719, 143, 854, 948, 721, 609, 154, 726, 186, 668, 755, 246, 723, 388, 355, 256, 751, 727, 775], [132, 418, 920, 290, 691, 623, 457, 925, 704, 704, 676, 396, 880, 88, 87, 717, 329, 415, 328, 182], [393, 546, 388, 996, 771, 322, 420, 357, 312, 118, 465, 400, 840, 560, 636, 284, 493, 312, 171, 218], [649, 467, 674, 897, 453, 382, 633, 279, 947, 378, 51, 241, 565, 657, 148, 352, 93, 121, 923, 609], [636, 13, 627, 520, 778, 948, 854, 942, 537, 570, 948, 779, 404, 221, 684, 303, 687, 402, 593, 629], [674, 254, 773, 657, 596, 609, 684, 183, 948, 926, 712, 541, 245, 693, 518, 561, 8, 527, 249, 305], [888, 932, 272, 295, 769, 107, 894, 481, 675, 708, 268, 396, 541, 808, 453, 77, 132, 531, 89, 712], [325, 921, 216, 172, 183, 714, 519, 374, 113, 62, 924, 332, 300, 482, 307, 895, 421, 719, 886, 745], [459, 695, 712, 707, 411, 943, 403, 249, 904, 264, 643, 148, 141, 590, 470, 721, 425, 51, 702, 598], [358, 369, 352, 617, 558, 188, 494, 708, 122, 903, 752, 320, 744, 827, 980, 628, 147, 606, 109, 123], [813, 477, 823, 865, 651, 849, 321, 180, 813, 844, 372, 827, 653, 845, 532, 932, 220, 519, 704, 779], [309, 243, 851, 819, 687, 768, 852, 726, 247, 746, 133, 57, 183, 179, 888, 762, 519, 660, 328, 542], [340, 123, 664, 945, 948, 821, 319, 670, 258, 849, 847, 722, 808, 417, 217, 431, 313, 113, 692, 881], [320, 682, 579, 328, 546, 492, 686, 555, 651, 521, 905, 88, 724, 292, 939, 122, 307, 947, 310, 825], [460, 639, 467, 483, 719, 406, 586, 565, 657, 416, 592, 651, 160, 650, 710, 633, 216, 531, 324, 710], [889, 894, 76, 243, 215, 245, 298, 570, 550, 320, 749, 110, 518, 902, 855, 853, 948, 129, 819, 90], [309, 282, 625, 172, 777, 938, 140, 290, 56, 686, 266, 353, 497, 671, 848, 653, 130, 139, 396, 735], [655, 361, 332, 240, 161, 219, 372, 671, 680, 242, 196, 998, 697, 628, 667, 660, 639, 550, 602, 604], [552, 60, 842, 744, 649, 270, 661, 820, 597, 254, 243, 903, 603, 322, 182, 652, 182, 295, 652, 408], [613, 607, 469, 615, 614, 558, 775, 597, 50, 372, 5, 137, 635, 703, 482, 129, 146, 383, 107, 824], [598, 679, 897, 478, 184, 243, 629, 535, 654, 315, 559, 15, 610, 363, 181, 290, 391, 621, 149, 298], [221, 457, 854, 468, 977, 540, 527, 664, 463, 722, 118, 86, 323, 691, 359, 744, 414, 352, 709, 273], [901, 569, 377, 481, 774, 673, 51, 90, 117, 721, 637, 744, 519, 75, 395, 257, 733, 620, 849, 458], [299, 337, 174, 326, 540, 423, 597, 394, 852, 561, 526, 677, 942, 135, 739, 391, 329, 360, 365, 475], [561, 750, 904, 415, 610, 631, 155, 542, 480, 283, 826, 290, 244, 332, 847, 342, 328, 470, 253, 493], [883, 622, 254, 141, 459, 410, 479, 156, 887, 270, 452, 976, 295, 598, 809, 650, 744, 589, 179, 85], [456, 699, 372, 607, 638, 855, 720, 152, 528, 540, 744, 595, 902, 159, 650, 451, 936, 609, 656, 322], [565, 937, 627, 308, 562, 274, 238, 492, 884, 291, 675, 817, 882, 308, 679, 261, 619, 705, 409, 364], [518, 623, 462, 591, 126, 683, 294, 650, 364, 214, 640, 116, 621, 553, 376, 477, 411, 624, 424, 148], [426, 284, 270, 885, 360, 85, 255, 718, 89, 680, 126, 272, 590, 937, 605, 419, 628, 469, 301, 53], [275, 723, 159, 636, 177, 196, 668, 526, 654, 732, 388, 387, 272, 262, 16, 926, 633, 422, 117, 558], [405, 151, 675, 929, 928, 497, 432, 428, 687, 369, 727, 462, 54, 129, 152, 466, 295, 383, 365, 630], [248, 50, 526, 816, 839, 227, 253, 698, 180, 519, 186, 852, 842, 531, 160, 258, 414, 385, 603, 91], [523, 651, 697, 562, 709, 603, 21, 90, 275, 479, 905, 526, 381, 475, 638, 278, 418, 414, 611, 362], [711, 274, 687, 643, 709, 389, 729, 225, 720, 948, 675, 819, 601, 412, 414, 434, 375, 650, 852, 377], [939, 685, 627, 643, 145, 275, 59, 258, 524, 903, 416, 635, 634, 896, 834, 657, 242, 466, 266, 270], [296, 771, 851, 676, 328, 852, 357, 260, 697, 52, 383, 456, 774, 179, 56, 905, 846, 945, 15, 398], [397, 412, 929, 838, 279, 286, 215, 845, 885, 127, 715, 586, 477, 930, 418, 552, 459, 536, 534, 292], [532, 461, 404, 453, 742, 269, 292, 694, 437, 309, 702, 56, 213, 64, 187, 171, 366, 661, 299, 713], [747, 481, 137, 520, 702, 891, 534, 174, 322, 946, 625, 898, 592, 326, 429, 852, 115, 52, 178, 184], [483, 936, 728, 794, 888, 496, 308, 256, 687, 284, 588, 538, 742, 296, 629, 51, 603, 716, 252, 890], [217, 497, 948, 382, 417, 327, 390, 148, 701, 617, 898, 529, 775, 437, 916, 183, 819, 676, 335, 393], [937, 472, 122, 288, 619, 743, 660, 725, 742, 313, 675, 605, 383, 741, 53, 69, 171, 618, 125, 742], [121, 376, 709, 858, 710, 387, 824, 468, 302, 922, 884, 699, 378, 582, 628, 525, 890, 534, 629, 459], [707, 745, 410, 476, 743, 307, 547, 121, 482, 699, 281, 309, 414, 689, 728, 424, 848, 140, 613, 714], [880, 632, 844, 627, 469, 947, 399, 767, 900, 185, 731, 409, 826, 430, 329, 50, 882, 50, 405, 253], [189, 922, 536, 313, 385, 272, 330, 932, 313, 117, 132, 737, 669, 182, 494, 493, 702, 522, 184, 609], [186, 634, 287, 716, 591, 55, 589, 175, 306, 452, 746, 694, 661, 646, 855, 259, 80, 221, 151, 857], [477, 243, 649, 546, 303, 683, 285, 518, 720, 367, 629, 841, 371, 395, 741, 333, 911, 367, 750, 811], [691, 693, 889, 244, 461, 759, 680, 932, 116, 139, 654, 719, 153, 260, 597, 269, 627, 899, 177, 883], [459, 323, 125, 748, 483, 370, 137, 751, 991, 708, 898, 149, 664, 307, 392, 419, 423, 256, 493, 376], [882, 853, 562, 694, 469, 428, 219, 158, 684, 587, 84, 87, 464, 86, 887, 712, 536, 679, 700, 767], [473, 623, 705, 565, 470, 404, 822, 409, 271, 665, 87, 214, 687, 880, 817, 849, 213, 146, 689, 190], [602, 245, 713, 115, 616, 639, 323, 80, 176, 824, 700, 240, 499, 598, 810, 535, 184, 187, 404, 684], [938, 0, 240, 433, 812, 283, 673, 855, 135, 156, 53, 393, 727, 570, 389, 216, 929, 109, 416, 288], [880, 401, 328, 653, 694, 161, 131, 747, 273, 946, 647, 699, 659, 309, 610, 247, 807, 609, 421, 69], [123, 700, 841, 697, 702, 279, 248, 55, 592, 552, 379, 185, 126, 856, 803, 357, 773, 568, 178, 377], [325, 124, 941, 826, 669, 238, 636, 595, 238, 934, 402, 131, 188, 146, 633, 436, 595, 362, 191, 498], [378, 632, 177, 992, 177, 606, 644, 626, 935, 323, 332, 823, 124, 380, 815, 518, 619, 293, 670, 821], [454, 273, 118, 752, 604, 526, 151, 932, 294, 544, 7, 462, 108, 804, 407, 423, 305, 134, 432, 549], [143, 59, 611, 463, 286, 722, 132, 191, 132, 712, 325, 592, 548, 362, 419, 108, 91, 710, 359, 320], [852, 905, 596, 730, 532, 528, 158, 116, 809, 231, 570, 634, 660, 681, 935, 904, 401, 406, 327, 695], [724, 318, 660, 683, 940, 635, 657, 692, 366, 750, 130, 463, 246, 680, 24, 117, 928, 608, 257, 690], [123, 225, 774, 336, 824, 624, 267, 772, 413, 180, 302, 269, 179, 897, 839, 596, 670, 679, 295, 135], [937, 291, 721, 253, 665, 356, 702, 292, 537, 556, 804, 932, 827, 695, 89, 734, 108, 692, 85, 708], [857, 889, 149, 728, 455, 461, 735, 293, 643, 596, 718, 274, 741, 279, 881, 825, 704, 298, 284, 820], [395, 659, 675, 588, 159, 54, 296, 809, 549, 707, 885, 625, 723, 901, 652, 677, 583, 457, 811, 674], [883, 238, 420, 473, 664, 306, 326, 650, 674, 390, 627, 160, 695, 196, 362, 579, 703, 298, 934, 287], [318, 689, 777, 948, 251, 530, 888, 668, 612, 732, 396, 604, 735, 822, 925, 645, 154, 613, 389, 108], [266, 936, 816, 376, 401, 52, 518, 239, 823, 732, 779, 892, 602, 568, 370, 897, 856, 768, 331, 901], [279, 622, 267, 728, 771, 923, 620, 417, 297, 744, 646, 329, 463, 545, 407, 778, 345, 534, 213, 399], [930, 180, 624, 492, 454, 380, 125, 409, 312, 535, 663, 132, 772, 192, 817, 681, 175, 704, 218, 645], [379, 128, 251, 902, 813, 472, 84, 273, 894, 273, 421, 407, 251, 674, 565, 555, 52, 310, 303, 544], [681, 180, 713, 370, 248, 160, 548, 718, 691, 189, 978, 90, 479, 676, 894, 686, 262, 141, 300, 639], [120, 140, 686, 522, 540, 131, 645, 142, 554, 533, 108, 59, 394, 645, 841, 57, 390, 762, 546, 658], [311, 704, 383, 750, 934, 615, 608, 320, 570, 724, 654, 538, 714, 119, 143, 252, 224, 135, 660, 713], [263, 633, 416, 658, 925, 610, 854, 887, 559, 732, 627, 492, 268, 21, 626, 406, 470, 154, 138, 298], [641, 677, 827, 125, 150, 552, 230, 359, 405, 115, 400, 749, 468, 57, 672, 184, 436, 659, 388, 393], [437, 895, 371, 529, 522, 604, 751, 274, 283, 399, 417, 636, 71, 318, 53, 186, 190, 652, 472, 110], [274, 673, 932, 582, 325, 352, 617, 883, 826, 292, 882, 820, 437, 124, 243, 619, 547, 678, 321, 216], [99, 417, 938, 312, 327, 337, 925, 882, 594, 550, 646, 128, 679, 683, 590, 617, 188, 682, 378, 387], [271, 732, 753, 561, 458, 141, 461, 75, 143, 935, 741, 902, 728, 562, 627, 218, 323, 616, 559, 556], [703, 703, 432, 903, 846, 519, 469, 391, 412, 455, 527, 691, 491, 710, 815, 676, 171, 192, 531, 547], [487, 329, 86, 123, 902, 547, 120, 945, 116, 925, 816, 271, 555, 844, 667, 816, 256, 217, 410, 554], [115, 110, 624, 559, 562, 375, 262, 254, 645, 414, 772, 373, 307, 432, 75, 458, 389, 249, 81, 703], [280, 256, 889, 588, 536, 144, 497, 113, 89, 607, 852, 881, 629, 617, 587, 561, 983, 309, 189, 180], [827, 536, 118, 698, 491, 898, 722, 851, 467, 481, 988, 855, 928, 284, 261, 328, 259, 175, 521, 538], [315, 52, 604, 656, 540, 769, 424, 846, 666, 930, 291, 54, 58, 423, 662, 140, 139, 742, 720, 525], [524, 890, 246, 104, 663, 141, 176, 73, 819, 715, 570, 530, 239, 255, 401, 161, 671, 307, 367, 87], [461, 728, 660, 935, 420, 805, 261, 644, 255, 381, 945, 637, 591, 15, 902, 663, 749, 846, 743, 647], [150, 436, 601, 269, 159, 699, 675, 926, 678, 416, 241, 637, 482, 280, 298, 526, 781, 681, 778, 245], [901, 530, 559, 528, 620, 535, 314, 141, 453, 326, 778, 239, 530, 148, 189, 729, 808, 552, 69, 334], [122, 665, 283, 128, 471, 270, 152, 196, 246, 807, 153, 109, 86, 466, 125, 108, 757, 714, 152, 648], [707, 324, 825, 587, 301, 776, 822, 290, 384, 824, 382, 809, 930, 439, 942, 181, 896, 695, 279, 360], [481, 678, 819, 345, 275, 538, 159, 710, 416, 491, 297, 949, 458, 385, 773, 360, 895, 367, 255, 945], [333, 709, 741, 55, 530, 455, 814, 604, 292, 415, 120, 149, 855, 309, 573, 614, 668, 404, 669, 307], [435, 886, 120, 410, 154, 109, 147, 259, 395, 669, 145, 668, 306, 804, 2, 499, 183, 144, 691, 144], [752, 424, 58, 52, 241, 175, 699, 638, 216, 179, 807, 657, 472, 547, 518, 86, 902, 373, 537, 768], [526, 356, 355, 253, 58, 921, 746, 557, 708, 406, 530, 998, 173, 519, 555, 474, 180, 469, 672, 125], [694, 214, 710, 390, 570, 890, 689, 152, 433, 644, 336, 60, 881, 378, 89, 692, 368, 823, 491, 249], [631, 665, 499, 657, 389, 828, 410, 255, 123, 375, 53, 903, 940, 754, 653, 421, 253, 676, 352, 173], [735, 179, 690, 779, 924, 54, 705, 644, 847, 373, 364, 547, 534, 90, 529, 664, 889, 358, 318, 770], [723, 725, 607, 321, 655, 354, 421, 130, 145, 949, 307, 804, 600, 716, 76, 437, 474, 813, 692, 544], [631, 685, 499, 992, 922, 371, 726, 374, 181, 359, 688, 329, 250, 406, 672, 242, 882, 551, 804, 122], [259, 107, 642, 656, 239, 604, 257, 705, 386, 622, 556, 946, 154, 474, 56, 697, 493, 439, 857, 124], [437, 885, 286, 111, 417, 160, 82, 151, 113, 711, 313, 276, 160, 395, 111, 560, 653, 435, 683, 897], [124, 382, 994, 773, 177, 594, 822, 300, 243, 697, 615, 518, 596, 453, 642, 841, 495, 498, 496, 296], [646, 821, 364, 271, 857, 492, 658, 643, 699, 418, 943, 364, 8, 84, 636, 375, 181, 922, 842, 277], [857, 313, 387, 932, 703, 853, 314, 324, 664, 769, 416, 653, 498, 131, 460, 881, 604, 20, 171, 554], [472, 533, 777, 287, 626, 112, 134, 608, 293, 218, 54, 805, 540, 326, 463, 656, 175, 1, 455, 143], [264, 731, 620, 282, 663, 646, 177, 778, 749, 523, 396, 124, 633, 539, 492, 837, 453, 881, 127, 337], [303, 897, 453, 213, 693, 880, 743, 23, 628, 595, 520, 53, 221, 813, 608, 184, 809, 842, 613, 185], [842, 547, 674, 361, 382, 291, 777, 302, 721, 852, 519, 158, 392, 537, 419, 184, 142, 737, 813, 630], [233, 301, 677, 839, 896, 545, 214, 150, 461, 806, 887, 148, 160, 555, 727, 307, 710, 142, 700, 932], [83, 498, 272, 693, 129, 824, 710, 770, 189, 855, 73, 183, 729, 279, 543, 23, 329, 892, 670, 273], [54, 664, 313, 255, 645, 945, 57, 496, 406, 546, 180, 847, 631, 542, 453, 525, 845, 418, 904, 999], [276, 338, 55, 481, 86, 274, 621, 850, 623, 382, 431, 273, 826, 226, 458, 750, 841, 275, 652, 495], [556, 614, 129, 769, 333, 534, 276, 300, 492, 190, 992, 319, 491, 329, 548, 142, 529, 55, 397, 942], [720, 218, 533, 488, 943, 699, 290, 609, 291, 659, 298, 402, 407, 325, 157, 246, 157, 243, 594, 611], [152, 246, 483, 218, 840, 449, 694, 112, 700, 352, 475, 773, 729, 52, 108, 769, 247, 534, 245, 282], [187, 700, 53, 939, 848, 152, 133, 113, 315, 729, 674, 110, 494, 987, 83, 589, 119, 569, 540, 116], [247, 114, 290, 715, 646, 412, 857, 921, 182, 176, 607, 632, 307, 773, 53, 184, 683, 285, 236, 562], [732, 381, 244, 328, 679, 775, 727, 251, 619, 805, 706, 827, 152, 821, 551, 903, 931, 702, 342, 716], [401, 685, 589, 389, 398, 891, 813, 127, 121, 420, 818, 330, 523, 593, 422, 87, 246, 200, 319, 371], [850, 856, 246, 624, 462, 182, 448, 335, 401, 381, 681, 620, 303, 645, 810, 883, 569, 416, 298, 594], [619, 707, 309, 477, 934, 624, 127, 657, 57, 157, 20, 196, 457, 254, 292, 182, 410, 742, 391, 147], [817, 271, 706, 467, 642, 554, 695, 709, 524, 596, 357, 318, 777, 689, 59, 223, 378, 687, 352, 530], [617, 935, 280, 213, 637, 183, 249, 332, 779, 398, 905, 492, 885, 455, 136, 594, 306, 747, 760, 693], [717, 730, 410, 903, 57, 92, 815, 298, 522, 409, 742, 680, 495, 377, 266, 376, 193, 126, 389, 653], [282, 538, 923, 654, 171, 258, 743, 257, 553, 628, 813, 220, 156, 135, 332, 529, 836, 647, 302, 899], [409, 73, 456, 372, 534, 541, 647, 354, 570, 117, 56, 59, 317, 807, 194, 943, 558, 769, 815, 431], [147, 598, 490, 587, 131, 779, 679, 134, 536, 673, 371, 419, 929, 729, 854, 535, 306, 927, 743, 400], [354, 364, 569, 717, 147, 244, 654, 624, 649, 700, 144, 702, 188, 341, 683, 647, 454, 88, 299, 394], [597, 751, 678, 493, 899, 748, 410, 479, 177, 761, 521, 612, 683, 536, 113, 900, 895, 92, 306, 658], [609, 730, 722, 402, 761, 731, 743, 143, 365, 401, 684, 897, 689, 384, 411, 844, 118, 359, 317, 715], [379, 659, 473, 399, 774, 555, 291, 853, 932, 587, 281, 461, 142, 925, 270, 602, 555, 69, 600, 310], [633, 674, 769, 265, 694, 82, 134, 180, 174, 608, 378, 824, 176, 56, 747, 881, 108, 605, 769, 885], [644, 730, 589, 447, 217, 522, 140, 533, 900, 265, 600, 613, 290, 709, 408, 934, 701, 216, 924, 853], [338, 257, 322, 123, 547, 806, 188, 904, 591, 381, 256, 535, 594, 538, 897, 940, 984, 942, 388, 294], [848, 663, 597, 125, 287, 720, 188, 87, 393, 491, 171, 54, 618, 221, 478, 112, 438, 699, 624, 378], [465, 174, 640, 362, 896, 718, 323, 287, 398, 719, 672, 606, 691, 739, 724, 497, 544, 803, 409, 434], [761, 460, 633, 263, 360, 814, 731, 252, 58, 752, 356, 172, 928, 641, 716, 374, 614, 721, 558, 242], [845, 324, 307, 519, 127, 671, 750, 709, 437, 652, 219, 112, 59, 682, 844, 267, 653, 936, 445, 561], [319, 554, 716, 53, 333, 422, 418, 151, 149, 641, 948, 186, 109, 807, 405, 160, 361, 424, 238, 322], [545, 244, 676, 311, 751, 855, 704, 766, 890, 532, 942, 921, 359, 548, 267, 264, 714, 723, 895, 111], [912, 308, 726, 668, 238, 307, 379, 619, 687, 530, 275, 245, 897, 369, 217, 777, 614, 403, 176, 940], [842, 893, 238, 815, 779, 407, 189, 602, 605, 361, 976, 927, 184, 386, 606, 370, 185, 921, 718, 455], [148, 51, 133, 250, 851, 455, 191, 806, 184, 846, 818, 823, 284, 651, 55, 51, 903, 933, 709, 51], [175, 607, 219, 379, 527, 290, 381, 529, 483, 398, 884, 777, 392, 452, 415, 912, 334, 694, 238, 295], [134, 708, 622, 299, 268, 452, 371, 436, 893, 727, 947, 498, 384, 141, 520, 147, 379, 630, 769, 82], [359, 702, 470, 918, 718, 128, 892, 646, 313, 695, 407, 411, 729, 313, 560, 58, 934, 377, 189, 496], [931, 464, 663, 697, 160, 525, 323, 317, 256, 286, 678, 178, 492, 422, 948, 185, 355, 572, 127, 316], [407, 456, 568, 948, 264, 949, 386, 597, 393, 602, 377, 924, 550, 770, 311, 703, 379, 327, 597, 941], [495, 740, 293, 407, 296, 881, 431, 550, 728, 625, 686, 900, 596, 276, 468, 127, 752, 731, 467, 674], [317, 644, 626, 539, 274, 184, 364, 395, 243, 889, 333, 663, 601, 83, 263, 490, 338, 338, 303, 528], [714, 853, 279, 216, 321, 769, 839, 901, 922, 809, 478, 940, 3, 372, 771, 261, 149, 267, 265, 810], [150, 732, 854, 684, 176, 124, 266, 458, 456, 738, 267, 904, 678, 823, 523, 602, 931, 826, 363, 361], [549, 742, 369, 557, 774, 185, 253, 21, 381, 374, 390, 857, 552, 896, 701, 613, 596, 280, 777, 588], [921, 491, 492, 764, 377, 891, 240, 668, 404, 694, 476, 381, 292, 371, 395, 648, 562, 821, 178, 724], [694, 595, 929, 522, 522, 248, 942, 68, 109, 625, 590, 743, 50, 364, 277, 273, 383, 895, 324, 267], [590, 326, 148, 317, 747, 644, 839, 397, 902, 122, 669, 154, 171, 365, 491, 145, 50, 282, 581, 394], [124, 492, 84, 550, 687, 181, 63, 708, 461, 542, 408, 569, 332, 636, 730, 708, 640, 436, 260, 779], [593, 554, 823, 369, 628, 377, 177, 455, 666, 557, 57, 147, 678, 385, 808, 475, 436, 873, 471, 322], [250, 723, 737, 52, 778, 594, 390, 187, 434, 922, 654, 327, 140, 244, 827, 523, 532, 362, 627, 724], [280, 112, 471, 85, 493, 59, 693, 301, 180, 551, 658, 318, 637, 727, 926, 158, 684, 397, 733, 640], [382, 620, 383, 81, 58, 727, 805, 161, 588, 476, 640, 322, 596, 465, 923, 274, 56, 700, 124, 122], [244, 821, 261, 17, 722, 287, 841, 814, 569, 308, 286, 635, 379, 903, 769, 414, 885, 178, 180, 649], [621, 815, 593, 475, 848, 668, 378, 637, 135, 728, 643, 496, 722, 836, 589, 466, 643, 544, 774, 218], [176, 381, 54, 368, 431, 252, 253, 923, 818, 728, 112, 559, 761, 855, 657, 528, 321, 134, 809, 422], [628, 946, 216, 459, 217, 476, 633, 391, 617, 546, 377, 187, 282, 825, 587, 975, 709, 260, 277, 714], [604, 749, 462, 740, 728, 893, 688, 603, 182, 141, 826, 374, 146, 679, 311, 498, 777, 523, 606, 142], [109, 552, 636, 215, 678, 401, 306, 654, 254, 941, 404, 274, 427, 814, 710, 266, 283, 466, 809, 279], [901, 670, 94, 304, 644, 672, 325, 900, 50, 693, 880, 493, 670, 622, 812, 946, 888, 239, 408, 625], [779, 263, 560, 134, 404, 407, 108, 188, 526, 635, 570, 112, 437, 313, 846, 628, 488, 380, 935, 322], [441, 713, 942, 379, 117, 702, 569, 473, 518, 653, 894, 839, 818, 495, 616, 142, 670, 288, 116, 559], [569, 308, 826, 465, 539, 539, 849, 248, 467, 716, 478, 221, 887, 811, 225, 173, 142, 240, 310, 842], [148, 406, 883, 195, 615, 362, 536, 253, 393, 177, 616, 562, 295, 415, 523, 896, 650, 846, 243, 548], [320, 188, 840, 189, 523, 247, 158, 447, 607, 394, 776, 842, 718, 117, 725, 747, 110, 73, 75, 465], [949, 180, 181, 475, 588, 496, 933, 700, 416, 305, 18, 714, 779, 682, 770, 335, 657, 602, 472, 945], [246, 77, 590, 697, 810, 491, 158, 670, 936, 296, 724, 633, 402, 745, 929, 367, 273, 361, 549, 73], [929, 943, 712, 386, 882, 666, 743, 360, 140, 821, 472, 745, 551, 303, 132, 86, 846, 20, 618, 842], [421, 238, 11, 817, 111, 545, 695, 651, 654, 840, 634, 296, 50, 632, 385, 642, 146, 549, 89, 675], [356, 650, 240, 202, 216, 253, 851, 556, 697, 111, 546, 293, 663, 818, 828, 719, 366, 849, 274, 851], [615, 397, 402, 590, 629, 694, 541, 932, 178, 311, 335, 534, 721, 928, 678, 118, 770, 917, 689, 718], [713, 593, 390, 534, 188, 295, 365, 621, 844, 153, 382, 547, 641, 720, 520, 355, 659, 889, 157, 996], [69, 245, 479, 255, 494, 618, 818, 158, 83, 853, 603, 929, 189, 130, 242, 525, 57, 360, 431, 716], [73, 289, 458, 611, 69, 134, 704, 145, 415, 127, 397, 811, 599, 935, 648, 743, 418, 466, 310, 587], [844, 597, 338, 477, 400, 742, 895, 659, 902, 464, 895, 218, 521, 772, 110, 54, 149, 838, 315, 562], [769, 399, 706, 130, 856, 312, 566, 465, 810, 238, 592, 807, 848, 433, 136, 354, 92, 174, 929, 52], [219, 499, 278, 562, 537, 63, 779, 240, 364, 775, 628, 435, 74, 843, 905, 547, 176, 54, 120, 297], [658, 248, 155, 556, 213, 196, 541, 641, 382, 933, 238, 368, 775, 79, 338, 629, 686, 266, 86, 400], [409, 741, 554, 284, 492, 537, 91, 132, 848, 113, 840, 302, 855, 413, 439, 665, 172, 542, 322, 252], [819, 122, 685, 935, 414, 387, 624, 53, 746, 637, 338, 245, 114, 256, 387, 596, 10, 120, 770, 817], [664, 846, 181, 150, 413, 283, 766, 466, 724, 929, 257, 188, 558, 366, 925, 523, 273, 656, 654, 483], [620, 397, 229, 287, 184, 454, 647, 327, 216, 776, 310, 719, 125, 183, 459, 594, 433, 279, 155, 142], [112, 648, 644, 155, 394, 924, 189, 406, 154, 405, 171, 726, 364, 569, 749, 529, 550, 513, 307, 840], [662, 240, 468, 235, 452, 289, 329, 806, 179, 588, 414, 824, 51, 621, 643, 273, 817, 53, 715, 128], [179, 807, 537, 53, 242, 740, 213, 555, 751, 528, 160, 680, 184, 435, 356, 258, 675, 433, 419, 528], [771, 499, 594, 635, 938, 940, 810, 354, 55, 644, 548, 690, 133, 364, 68, 727, 247, 90, 823, 693], [849, 748, 358, 638, 899, 357, 435, 329, 83, 419, 629, 847, 731, 352, 238, 526, 243, 79, 51, 196], [542, 308, 428, 637, 718, 410, 93, 240, 481, 722, 287, 93, 692, 807, 923, 176, 149, 310, 550, 552], [306, 975, 900, 315, 216, 479, 743, 494, 901, 535, 597, 924, 239, 186, 925, 124, 491, 750, 588, 323], [76, 929, 694, 844, 114, 410, 842, 941, 307, 377, 553, 528, 481, 858, 243, 771, 818, 614, 535, 749], [899, 143, 342, 888, 256, 750, 465, 173, 855, 887, 312, 827, 714, 452, 550, 776, 845, 242, 839, 250], [525, 387, 844, 731, 185, 261, 935, 895, 331, 840, 928, 726, 821, 709, 896, 891, 680, 340, 172, 742], [153, 93, 639, 469, 947, 776, 336, 362, 75, 387, 310, 711, 630, 282, 402, 469, 567, 538, 455, 695], [817, 395, 849, 456, 275, 645, 310, 382, 240, 255, 296, 926, 267, 354, 760, 219, 529, 810, 813, 559], [610, 118, 495, 624, 493, 119, 628, 491, 715, 266, 420, 690, 586, 411, 16, 496, 902, 405, 841, 146], [221, 375, 534, 309, 390, 616, 521, 704, 853, 645, 353, 221, 497, 493, 395, 939, 752, 3, 544, 844], [823, 302, 638, 522, 157, 616, 178, 339, 705, 988, 610, 467, 84, 466, 886, 898, 650, 814, 940, 300], [191, 189, 59, 329, 596, 884, 728, 921, 214, 679, 335, 308, 752, 136, 534, 494, 475, 937, 551, 606], [852, 633, 407, 371, 608, 645, 627, 59, 813, 189, 586, 708, 522, 598, 59, 353, 71, 888, 325, 174], [805, 840, 110, 69, 923, 294, 658, 608, 86, 693, 903, 253, 181, 155, 420, 688, 55, 55, 750, 904], [396, 454, 155, 431, 894, 178, 473, 312, 937, 295, 24, 75, 498, 339, 818, 676, 161, 270, 244, 138], [365, 597, 419, 818, 216, 729, 707, 464, 371, 383, 772, 189, 217, 367, 295, 819, 990, 805, 391, 586], [93, 278, 65, 161, 469, 701, 601, 714, 849, 274, 569, 196, 75, 544, 57, 57, 411, 418, 413, 147], [646, 270, 632, 405, 303, 676, 499, 478, 559, 410, 709, 395, 81, 321, 647, 609, 247, 153, 816, 126], [769, 466, 193, 602, 529, 327, 335, 215, 930, 121, 743, 609, 306, 288, 332, 725, 217, 399, 619, 819], [827, 296, 445, 618, 778, 897, 238, 691, 474, 723, 679, 215, 934, 179, 528, 645, 620, 359, 499, 890], [401, 812, 352, 813, 533, 274, 675, 698, 121, 175, 409, 774, 411, 402, 348, 626, 481, 898, 589, 298], [745, 819, 605, 815, 87, 276, 352, 821, 301, 171, 937, 710, 525, 327, 305, 749, 930, 904, 635, 753], [646, 56, 534, 523, 287, 271, 713, 738, 115, 889, 92, 750, 700, 655, 113, 946, 110, 747, 615, 545], [806, 288, 122, 176, 52, 466, 453, 539, 757, 218, 337, 453, 383, 474, 939, 660, 892, 384, 115, 383], [437, 803, 570, 466, 458, 284, 687, 405, 279, 374, 393, 297, 634, 369, 317, 192, 494, 690, 689, 260], [359, 759, 606, 108, 544, 300, 239, 856, 550, 117, 933, 401, 660, 624, 457, 728, 688, 685, 605, 57], [616, 125, 698, 214, 934, 115, 182, 299, 5, 276, 244, 822, 688, 295, 559, 261, 770, 903, 357, 724]]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "K6psuLvekuiD",
        "outputId": "87a90eb3-6659-4b26-bf8c-94858a3c2c3f"
      },
      "source": [
        "valid_tickets = []\n",
        "rate = 0\n",
        "for ticket in tickets:\n",
        "  ticket_valid = True\n",
        "  for field in ticket:\n",
        "    valid = False\n",
        "    for rule in rules.values():\n",
        "      if (field in rule[0] or field in rule[1]):\n",
        "        valid = True\n",
        "    if not valid:\n",
        "      rate += field\n",
        "      ticket_valid = False\n",
        "  if ticket_valid:\n",
        "    valid_tickets.append(ticket)\n",
        "\n",
        "# 1\n",
        "rate"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "24110"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 27
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LgOKFoD30H23"
      },
      "source": [
        "# 2\n",
        "# 1. collect possibilities for each position\n",
        "num_fields = len(my_ticket)\n",
        "fields_in_order = []\n",
        "for pos in range(0, num_fields):\n",
        "  rule_names = list(rules)\n",
        "  for ticket in valid_tickets:\n",
        "    field = ticket[pos]\n",
        "    for rule_name in rule_names.copy():\n",
        "      rule = rules[rule_name]\n",
        "      if field not in rule[0] and field not in rule[1]:\n",
        "        rule_names.remove(rule_name)\n",
        "  fields_in_order.append(rule_names)\n",
        "\n",
        "#print(fields_in_order)\n",
        "\n",
        "# 2. reduce possibilities for all positions to one by starting at the position with just one possibility,\n",
        "# removing that possibility from all other positions and repeat until there is only one possibility per position\n",
        "\n",
        "def max_len(fields_in_order):\n",
        "  return max(list(map(len, fields_in_order)))\n",
        "\n",
        "final_fields_in_order = [''] * num_fields\n",
        "\n",
        "while (max_len(fields_in_order) > 1):\n",
        "  for pos in range(0, num_fields):\n",
        "    if (len(fields_in_order[pos]) == 1):\n",
        "      field_name = fields_in_order[pos][0]\n",
        "      final_fields_in_order[pos] = field_name\n",
        "      for field in fields_in_order:\n",
        "        if field_name in field:\n",
        "          field.remove(field_name)\n",
        "\n",
        "print(final_fields_in_order)\n",
        "\n",
        "# 3. multiply field values from my_ticket for field names starting with 'departure'\n",
        "dep_prod = 1\n",
        "for pos in range(0, num_fields):\n",
        "  if final_fields_in_order[pos].startswith('departure'):\n",
        "    dep_prod *= my_ticket[pos]\n",
        "\n",
        "dep_prod\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "n6QooBYLN2Qk"
      },
      "source": [
        "Day 17"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y3GQXZ0i3tSh"
      },
      "source": [
        "def init(d):\n",
        "  alive_cells = set()\n",
        "  lines = [l.strip('\\n ') for l in open('input.txt')]\n",
        "  for iline in zip(lines, range(0, len(lines))):\n",
        "    line = iline[0]\n",
        "    y = iline[1]\n",
        "    for x in range(0, len(line)):\n",
        "      if line[x] == '#':\n",
        "        alive_cells.add(tuple([x, y] + [0] * (d-2)))\n",
        "  return alive_cells"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NdfHW7T3e36-"
      },
      "source": [
        "def permutate(cells, d):\n",
        "  if (d >= 0):\n",
        "    return permutate([cell for sublist in [[c[0:d] + [c[d]] + c[d+1:], c[0:d] + [c[d]-1] + c[d+1:], c[0:d] + [c[d]+1] + c[d+1:]] for c in cells] for cell in sublist], d-1)\n",
        "  else:\n",
        "    return cells\n",
        "\n",
        "def neighbors(cell):\n",
        "  if cell in nbcache:\n",
        "    return nbcache[cell]\n",
        "  else:\n",
        "    nb = [tuple(c) for c in permutate([list(cell)], len(cell)-1) if c != list(cell)]\n",
        "    nbcache[cell] = nb\n",
        "    return nb\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BA5tn9oJ_h9x"
      },
      "source": [
        "from time import time\n",
        "\n",
        "def count_alive_neighbors(cell, alive_cells):\n",
        "  return len(list(filter(lambda n: n in alive_cells, neighbors(cell))))\n",
        "\n",
        "def iterate(alive_cells):\n",
        "  t = time()\n",
        "  cells_to_check = dict()\n",
        "  for a in alive_cells:\n",
        "    cells_to_check.add(a)\n",
        "    for c in neighbors(a):\n",
        "      cells_to_check.add(c)\n",
        "  print(len(nbcache), time() - t)\n",
        "  t = time()\n",
        "  new_alive_cells = set()\n",
        "  for c in cells_to_check:\n",
        "    n = count_alive_neighbors(c, alive_cells)\n",
        "    if n == 3:\n",
        "      new_alive_cells.add(c)\n",
        "    elif n == 2 and c in alive_cells:\n",
        "      new_alive_cells.add(c)\n",
        "  print(len(nbcache), time() - t)\n",
        "\n",
        "  return new_alive_cells"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "oiNudR0Adkt8",
        "outputId": "6019dffc-d5ad-45ef-c9d3-ec74268c681f"
      },
      "source": [
        "alive_cells = init(4)  # dimensions, 2..\n",
        "nbcache = dict()\n",
        "t = time()\n",
        "for i in range(0,6):\n",
        "  alive_cells = iterate(alive_cells)\n",
        "(len(alive_cells), time() - t)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "41 0.006627559661865234\n",
            "891 0.09676599502563477\n",
            "891 0.0027832984924316406\n",
            "2450 0.1760728359222412\n",
            "2450 0.0042629241943359375\n",
            "6050 0.3920009136199951\n",
            "6050 0.02123427391052246\n",
            "11503 0.7507936954498291\n",
            "11503 0.011909008026123047\n",
            "19135 0.8970203399658203\n",
            "19135 0.07243800163269043\n",
            "29985 1.614008903503418\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(2280, 4.053617715835571)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 86
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RVOR8nI91soO"
      },
      "source": [
        "Day 18"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cLofdC-kd4sE"
      },
      "source": [
        "#import abc\n",
        "from functools import reduce\n",
        "#from operator import methodcaller\n",
        "\n",
        "#class Node(object):\n",
        "#  __metaclass__ = abc.ABCMeta\n",
        "#\n",
        "#  @abc.abstractmethod\n",
        "#  def evaluate(self):\n",
        "#    return None\n",
        "\n",
        "class ValueNode: #(Node):\n",
        "  def __init__(self, val):\n",
        "    self.val = val\n",
        "  def evaluate(self):\n",
        "    return self.val\n",
        "  def __str__(self):\n",
        "    return f'{self.val}'\n",
        "  __repr__ = __str__\n",
        "\n",
        "class ParanthesesNode:\n",
        "  def __init__(self, node):\n",
        "    self.node = node\n",
        "  def evaluate(self):\n",
        "    return self.node.evaluate()\n",
        "  def __str__(self):\n",
        "    return f'({self.node.__str__()})'\n",
        "  __repr__ = __str__\n",
        "\n",
        "class ExprNode: #(Node):\n",
        "  def __init__(self, operator, left, right, parantheses = False):\n",
        "    self.operator = operator\n",
        "    self.left = left\n",
        "    self.right = right\n",
        "  def evaluate(self):\n",
        "    return self.left.evaluate() + self.right.evaluate() if self.operator == '+' else self.left.evaluate() * self.right.evaluate()\n",
        "  def __str__(self):\n",
        "    return f\"[{self.left.__str__()} {self.operator} {self.right.__str__()}]\"\n",
        "  __repr__ = __str__\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "dQeh-DIPdwGY"
      },
      "source": [
        "# 1: + and * with same precedence\n",
        "# 2: + > *\n",
        "def p(expr):\n",
        "  #print(f\"parsing '{expr}'\")\n",
        "  operand = ''\n",
        "  node = None\n",
        "  rest = expr\n",
        "  space = False\n",
        "  while True:\n",
        "    c = rest[-1:] # last char\n",
        "    rest = rest[:-1] # everything except last char\n",
        "    if c in '0123456789':\n",
        "      if node:\n",
        "        raise Exception(f\"syntax error: unexpected '{node}' following '{rest}{c}'\")\n",
        "      if operand and space:\n",
        "        raise Exception(f\"syntax error: unexpected '<SPACE>{operand}' following '{rest}{c}'\")\n",
        "      operand = c + operand\n",
        "    elif c in '+*':\n",
        "      if bool(operand) ^ bool(node):\n",
        "        right = ValueNode(int(operand)) if operand else node\n",
        "        (rest, left) = p(rest)\n",
        "        # 2:\n",
        "        # if op is '+' and the left side is '*' without parantheses (i. e. left: x * y, right: z),\n",
        "        # we need to swap, i. e. make '*' the top with x on the left, and y + z on the right\n",
        "        if c == '+' and isinstance(left, ExprNode) and left.operator == '*':\n",
        "          return (rest, ExprNode('*', left.left, ExprNode('+', left.right, right)))\n",
        "        return (rest, ExprNode(c, left, right))\n",
        "      raise Exception(f\"syntax error: unexpected operator '{c}' without operand following '{rest}'\")\n",
        "    elif c == ')':\n",
        "      if operand:\n",
        "        raise Exception(f\"syntax error: unexpected value '{operand}' following '{rest})'\")\n",
        "      (rest, n) = p(rest)\n",
        "      node = ParanthesesNode(n)\n",
        "    elif c == '(':\n",
        "      if bool(operand) ^ bool(node):\n",
        "        return (rest, ValueNode(int(operand)) if operand else node)\n",
        "      raise Exception(f\"syntax error: '(' without expression following '{rest}'\")\n",
        "    elif c == ' ':\n",
        "      space = True\n",
        "    else:\n",
        "      raise Exception(f\"syntax error: invalid character '{c}' following '{rest}'\")\n",
        "    if not rest:\n",
        "      break # do ... while rest (is not empty)\n",
        "  if bool(operand) ^ bool(node):\n",
        "    return (rest, ValueNode(int(operand)) if operand else node)\n",
        "  raise Exception(f\"syntax error in expression '{expr}', operand='{operand}', node='{node}''\")\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ess62mrEbUyL"
      },
      "source": [
        "def parse(expr):\n",
        "  (rest, tree) = p(expr)\n",
        "  if (rest):\n",
        "    raise Exception(f\"syntax error: unbalanced parantheses in '{rest}({tree}'\")\n",
        "  return tree"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Ur3EdOeUDhQJ",
        "outputId": "d478b8cb-1be7-4551-b089-2c4f70a0b740"
      },
      "source": [
        "sum([parse(line.strip('\\n ')).evaluate() for line in open('input.txt')])\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "129770152447927"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 37
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "mQaBl8_mWO1v"
      },
      "source": [
        "Day 19"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "GxbS2RmxE-jB",
        "outputId": "da403487-a988-4b66-bb73-fa4f6e564550"
      },
      "source": [
        "# part 1 + 2, long\n",
        "import re\n",
        "rules = list(map(lambda rule_tuple: rule_tuple[1], sorted([(int(rule_line.split(':')[0]), list(map(lambda rule: rule[0] if rule[0] in 'ab' else list(map(lambda rule_num: int(rule_num), rule)), [r.strip().split(' ') for r in rule_line.split(':')[1].strip(' \"\\n').split(\"|\")]))) for rule_line in open('input.txt')])))\n",
        "\n",
        "# part 2\n",
        "rules[8] = [[42]] # [[42], [42, 8]] => (42)+\n",
        "rules[11] = [[42, 31]] # [[42,31], [42, 11, 31]] => ((42){1}(31){1}|(42){2}(31){2}|...)\n",
        "\n",
        "def build(rule):\n",
        "  r = rules[rule]\n",
        "  if r[0] == 'a' or r[0] == 'b':\n",
        "    return r[0]\n",
        "  expr = \"(\"\n",
        "  # part 2\n",
        "  if (rule == 11):\n",
        "    #$rule{11} = \"($rule{42}(?-1)?$rule{31})\";\n",
        "    r11_0 = build(r[0][0])\n",
        "    r11_1 = build(r[0][1])\n",
        "    expr += \"|\".join([r11_0 + \"{\" + str(i) + \"}\" + r11_1 + \"{\" + str(i) + \"}\" for i in range(1, 11)])\n",
        "  else:\n",
        "    for i in r[0]:\n",
        "      expr += build(i)\n",
        "      # part2\n",
        "      if (rule == 8):\n",
        "        expr += \"+\"\n",
        "  if len(r) >= 2:\n",
        "    for part in r[1:]:\n",
        "      expr = expr + \"|\"\n",
        "      for i in part:\n",
        "        expr += build(i)\n",
        "  return expr + \")\"\n",
        "\n",
        "pattern = re.compile(\"^\" + build(0) + \"$\")\n",
        "\n",
        "len(list(filter(lambda line: pattern.match(line), [l.strip('\\n') for l in open('input2.txt')])))\n",
        "\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "389"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qFdyCSGe8t1N",
        "outputId": "2b5b14f9-bfe7-4549-f12a-e4870f92f70d"
      },
      "source": [
        "# part 1, short\n",
        "import re\n",
        "rules = list(map(lambda rule_tuple: rule_tuple[1], sorted([(int(rule_line.split(':')[0]), list(map(lambda rule: rule[0] if rule[0] in 'ab' else list(map(lambda rule_num: int(rule_num), rule)), [r.strip().split(' ') for r in rule_line.split(':')[1].strip(' \"\\n').split(\"|\")]))) for rule_line in open('input.txt')])))\n",
        "def build(rule):\n",
        "  return rules[rule][0] if rules[rule][0] == 'a' or rules[rule][0] == 'b' else \"(\" + \"|\".join([\"\".join([build(next_rule) for next_rule in next_rules]) for next_rules in rules[rule]]) + \")\"\n",
        "pattern = re.compile(\"^\" + build(0) + \"$\")\n",
        "len(list(filter(lambda line: pattern.match(line), [l.strip('\\n') for l in open('input2.txt')])))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "184"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Yyt3j9HA5rPg"
      },
      "source": [
        "Day 20"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Z_SkFnM45sNE",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "26f41ca0-5fb8-4757-9a45-4873a677b2c7"
      },
      "source": [
        "import re\n",
        "from math import sqrt\n",
        "\n",
        "def flip(tile):\n",
        "  return tile[::-1] # flip around x axis -> reverse list of rows\n",
        "\n",
        "def rot90(tile):\n",
        "  return [\"\".join([t[x] for t in tile[::-1]]) for x in range(0, len(tile))]\n",
        "\n",
        "def border_codes(tile):\n",
        "  bin_tile = [t.replace('.', '0').replace('#', '1') for t in tile]\n",
        "  return [int(bin_tile[0], 2), # TOP\n",
        "          int(\"\".join([row[-1] for row in bin_tile]), 2), # RIGHT\n",
        "          int(bin_tile[-1], 2), # BOTTOM\n",
        "          int(\"\".join([row[0] for row in bin_tile]), 2)] # LEFT\n",
        "\n",
        "# part 2\n",
        "def strip_borders(tile):\n",
        "  return [tile[i][1:-1] for i in range(1, len(tile)-1)]\n",
        "\n",
        "def rotate_flip_strip(tile):\n",
        "  return [(border_codes(t), strip_borders(t)) for t in \\\n",
        "          [tile,\n",
        "           rot90(tile),\n",
        "           rot90(rot90(tile)),\n",
        "           rot90(rot90(rot90(tile))),\n",
        "           flip(tile),\n",
        "           rot90(flip(tile)),\n",
        "           rot90(rot90(flip(tile))),\n",
        "           rot90(rot90(rot90(flip(tile))))\n",
        "          ]]\n",
        "\n",
        "TOP=0\n",
        "RIGHT=1\n",
        "BOTTOM=2\n",
        "LEFT=3\n",
        "input = [l.strip('\\n ') for l in open('input.txt')]\n",
        "tiles = []\n",
        "tile = None\n",
        "id = None\n",
        "for i in range(0, len(input)):\n",
        "  line = input[i]\n",
        "  if line.startswith('Tile'):\n",
        "    id = int(re.match('Tile (\\d+):', line).group(1))\n",
        "    tile = []\n",
        "  elif not line:\n",
        "    for (borders, stripped_tile) in rotate_flip_strip(tile):\n",
        "      tiles.append((id, borders, stripped_tile))\n",
        "  else:\n",
        "    tile.append(line)\n",
        "if line:\n",
        "  for (borders, stripped_tile) in rotate_flip_strip(tile):\n",
        "    tiles.append((id, borders, stripped_tile))\n",
        "\n",
        "size = len(tiles)/8\n",
        "width = int(sqrt(size))\n",
        "\n",
        "def compare_borders(border1, border2):\n",
        "  if border1 is not None and border2 is not None:\n",
        "    return border1 == border2\n",
        "  return True\n",
        "\n",
        "def get_used_ids(grid):\n",
        "  return set(map(lambda t: t[0], grid.values()))\n",
        "\n",
        "def iterate(grid, x, y):\n",
        "  if (len(grid) == size):\n",
        "    return grid\n",
        "  # required border codes at x, y\n",
        "  top = grid[(x, y-1)][1][BOTTOM] if y > 0 and (x,y-1) in grid else None\n",
        "  right = grid[(x+1, y)][1][LEFT] if x < (width-1) and (x+1,y) in grid else None\n",
        "  bottom = grid[(x, y+1)][1][TOP] if y < (width-1) and (x,y+1) in grid else None\n",
        "  left = grid[(x-1, y)][1][RIGHT] if x > 0 and (x-1,y) in grid else None\n",
        "  nx = x + 1 if x < (width - 1) else 0\n",
        "  ny = y + 1 if nx == 0 else y\n",
        "  used_ids = get_used_ids(grid)\n",
        "  for (id, borders, stripped_tile) in tiles:\n",
        "    if id not in used_ids and \\\n",
        "          compare_borders(borders[TOP], top) and compare_borders(borders[RIGHT], right) and \\\n",
        "          compare_borders(borders[BOTTOM], bottom) and compare_borders(borders[LEFT], left):\n",
        "        #print(len(grid), \"match\", x, y, id, borders)\n",
        "        new_grid = dict(grid)\n",
        "        new_grid[(x, y)] = (id, borders, stripped_tile)\n",
        "        result_grid = iterate(new_grid, nx, ny)\n",
        "        if (result_grid is not None):\n",
        "          return result_grid\n",
        "  return None\n",
        "\n",
        "grid = iterate(dict(), 0, 0)\n",
        "print('part 1:', res[(0,0)][0] * res[(width-1,0)][0] * res[(width-1,width-1)][0] * res[(0, width-1)][0])\n",
        "\n",
        "# part 2\n",
        "print('part 2:')\n",
        "\n",
        "sea_monster_raw = [\n",
        "       '                  # ',\n",
        "       '#    ##    ##    ###',\n",
        "       ' #  #  #  #  #  #   '\n",
        "]\n",
        "sm_width = len(sea_monster_raw[0])\n",
        "sm_height = len(sea_monster_raw)\n",
        "sea_monster = [(x, y) for y in range(0, sm_height) for x in range(0, sm_width) if sea_monster_raw[y][x] == '#']\n",
        "\n",
        "tile_width = len(grid[(0,0)][2])\n",
        "sea = [\"\".join([grid[(x, y)][2][yt] for x in range(0, width)]) for y in range(0, width) for yt in range(0, tile_width)]\n",
        "sea_width = len(sea[0])\n",
        "sea_height = len(sea)\n",
        "print('sea:', sea_width, sea_height)\n",
        "\n",
        "def check_sea_monster(sea, x, y):\n",
        "  if (x < sea_width and y < sea_height):\n",
        "    for (dx, dy) in sea_monster:\n",
        "      if (sea[y+dy][x+dx] != '#'):\n",
        "        return False\n",
        "    return True\n",
        "  return False\n",
        "\n",
        "def check_sea(sea):\n",
        "  sm_coord = []\n",
        "  for y in range(0, sea_height - sm_height):\n",
        "    for x in range(0, sea_width - sm_width):\n",
        "      if check_sea_monster(sea, x, y):\n",
        "        sm_coord.append((x,y))\n",
        "        x+=sm_width\n",
        "  print('sea monsters:', len(sm_coord), '-', sm_coord)\n",
        "  sea_roughness = sum([row.count('#') for row in sea])\n",
        "  print('sea roughness:', sea_roughness - len(sm_coord) * len(sea_monster))\n",
        "\n",
        "check_sea(sea) # might also want to try rot90(sea), (1x, 2x, 3x rot90) and rot90(flip(sea)) (1x, 2x, 3x rot90)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "part 1: 79412832860579\n",
            "part 2:\n",
            "sea: 96 96\n",
            "sea monsters: 25 - [(14, 1), (60, 1), (42, 8), (16, 9), (58, 13), (26, 19), (62, 21), (9, 30), (50, 31), (24, 34), (58, 38), (13, 39), (48, 43), (25, 44), (39, 50), (12, 52), (63, 55), (18, 58), (46, 63), (10, 70), (38, 75), (6, 80), (46, 83), (3, 87), (73, 91)]\n",
            "sea roughness: 2155\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "dnRFsf4SIDAk"
      },
      "source": [
        "Day 21"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "AwRxWu1WICP4",
        "outputId": "bb2dfb58-d3c3-41b0-a08d-90645e9a72d9"
      },
      "source": [
        "import re\n",
        "from functools import reduce\n",
        "\n",
        "# part 1\n",
        "a_to_i = dict()\n",
        "ingredients = set()\n",
        "foods = []\n",
        "for food in [l.strip('\\n ') for l in open('input.txt')]:\n",
        "  m = re.match('([a-z ]+) \\(contains ([a-z, ]+)\\)', food)\n",
        "  ing = set(m.group(1).split(' '))\n",
        "  ingredients = ingredients.union(ing)\n",
        "  alg = set(m.group(2).split(', '))\n",
        "  for a in alg:\n",
        "    a_to_i[a] = ing if a not in a_to_i else a_to_i[a].intersection(ing)\n",
        "  foods.append((ing, alg))\n",
        "print('foods ', foods)\n",
        "print('a_to_i', a_to_i)\n",
        "i_with_a = reduce(lambda a,b: a.union(b), a_to_i.values())\n",
        "print('with a', i_with_a)\n",
        "i_without_a = ingredients.difference(i_with_a)\n",
        "print('w/o a ', i_without_a)\n",
        "sum([len(list(filter(lambda f: i in f[0], foods))) for i in i_without_a])\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "foods  [({'pthkfzr', 'nvmpqzd', 'zbqrfb', 'tnrmchc', 'gstsgf', 'xpdqxtrh', 'htnmftg', 'dtbfb', 'lnhx', 'ddgd', 'cqtmst', 'kndt', 'qmst', 'fzhhqp', 'pnqdpt', 'rcqb', 'sqr', 'drmssh', 'pbjgn', 'pkvhv', 'tfqsb', 'dmrfb', 'nrl', 'jbjnx', 'kskjbx', 'kxjszsfm', 'qjm', 'jncgc', 'zbvflpl', 'tzqf', 'njtvrpc', 'jhddxv', 'kxhh', 'vndmsf', 'xhnk', 'prbcss', 'lxjkr', 'jsbpht', 'jdlvgvp', 'fkxl', 'mntxnf', 'ffc', 'jdcc', 'tsqpn', 'vvgz', 'kxsll', 'sphfb', 'qdrcnt', 'llpfvs', 'vkcf', 'zmnpsx', 'lbgl', 'zkshp', 'jxdms', 'rzl', 'vgj', 'vtxf', 'sfp', 'zqzmzl', 'qxptn', 'tvbppb', 'cltx', 'srsl', 'hmhqq', 'znmhcfmc', 'jrlvrx', 'rcl', 'mxvjf', 'kvlx', 'gbzml', 'bbgjn', 'mdxq', 'nccmqg', 'szqr', 'fjcrzgq', 'tzgkm', 'dtphdp', 'zbhf', 'cndz', 'dmx', 'dsqdcl', 'qltkhqt', 'crgmxg', 'zvthr', 'xkthpt', 'sbzllf', 'bsdjq', 'rlpkdv', 'grgjkz', 'fgdn'}, {'peanuts'}), ({'nrl', 'fr', 'jbjnx', 'ccsm', 'qlmtgt', 'sdtsq', 'zmnpsx', 'vgssk', 'jxdms', 'bfbcl', 'krhfmd', 'mbfb', 'zkqmd', 'rzrb', 'kjflc', 'jxbzxd', 'tsktk', 'sphfb', 'dmpnpc', 'rpjlrl', 'crgmxg', 'skjn', 'tzqf', 'ztmqrbvb', 'pkknz', 'rtdhc', 'hsbgl', 'djqrsd', 'kqzdmd', 'hzkcvk', 'xkthpt', 'bcfhrtlx', 'kfzm', 'xnqfx', 'kxhh', 'cqstff', 'cltx', 'bcbsh', 'slzdx', 'pbqgcl', 'kndt', 'xhnk', 'lqqbz', 'qmst', 'rcqb', 'znmhcfmc', 'lknk', 'sqr', 'xrlvd', 'fgdn', 'cfn', 'mntxnf', 'klqj', 'ngqdpq', 'vxltmm', 'rkdrk', 'tsqpn', 'jngvsq', 'vvgz', 'kvlx', 'ztjqx', 'qjvvcvz', 'tfqsb'}, {'sesame', 'dairy'}), ({'pthkfzr', 'cctgq', 'nvmpqzd', 'zkqmd', 'jxbzxd', 'vbbxd', 'kschtq', 'pkknz', 'dtbfb', 'ddgd', 'xmctlnjx', 'cqtmst', 'kndt', 'qmst', 'pnqdpt', 'rcqb', 'xbbcn', 'jxfz', 'cvkmvd', 'pzvx', 'pbjgn', 'vxltmm', 'xxf', 'qjvvcvz', 'nrl', 'ccsm', 'xggvd', 'qjm', 'rzrb', 'fjqns', 'jncgc', 'fccp', 'rtdhc', 'kqzdmd', 'kxhh', 'vndmsf', 'xhnk', 'lqqbz', 'qqtnt', 'lxjkr', 'fkxl', 'jfbds', 'tsqpn', 'vkcf', 'lbgl', 'vgj', 'vtxf', 'zqzmzl', 'skjn', 'lhvcd', 'gdffb', 'qdhfqx', 'hzkcvk', 'ktsnqg', 'tvbppb', 'cltx', 'bcbsh', 'lcktf', 'dkjjpmt', 'hmhqq', 'xrlvd', 'fmlc', 'zvsgzv', 'cfn', 'kvlx', 'xskcmdk', 'mdxq', 'szqr', 'fjcrzgq', 'dtphdp', 'ppphm', 'dmx', 'ckrf', 'rpjlrl', 'zvthr', 'txjxng', 'xvtbk', 'mfcf', 'xkthpt', 'zkr', 'pbqgcl', 'vllhf', 'rlpkdv', 'vjj', 'crxd', 'fgdn', 'kqpcn', 'ngqdpq', 'ztjqx', 'ptnpb'}, {'nuts', 'sesame'}), ({'nrl', 'kskjbx', 'dq', 'sdtsq', 'fjcrzgq', 'pjkkm', 'bfbcl', 'zkshp', 'mbfb', 'hcqs', 'fftkllp', 'vtxf', 'ppphm', 'tcgmz', 'cndz', 'ckrf', 'jncgc', 'dmpnpc', 'llghzs', 'zqzmzl', 'crgmxg', 'gstsgf', 'zvthr', 'lhvcd', 'ztmqrbvb', 'mfcf', 'jhddxv', 'djqrsd', 'hzkcvk', 'bcfhrtlx', 'cqstff', 'cltx', 'hllqx', 'kndt', 'vndmsf', 'rcqb', 'prbcss', 'znmhcfmc', 'lknk', 'jrlvrx', 'crxd', 'crrh', 'cvkmvd', 'fkxl', 'klqj', 'tsqpn', 'vvgz', 'jngvsq', 'nrzc', 'xskcmdk', 'qjvvcvz', 'bbgjn', 'tfqsb'}, {'dairy', 'peanuts'}), ({'xqlvq', 'nrl', 'dmrfb', 'szqr', 'fr', 'kskjbx', 'nvmpqzd', 'qlmtgt', 'bfbcl', 'zkshp', 'rzl', 'mzhp', 'qjm', 'zvbpd', 'rzrb', 'vgj', 'ppphm', 'tsktk', 'zbhf', 'tcgmz', 'dmx', 'dmpnpc', 'fccp', 'lhvcd', 'kschtq', 'txjxng', 'tzqf', 'htnmftg', 'pkknz', 'hxgbnc', 'qdhfqx', 'hsbgl', 'djqrsd', 'kqzdmd', 'jhddxv', 'kxhh', 'cltx', 'qxplxtp', 'vqmdd', 'lcktf', 'kxsll', 'gvpd', 'pttq', 'dkjjpmt', 'kndt', 'xhnk', 'rcqb', 'qqtnt', 'jrlvrx', 'lknk', 'sqr', 'cvkmvd', 'fgdn', 'pzvx', 'fkxl', 'mntxnf', 'cfn', 'klqj', 'spthcff', 'jdcc', 'tsqpn', 'vvgz', 'pkvhv', 'qjvvcvz', 'ptnpb', 'tfqsb'}, {'eggs', 'fish'}), ({'nrl', 'nccmqg', 'kskjbx', 'nvmpqzd', 'zmnpsx', 'sdtsq', 'vgssk', 'gtvk', 'xggvd', 'zkshp', 'krhfmd', 'mzhp', 'krg', 'vtxf', 'zbhf', 'ckrf', 'tsktk', 'sfp', 'jncgc', 'kvlx', 'zbvflpl', 'llghzs', 'crgmxg', 'zqzmzl', 'txjxng', 'pkknz', 'bnjq', 'fchtgm', 'kqzdmd', 'hzkcvk', 'dtbfb', 'dnxhx', 'djqrsd', 'bcfhrtlx', 'ktsnqg', 'sbzllf', 'tvbppb', 'cltx', 'hllqx', 'qxplxtp', 'pttq', 'xmctlnjx', 'slzdx', 'cqtmst', 'pbqgcl', 'qmst', 'xhnk', 'lqqbz', 'qqtnt', 'rcqb', 'lknk', 'xrlvd', 'crrh', 'rcl', 'xbbcn', 'crxd', 'kqpcn', 'fgdn', 'cvkmvd', 'fkxl', 'ndn', 'ffc', 'rkdrk', 'hjkvk', 'jfbds', 'mntxnf', 'xxf', 'tsqpn', 'jdcc', 'nrzc', 'xskcmdk', 'qjvvcvz', 'bbgjn', 'mdxq'}, {'nuts', 'wheat', 'eggs'}), ({'qdrcnt', 'nrl', 'dmrfb', 'szqr', 'cxtgtz', 'jbjnx', 'qlmtgt', 'gtvk', 'fjcrzgq', 'krhfmd', 'kxjszsfm', 'mzhp', 'dmx', 'kjflc', 'tcgmz', 'dsqdcl', 'jncgc', 'llghzs', 'zqzmzl', 'xpdqxtrh', 'njtvrpc', 'hsbgl', 'jhddxv', 'kqzdmd', 'djqrsd', 'dnxhx', 'qxptn', 'bcfhrtlx', 'tvbppb', 'cltx', 'pttq', 'xmctlnjx', 'kndt', 'bsdjq', 'xhnk', 'rcqb', 'prbcss', 'sqr', 'crxd', 'mxvjf', 'xrlvd', 'cvkmvd', 'kqpcn', 'mntxnf', 'qjvvcvz', 'bbgjn', 'tfqsb'}, {'fish'}), ({'qdrcnt', 'nrl', 'fr', 'cxtgtz', 'kskjbx', 'nvmpqzd', 'lbgl', 'zkshp', 'pjkkm', 'xggvd', 'rzl', 'zkqmd', 'krg', 'fftkllp', 'tsktk', 'cndz', 'kvlx', 'chtpkf', 'pkknz', 'hxgbnc', 'gdffb', 'djqrsd', 'dnxhx', 'qxptn', 'xkthpt', 'tvbppb', 'cqstff', 'cltx', 'hllqx', 'vqmdd', 'slzdx', 'pbqgcl', 'vndmsf', 'xhnk', 'hmhqq', 'rcqb', 'drmssh', 'zvsgzv', 'pbjgn', 'hjkvk', 'vxltmm', 'xxf', 'tsqpn', 'nrzc', 'ztjqx', 'qjvvcvz', 'ptnpb', 'tfqsb'}, {'fish'}), ({'qdrcnt', 'nrl', 'dmrfb', 'llpfvs', 'vkcf', 'jbjnx', 'kskjbx', 'gtvk', 'xggvd', 'jxdms', 'bfbcl', 'zkshp', 'tzgkm', 'qjm', 'zzmvlnq', 'hcqs', 'zbqrfb', 'nhgmnc', 'gzbs', 'vtxf', 'fftkllp', 'kjflc', 'ckrf', 'fjqns', 'sfp', 'dsqdcl', 'tnrmchc', 'zbvflpl', 'zqzmzl', 'qsddtb', 'skjn', 'chtpkf', 'kschtq', 'txjxng', 'rtdhc', 'mfcf', 'gdffb', 'qdhfqx', 'hzkcvk', 'qxptn', 'ktsnqg', 'tvbppb', 'kxhh', 'cltx', 'hllqx', 'ddgd', 'vqmdd', 'zkr', 'dkjjpmt', 'nhqz', 'kndt', 'hmhqq', 'xhnk', 'bsdjq', 'vjj', 'znmhcfmc', 'qqtnt', 'jrlvrx', 'jsbpht', 'crrh', 'crxd', 'jxfz', 'drmssh', 'pzvx', 'fkxl', 'mntxnf', 'klqj', 'spthcff', 'hjkvk', 'rkdrk', 'xxf', 'tsqpn', 'jdcc', 'vxltmm', 'qjvvcvz', 'kxsll', 'mdxq', 'tfqsb'}, {'nuts', 'sesame', 'peanuts'}), ({'nrl', 'szqr', 'fr', 'vkcf', 'kskjbx', 'lbgl', 'vgssk', 'gtvk', 'zkshp', 'pjkkm', 'jxdms', 'kxjszsfm', 'nhgmnc', 'zzmvlnq', 'hcqs', 'vgj', 'zkqmd', 'rzrb', 'fftkllp', 'vtxf', 'jxbzxd', 'tsktk', 'kjflc', 'qltkhqt', 'krg', 'dmpnpc', 'zqzmzl', 'qsddtb', 'fccp', 'vbbxd', 'chtpkf', 'lhvcd', 'tzqf', 'xvtbk', 'htnmftg', 'gdffb', 'fchtgm', 'qdhfqx', 'hsbgl', 'kqzdmd', 'bcfhrtlx', 'sbzllf', 'tvbppb', 'cltx', 'srsl', 'qxplxtp', 'lcktf', 'vqmdd', 'pttq', 'xmctlnjx', 'gvpd', 'cqtmst', 'nhqz', 'vndmsf', 'xhnk', 'rcqb', 'znmhcfmc', 'vllhf', 'jrlvrx', 'jsbpht', 'lxjkr', 'crxd', 'mxvjf', 'sqr', 'rcl', 'drmssh', 'fmlc', 'mntxnf', 'cfn', 'pbjgn', 'vxltmm', 'xxf', 'tsqpn', 'jngvsq', 'kvlx', 'xskcmdk', 'gbzml', 'kxsll', 'tfqsb'}, {'peanuts'}), ({'qdrcnt', 'nrl', 'nccmqg', 'xqlvq', 'cxtgtz', 'dq', 'zmnpsx', 'sdtsq', 'gtvk', 'dtphdp', 'kxjszsfm', 'mzhp', 'nhgmnc', 'hcqs', 'zzmvlnq', 'zvbpd', 'vgj', 'vtxf', 'zbhf', 'cndz', 'dmx', 'ckrf', 'jncgc', 'dmpnpc', 'zbvflpl', 'llghzs', 'rpjlrl', 'crgmxg', 'qjvvcvz', 'zvthr', 'chtpkf', 'lhvcd', 'xvtbk', 'pkknz', 'njtvrpc', 'bnjq', 'rtdhc', 'hxgbnc', 'hsbgl', 'hzkcvk', 'kqzdmd', 'xkthpt', 'sbzllf', 'tvbppb', 'cqstff', 'ddgd', 'cltx', 'bcbsh', 'lcktf', 'vqmdd', 'srsl', 'xmctlnjx', 'bsdjq', 'xhnk', 'lqqbz', 'fzhhqp', 'qqtnt', 'znmhcfmc', 'rcqb', 'vjj', 'mxvjf', 'xbbcn', 'fgdn', 'kqpcn', 'drmssh', 'pzvx', 'zvsgzv', 'ndn', 'fkxl', 'rkdrk', 'cfn', 'jfbds', 'vxltmm', 'tsqpn', 'vvgz', 'gbzml', 'tfqsb'}, {'shellfish'}), ({'nrl', 'szqr', 'llpfvs', 'pthkfzr', 'jbjnx', 'vkcf', 'ccsm', 'sdtsq', 'vgssk', 'xggvd', 'dtphdp', 'kxjszsfm', 'rzl', 'zbqrfb', 'mbfb', 'zkqmd', 'zvbpd', 'vtxf', 'zbhf', 'tcgmz', 'qltkhqt', 'dsqdcl', 'sfp', 'rpjlrl', 'zqzmzl', 'gstsgf', 'fccp', 'skjn', 'lhvcd', 'kschtq', 'htnmftg', 'bnjq', 'fchtgm', 'qdhfqx', 'kqzdmd', 'xhc', 'qhps', 'qxptn', 'bcfhrtlx', 'kfzm', 'tvbppb', 'kxhh', 'cltx', 'lcktf', 'pttq', 'pbqgcl', 'kndt', 'xhnk', 'qmst', 'fzhhqp', 'znmhcfmc', 'rlpkdv', 'jrlvrx', 'xrlvd', 'xbbcn', 'crxd', 'jxfz', 'mxvjf', 'jdlvgvp', 'grgjkz', 'zvsgzv', 'ndn', 'ffc', 'klqj', 'ngqdpq', 'vxltmm', 'hjkvk', 'flrxh', 'jfbds', 'tsqpn', 'rkdrk', 'kvlx', 'qjvvcvz', 'ptnpb', 'tfqsb'}, {'fish'}), ({'nrl', 'szqr', 'kskjbx', 'zmnpsx', 'sdtsq', 'qlmtgt', 'pjkkm', 'tzgkm', 'gzbs', 'zbqrfb', 'zbhf', 'tcgmz', 'dsqdcl', 'zqzmzl', 'fccp', 'txjxng', 'htnmftg', 'fchtgm', 'rtdhc', 'dnxhx', 'djqrsd', 'xhc', 'qxptn', 'sbzllf', 'tvbppb', 'cqstff', 'cltx', 'hllqx', 'bcbsh', 'vqmdd', 'dkjjpmt', 'xmctlnjx', 'slzdx', 'cqtmst', 'nhqz', 'pbqgcl', 'xhnk', 'prbcss', 'rcqb', 'rlpkdv', 'sqr', 'cvkmvd', 'jdlvgvp', 'drmssh', 'kqpcn', 'spthcff', 'jfbds', 'hjkvk', 'tsqpn', 'xskcmdk', 'gbzml', 'mdxq', 'tfqsb'}, {'sesame', 'peanuts'}), ({'xqlvq', 'dmrfb', 'nrl', 'llpfvs', 'cxtgtz', 'cctgq', 'nvmpqzd', 'gtvk', 'jxdms', 'xggvd', 'tzgkm', 'dtphdp', 'zbqrfb', 'gzbs', 'nhgmnc', 'zvbpd', 'zkqmd', 'ppphm', 'kjflc', 'qltkhqt', 'cndz', 'dmx', 'dsqdcl', 'tnrmchc', 'jxbzxd', 'zbhf', 'zbvflpl', 'tfqsb', 'zqzmzl', 'fccp', 'skjn', 'tzqf', 'xvtbk', 'pkknz', 'fchtgm', 'mfcf', 'hsbgl', 'qxptn', 'bcfhrtlx', 'sbzllf', 'xnqfx', 'kxhh', 'cqstff', 'cltx', 'hllqx', 'bcbsh', 'zkr', 'pttq', 'nhqz', 'xmctlnjx', 'slzdx', 'vndmsf', 'hmhqq', 'lqqbz', 'xhnk', 'lxjkr', 'jsbpht', 'xrlvd', 'xbbcn', 'jxfz', 'fgdn', 'fmlc', 'pzvx', 'fkxl', 'cfn', 'zvsgzv', 'rkdrk', 'spthcff', 'hjkvk', 'tsqpn', 'nrzc', 'qjvvcvz', 'ptnpb', 'bbgjn', 'mdxq', 'sphfb'}, {'shellfish', 'wheat', 'eggs'}), ({'nccmqg', 'szqr', 'llpfvs', 'fr', 'jbjnx', 'ccsm', 'sdtsq', 'zkshp', 'xggvd', 'rzl', 'mzhp', 'kxjszsfm', 'nhgmnc', 'mbfb', 'zvbpd', 'rzrb', 'dmx', 'tfqsb', 'sfp', 'jncgc', 'dsqdcl', 'llghzs', 'zqzmzl', 'qsddtb', 'zvthr', 'lhvcd', 'txjxng', 'htnmftg', 'pkknz', 'fchtgm', 'qdhfqx', 'hzkcvk', 'qhps', 'xkthpt', 'bcfhrtlx', 'lnhx', 'sbzllf', 'xnqfx', 'tvbppb', 'kxhh', 'cltx', 'ddgd', 'zkr', 'lcktf', 'pttq', 'xmctlnjx', 'cqtmst', 'vndmsf', 'qmst', 'xhnk', 'lqqbz', 'vllhf', 'rcqb', 'rlpkdv', 'xrlvd', 'fmlc', 'zvsgzv', 'ndn', 'ffc', 'mntxnf', 'spthcff', 'jfbds', 'pbjgn', 'fkxl', 'tsqpn', 'flrxh', 'krg', 'xskcmdk', 'ztjqx', 'qjvvcvz', 'mdxq', 'sphfb'}, {'shellfish', 'eggs'}), ({'mzhp', 'zbqrfb', 'zvbpd', 'tsktk', 'tcgmz', 'jxbzxd', 'gstsgf', 'kschtq', 'pkknz', 'lnhx', 'hllqx', 'xmctlnjx', 'rcqb', 'xbbcn', 'jxfz', 'drmssh', 'pzvx', 'krg', 'qjvvcvz', 'nrl', 'jbjnx', 'kskjbx', 'kjflc', 'zbvflpl', 'llghzs', 'fccp', 'tzqf', 'njtvrpc', 'rtdhc', 'dnxhx', 'xhnk', 'lqqbz', 'qqtnt', 'jsbpht', 'tsqpn', 'jdcc', 'qdrcnt', 'llpfvs', 'fr', 'vkcf', 'zmnpsx', 'lbgl', 'bfbcl', 'zkshp', 'zzmvlnq', 'hcqs', 'fftkllp', 'zqzmzl', 'chtpkf', 'hxgbnc', 'xhc', 'qxptn', 'bcfhrtlx', 'tvbppb', 'cltx', 'srsl', 'lcktf', 'vqmdd', 'znmhcfmc', 'jrlvrx', 'xrlvd', 'mxvjf', 'rcl', 'zvsgzv', 'cfn', 'jngvsq', 'xskcmdk', 'gbzml', 'bbgjn', 'nccmqg', 'szqr', 'gtvk', 'dtphdp', 'ppphm', 'zbhf', 'cndz', 'ckrf', 'xvtbk', 'zkr', 'gvpd', 'slzdx', 'pbqgcl', 'bsdjq', 'vllhf', 'rlpkdv', 'vjj', 'grgjkz', 'fgdn', 'ptnpb'}, {'sesame', 'dairy', 'wheat'}), ({'qdrcnt', 'nrl', 'fr', 'cxtgtz', 'vkcf', 'jbjnx', 'ccsm', 'zmnpsx', 'zkshp', 'rzl', 'kxjszsfm', 'zbqrfb', 'vgj', 'zvbpd', 'zkqmd', 'ppphm', 'kjflc', 'cndz', 'tsktk', 'tnrmchc', 'dmpnpc', 'zbvflpl', 'rpjlrl', 'zqzmzl', 'fccp', 'skjn', 'chtpkf', 'kschtq', 'txjxng', 'ztmqrbvb', 'pkknz', 'bnjq', 'njtvrpc', 'hsbgl', 'dnxhx', 'xkthpt', 'lnhx', 'bcfhrtlx', 'kfzm', 'cltx', 'hllqx', 'gvpd', 'pttq', 'slzdx', 'cqtmst', 'kndt', 'qmst', 'hmhqq', 'xhnk', 'fzhhqp', 'vllhf', 'rcqb', 'lknk', 'jrlvrx', 'crxd', 'rcl', 'grgjkz', 'cvkmvd', 'kqpcn', 'jdlvgvp', 'fmlc', 'ndn', 'pbjgn', 'hjkvk', 'vxltmm', 'tsqpn', 'jngvsq', 'pkvhv', 'qjvvcvz', 'mdxq'}, {'nuts'}), ({'xqlvq', 'nccmqg', 'szqr', 'cxtgtz', 'cctgq', 'vkcf', 'qlmtgt', 'zkshp', 'tzgkm', 'krhfmd', 'qjm', 'nhgmnc', 'zvbpd', 'kjflc', 'cndz', 'qltkhqt', 'dsqdcl', 'sfp', 'sphfb', 'zqzmzl', 'qjvvcvz', 'qsddtb', 'vbbxd', 'xpdqxtrh', 'lhvcd', 'kschtq', 'ztmqrbvb', 'pkknz', 'htnmftg', 'bnjq', 'rtdhc', 'mfcf', 'fchtgm', 'djqrsd', 'xhc', 'qhps', 'hzkcvk', 'xnqfx', 'cltx', 'lcktf', 'qxplxtp', 'pttq', 'kndt', 'hmhqq', 'xhnk', 'vndmsf', 'fzhhqp', 'rcqb', 'znmhcfmc', 'vjj', 'sqr', 'qqtnt', 'lxjkr', 'crrh', 'jrlvrx', 'jsbpht', 'fgdn', 'zvsgzv', 'ndn', 'mntxnf', 'rkdrk', 'xxf', 'tsqpn', 'gbzml', 'ptnpb', 'bbgjn', 'mdxq', 'tfqsb'}, {'nuts', 'sesame', 'dairy'}), ({'vkcf', 'ccsm', 'pjkkm', 'zkshp', 'jxdms', 'xggvd', 'krhfmd', 'kxjszsfm', 'qjm', 'hcqs', 'ppphm', 'jxbzxd', 'qltkhqt', 'tcgmz', 'zqzmzl', 'crgmxg', 'xpdqxtrh', 'vbbxd', 'gdffb', 'mfcf', 'hsbgl', 'jhddxv', 'djqrsd', 'dnxhx', 'dtbfb', 'xkthpt', 'kqzdmd', 'kfzm', 'tvbppb', 'cqstff', 'cltx', 'srsl', 'lcktf', 'vqmdd', 'bcbsh', 'gvpd', 'xmctlnjx', 'slzdx', 'pbqgcl', 'bsdjq', 'xhnk', 'kndt', 'rcqb', 'znmhcfmc', 'jrlvrx', 'lknk', 'jdlvgvp', 'fmlc', 'zvsgzv', 'pbjgn', 'spthcff', 'ngqdpq', 'tsqpn', 'vvgz', 'xskcmdk', 'qjvvcvz', 'ptnpb', 'bbgjn', 'mdxq', 'tfqsb'}, {'shellfish', 'eggs'}), ({'nrl', 'llpfvs', 'ccsm', 'vgssk', 'jxdms', 'tzgkm', 'kxjszsfm', 'zbqrfb', 'gzbs', 'vtxf', 'kjflc', 'sfp', 'zbvflpl', 'rpjlrl', 'crgmxg', 'zqzmzl', 'vbbxd', 'ztmqrbvb', 'bnjq', 'hxgbnc', 'fchtgm', 'njtvrpc', 'qdhfqx', 'kqzdmd', 'xkthpt', 'lnhx', 'cltx', 'ddgd', 'gvpd', 'slzdx', 'cqtmst', 'kndt', 'qmst', 'xhnk', 'lqqbz', 'fzhhqp', 'pnqdpt', 'prbcss', 'rlpkdv', 'vllhf', 'lknk', 'vjj', 'znmhcfmc', 'nrzc', 'zvsgzv', 'klqj', 'ngqdpq', 'flrxh', 'xxf', 'jdcc', 'tsqpn', 'pkvhv', 'qjvvcvz', 'kxsll', 'tfqsb'}, {'nuts', 'eggs'}), ({'pthkfzr', 'nvmpqzd', 'mbfb', 'tsktk', 'gstsgf', 'vbbxd', 'kschtq', 'htnmftg', 'pkknz', 'hsbgl', 'lnhx', 'kfzm', 'ddgd', 'nhqz', 'cqtmst', 'kndt', 'fzhhqp', 'rcqb', 'sqr', 'xbbcn', 'jxfz', 'drmssh', 'pzvx', 'pkvhv', 'krg', 'tfqsb', 'nrl', 'jbjnx', 'kskjbx', 'qlmtgt', 'xggvd', 'rzrb', 'fccp', 'vndmsf', 'xhnk', 'prbcss', 'lxjkr', 'jsbpht', 'fkxl', 'mntxnf', 'ndn', 'ffc', 'klqj', 'tsqpn', 'vvgz', 'sphfb', 'cxtgtz', 'zmnpsx', 'zkshp', 'bfbcl', 'nhgmnc', 'vgj', 'zqzmzl', 'lhvcd', 'hxgbnc', 'gdffb', 'qdhfqx', 'xhc', 'bcfhrtlx', 'cltx', 'bcbsh', 'hmhqq', 'jrlvrx', 'rcl', 'mxvjf', 'zvsgzv', 'cfn', 'bbgjn', 'nccmqg', 'dtphdp', 'zbhf', 'cndz', 'ckrf', 'crgmxg', 'bnjq', 'mfcf', 'qhps', 'sbzllf', 'slzdx', 'vllhf', 'vjj', 'crrh', 'crxd', 'fgdn', 'ptnpb'}, {'shellfish', 'sesame'}), ({'cctgq', 'nvmpqzd', 'zbqrfb', 'mbfb', 'zvbpd', 'jxbzxd', 'kschtq', 'hsbgl', 'djqrsd', 'pttq', 'xmctlnjx', 'cqtmst', 'kndt', 'pnqdpt', 'rcqb', 'jxfz', 'nrzc', 'qjvvcvz', 'tfqsb', 'dmrfb', 'ccsm', 'kxjszsfm', 'qjm', 'kjflc', 'jncgc', 'llghzs', 'fccp', 'tzqf', 'ztmqrbvb', 'rtdhc', 'jhddxv', 'kqzdmd', 'vndmsf', 'xhnk', 'lqqbz', 'qqtnt', 'jsbpht', 'jdlvgvp', 'mntxnf', 'klqj', 'tsqpn', 'jdcc', 'kxsll', 'sphfb', 'cxtgtz', 'zkshp', 'jxdms', 'pjkkm', 'rzl', 'zzmvlnq', 'vtxf', 'sfp', 'zqzmzl', 'skjn', 'lhvcd', 'hxgbnc', 'gdffb', 'qdhfqx', 'xhc', 'qxptn', 'cltx', 'lcktf', 'znmhcfmc', 'zvsgzv', 'kvlx', 'sdtsq', 'fjcrzgq', 'dtphdp', 'ppphm', 'qltkhqt', 'dsqdcl', 'rpjlrl', 'crgmxg', 'zvthr', 'mfcf', 'qhps', 'sbzllf', 'xnqfx', 'zkr', 'crrh', 'crxd', 'grgjkz', 'fgdn', 'kqpcn', 'rkdrk', 'ngqdpq', 'ztjqx', 'ptnpb'}, {'wheat', 'eggs', 'peanuts'}), ({'qdrcnt', 'nccmqg', 'szqr', 'nrl', 'fr', 'kskjbx', 'ccsm', 'vgssk', 'pjkkm', 'dtphdp', 'rzl', 'gzbs', 'mbfb', 'zbqrfb', 'zkqmd', 'rzrb', 'vtxf', 'vgj', 'nhgmnc', 'fjqns', 'cndz', 'jncgc', 'tnrmchc', 'dmpnpc', 'rpjlrl', 'zqzmzl', 'qsddtb', 'fccp', 'xpdqxtrh', 'lhvcd', 'txjxng', 'xvtbk', 'ztmqrbvb', 'htnmftg', 'fchtgm', 'hsbgl', 'qdhfqx', 'kqzdmd', 'dnxhx', 'qhps', 'bcfhrtlx', 'sbzllf', 'cltx', 'vqmdd', 'xmctlnjx', 'pbqgcl', 'qmst', 'xhnk', 'vjj', 'rcqb', 'sqr', 'lxjkr', 'crrh', 'grgjkz', 'cvkmvd', 'kqpcn', 'fmlc', 'pzvx', 'fkxl', 'ndn', 'fgdn', 'pbjgn', 'rkdrk', 'vxltmm', 'hjkvk', 'tsqpn', 'kvlx', 'qjvvcvz', 'sphfb'}, {'nuts', 'eggs'}), ({'nrl', 'llpfvs', 'pthkfzr', 'kskjbx', 'ccsm', 'qlmtgt', 'sdtsq', 'fjcrzgq', 'jxdms', 'xggvd', 'rzl', 'nhgmnc', 'hcqs', 'zbqrfb', 'vgj', 'zvbpd', 'vtxf', 'krg', 'rzrb', 'zkqmd', 'qltkhqt', 'sfp', 'kvlx', 'zbvflpl', 'dmpnpc', 'crgmxg', 'zqzmzl', 'lhvcd', 'htnmftg', 'pkknz', 'rtdhc', 'dnxhx', 'djqrsd', 'dtbfb', 'xkthpt', 'kqzdmd', 'lnhx', 'ktsnqg', 'bcfhrtlx', 'cqstff', 'ddgd', 'hllqx', 'cltx', 'zkr', 'vqmdd', 'srsl', 'gvpd', 'cqtmst', 'pbqgcl', 'qmst', 'xhnk', 'rcqb', 'znmhcfmc', 'vjj', 'lknk', 'mxvjf', 'jxfz', 'grgjkz', 'drmssh', 'pzvx', 'cfn', 'ffc', 'rkdrk', 'hjkvk', 'ngqdpq', 'klqj', 'flrxh', 'tsqpn', 'jngvsq', 'nrzc', 'ztjqx', 'gbzml', 'tfqsb'}, {'shellfish', 'wheat', 'eggs'}), ({'nrl', 'llpfvs', 'szqr', 'vgssk', 'bfbcl', 'pjkkm', 'xggvd', 'krhfmd', 'kxjszsfm', 'mzhp', 'gzbs', 'mbfb', 'vgj', 'rzrb', 'fftkllp', 'jxbzxd', 'kjflc', 'fjqns', 'dsqdcl', 'tnrmchc', 'rpjlrl', 'crgmxg', 'qjvvcvz', 'zqzmzl', 'kschtq', 'txjxng', 'htnmftg', 'pkknz', 'rtdhc', 'hsbgl', 'djqrsd', 'kqzdmd', 'sbzllf', 'kfzm', 'tvbppb', 'cqstff', 'cltx', 'bcbsh', 'zkr', 'qxplxtp', 'srsl', 'xmctlnjx', 'bsdjq', 'xhnk', 'fzhhqp', 'pnqdpt', 'vllhf', 'znmhcfmc', 'rcqb', 'drmssh', 'jdlvgvp', 'zvsgzv', 'mntxnf', 'rkdrk', 'spthcff', 'tsqpn', 'vvgz', 'pkvhv', 'xskcmdk', 'gbzml'}, {'sesame'}), ({'xqlvq', 'nccmqg', 'qdrcnt', 'pthkfzr', 'nvmpqzd', 'dq', 'kskjbx', 'jxdms', 'kxjszsfm', 'nhgmnc', 'zkqmd', 'tsktk', 'cndz', 'zbhf', 'ckrf', 'sphfb', 'kjflc', 'zbvflpl', 'dmpnpc', 'zqzmzl', 'gstsgf', 'skjn', 'ztmqrbvb', 'bnjq', 'hxgbnc', 'dnxhx', 'bcfhrtlx', 'kxhh', 'cqstff', 'cltx', 'hllqx', 'srsl', 'zkr', 'qxplxtp', 'dkjjpmt', 'gvpd', 'pttq', 'slzdx', 'cqtmst', 'vndmsf', 'xhnk', 'fzhhqp', 'rcqb', 'znmhcfmc', 'prbcss', 'jsbpht', 'rcl', 'kqpcn', 'mntxnf', 'ffc', 'ndn', 'vxltmm', 'jfbds', 'flrxh', 'jdcc', 'tsqpn', 'xskcmdk', 'qjvvcvz', 'mdxq', 'tfqsb'}, {'dairy', 'peanuts'}), ({'qdrcnt', 'nccmqg', 'szqr', 'xqlvq', 'pthkfzr', 'nrl', 'jbjnx', 'fr', 'ccsm', 'dmrfb', 'sdtsq', 'lbgl', 'vgssk', 'fjcrzgq', 'dtphdp', 'krhfmd', 'zzmvlnq', 'zkqmd', 'rzrb', 'fftkllp', 'kjflc', 'sfp', 'jncgc', 'dmpnpc', 'zbvflpl', 'rpjlrl', 'zqzmzl', 'gstsgf', 'fccp', 'xpdqxtrh', 'skjn', 'kschtq', 'txjxng', 'ztmqrbvb', 'htnmftg', 'njtvrpc', 'rtdhc', 'mfcf', 'gdffb', 'hsbgl', 'xhc', 'bcfhrtlx', 'lnhx', 'sbzllf', 'ddgd', 'lcktf', 'zkr', 'pttq', 'nhqz', 'slzdx', 'xmctlnjx', 'qmst', 'bsdjq', 'vndmsf', 'xhnk', 'lqqbz', 'vjj', 'rlpkdv', 'znmhcfmc', 'jrlvrx', 'rcqb', 'qqtnt', 'xbbcn', 'mxvjf', 'fgdn', 'kqpcn', 'jdlvgvp', 'zvsgzv', 'ndn', 'ffc', 'cfn', 'pbjgn', 'jfbds', 'mntxnf', 'xxf', 'klqj', 'vvgz', 'tsqpn', 'kvlx', 'xskcmdk', 'qjvvcvz', 'kxsll', 'bbgjn', 'tfqsb'}, {'nuts'}), ({'nrl', 'nccmqg', 'pthkfzr', 'cctgq', 'lbgl', 'gtvk', 'fjcrzgq', 'bfbcl', 'xggvd', 'tzgkm', 'krhfmd', 'kxjszsfm', 'qjm', 'zbqrfb', 'mbfb', 'zkqmd', 'fftkllp', 'zbhf', 'cndz', 'ckrf', 'qltkhqt', 'jncgc', 'sphfb', 'kvlx', 'dsqdcl', 'sfp', 'llghzs', 'zqzmzl', 'fccp', 'kschtq', 'ztmqrbvb', 'htnmftg', 'pkknz', 'xhc', 'dnxhx', 'kfzm', 'xnqfx', 'tvbppb', 'cltx', 'zkr', 'nhqz', 'cqtmst', 'xhnk', 'znmhcfmc', 'sqr', 'jrlvrx', 'lknk', 'nrzc', 'grgjkz', 'drmssh', 'fmlc', 'rkdrk', 'ngqdpq', 'jfbds', 'xxf', 'tsqpn', 'vvgz', 'pkvhv', 'qjvvcvz', 'kxsll', 'mdxq', 'tfqsb'}, {'fish', 'peanuts'}), ({'nrl', 'pthkfzr', 'cxtgtz', 'cctgq', 'nvmpqzd', 'vkcf', 'qlmtgt', 'fjcrzgq', 'rzl', 'kxjszsfm', 'nhgmnc', 'hcqs', 'zbhf', 'ckrf', 'tsktk', 'zqzmzl', 'gstsgf', 'zvthr', 'fccp', 'tzqf', 'txjxng', 'htnmftg', 'pkknz', 'fchtgm', 'hsbgl', 'qdhfqx', 'xhc', 'sbzllf', 'tvbppb', 'cqstff', 'ddgd', 'bcbsh', 'lcktf', 'qxplxtp', 'pttq', 'bsdjq', 'vndmsf', 'xhnk', 'lqqbz', 'rcqb', 'rlpkdv', 'jsbpht', 'mxvjf', 'jxfz', 'drmssh', 'mntxnf', 'cfn', 'pbjgn', 'klqj', 'flrxh', 'rkdrk', 'ffc', 'tsqpn', 'jngvsq', 'qjvvcvz', 'tfqsb'}, {'sesame', 'wheat'}), ({'nrl', 'fr', 'vkcf', 'kskjbx', 'zmnpsx', 'bfbcl', 'dtphdp', 'kxjszsfm', 'mzhp', 'gzbs', 'zzmvlnq', 'mbfb', 'rzrb', 'kjflc', 'zbhf', 'tfqsb', 'sfp', 'fjqns', 'kvlx', 'rpjlrl', 'zqzmzl', 'ptnpb', 'tzqf', 'bnjq', 'dnxhx', 'xkthpt', 'ktsnqg', 'xnqfx', 'cltx', 'hllqx', 'bcbsh', 'lcktf', 'qxplxtp', 'zkr', 'kndt', 'bsdjq', 'xhnk', 'pbqgcl', 'fzhhqp', 'hmhqq', 'qqtnt', 'rlpkdv', 'prbcss', 'sqr', 'rcqb', 'rcl', 'ndn', 'pbjgn', 'hjkvk', 'jfbds', 'tsqpn', 'nrzc', 'xskcmdk', 'kxsll', 'sphfb'}, {'sesame', 'dairy', 'wheat'}), ({'qdrcnt', 'llpfvs', 'szqr', 'cxtgtz', 'vkcf', 'nvmpqzd', 'dq', 'ccsm', 'qlmtgt', 'tzgkm', 'dtphdp', 'gzbs', 'nhgmnc', 'vgj', 'zkqmd', 'vtxf', 'fftkllp', 'zbhf', 'tfqsb', 'tsktk', 'dsqdcl', 'tcgmz', 'tnrmchc', 'dmpnpc', 'zqzmzl', 'qjvvcvz', 'xpdqxtrh', 'skjn', 'kschtq', 'txjxng', 'tzqf', 'xvtbk', 'pkknz', 'hxgbnc', 'xhc', 'dnxhx', 'hzkcvk', 'qxptn', 'bcfhrtlx', 'sbzllf', 'cltx', 'srsl', 'vqmdd', 'lcktf', 'dkjjpmt', 'zkr', 'bcbsh', 'pbqgcl', 'xhnk', 'fzhhqp', 'vjj', 'rcqb', 'qqtnt', 'lknk', 'jsbpht', 'sqr', 'crrh', 'rlpkdv', 'pzvx', 'fkxl', 'cfn', 'mntxnf', 'klqj', 'zvsgzv', 'flrxh', 'vxltmm', 'ngqdpq', 'tsqpn', 'pkvhv', 'ztjqx', 'gbzml', 'kxsll', 'bbgjn', 'sphfb'}, {'eggs'}), ({'gzbs', 'tcgmz', 'jxbzxd', 'gstsgf', 'xpdqxtrh', 'vbbxd', 'kschtq', 'hsbgl', 'lnhx', 'kfzm', 'hllqx', 'pttq', 'nhqz', 'cqtmst', 'rcqb', 'sqr', 'jxfz', 'cvkmvd', 'drmssh', 'pzvx', 'pbjgn', 'vxltmm', 'xxf', 'pkvhv', 'qjvvcvz', 'tfqsb', 'nrl', 'jbjnx', 'qlmtgt', 'kxjszsfm', 'qjm', 'rzrb', 'fccp', 'tzqf', 'njtvrpc', 'dnxhx', 'kxhh', 'xhnk', 'prbcss', 'qqtnt', 'lxjkr', 'jsbpht', 'fkxl', 'mntxnf', 'ndn', 'ffc', 'spthcff', 'jfbds', 'vvgz', 'sphfb', 'lbgl', 'zkshp', 'pjkkm', 'rzl', 'nhgmnc', 'fftkllp', 'zqzmzl', 'skjn', 'hxgbnc', 'gdffb', 'qxptn', 'cltx', 'qxplxtp', 'dkjjpmt', 'cfn', 'jngvsq', 'kvlx', 'gbzml', 'bbgjn', 'sdtsq', 'gtvk', 'fjcrzgq', 'dtphdp', 'ppphm', 'dmx', 'dsqdcl', 'dmpnpc', 'xvtbk', 'bnjq', 'qhps', 'xkthpt', 'gvpd', 'bsdjq', 'fgdn', 'kqpcn'}, {'shellfish', 'wheat', 'fish'}), ({'qdrcnt', 'nrl', 'xqlvq', 'dq', 'lbgl', 'vgssk', 'fjcrzgq', 'zkshp', 'pjkkm', 'jxdms', 'bfbcl', 'mzhp', 'mbfb', 'rzrb', 'fftkllp', 'ppphm', 'tsktk', 'fjqns', 'sfp', 'jncgc', 'tnrmchc', 'zbvflpl', 'rpjlrl', 'crgmxg', 'zqzmzl', 'xpdqxtrh', 'vbbxd', 'htnmftg', 'pkknz', 'njtvrpc', 'rtdhc', 'fchtgm', 'qdhfqx', 'jhddxv', 'hzkcvk', 'djqrsd', 'qhps', 'qxptn', 'xkthpt', 'lnhx', 'cqstff', 'cltx', 'lcktf', 'vqmdd', 'pttq', 'slzdx', 'cqtmst', 'kndt', 'hmhqq', 'xhnk', 'lqqbz', 'bsdjq', 'pnqdpt', 'vndmsf', 'znmhcfmc', 'qqtnt', 'lknk', 'lxjkr', 'jsbpht', 'xbbcn', 'nrzc', 'jxfz', 'cvkmvd', 'drmssh', 'kqpcn', 'grgjkz', 'cfn', 'ffc', 'pbjgn', 'spthcff', 'klqj', 'xxf', 'tsqpn', 'jdcc', 'pkvhv', 'ztjqx', 'qjvvcvz', 'kxsll', 'tfqsb'}, {'nuts', 'wheat', 'fish'}), ({'qdrcnt', 'nrl', 'jbjnx', 'kskjbx', 'nvmpqzd', 'dq', 'lbgl', 'klqj', 'vgssk', 'gtvk', 'pjkkm', 'kxjszsfm', 'hcqs', 'ppphm', 'dmx', 'cndz', 'fjqns', 'dsqdcl', 'jncgc', 'tnrmchc', 'kvlx', 'tfqsb', 'qltkhqt', 'rpjlrl', 'zqzmzl', 'qjvvcvz', 'pkvhv', 'gstsgf', 'qsddtb', 'vbbxd', 'kschtq', 'txjxng', 'xvtbk', 'htnmftg', 'qdhfqx', 'kqzdmd', 'lnhx', 'xnqfx', 'cltx', 'bcbsh', 'zkr', 'vqmdd', 'nhqz', 'pbqgcl', 'bsdjq', 'hmhqq', 'vndmsf', 'kndt', 'pnqdpt', 'rcqb', 'jrlvrx', 'crrh', 'grgjkz', 'cvkmvd', 'jxfz', 'drmssh', 'fgdn', 'zvsgzv', 'mntxnf', 'cfn', 'pbjgn', 'spthcff', 'vxltmm', 'hjkvk', 'fkxl', 'tsqpn', 'vvgz', 'ndn', 'nrzc', 'xskcmdk', 'ztjqx', 'gbzml', 'ptnpb', 'bbgjn', 'mdxq', 'sphfb'}, {'nuts', 'shellfish', 'dairy'}), ({'qdrcnt', 'nrl', 'llpfvs', 'pthkfzr', 'cxtgtz', 'jbjnx', 'kskjbx', 'dq', 'zmnpsx', 'qlmtgt', 'fjcrzgq', 'pjkkm', 'tzgkm', 'qjm', 'nhgmnc', 'hcqs', 'mbfb', 'rzrb', 'zbhf', 'ckrf', 'fjqns', 'sfp', 'tcgmz', 'jncgc', 'crgmxg', 'qsddtb', 'vbbxd', 'skjn', 'txjxng', 'xvtbk', 'ztmqrbvb', 'htnmftg', 'bnjq', 'njtvrpc', 'rtdhc', 'hxgbnc', 'qdhfqx', 'xhc', 'djqrsd', 'hzkcvk', 'xkthpt', 'dtbfb', 'bcfhrtlx', 'qxptn', 'tvbppb', 'cqstff', 'cltx', 'hllqx', 'srsl', 'dkjjpmt', 'nhqz', 'xmctlnjx', 'cqtmst', 'kndt', 'bsdjq', 'xhnk', 'qmst', 'lqqbz', 'pbqgcl', 'vjj', 'rlpkdv', 'rcqb', 'lknk', 'jsbpht', 'pnqdpt', 'rcl', 'xbbcn', 'jxfz', 'cvkmvd', 'drmssh', 'fmlc', 'pzvx', 'zvsgzv', 'ndn', 'ffc', 'klqj', 'spthcff', 'jfbds', 'pbjgn', 'tsqpn', 'nrzc', 'ztjqx', 'qjvvcvz', 'tfqsb'}, {'sesame', 'peanuts'}), ({'nrl', 'dmrfb', 'fr', 'cctgq', 'jbjnx', 'kskjbx', 'dtphdp', 'kxjszsfm', 'krhfmd', 'zzmvlnq', 'gzbs', 'zbqrfb', 'vgj', 'rzrb', 'vtxf', 'tsktk', 'ckrf', 'qltkhqt', 'cndz', 'sphfb', 'zqzmzl', 'hxgbnc', 'rtdhc', 'hsbgl', 'jhddxv', 'xhc', 'djqrsd', 'qhps', 'xkthpt', 'sbzllf', 'cltx', 'ddgd', 'dkjjpmt', 'gvpd', 'xmctlnjx', 'slzdx', 'cqtmst', 'kndt', 'vndmsf', 'rcqb', 'qqtnt', 'crxd', 'rcl', 'xbbcn', 'jxfz', 'grgjkz', 'mxvjf', 'pzvx', 'zvsgzv', 'ndn', 'fkxl', 'tsqpn', 'jngvsq', 'vvgz', 'pkvhv', 'xskcmdk', 'qjvvcvz', 'ptnpb', 'tfqsb'}, {'shellfish', 'eggs'}), ({'qdrcnt', 'nrl', 'nccmqg', 'vkcf', 'kskjbx', 'dq', 'zmnpsx', 'ccsm', 'jxdms', 'krhfmd', 'qjm', 'nhgmnc', 'vgj', 'vtxf', 'krg', 'kjflc', 'tcgmz', 'ckrf', 'jxbzxd', 'jncgc', 'tnrmchc', 'sphfb', 'zbvflpl', 'llghzs', 'crgmxg', 'zqzmzl', 'zvthr', 'xpdqxtrh', 'fccp', 'txjxng', 'xvtbk', 'ztmqrbvb', 'pkknz', 'hsbgl', 'jhddxv', 'dnxhx', 'bcfhrtlx', 'ktsnqg', 'xnqfx', 'cqstff', 'cltx', 'hllqx', 'bcbsh', 'qxplxtp', 'vqmdd', 'ddgd', 'pttq', 'zkr', 'pbqgcl', 'vndmsf', 'xhnk', 'lqqbz', 'pnqdpt', 'qqtnt', 'jrlvrx', 'lxjkr', 'sqr', 'jxfz', 'zvsgzv', 'ndn', 'ngqdpq', 'jfbds', 'spthcff', 'vxltmm', 'hjkvk', 'tsqpn', 'pkvhv', 'qjvvcvz', 'kxsll', 'mdxq', 'tfqsb'}, {'wheat', 'peanuts'}), ({'xqlvq', 'nrl', 'szqr', 'qdrcnt', 'cxtgtz', 'cctgq', 'jbjnx', 'kskjbx', 'ccsm', 'vkcf', 'vgssk', 'fjcrzgq', 'xggvd', 'tzgkm', 'rzl', 'kxjszsfm', 'qjm', 'mzhp', 'zvbpd', 'fftkllp', 'tsktk', 'dmx', 'ckrf', 'jxbzxd', 'sfp', 'tnrmchc', 'zbhf', 'cndz', 'dmpnpc', 'rpjlrl', 'zqzmzl', 'qsddtb', 'zvthr', 'xpdqxtrh', 'lhvcd', 'pkknz', 'bnjq', 'fchtgm', 'rtdhc', 'jhddxv', 'xhc', 'djqrsd', 'kqzdmd', 'qxptn', 'xkthpt', 'lnhx', 'kfzm', 'xnqfx', 'cqstff', 'cltx', 'hllqx', 'bcbsh', 'zkr', 'nhqz', 'hmhqq', 'qmst', 'lqqbz', 'rcqb', 'rlpkdv', 'znmhcfmc', 'sqr', 'jsbpht', 'lxjkr', 'crrh', 'rcl', 'grgjkz', 'kqpcn', 'fmlc', 'fkxl', 'mntxnf', 'ndn', 'klqj', 'pbjgn', 'vxltmm', 'spthcff', 'xxf', 'tsqpn', 'xskcmdk', 'qjvvcvz', 'ptnpb', 'mdxq', 'tfqsb'}, {'shellfish'}), ({'nrl', 'nccmqg', 'llpfvs', 'fr', 'vkcf', 'kskjbx', 'nvmpqzd', 'xggvd', 'bfbcl', 'krhfmd', 'mzhp', 'zbqrfb', 'mbfb', 'zkqmd', 'vgj', 'fftkllp', 'vtxf', 'jxbzxd', 'tsktk', 'tcgmz', 'dsqdcl', 'sphfb', 'jncgc', 'zbvflpl', 'llghzs', 'zqzmzl', 'xpdqxtrh', 'skjn', 'lhvcd', 'kschtq', 'xvtbk', 'bnjq', 'rtdhc', 'mfcf', 'qdhfqx', 'kqzdmd', 'djqrsd', 'qxptn', 'ktsnqg', 'sbzllf', 'tvbppb', 'cltx', 'zkr', 'dkjjpmt', 'cqtmst', 'pbqgcl', 'hmhqq', 'xhnk', 'pnqdpt', 'prbcss', 'rlpkdv', 'rcqb', 'jrlvrx', 'jsbpht', 'vjj', 'crrh', 'cvkmvd', 'fgdn', 'jdlvgvp', 'drmssh', 'mntxnf', 'pbjgn', 'jfbds', 'vxltmm', 'jdcc', 'tsqpn', 'krg', 'xskcmdk', 'gbzml', 'tfqsb'}, {'peanuts', 'fish'}), ({'nrl', 'kskjbx', 'fjcrzgq', 'dtphdp', 'rzl', 'nhgmnc', 'mbfb', 'gzbs', 'zvbpd', 'vgj', 'vtxf', 'hcqs', 'zbqrfb', 'dmx', 'ckrf', 'jncgc', 'zqzmzl', 'gstsgf', 'xpdqxtrh', 'chtpkf', 'htnmftg', 'gdffb', 'qdhfqx', 'jhddxv', 'dtbfb', 'bcfhrtlx', 'cqstff', 'bcbsh', 'lcktf', 'vqmdd', 'nhqz', 'cqtmst', 'xhnk', 'rcqb', 'rlpkdv', 'lknk', 'spthcff', 'jfbds', 'hjkvk', 'tsqpn', 'pkvhv', 'qjvvcvz', 'tfqsb'}, {'sesame', 'dairy'}), ({'llpfvs', 'cxtgtz', 'pthkfzr', 'cctgq', 'sdtsq', 'tzgkm', 'vgj', 'krg', 'ckrf', 'jncgc', 'rpjlrl', 'zqzmzl', 'qsddtb', 'chtpkf', 'htnmftg', 'rtdhc', 'qdhfqx', 'qhps', 'bcfhrtlx', 'xnqfx', 'cqstff', 'cltx', 'qxplxtp', 'zkr', 'dkjjpmt', 'nhqz', 'slzdx', 'cqtmst', 'hmhqq', 'xhnk', 'bsdjq', 'fzhhqp', 'rcqb', 'vjj', 'jrlvrx', 'rcl', 'cvkmvd', 'fgdn', 'cfn', 'pbjgn', 'spthcff', 'xxf', 'tsqpn', 'nrzc', 'qjvvcvz', 'ptnpb', 'tfqsb'}, {'shellfish', 'wheat', 'peanuts'}), ({'nrl', 'vkcf', 'kskjbx', 'nvmpqzd', 'qlmtgt', 'gtvk', 'fjcrzgq', 'jxdms', 'zkshp', 'tzgkm', 'dtphdp', 'qjm', 'hcqs', 'zvbpd', 'jxbzxd', 'fjqns', 'kjflc', 'dsqdcl', 'zqzmzl', 'zvthr', 'xpdqxtrh', 'skjn', 'htnmftg', 'mfcf', 'hsbgl', 'hzkcvk', 'dtbfb', 'xkthpt', 'qxptn', 'ktsnqg', 'kfzm', 'cqstff', 'cltx', 'qxplxtp', 'pttq', 'pbqgcl', 'xhnk', 'fzhhqp', 'pnqdpt', 'rcqb', 'jsbpht', 'crxd', 'crrh', 'xrlvd', 'grgjkz', 'jxfz', 'kqpcn', 'fgdn', 'pzvx', 'ndn', 'klqj', 'qjvvcvz', 'bbgjn', 'mdxq', 'tfqsb'}, {'nuts', 'eggs'}), ({'nccmqg', 'nrl', 'cxtgtz', 'jbjnx', 'kskjbx', 'dq', 'zmnpsx', 'pjkkm', 'jxdms', 'dtphdp', 'krhfmd', 'qjm', 'hcqs', 'vgj', 'tcgmz', 'ckrf', 'dsqdcl', 'jncgc', 'zbvflpl', 'zqzmzl', 'gstsgf', 'zvthr', 'vbbxd', 'kschtq', 'tzqf', 'htnmftg', 'njtvrpc', 'rtdhc', 'kqzdmd', 'hzkcvk', 'kfzm', 'cltx', 'hllqx', 'vqmdd', 'xmctlnjx', 'slzdx', 'hmhqq', 'qmst', 'xhnk', 'bsdjq', 'rcqb', 'znmhcfmc', 'sqr', 'lknk', 'xrlvd', 'mxvjf', 'xbbcn', 'drmssh', 'fmlc', 'pbjgn', 'ngqdpq', 'vxltmm', 'spthcff', 'xxf', 'tsqpn', 'xskcmdk', 'ztjqx', 'gbzml', 'ptnpb', 'tfqsb'}, {'sesame'})]\n",
            "a_to_i {'peanuts': {'tsqpn', 'cltx', 'tfqsb'}, 'sesame': {'xhnk', 'tsqpn'}, 'dairy': {'tsqpn', 'rcqb'}, 'nuts': {'zqzmzl', 'qjvvcvz'}, 'eggs': {'cltx'}, 'fish': {'nrl', 'xhnk', 'cltx', 'tfqsb'}, 'wheat': {'zqzmzl', 'xhnk'}, 'shellfish': {'cltx', 'tfqsb'}}\n",
            "with a {'nrl', 'zqzmzl', 'xhnk', 'cltx', 'tsqpn', 'tfqsb', 'qjvvcvz', 'rcqb'}\n",
            "w/o a  {'pthkfzr', 'cctgq', 'nvmpqzd', 'vgssk', 'mzhp', 'zbqrfb', 'mbfb', 'gzbs', 'zkqmd', 'zvbpd', 'jxbzxd', 'tsktk', 'tcgmz', 'tnrmchc', 'gstsgf', 'qsddtb', 'xpdqxtrh', 'vbbxd', 'kschtq', 'htnmftg', 'pkknz', 'hsbgl', 'djqrsd', 'dtbfb', 'lnhx', 'kfzm', 'ddgd', 'hllqx', 'pttq', 'xmctlnjx', 'nhqz', 'cqtmst', 'kndt', 'qmst', 'fzhhqp', 'pnqdpt', 'sqr', 'xbbcn', 'jxfz', 'cvkmvd', 'drmssh', 'pzvx', 'pbjgn', 'vxltmm', 'xxf', 'pkvhv', 'nrzc', 'krg', 'xqlvq', 'dmrfb', 'jbjnx', 'kskjbx', 'ccsm', 'qlmtgt', 'xggvd', 'kxjszsfm', 'qjm', 'rzrb', 'kjflc', 'fjqns', 'jncgc', 'zbvflpl', 'llghzs', 'fccp', 'tzqf', 'ztmqrbvb', 'njtvrpc', 'rtdhc', 'jhddxv', 'kqzdmd', 'dnxhx', 'kxhh', 'vndmsf', 'lqqbz', 'prbcss', 'qqtnt', 'lknk', 'lxjkr', 'jsbpht', 'jdlvgvp', 'fkxl', 'mntxnf', 'ffc', 'klqj', 'spthcff', 'jfbds', 'ndn', 'hjkvk', 'jdcc', 'vvgz', 'kxsll', 'sphfb', 'qdrcnt', 'llpfvs', 'fr', 'cxtgtz', 'vkcf', 'dq', 'zmnpsx', 'lbgl', 'zkshp', 'jxdms', 'bfbcl', 'pjkkm', 'krhfmd', 'rzl', 'zzmvlnq', 'hcqs', 'nhgmnc', 'vgj', 'vtxf', 'fftkllp', 'sfp', 'skjn', 'chtpkf', 'lhvcd', 'hxgbnc', 'gdffb', 'qdhfqx', 'hzkcvk', 'xhc', 'qxptn', 'bcfhrtlx', 'ktsnqg', 'tvbppb', 'cqstff', 'srsl', 'bcbsh', 'lcktf', 'dkjjpmt', 'qxplxtp', 'vqmdd', 'hmhqq', 'znmhcfmc', 'jrlvrx', 'xrlvd', 'rcl', 'mxvjf', 'fmlc', 'zvsgzv', 'cfn', 'flrxh', 'jngvsq', 'kvlx', 'xskcmdk', 'gbzml', 'bbgjn', 'mdxq', 'nccmqg', 'szqr', 'sdtsq', 'gtvk', 'fjcrzgq', 'tzgkm', 'dtphdp', 'ppphm', 'zbhf', 'cndz', 'dmx', 'dsqdcl', 'qltkhqt', 'ckrf', 'dmpnpc', 'rpjlrl', 'crgmxg', 'zvthr', 'txjxng', 'xvtbk', 'bnjq', 'fchtgm', 'mfcf', 'qhps', 'xkthpt', 'sbzllf', 'xnqfx', 'zkr', 'gvpd', 'slzdx', 'pbqgcl', 'bsdjq', 'vllhf', 'rlpkdv', 'vjj', 'crxd', 'crrh', 'grgjkz', 'fgdn', 'kqpcn', 'rkdrk', 'ngqdpq', 'ztjqx', 'ptnpb'}\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2659"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 150
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "id": "dwLnpOGcNNmP",
        "outputId": "fe699aac-e93b-4073-94d9-e7f3c703a9f2"
      },
      "source": [
        "# part 2\n",
        "a_to_i_clean = dict()\n",
        "a_to_i_tmp = dict(a_to_i)\n",
        "while a_to_i_tmp:\n",
        "  uniq = list(filter(lambda i: len(i[1]) == 1, a_to_i_tmp.items()))[0]\n",
        "  (alg, ing) = uniq\n",
        "  del a_to_i_tmp[alg]\n",
        "  for a in a_to_i_tmp:\n",
        "    a_to_i_tmp[a] = a_to_i_tmp[a].difference(ing)\n",
        "  a_to_i_clean[alg] = next(iter(ing))\n",
        "\n",
        "\",\".join(list(map(lambda t: t[1], sorted(a_to_i_clean.items()))))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'rcqb,cltx,nrl,qjvvcvz,tsqpn,xhnk,tfqsb,zqzmzl'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 151
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tugcpnmNYvtV"
      },
      "source": [
        "Day 22"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "_JQ0_tHcYxkW",
        "outputId": "2482d0ec-df33-40f0-ba40-4494785d6f16"
      },
      "source": [
        "# part 1\n",
        "import re\n",
        "from functools import reduce\n",
        "decks = []\n",
        "deck = []\n",
        "for line in [l.strip('\\n ') for l in open('input.txt')]:\n",
        "  if re.match('^\\d+$', line):\n",
        "    deck.append(int(line))\n",
        "  elif line.startswith('Player'):\n",
        "    decks.append(deck)\n",
        "  elif not line:\n",
        "    deck = []\n",
        "\n",
        "def round():\n",
        "  top = []\n",
        "  for i in range(0, len(decks)):\n",
        "    top.append(decks[i].pop(0))\n",
        "  tops = sorted(top, reverse=True)\n",
        "  winner = top.index(tops[0])\n",
        "  decks[winner].extend(tops)\n",
        "  return winner\n",
        "\n",
        "while min(list(map(len, decks))) > 0:\n",
        "  winner = round()\n",
        "\n",
        "reduce(lambda res, t: res + t[0] * t[1], zip(range(1, len(decks[winner])+1), decks[winner][::-1]), 0)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "33680"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 171
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "hlBLmQnubMN1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ac979098-5191-4b58-ad8f-ccc0a2f980a3"
      },
      "source": [
        "# part 2\n",
        "# !!! This can take a while, especially with all the print statements\n",
        "import re\n",
        "from functools import reduce\n",
        "from copy import deepcopy\n",
        "decks = []\n",
        "deck = []\n",
        "for line in [l.strip('\\n ') for l in open('input22.txt')]:\n",
        "  if re.match('^\\d+$', line):\n",
        "    deck.append(int(line))\n",
        "  elif line.startswith('Player'):\n",
        "    decks.append(deck)\n",
        "  elif not line:\n",
        "    deck = []\n",
        "\n",
        "#decks = [[9, 2, 6, 3, 1], [5, 8, 4, 7, 10]]\n",
        "#decks = [[43, 19], [2, 29, 14]]\n",
        "\n",
        "def game(decks, g, gc):\n",
        "  rounds = []\n",
        "  gc[0] += 1\n",
        "  r = 1\n",
        "\n",
        "  def round():\n",
        "    if decks in rounds:\n",
        "#      print('infinite game prevention rule applies in round', r, 'of game', g, 'for decks', decks)\n",
        "      return -1 # infinite game prevention rule, let player 1 win\n",
        "    rounds.append(deepcopy(decks))\n",
        "    top = []\n",
        "    subdecks = []\n",
        "    for i in range(0, len(decks)):\n",
        "      top.append(decks[i].pop(0))\n",
        "      if len(decks[i]) >= top[i]:\n",
        "        subdecks.append(decks[i][:top[i]])\n",
        "    # sub game?\n",
        "    if len(subdecks) == len(decks):\n",
        "#      print('sub game!')\n",
        "      winner = game(subdecks, gc[0], gc)\n",
        "#      print('back to game', g)\n",
        "      decks[winner].append(top[winner])\n",
        "      decks[winner].extend([t[0] for t in zip(top, range(0, len(top))) if t[1] != winner])\n",
        "    else:\n",
        "      tops = sorted(top, reverse=True)\n",
        "      winner = top.index(tops[0])\n",
        "      decks[winner].extend(tops)\n",
        "    return winner\n",
        "\n",
        "  winner = None\n",
        "#  print(\"game: \", g)\n",
        "  while min(list(map(len, decks))) > 0 and winner != -1:\n",
        "#    print('round:', r)\n",
        "#    print('decks:', decks)\n",
        "    winner = round()\n",
        "    w = max(0, winner)\n",
        "#    print('player', w + 1,'wins round', r, 'of game', g)\n",
        "    r += 1\n",
        "#  print('the winner of game', g, 'is player', w + 1)\n",
        "  return w\n",
        "\n",
        "gc = [1]\n",
        "winner = game(decks, gc[0], gc)\n",
        "print('OVERALL RESULT after', gc[0], 'games')\n",
        "print('Player', winner + 1, 'wins with deck:', decks[winner])\n",
        "reduce(lambda res, t: res + t[0] * t[1], zip(range(1, len(decks[winner])+1), decks[winner][::-1]), 0)\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "OVERALL RESULT after 25619 games\n",
            "Player 1 wins with deck: [50, 23, 36, 17, 19, 12, 49, 35, 33, 4, 44, 42, 39, 21, 37, 30, 28, 16, 14, 10, 1, 3, 41, 9, 32, 7, 38, 15, 22, 11, 48, 31, 29, 27, 40, 25, 46, 18, 13, 5, 26, 8, 47, 24, 45, 20, 43, 6, 34, 2]\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "33683"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 54
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "L2Hi7D47xdYL"
      },
      "source": [
        "Day 23\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 52
        },
        "id": "tZAMuBrExf5d",
        "outputId": "62dea51c-4aa2-49f5-ab96-0437b9bf76b4"
      },
      "source": [
        "#1, using a lot of dynamic list operations\n",
        "CUPS_CNT = 9\n",
        "INITIAL = '974618352'\n",
        "# INITIAL = '389125467' # example\n",
        "MOVES = 100\n",
        "MOVE_CNT = 3\n",
        "DELTA_LABEL = -1\n",
        "DELTA_POS = 1\n",
        "\n",
        "def add_to_pos(pos, delta):\n",
        "  return (pos + CUPS_CNT + delta) % CUPS_CNT\n",
        "\n",
        "def add_to_label(label, delta):\n",
        "  return (label + CUPS_CNT + delta - 1) % CUPS_CNT + 1\n",
        "\n",
        "def next(pos, n):\n",
        "  return [(pos + i) % CUPS_CNT for i in range(1, n + 1)]\n",
        "\n",
        "def remove(cups, curr_pos, n):\n",
        "  curr_label = cups[curr_pos]\n",
        "  posns = next(curr_pos, n)\n",
        "  removed_cups = [cups[p] for p in posns]\n",
        "  remaining_cups = [cups[p] for p in range(0, CUPS_CNT) if p not in posns]\n",
        "  new_curr_pos = remaining_cups.index(curr_label)\n",
        "  return (removed_cups, remaining_cups, new_curr_pos)\n",
        "\n",
        "def find_target_pos(cups, curr_pos, delta):\n",
        "  target_label = add_to_label(cups[curr_pos], delta)\n",
        "  while(target_label not in cups):\n",
        "    target_label = add_to_label(target_label, delta)\n",
        "  return cups.index(target_label)\n",
        "\n",
        "def insert(cups, curr_pos, target_pos, cups_to_insert):\n",
        "  return (cups[:target_pos+1] + cups_to_insert + cups[target_pos+1:], curr_pos if curr_pos <= target_pos else curr_pos + len(cups_to_insert))\n",
        "\n",
        "cups = list(map(int, list(INITIAL)))\n",
        "curr_pos = 0\n",
        "for i in range(0, MOVES):\n",
        "  (removed_cups, remaining_cups, tmp_curr_pos) = remove(cups, curr_pos, MOVE_CNT)\n",
        "  target_pos = find_target_pos(remaining_cups, tmp_curr_pos, DELTA_LABEL)\n",
        "  (cups, curr_pos) = insert(remaining_cups, tmp_curr_pos, target_pos, removed_cups)\n",
        "  curr_pos = add_to_pos(curr_pos, DELTA_POS)\n",
        "\n",
        "print(cups)\n",
        "x = cups.index(1)\n",
        "\"\".join(list(map(str, cups[x+1:] + cups[:x])))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[2, 6, 4, 1, 7, 5, 8, 9, 3]\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'75893264'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 2
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "eVEVUNRdH07k",
        "outputId": "05eb5c18-c41f-490b-e5b4-0c647aa6f825"
      },
      "source": [
        "# 2\n",
        "# Approach 1 above would not scale here, so just use a uni-directional (clockwise) linked list,\n",
        "# implemented using a dict: label -> next label, clockwise\n",
        "CUPS_CNT = 1000000   # 1: 9, 2: 1000000\n",
        "INITIAL = '974618352'\n",
        "# INITIAL = '389125467' # example\n",
        "MOVES = 10000000     # 1: 100, 2: 10000000\n",
        "MOVE_CNT = 3\n",
        "DELTA_LABEL = -1\n",
        "DELTA_POS = 1\n",
        "\n",
        "from time import time\n",
        "\n",
        "def add_to_label(label, delta):\n",
        "  return (label + CUPS_CNT + delta - 1) % CUPS_CNT + 1\n",
        "\n",
        "nx = dict()\n",
        "\n",
        "# init the linked list:\n",
        "# 1 the input\n",
        "init = list(map(int, list(INITIAL)))\n",
        "for i in range(0, len(init) - 1):\n",
        "  nx[init[i]] = init[i + 1]\n",
        "if CUPS_CNT > len(init):\n",
        "  # 2 if we have more cups than given in input (part 2), fill up the rest with incrementing labels, starting with one above max input label\n",
        "  m = max(init) + 1\n",
        "  nx[init[-1]] = m\n",
        "  for i in range(m, CUPS_CNT):\n",
        "    nx[i] = i + 1\n",
        "  nx[CUPS_CNT] = init[0] # close the circle\n",
        "else:\n",
        "  # otherwise just link the last label to the first to close the circle (part 1)\n",
        "  nx[init[-1]] = init[0]\n",
        "\n",
        "def collect_next(curr_label, n):\n",
        "# using a function rather than just doing c1 = nx[curr_label], c2 = nx[c1], etc., slows down execution:\n",
        "  res = [None] * n\n",
        "  res[0] = nx[curr_label]\n",
        "  for i in range(1, n):\n",
        "    res[i] = nx[res[i-1]]\n",
        "  return res\n",
        "# recursion with list concat is even slower:\n",
        "#  if n == 0:\n",
        "#    return []\n",
        "#  else:\n",
        "#    return [nx[curr_label]] + collect_next(nx[curr_label], n-1)\n",
        "\n",
        "curr_label = init[0]\n",
        "\n",
        "start = time()\n",
        "\n",
        "for m in range(0, MOVES):\n",
        "  moving = collect_next(curr_label, MOVE_CNT)          # get next labels following the current label\n",
        "  target_label = add_to_label(curr_label, DELTA_LABEL) # determine where to move them\n",
        "  while target_label in moving:\n",
        "    target_label = add_to_label(target_label, DELTA_LABEL)\n",
        "  nx[curr_label] = nx[moving[-1]]                      # bridge from current label to the label after the moved labels\n",
        "  nx[moving[-1]] = nx[target_label]                    # the last of the moved labels will be followed by the label after the target label\n",
        "  nx[target_label] = moving[0]                         # the target label will be followed by the first of the moved labels\n",
        "  # for i in range(0, DELTA_POS):  # use if DELTA_POS > 1, slows down execution\n",
        "  curr_label = nx[curr_label]\n",
        "\n",
        "print('time:', time() - start)\n",
        "\n",
        "# 1\n",
        "# \"\".join(list(map(str, collect_next(1, CUPS_CNT - 1))))\n",
        "\n",
        "# 2\n",
        "nx[1] * nx[nx[1]]"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "time: 24.698631525039673\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "38162588308"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 51
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BtdYwucSLPRi"
      },
      "source": [
        "Day 24"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "EfkJJWRGLQkm",
        "outputId": "004494af-e321-49e8-e247-af0636a76872"
      },
      "source": [
        "# Grid\n",
        "#     |2|3|4|  0: (0,0)   5: (-1,-1)\n",
        "#     \\/\\/\\/   1: (2,0)   6: (1,-1)\n",
        "#      |0|1|   2: (-1,1)  7: (3,-1)\n",
        "#     /\\/\\/\\   3: (1,1)\n",
        "#     |5|6|7|  4: (3,1)\n",
        "\n",
        "from numpy import array as a, asarray\n",
        "from functools import reduce\n",
        "\n",
        "# 1\n",
        "\n",
        "transitions = {\n",
        "    'e': a([2,0]),\n",
        "    'w': a([-2,0]),\n",
        "    'ne': a([1,1]),\n",
        "    'se': a([1,-1]),\n",
        "    'nw': a([-1,1]),\n",
        "    'sw': a([-1,-1])\n",
        "}\n",
        "\n",
        "grid = set()\n",
        "\n",
        "def pop(s):\n",
        "  return (s[0], s[1:])\n",
        "\n",
        "input = [l.strip('\\n ') for l in open('input24.txt')]\n",
        "# input = ['nwwswee']\n",
        "\n",
        "for line in input:\n",
        "  pos = a([0,0])\n",
        "  while line:\n",
        "    (t, line) = pop(line)\n",
        "    if t not in ('e', 'w'):\n",
        "      (t2, line) = pop(line)\n",
        "      t += t2\n",
        "    pos += transitions[t]\n",
        "    index = tuple(pos)\n",
        "  if index not in grid:\n",
        "    grid.add(index)\n",
        "  else:\n",
        "    grid.remove(index)\n",
        "\n",
        "print('part 1:', len(grid), 'black tiles')\n",
        "\n",
        "# 2\n",
        "nbcache = dict()\n",
        "\n",
        "def neighbors(pos):\n",
        "  if pos in nbcache:\n",
        "    return nbcache[pos]\n",
        "  pos_arr = asarray(pos)\n",
        "  nb = set((tuple(pos_arr + t) for t in transitions.values()))\n",
        "  nbcache[pos] = nb\n",
        "  return nb\n",
        "\n",
        "def count_adj_blacks(grid, pos):\n",
        "  return len(list(filter(lambda p: p in grid, neighbors(pos))))\n",
        "\n",
        "def iterate(grid):\n",
        "  posns_to_check = reduce(lambda a, b: a.union(b), map(lambda pos: neighbors(pos) | { pos }, grid))\n",
        "  new_grid = set()\n",
        "  for pos in posns_to_check:\n",
        "    blacks = count_adj_blacks(grid, pos)\n",
        "    if pos not in grid and blacks == 2 or pos in grid and blacks in (1, 2):\n",
        "      new_grid.add(pos)\n",
        "  return new_grid\n",
        "\n",
        "for d in range(1, 101):\n",
        "  grid = iterate(grid)\n",
        "  print('day', d, ':', len(grid))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "part 1: 375 black tiles\n",
            "day 1 : 217\n",
            "day 2 : 276\n",
            "day 3 : 278\n",
            "day 4 : 347\n",
            "day 5 : 346\n",
            "day 6 : 361\n",
            "day 7 : 382\n",
            "day 8 : 422\n",
            "day 9 : 405\n",
            "day 10 : 440\n",
            "day 11 : 484\n",
            "day 12 : 462\n",
            "day 13 : 517\n",
            "day 14 : 506\n",
            "day 15 : 533\n",
            "day 16 : 574\n",
            "day 17 : 595\n",
            "day 18 : 636\n",
            "day 19 : 640\n",
            "day 20 : 693\n",
            "day 21 : 682\n",
            "day 22 : 732\n",
            "day 23 : 747\n",
            "day 24 : 743\n",
            "day 25 : 776\n",
            "day 26 : 780\n",
            "day 27 : 913\n",
            "day 28 : 820\n",
            "day 29 : 867\n",
            "day 30 : 956\n",
            "day 31 : 964\n",
            "day 32 : 1010\n",
            "day 33 : 1062\n",
            "day 34 : 1047\n",
            "day 35 : 1060\n",
            "day 36 : 1113\n",
            "day 37 : 1100\n",
            "day 38 : 1187\n",
            "day 39 : 1267\n",
            "day 40 : 1244\n",
            "day 41 : 1263\n",
            "day 42 : 1394\n",
            "day 43 : 1317\n",
            "day 44 : 1398\n",
            "day 45 : 1406\n",
            "day 46 : 1465\n",
            "day 47 : 1453\n",
            "day 48 : 1485\n",
            "day 49 : 1484\n",
            "day 50 : 1705\n",
            "day 51 : 1571\n",
            "day 52 : 1594\n",
            "day 53 : 1789\n",
            "day 54 : 1676\n",
            "day 55 : 1731\n",
            "day 56 : 1843\n",
            "day 57 : 1840\n",
            "day 58 : 2013\n",
            "day 59 : 1910\n",
            "day 60 : 1920\n",
            "day 61 : 2094\n",
            "day 62 : 2108\n",
            "day 63 : 2013\n",
            "day 64 : 2127\n",
            "day 65 : 2183\n",
            "day 66 : 2383\n",
            "day 67 : 2282\n",
            "day 68 : 2287\n",
            "day 69 : 2385\n",
            "day 70 : 2412\n",
            "day 71 : 2499\n",
            "day 72 : 2493\n",
            "day 73 : 2672\n",
            "day 74 : 2550\n",
            "day 75 : 2633\n",
            "day 76 : 2612\n",
            "day 77 : 2825\n",
            "day 78 : 2800\n",
            "day 79 : 2934\n",
            "day 80 : 2953\n",
            "day 81 : 2902\n",
            "day 82 : 3036\n",
            "day 83 : 3031\n",
            "day 84 : 3092\n",
            "day 85 : 3199\n",
            "day 86 : 3235\n",
            "day 87 : 3269\n",
            "day 88 : 3337\n",
            "day 89 : 3471\n",
            "day 90 : 3603\n",
            "day 91 : 3483\n",
            "day 92 : 3644\n",
            "day 93 : 3576\n",
            "day 94 : 3671\n",
            "day 95 : 3743\n",
            "day 96 : 3842\n",
            "day 97 : 3790\n",
            "day 98 : 3963\n",
            "day 99 : 4100\n",
            "day 100 : 3937\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}