Advent of Code 2020 Dyalog APL.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Advent of Code 2020, Dyalog APL edition\n",
    "\n",
    "To see a correct render of this notebook, check it out on [nbviewer](https://nbviewer.jupyter.org/github/xpqz/AoCDyalog/blob/master/Advent%20of%20Code%202020%20Dyalog%20APL.ipynb).\n",
    "\n",
    "Annotated solutions in Dyalog APL. Why? A language that doesn't affect the way you think about programming is not worth knowing.\n",
    "\n",
    "Note that part of the charm of AoC is that every user (or at least groups of users) gets their own unique data set. Some of the solutions below exploit quirks in my particular data set, and so may conceivably not work for the general case."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">done\n",
       "</span>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→─────────────────────────────────────┐\n",
       "│Was ON -style=min -trains=tree -fns=on│\n",
       "└──────────────────────────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────┐\n",
       "│Was OFF│\n",
       "└───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⍝ Helper functions and common settings\n",
    "⎕FR ⎕PP ⎕IO←1287 34 0\n",
    "assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕signal 8 ⋄ shy←0}\n",
    "rg←{⍵.(1↓Lengths↑¨Offsets↓¨⊂Block)} ⍝ capture groups as vector\n",
    "'segs'⎕CY'dfns'\n",
    "nums←⍎¨∊∘⎕D⊆⊢\n",
    "\n",
    "⍝ Some visualisation help, please\n",
    "]box on -style=max -trains=tree -fns=on\n",
    "]rows on"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 1: Report Repair\n",
    "https://adventofcode.com/2020/day/1\n",
    "\n",
    "Outer product sum, find locations of 2020 and multiply. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────────────┐\n",
       "│73371 127642310│\n",
       "└~──────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢result←1 2{×/⍵[⊃⍸2020=∘.+⍣⍺⍨⍵]}¨⊂⍎⍕⊃⎕NGET'data/2020/day01.txt'1\n",
    "assert 73371 127642310≡result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 2: Password Philosophy\n",
    "https://adventofcode.com/2020/day/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "DAY02←⍎¨@1 2¨'- :'∘segs¨⊃⎕NGET'data/2020/day02.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────┐\n",
       "│528 497│\n",
       "└~──────┘\n",
       "</span>"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢result←+⌿↑{(b t l s)←⍵⋄((b∘≤∧t∘≥)+/l=s)(⊃(l=b⊃s)≠l=t⊃s)}¨DAY02\n",
    "assert 528 497≡result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, perhaps a bit messy. Here's the same idea, in long-hand:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Part1←{\n",
    "    (min max letter string)←⍵\n",
    "    count←+/letter=string\n",
    "    (min∘≤∧≤∘max) count\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Part2←{\n",
    "    (min max letter string)←⍵                ⍝ De-structure \n",
    "    ⊃(letter=min⊃string)≠(letter=max⊃string) ⍝ Pick the values, and XOR\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert 528=+/Part1¨DAY02\n",
    "assert 497=+/Part2¨DAY02  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another neat trick worth remembering is that the built-in ⎕CSV can do numeric conversion:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "b t l s←↓⍉⎕CSV('\\W+'⎕R','⊃⎕NGET'data/2020/day02.txt' 1)''4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's another version, jazzed up by ninja-master @ngn:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "528\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "497\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "528\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "497\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p q l s←↓⍉↑DAY02\n",
    "+/(p∘≤∧≤∘q)+/¨s=∊l\n",
    "+/≠⌿↑p q⊃¨¨⊂s=∊l\n",
    "\n",
    "⍝ Or as a matrix\n",
    "b←↑s=∊l\n",
    "+/(p∘≤∧≤∘q)+/b\n",
    "+/≠/(p,⍪q)⊃⍤0 1⍤1⊢b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 3: Toboggan Trajectory\n",
    "https://adventofcode.com/2020/day/3\n",
    "\n",
    "The first approach that comes to mind is a reduce over the path's steps which we can implement either as a tail-recursive function, or by pre-calculating the coordinate vector."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "DAY03←↑⊃⎕NGET'data/2020/day03.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Slope←{\n",
    "    (dy dx)←⍵\n",
    "    d←⍺\n",
    "    0 { ⍝ Tail-recursive accumulation\n",
    "        (y x)←⍵\n",
    "        y≥≢d:⍺\n",
    "        (⍺+'#'=d[y;(1⊃⍴d)|x])∇dy dx + y x\n",
    "    } 0 0\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────────────┐\n",
       "│68 203 78 77 40│\n",
       "└~──────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢result←DAY03∘Slope¨(1 1)(1 3)(1 5)(1 7)(2 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert 203=1⊃result ⍝ Part 1\n",
    "assert 3316272960=×/result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Considerably more idiomatically, we can simply create the coordinate vector representing the slope first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Slope2←{\n",
    "    coords←↓⍉↑(⍴⍺)|⍵×⊂⍳⌈(≢⍺)÷⊃⍵\n",
    "    +/'#'=⍺[coords]\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────────────┐\n",
       "│68 203 78 77 40│\n",
       "└~──────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢result←DAY03∘Slope2¨(1 1)(1 3)(1 5)(1 7)(2 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 4: Passport Processing\n",
    "https://adventofcode.com/2020/day/4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY04←⊃¨{,/¨(' :'∘segs¨⍵)⊆⍨×≢¨⍵} ⊃⎕NGET'data/2020/day04.txt'1\n",
    "eyr←(2020∘≤∧≤∘2030)⍎\n",
    "iyr←(2010∘≤∧≤∘2020)⍎\n",
    "byr←(1920∘≤∧≤∘2002)⍎\n",
    "ecl←'amb' 'blu' 'brn' 'gry' 'grn' 'hzl' 'oth'∊⍨⊂\n",
    "pid←≢'^\\d{9}$'⎕S''\n",
    "hcl←≢'^#[a-f0-9]{6}$'⎕S''\n",
    "cid←{1}\n",
    "hgt←≢'^(((59|6[0-9]|7[0-6])in)|((1[5-8][0-9]|19[0-3])cm))$'⎕S''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────┐\n",
       "│256 198│\n",
       "└~──────┘\n",
       "</span>"
      ]
     },
     "execution_count": 121,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "part1←'byr' 'iyr' 'eyr' 'hgt' 'hcl' 'ecl' 'pid'∘(∧/∊)¨pp←(0≠≢¨DAY04)/DAY04\n",
    "part2←{∧/{(⍎⍺)⍵}/(2÷⍨≢⍵)2⍴⍵}¨part1/pp\n",
    "⊢result←+/¨part1 part2\n",
    "assert 256 198≡result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 5: Binary Boarding\n",
    "https://adventofcode.com/2020/day/5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "888\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←⌈/seats←2⊥'BR'∊⍨⍉↑⊃⎕NGET'data/2020/day05.txt'1\n",
    "assert 888=part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 243,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "522\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 243,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part2←1+(⍸~2{⍵=⍺+1}/sorted)⊃sorted←(⍋⌷¨⊂)seats\n",
    "assert 522=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 6: Custom Customs\n",
    "https://adventofcode.com/2020/day/6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY06←{⍵⊆⍨×≢¨⍵}⊃⎕NGET'data/2020/day06.txt'1 ⍝ Groups separated by empty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "6416\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 123,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←≢∊∪/¨DAY06\n",
    "assert 6416=part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "3050\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 124,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part2←≢∊∩/¨DAY06\n",
    "assert 3050=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 7: Handy Haversacks\n",
    "https://adventofcode.com/2020/day/7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY07←⊃⎕NGET'data/2020/day07.txt'1\n",
    "bags←'^(\\w+)\\s(\\w+)'⎕S'&'⊢DAY07\n",
    "contained←(⊃,/)¨'(?:\\d+|no)\\s(\\w+\\s\\w+)'⎕S rg¨DAY07"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [],
   "source": [
    "no←0\n",
    "counts←(⍎¨∘⊃,/)¨'(\\d+|no)'⎕S rg¨DAY07\n",
    "cap←↓⍉↑(contained)(counts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Part1←{\n",
    "    ⍺←⍬\n",
    "    0=≢,⍵:¯1+≢⍺\n",
    "    item←⊃,⍵\n",
    "    idx←⍸∨/(⊂item)⍷↑contained\n",
    "    (⍺,⊂item)∇⍺~⍨bags[idx],1↓⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "185\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←Part1 ⊂'shiny gold'\n",
    "assert 185=part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "Part2←{⍵≡'other bags': 0 ⋄ +/{(b c)←⍵⋄c×1+Part2 b}¨↓⍉↑(bags⍳⊂⍵)⊃cap}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "89084\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part2←Part2 'shiny gold'\n",
    "assert 89084=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 8: Handheld Halting\n",
    "https://adventofcode.com/2020/day/8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY08←⊃⎕NGET'data/2020/day08.txt'1\n",
    "(op arg)←↓⍉↑' '(≠⊆⊢)¨DAY08\n",
    "init←{(c a)←⍺ ⍵⋄{⍵⊣⍵.(code args ip acc lines)←c a 0 0(0/⍨≢c)}⎕NS''}\n",
    "halted←{⍵.ip≥≢⍵.code}\n",
    "infloop←{2∊⍵.lines}\n",
    "tweak←{to←⍵⋄{(⊂to)@⍵⊢op}¨⍸(⊂⍺)≡⍤0⊢op}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "step←{\n",
    "    instr←⍵.ip⊃⍵.code\n",
    "    arg←⍵.ip⊃⍵.args\n",
    "    ⍵.lines[⍵.ip]+←1\n",
    "    infloop ⍵:⍵\n",
    "    'nop'≡instr:⍵⊣⍵.ip+←1\n",
    "    'acc'≡instr:⍵⊣⍵.(acc ip)+←arg 1\n",
    "    ⍵⊣⍵.ip+←arg\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "run←step⍣{(infloop ⍺)∨halted ⍺}⊢"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "1134\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result←run (op init ⍎¨arg)\n",
    "⊢part1←result.acc\n",
    "assert 1134=part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Part2←{\n",
    "    0=≢⍵:⍬\n",
    "    result←run (0⊃⍵)init ⍺\n",
    "    halted result:result\n",
    "    ⍺∇1↓⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "1205\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result←(⍎¨arg)∘Part2 ⊃,/tweak⌿2 2⍴('jmp')('nop')('nop')('jmp')\n",
    "⊢part2←result.acc\n",
    "assert 1205=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 9: Encoding Error\n",
    "https://adventofcode.com/2020/day/9\n",
    "\n",
    "The running sums in part 1 change very little, so can be cached. In retrospect, the performance gain was probably negligible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 238,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY09←⍎⍕⊃⎕NGET'data/2020/day09.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 239,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day09←{\n",
    "    (i s)←⍵\n",
    "    r←(i-24)+⍳25                  ⍝ Considered range\n",
    "    d←DAY09[r]+(¯1↑r)⊃DAY09       ⍝ Changed vals\n",
    "    n←1⌽1⊖s ⋄ n[;24]←d ⋄ n[24;]←d ⍝ Update the sums cache. Also: new←25 25↑1 1↓cache\n",
    "    (i+1) (n)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 240,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">          \n",
       "1639024365\n",
       "          \n",
       "</span>"
      ]
     },
     "execution_count": 240,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(i _)←Day09⍣{(i s)←⍺ ⋄ ~s∊⍨i⊃DAY09} 25 (∘.+⍨25↑DAY09)\n",
    "⊢part1←i⊃DAY09\n",
    "assert 1639024365=part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 241,
   "metadata": {},
   "outputs": [],
   "source": [
    "win←part1{⍺∊⍵+/DAY09:⍵⋄⍵+1}⍣≡⊢2\n",
    "i←part1⍳⍨win+/DAY09"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 242,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">         \n",
       "219202240\n",
       "         \n",
       "</span>"
      ]
     },
     "execution_count": 242,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part2←(⌈/+⌊/)DAY09[i+⍳win]\n",
    "assert 219202240=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We found the stretch by trying increasing lengths of windowed reduction. Another variety is to use scan, noting that the sum of a stretch is the sum to the end of the stretch minus the sum to the beginning of the stretch:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">         \n",
       "219202240\n",
       "         \n",
       "</span>"
      ]
     },
     "execution_count": 181,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(end start)←⊃⍸part1=∘.-⍨+\\DAY09\n",
    "(⌈/+⌊/)(start+1)↓(end+1)↑DAY09"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 10: Adapter Array\n",
    "https://adventofcode.com/2020/day/10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "DAY10←(⍋⌷¨⊂)0,d,3+⌈/d←⍎⍕⊃⎕NGET'data/2020/day10.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "2059\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←×⌿+/↑1 3=⊂-2-/DAY10\n",
    "assert 2059=part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From a solution by @ngn, which roughly goes like so:\n",
    "\n",
    "```python\n",
    "with open('data/2020/day10.txt') as f:\n",
    "    DAY10 = sorted(list(map(int, f)))                 # (⍋⌷¨⊂)⍎⍕⊃⎕NGET'data/2020/day10.txt'1\n",
    "\n",
    "print(reduce(                                         #             /\n",
    "    lambda acc, w:[*acc[1:], w*sum(acc)],             # {1↓⍵,⍺×+/⍵}\n",
    "    [int(i in DAY10) for i in range(1, DAY10[-1]+1)], #              (⌽DAY10∊⍨1+⍳⊃⌽DAY10)\n",
    "    [0, 0, 1]                                         #                                  ,⊂0 0 1\n",
    ")[2])                                                 # 2⊃⊃\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">              \n",
       "86812553324672\n",
       "              \n",
       "</span>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part2←2⊃⊃{1↓⍵,⍺×+/⍵}/(⌽DAY10∊⍨1+⍳⊃⌽DAY10),⊂0 0 1\n",
    "assert 86812553324672=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 11: Seating System\n",
    "https://adventofcode.com/2020/day/11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 266,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY11←'L'=↑⊃⎕NGET'data/2020/day11.txt'1 ⍝ seats = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Apply the rules: \n",
    "\n",
    "- if seat is empty, and no occupied seats → seat filled\n",
    "- if seat is occupied, and 4 or more occupied neighbours → seat vacated \n",
    "- else: state unchanged"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 267,
   "metadata": {},
   "outputs": [],
   "source": [
    "Apply←{⍺=0:0⋄(1=⍺)∧0=2⊃⍵:2⋄(2=⍺)∧5≤2⊃⍵:1⋄⍺}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 268,
   "metadata": {},
   "outputs": [],
   "source": [
    "T←{⍵[1;1] Apply +/¨0 1 2=⊂∊⍵} ⍝ State transition, part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 269,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "2344\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 269,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←+/2=∊⊢∘T⌺3 3⍣≡DAY11\n",
    "assert 2344=part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we're no longer considering the direct neighbours, but the number of seats visible along the eight directions of line of sight."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "LoS←{\n",
    "    (m pos)←⍺ ⍵\n",
    "    max←¯1+≢m\n",
    "    seat←{b←0∊(0∘≤∧≤∘max)⍺⋄b:1⋄0≠m[⊂⍺]}\n",
    "    ((⊢≡0⌈max⌊⊢)¨coords)/coords←{⍵+⍣seat pos}¨1-1↓4⌽,⍳3 3\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [],
   "source": [
    "T2←{⍺[⊂⍵] Apply +/¨0 1 2=⊂⍺[⍺ LoS ⍵]} ⍝ State transition, part 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we're no longer operating in blocks we can't use stencil (⌺) this time. Although all the example data are square, the competition data isn't:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→────┐\n",
       "│93 97│\n",
       "└~────┘\n",
       "</span>"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⍴DAY11"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The T2 dfn above assumes that the data are square when testing for bounds. We can solve this by simply padding out the data a bit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "2076\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part2←+/2=∊{(⍴⍵)⍴⍵∘T2¨,⍳⍴⍵}⍣≡(2/⌈/⍴DAY11)↑DAY11 ⍝ Takes a few seconds...\n",
    "assert 2076=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This one from @ngn takes a radically different and _much_ faster approach by not using stencil, and using a ravel of the source data. When you flatten (`,⍵`) a matrix m with shape `⍴m` its set of coordinates changes from `⍳⍴m` to `⍳×/⍴m`. They become simply the indices of a vector. The mapping between the two can be done with `k←(⍴m)⊥i j` and its inverse `i j←(⍴m)⊤k` where `i j` are a pair of indices in `m`, and `k` is an index in `,m`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 272,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "2344\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 272,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "2076\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 272,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a←↑⊃⎕NGET'data/2020/day11.txt'1\n",
    "\n",
    "M←×/n←⍴a\n",
    "a←'.',⍨,a\n",
    "b←a≠'.'\n",
    "c←a='#'\n",
    "d←1-3 3⊤4~⍨⍳9\n",
    "\n",
    "f←{x←⍺⋄y←⍵⋄+/{b×(0=s+⍵)∨⍵×x>s←+⌿⍵[y]}⍣≡c}\n",
    "\n",
    "4 f M,⍨(M×~u)+(n⊥h)×u←⌊⌿(¯1↓b)×⍤1⊢u←(0∘≤∧<[0]∘n)h←d∘.+⍤1⊢n⊤⍳M ⍝ Part 1\n",
    "\n",
    "5 f M,⍨,[⍳2]{(u@v,[¯.5]v@u)⍴⍨M⊣u v←∊¨1 ¯1↓¨¨⊂⌷∘B∘⊂¨⊢∘⊂⌸⍵}⍤1(+⌿⍪-⌿⍪⊢)n⊤B←⍸b ⍝ Part 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 12: Rain Risk\n",
    "https://adventofcode.com/2020/day/12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY12←{↓⍉↑(1↑¨⍵)(⍎⍕1↓¨⍵)}⊃⎕NGET'data/2020/day12.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [],
   "source": [
    "R←{(2↑⍵),⊂(⍺÷90)⊖2⊃⍵} ⋄ L←{⍵R⍨-⍺}\n",
    "F←{dv←⍺×(⊃2⊃⍵)⊃(0 1)(1 0)(0 ¯1)(¯1 0)⋄(dv+2↑⍵),2⌷⍵}\n",
    "N←{((2↑⍵)-⍺ 0),2⌷⍵} ⋄ S←{⍵N⍨-⍺}\n",
    "E←{((2↑⍵)+0 ⍺),2⌷⍵} ⋄ W←{⍵E⍨-⍺}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "2879\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 155,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←+/|2↑⊃{(1⊃⍺)(⍎0⊃⍺)⍵}/(⌽DAY12),⊂(0,0,⊂⍳4)\n",
    "assert 2879=part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2 introduces a waypoint, which is relative to the ship's location. The NESW functions move the waypoint location (start value: ⊂1 10). Our accumulator now needs to also keep track of the location of the waypoint:\n",
    "\n",
    "    wpy, wpx, sy, sx\n",
    "    \n",
    "We no longer need a heading vector."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The compass functions remain largely the same:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {},
   "outputs": [],
   "source": [
    "N←{((2↑⍵)-⍺ 0),¯2↑⍵} ⋄ S←{⍵N⍨-⍺}\n",
    "E←{((2↑⍵)+0 ⍺),¯2↑⍵} ⋄ W←{⍵E⍨-⍺}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Forward (F) function adds arg×wp to the ship's position."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [],
   "source": [
    "F←{d←⍺×2↑⍵ ⋄ (2↑⍵),d+¯2↑⍵}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The rotation functions rotate the waypoint relative to the ship -- this corresponds to reflections."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [],
   "source": [
    "R←{90=⍺:(⊖¯1 1×2↑⍵),¯2↑⍵⋄180=⍺:(¯1 ¯1×2↑⍵),¯2↑⍵⋄(⊖1 ¯1×2↑⍵),¯2↑⍵}\n",
    "L←{(360-⍺) R ⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">      \n",
       "178986\n",
       "      \n",
       "</span>"
      ]
     },
     "execution_count": 176,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part2←+/|¯2↑⊃{(1⊃⍺)(⍎0⊃⍺)⍵}/(⌽DAY12),⊂(¯1 10 0 0)\n",
    "assert 178986=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 13: Shuttle Search\n",
    "https://adventofcode.com/2020/day/13\n",
    "\n",
    "[Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) taken from APL Cart https://aplcart.info/?q=chinese#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 262,
   "metadata": {},
   "outputs": [],
   "source": [
    "(ts tt)←⊃⎕NGET'data/2020/day13.txt'1\n",
    "time←⍎ts\n",
    "x←0\n",
    "buses←⍎','⎕R' '⊢tt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 263,
   "metadata": {},
   "outputs": [],
   "source": [
    "first←⊃⍸⍉↑0=buses|⊂time+⍳20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 264,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "410\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 264,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←(⊃first)×buses⊃⍨1⊃first\n",
    "assert 410=part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 256,
   "metadata": {},
   "outputs": [],
   "source": [
    "CRT←{m|⍵+.×⍺(⊣×⊢|∘⊃{0=⍵:1 0 ⋄ (⍵∇⍵|⍺)+.×0 1,⍪1,-⌊⍺÷⍵})¨⍨⍺÷⍨m←×/⍺}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 265,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">               \n",
       "600691418730595\n",
       "               \n",
       "</span>"
      ]
     },
     "execution_count": 265,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "i←buses⍳buses~0\n",
    "buses←buses~0\n",
    "\n",
    "⊢part2←¯1+buses CRT buses-i-1\n",
    "assert 600691418730595=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 14: Docking Data\n",
    "https://adventofcode.com/2020/day/14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 273,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY14←{('10X'=⊂7↓0⊃⍵)({⍎⍕'\\d+'⎕S'&'⊢⍵}¨1↓⍵)}¨({'mask'≡4↑⍵}¨d)⊂d←⊃⎕NGET'data/2020/day14.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 224,
   "metadata": {},
   "outputs": [],
   "source": [
    "mem←65436/0\n",
    "_←{(0⊃⍵)∘{mem[0⊃⍵]←2⊥(((36⍴2)⊤1⊃⍵)∨0⊃⍺)∧~1⊃⍺⋄⍬}¨1⊃⍵}¨DAY14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 225,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">              \n",
       "13496669152158\n",
       "              \n",
       "</span>"
      ]
     },
     "execution_count": 225,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←+/mem\n",
    "assert 13496669152158=part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, we apply the masks to the address, rather than the value. This means we can't pre-allocate the memory, as an addressable space of 36 bits is too large."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 274,
   "metadata": {},
   "outputs": [],
   "source": [
    "mem←⍬\n",
    "val←⍬"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 275,
   "metadata": {},
   "outputs": [],
   "source": [
    "SetMem←{i←mem⍳⍵⋄i<≢mem:⍬⊣val[i]←⍺⋄mem,←⍵⋄val,←⍺⋄⍬}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 276,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Addr←{\n",
    "    b←((36⍴2)⊤⊃⍵)∨⊃⍺              ⍝ Address in binary, with set-bit mask applied\n",
    "    bits←⍉(x⍴2)⊤⍳2*x←+/flb←2⊃⍺\n",
    "    all←(≢bits)(≢b)⍴b\n",
    "    all[;⍸flb]←bits               ⍝ 'all' now contains all expanded floating bits\n",
    "    _←(1⊃⍵)∘SetMem¨2⊥¨↓all\n",
    "    ⍬\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 277,
   "metadata": {},
   "outputs": [],
   "source": [
    "_←{(0⊃⍵)∘Addr¨1⊃⍵}¨DAY14          ⍝ Around 30 seconds..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 278,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">             \n",
       "3278997609887\n",
       "             \n",
       "</span>"
      ]
     },
     "execution_count": 278,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part2←+/val\n",
    "assert 3278997609887=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 15: Rambunctious Recitation\n",
    "https://adventofcode.com/2020/day/15\n",
    "\n",
    "This is the [Van Eck](https://www.youtube.com/watch?v=etMJxB-igrc) sequence.\n",
    "\n",
    "Not playing to APL strengths here; part 2 takes around 70s on my machine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 315,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY15←18 8 0 5 4 1 20\n",
    "spoken←⊃¯1↑DAY15\n",
    "next←1+≢DAY15\n",
    "cache←1500⌶¯1↓DAY15\n",
    "vals←1+⍳¯1+≢DAY15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 316,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "day15←{\n",
    "    (n i)←⍵\n",
    "    ~n∊cache: 0,i+1⊣vals,←i-1⊣cache,←n\n",
    "    d←¯1+i-vals[cache⍳n]\n",
    "    vals[cache⍳n]←i-1\n",
    "    d,i+1\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 317,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "253\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 317,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←⊃day15⍣(2020-1+≢cache)⊢spoken next\n",
    "assert 253=part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 318,
   "metadata": {},
   "outputs": [],
   "source": [
    "cache←1500⌶¯1↓DAY15\n",
    "vals←1+⍳¯1+≢DAY15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 319,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "13710\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 319,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part2←⊃day15⍣(3e7-1+≢cache)⊢spoken next ⍝ ~1m10s\n",
    "assert 13710=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 16: Ticket Translation\n",
    "https://adventofcode.com/2020/day/16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY16←{⍵⊆⍨×≢¨⍵}⊃⎕NGET'data/2020/day16.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "(type first second)←↓⍉↑(⊃,/)¨'^([^:]+):\\s([^\\s]+)\\sor\\s(.+)$'⎕S rg¨0⊃DAY16\n",
    "(first second)←⍎¨¨' '@(=∘'-')¨¨first second\n",
    "ticket←⊃⍎¨1↓1⊃DAY16\n",
    "valid←∪∊{⍺+⍳1+⍵-⍺}/↑first,second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "29019\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←+/invalid←(~(∊near)∊valid)/∊near←⍎¨1↓2⊃DAY16\n",
    "assert 29019=part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2: match the fields. With 20 fields and ~200 valid tickets, it's too much to search. Instead, we look to resolve the rules by checking which fields they are valid for, and substituting. First we must exclude any tickets known to be invalid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "tickets←(~{∨/⍵∊invalid}¨near)/near"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "resolve←{ ⍝ Find row in rulemap which have single 1. Zero corresp col in others\n",
    "    ⍺←⍬    \n",
    "    (≢⍺)=≢⍵:⊢/↑⍸⍵\n",
    "    fld←⍵\n",
    "    row←⊃⍺~⍨⍸1=+/fld ⍝ r is first unseen row with single 1\n",
    "    col←⊃⍸row⌷fld\n",
    "    fld[;col]←0\n",
    "    fld[row;col]←1\n",
    "    fld∇⍨⍺,row\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First we check every rule against every field in every ticket to see which rules can match each field. The rules are basically just the expanded ranges of integers, concatenated together."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "expand←{⍺+⍳1+⍵-⍺}\n",
    "rules←(⊃,/)¨↓⍉↑(expand/↑first)(expand/↑second)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "order←resolve ∧⌿↑(↑tickets)∘.∊rules  ⍝ Apply the rules by outer prod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">            \n",
       "517827547723\n",
       "            \n",
       "</span>"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part2←×/ticket[⍸{'dep'≡3↑⍵}¨type[order]]\n",
    "assert 517827547723=part2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────────────────────────────────────┐\n",
       "↓1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 0│\n",
       "│1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0│\n",
       "│0 0 0 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 0│\n",
       "│1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0│\n",
       "│1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0│\n",
       "│0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0│\n",
       "│0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0│\n",
       "│0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 0│\n",
       "│1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1│\n",
       "│0 1 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 0 0│\n",
       "│0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0│\n",
       "│1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 0 0│\n",
       "│1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1│\n",
       "│0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 0 0│\n",
       "│0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0│\n",
       "│0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0│\n",
       "│0 0 0 0 0 0 1 0 1 0 1 0 1 1 1 0 1 1 0 0│\n",
       "│0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0│\n",
       "│0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0│\n",
       "│0 0 0 1 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0│\n",
       "└~──────────────────────────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "∧⌿↑(↑tickets)∘.∊rules"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 17: Conway Cubes\n",
    "https://adventofcode.com/2020/day/17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 249,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY17←'#'=↑⊃⎕NGET'data/2020/day17.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 250,
   "metadata": {},
   "outputs": [],
   "source": [
    "Pad←{⍵@(1+⍳⍴⍵)⊢0⍴⍨2+⍴⍵} ⍝ https://aplcart.info/?q=surround%20array#"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 254,
   "metadata": {},
   "outputs": [],
   "source": [
    "final←({≢⍸⍵}⌺3 3 3∊¨3+0,¨⊢)⍣6⊢Pad⍣6⊢(↑,∘⊂)DAY17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 255,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "375\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 255,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←+/∊final\n",
    "assert 375=part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 256,
   "metadata": {},
   "outputs": [],
   "source": [
    "final←({≢⍸⍵}⌺3 3 3 3∊¨3+0,¨⊢)⍣6⊢Pad⍣6⊢(↑,∘⊂)⍣2⊢DAY17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 257,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "2192\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 257,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part2←+/∊final\n",
    "assert 2192=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 18: Operation Order\n",
    "https://adventofcode.com/2020/day/18\n",
    "\n",
    "For part 1, the evaluation rules are those of APL, but R-L instead of L-R. So we flip each expression, mirror brackets and change * to × and evaluate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">             \n",
       "7293529867931\n",
       "             \n",
       "</span>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DAY18←⊃⎕NGET'data/2020/day18.txt'1\n",
    "p1←{c←'()*'=⊂r←⊖⍵⋄_←{r[⍸⍵⊃c]←⍵⊃')(×'}¨⍳3⋄⍎r}\n",
    "⊢part1←+/p1¨DAY18\n",
    "assert 7293529867931=part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, now addition has higher precedence than multiplication. We can approach this in a number of ways. One is to bracket the expression fully, according to the new rules, and then have APL evaluate it for us. For example, given\n",
    "\n",
    "    5+(8×3+9+3×4×3)\n",
    "    \n",
    "we need to transform that to:\n",
    "\n",
    "    5+(8×(3+9+3)×4×3)\n",
    "\n",
    "We can solve this using some filthy regexing:\n",
    "\n",
    "- Repeat each existing paranthesis: \n",
    "    \n",
    "    `5+((8×((3+9+3))×4×3)) → '\\(' '\\)'⎕R'&&' '&&'⊢`\n",
    "    \n",
    "    \n",
    "- Surround each digit with a pair of parentheses.\n",
    "\n",
    "    `(5)+(((8)×(((3)+(9)+(3)))×(4)×(3))) → '\\d'⎕R'(&)'⊢`\n",
    "    \n",
    "    \n",
    "- Remove the internal brackets in plus-groups \n",
    "\n",
    "    `(5+((8)×(((3+9+3)))×(4)×(3))) → '\\)\\+\\('⎕R'+'⊢`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Part2←{\n",
    "    string←'×'@(=∘'*')⊢⍵~' '           ⍝ Remove spaces, and change * to ×\n",
    "    string←'\\(' '\\)'⎕R'&&' '&&'⊢string ⍝ Double up parentheses\n",
    "    string←'\\d'⎕R'(&)'⊢string          ⍝ Surround digits with parentheses\n",
    "    string←'\\)\\+\\('⎕R'+'⊢string        ⍝ Remove internal brackets in +-groups\n",
    "    ⍎string                            ⍝ Eval\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">              \n",
       "60807587180737\n",
       "              \n",
       "</span>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part2←+/Part2¨DAY18\n",
    "assert 60807587180737=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 19: Monster Messages\n",
    "https://adventofcode.com/2020/day/19\n",
    "\n",
    "Regex the regexes. A set of regular expressions. First resolve rule 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY19←{⍵⊆⍨×≢¨⍵}⊃⎕NGET'data/2020/day19.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "data←(⊃,/)¨'^(\\d+):\\s(.+)$'⎕S rg¨0⊃DAY19\n",
    "rules←('\"'⎕R''¨⊃¨1↓¨data)[⍋⍎¨⊣/↑data]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "subs←{ ⍝ strings←⍺\n",
    "    (from to)←⍵\n",
    "    patt←{'\\s+'⎕R''⊢'\\b',⍕⍵,'\\b'}¨from\n",
    "    repl←{'(?:',⍵,')'}¨to  ⍝ Non-capturing brackets.\n",
    "    ⍺ {0=≢⍵:⍺⋄((patt⊃⍨⊃⍵)⎕R(repl⊃⍨⊃⍵)⊢⍺)∇1↓⍵} ⍳≢patt\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "resolve←{ ⍝ rules←⍵\n",
    "    nodr←SEEN~⍨⍸{~∨/⎕D∊⍵}¨⍵ ⍝ indices of no-digit rules\n",
    "    SEEN,←nodr\n",
    "    ⍵ subs (nodr)(⍵[nodr])  ⍝ substitute everywhere\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "SEEN ← ⍬"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [],
   "source": [
    "rr←resolve⍣{~∨/⎕D∊0⊃⍺} rules    ⍝ Resolve until rule 0 has no digits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [],
   "source": [
    "patt←'\\(\\?:([ab ]+)\\)'⎕R'\\1'⍣2⊢0⊃rr ⍝ Remove some unneeded brackets\n",
    "patt←'\\s'⎕R''⊢patt                  ⍝ Kill spaces\n",
    "patt←'^',patt,'$'                   ⍝ Anchors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "230\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←+/{0≠≢⍵}¨patt⎕S'&'¨1⊃DAY19\n",
    "assert 230=part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suddenly, the earth moves, and two rules become recursive!\n",
    "\n",
    "Rules 8 and 11 which used to look like:\n",
    "\n",
    "    8:  42\n",
    "    11: 42 31\n",
    "\n",
    "instead now look like \t\n",
    "\n",
    "    8:  42 | 42 8\n",
    "    11: 42 31 | 42 11 31\n",
    "    \n",
    "We can do a little bit of manual rewriting here. Looking at 8, it essentially matches one or more 42, so that can be replaced by \n",
    "\n",
    "    8: 42+\n",
    "    \n",
    "Rule number 11 matches a sequence of 42, followed by the same number of 31, so that can become something like\n",
    "\n",
    "    11: 42{n} 31{n}\n",
    "\n",
    "\n",
    "These two rules contribute only to rule zero:\n",
    "\n",
    "    0: 8 11\n",
    "    \n",
    "If we expand that we get \n",
    "\n",
    "    0: 42+ 42{n} 31{n}\n",
    "    0: 42{n+1,} 31{n}\n",
    "    \n",
    "..but that still gives us a free parameter. We could guess what the max might be and generate a long list, but we can instead try a slightly broader match: \n",
    "\n",
    "    0: ((42)+)((31+))\n",
    "    \n",
    "under the provision that we check that the first pattern matches more than the second group. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Part2←{ \n",
    "    ⍝ Check that the first group matched more times than the second.\n",
    "    ⍝ This is technically still too broad -- should be strictly n+1.\n",
    "    match←⊃⍺⎕S rg⊣⍵\n",
    "    0=≢match:0\n",
    "    (m1 m2 m3 m4)←≢¨match\n",
    "    (m1÷m2)>m3÷m4\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "341\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "patt←'^((',(42⊃rr), ')+)((', (31⊃rr), ')+)$'\n",
    "patt←'\\s'⎕R''⊢patt\n",
    "⊢part2←+/patt∘Part2¨1⊃DAY19\n",
    "assert 341=part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 20: Jurassic Jigsaw\n",
    "https://adventofcode.com/2020/day/20\n",
    "\n",
    "Part 1 can be done without solving the whole board by looking at the edge ids -- the corner pieces have two edges that don't match any other tiles. However, for part 2, we'd still need the full solution, although knowing the corners, the BFS would have a smaller search space. But the full solution is curiously fast in APL without any such cleverness.\n",
    "\n",
    "Python solution [here](https://gist.github.com/xpqz/23523efeca6c256761367d6131e26262). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 262,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY20←{⍵⊆⍨×≢¨⍵}⊃⎕NGET'data/2020/day20.txt'1\n",
    "TILEIDS←⍎¨⊃,/'(\\d+)'⎕S rg ⊃,/{0⊃⍵}¨DAY20\n",
    "DAY20←↑¨1∘↓¨DAY20\n",
    "tr←¯1 ¯1∘↓1 1∘↓ ⍝ trim edges of matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 263,
   "metadata": {},
   "outputs": [],
   "source": [
    "symm←{(⍵)(⍉∘⊖⍵)(⌽∘⊖⍵)(⍉∘⌽⍵)(⊖⍵)(⍉⍵)(⌽⍵)(⍉∘⌽∘⊖⍵)}\n",
    "edges←{t←⍉⍵⋄(2⊥'#'=0⌷⍵),(2⊥'#'=⊃↓¯1↑t),(2⊥'#'=⊃↓¯1↑⍵),(2⊥'#'=0⌷t)} ⍝ NESW\n",
    "gen←{e←edges¨s←symm ⍵⋄(tr¨s)e} ⍝ Build all symmetries, edges and trim."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 264,
   "metadata": {},
   "outputs": [],
   "source": [
    "all←↑gen¨DAY20 \n",
    "TILES←⊃,/⊣/all\n",
    "EDGEIDS←⍉↑⊃,/⊢/all\n",
    "SIZE←12 12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 265,
   "metadata": {},
   "outputs": [],
   "source": [
    "state←{⍵⊣⍵.(next used tiles found)←(0 0) (,⍬) (SIZE⍴¯1) 0}⎕NS''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 266,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "neigh←{\n",
    "    next←SIZE⊤1+cur←SIZE⊥⍵.next ⍝ Map 2D→1D coordinates, add 1, map back to 2D\n",
    "    tiles←,⍵.tiles ⋄ used←⍵.used\n",
    "    \n",
    "    genStates←{ ⍝ Generate valid new states\n",
    "        0=≢⍵:⍺\n",
    "        m←0⊃⍵\n",
    "        fam←used~⍨⌊m÷8\n",
    "        ⍬≡fam:⍺ ∇ 1↓⍵\n",
    "        state←{⍵⊣⍵.(next used tiles found)←next(used,⊃fam)(SIZE⍴m@cur⊢tiles)(0 0≡next)}⎕NS''\n",
    "        (⍺,state)∇ 1↓⍵\n",
    "    }\n",
    "\n",
    "    NW←{ ⍝ Return N and W edge ids\n",
    "        n←{0<0⊃⍵.next:⍵.tiles[⊂¯1 0+⍵.next]⊃0⌷EDGEIDS ⋄ ⍬}⍵\n",
    "        w←{0<1⊃⍵.next:⍵.tiles[⊂0 ¯1+⍵.next]⊃3⌷EDGEIDS ⋄ ⍬}⍵\n",
    "        n w\n",
    "    }\n",
    "\n",
    "    (N W)←NW ⍵\n",
    "\n",
    "    ⍝ Find tiles matching the edge specification.\n",
    "    ns←{⍵≢⍬:⍵=2⌷EDGEIDS ⋄ 1/⍨1⊃⍴EDGEIDS}N\n",
    "    ew←{⍵≢⍬:⍵=1⌷EDGEIDS ⋄ 1/⍨1⊃⍴EDGEIDS}W\n",
    "    ⍬ genStates⍸∧⌿↑(ns)(ew)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 267,
   "metadata": {},
   "outputs": [],
   "source": [
    "final←{0=≢⍵:⍬⋄s←⊃1↑⍵⋄s.found:s⋄∇(1↓⍵),neigh ⊃1↑⍵},state ⍝ Breadth-first search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 268,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">              \n",
       "59187348943703\n",
       "              \n",
       "</span>"
      ]
     },
     "execution_count": 268,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←×/TILEIDS[⌊8÷⍨,{↑(⊣/⍵)(⊢/⍵)}⍣2⊢final.tiles] ⍝ Multiply tile-ids of the corners\n",
    "assert 59187348943703=part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 21: Allergen Assessment\n",
    "https://adventofcode.com/2020/day/21"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY21←', '∘((~∊⍨)⊆⊢)¨¨(⊃,/)¨'^(.+)\\s\\(contains\\s(.+)\\)$'⎕S rg¨⊃⎕NGET'data/2020/day21.txt'1\n",
    "(ingr alg)←∪⌿↑DAY21\n",
    "recipes←{ingr⍳⍵}¨⊣/↑DAY21\n",
    "allergens←↓alg∘.{⍵∊⍨∘⊂⍺}⊢/↑DAY21\n",
    "a2i←(⊃,/)¨recipes∘{∩/⍺[⍸⍵]}¨allergens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [],
   "source": [
    "Resolve←{⍬≡i←⍸⍺∘{1=≢⍵~⍺}¨⍵:⍺⋄((⊃⍺~⍨(⊃i)⊃⍵)@(⊃i)⊢⍺)∇⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [],
   "source": [
    "resolved←(¯1/⍨≢a2i) Resolve a2i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now know which ingredients map to which allergens. For part 1 we're asked to count the number of times the inert (non-allergenic) ingredients occur in the recipes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "2282\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 140,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part1←≢resolved~⍨∊recipes\n",
    "assert 2282=part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we seek to arrange the allergenic ingredients alphabetically by their allergen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→───────────────────────────────────────────────┐\n",
       "│vrzkz,zjsh,hphcb,mbdksj,vzzxl,ctmzsr,rkzqs,zmhnj│\n",
       "└────────────────────────────────────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 153,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢part2←1↓','{⊃,/⍺∘,¨⍵}(ingr[resolved])[⍋alg]\n",
    "assert 'vrzkz,zjsh,hphcb,mbdksj,vzzxl,ctmzsr,rkzqs,zmhnj'≡part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Resolve function above simply looks through the a2i array finding items of length 1, and substituting those into the  others in turn. We can write that out in more verbose form as:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Resolve←{\n",
    "    ⍺←¯1/⍨≢⍵\n",
    "    res←⍺\n",
    "    idx←⍸{1=≢⍵~res}¨⍵        ⍝ First unseen position with 1 element\n",
    "    ⍬≡idx:res                ⍝ None found; must be done\n",
    "    res[⊃idx]←⊃res~⍨(⊃idx)⊃⍵ ⍝ Mark as resolved\n",
    "    res∇⍵                    ⍝ Keep looking\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 25: Combo Breaker\n",
    "https://adventofcode.com/2020/day/25\n",
    "\n",
    "This could be speeded up by noting that this is an example of where the [Baby-Step-Giant-Step](https://en.wikipedia.org/wiki/Baby-step_giant-step) algorithm could be employed. Although it's reasonably swift as brute force."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">        \n",
       "18329280\n",
       "        \n",
       "</span>"
      ]
     },
     "execution_count": 123,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "card_pk←12092626\n",
    "door_pk←4707356\n",
    "card_loop←0⋄_←(20201227∘|7∘×)⍣{card_loop+←1⋄⍺=card_pk}⊢1\n",
    "⊢part1←(20201227∘|door_pk∘×)⍣card_loop⊢1\n",
    "assert 18329280=part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Dyalog APL",
   "language": "apl",
   "name": "dyalog-kernel"
  },
  "language_info": {
   "file_extension": ".apl",
   "mimetype": "text/apl",
   "name": "APL"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}