Advent of Code 2018 Dyalog APL.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Advent of Code 2018, 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%202018%20Dyalog%20APL.ipynb).\n",
    "\n",
    "Annotated solutions in Dyalog APL.\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": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "⍝ Helper functions and common settings\n",
    "⎕IO←0\n",
    "assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕signal 8 ⋄ shy←0}\n",
    "lines←{⊃⎕NGET ⍵ 1}\n",
    "line←{⊃lines ⍵}\n",
    "sorted←{⍵[⍋⍵]}\n",
    "sortbycol←⊢⌷⍨∘⊂∘⍒⌷⍤1\n",
    "pairs←{↓(2÷⍨≢⍵) 2⍴⍵}\n",
    "bin←{(32⍴2)⊤⍵}\n",
    "dec←2∘⊥\n",
    "and←{(bin ⍺)∧bin ⍵}\n",
    "or←{(bin ⍺)∨bin ⍵}\n",
    "rs←⊢∘-∘≢↑↓⍨∘-⍨"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "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": 2,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────┐\n",
       "│Was OFF│\n",
       "└───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⍝ Some visualisation help, please\n",
    "]box on -style=max -trains=tree -fns=on\n",
    "]rows on"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 1: Chronal Calibration\n",
    "https://adventofcode.com/2018/day/1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY1←⍎¨¨'(-?\\d+)'⎕s'\\1'¨lines'data/2018/01.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "477\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←⊃⊃+/DAY1\n",
    "assert 477=Part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we're looking for the first frequency to recur. If we get to the end, take the last value and use that as the start value for the next iteration. We look for the first duplicate using Dyalog's [unique mask](https://aplwiki.com/wiki/Nub_Sieve) function (monadic `≠`), introduced in v18."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day1p2←{t←⍬⋄0{t,←1↓+\\⍺,⍵⋄1=≢e←t[⍸<\\~≠t]:⊃e⋄⍵∇⍨⊃¯1↑t}⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "390\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←Day1p2 DAY1\n",
    "assert 390=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 2: Inventory Management System\n",
    "https://adventofcode.com/2018/day/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "8118\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←×/+/⍉↑2 3∘∊¨(≢⊢)⌸¨DAY2←lines'data/2018/02.txt'\n",
    "assert 8118=Part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→────────────────────────┐\n",
       "│jbbenqtlaxhivmwyscjukztdp│\n",
       "└─────────────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←(=⌿l)/0⌷l←↑DAY2[⍸{1∊⍵}¨↓DAY2∘.{+/≠/⍺,⍪⍵}DAY2]\n",
    "assert 'jbbenqtlaxhivmwyscjukztdp'≡Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 3: No Matter How You Slice It\n",
    "https://adventofcode.com/2018/day/3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY3←⍎¨¨'\\d+'⎕s'&'¨lines'data/2018/03.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [],
   "source": [
    "R←1000 1000⍴0⋄_←{R[⍵]+←1}¨CL←{,((2⊃⍵)+⍳4⊃⍵)∘.,((1⊃⍵)+⍳3⌷⍵)}¨DAY3 ⍝ Convert origin + dx dy to coord pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">      \n",
       "104126\n",
       "      \n",
       "</span>"
      ]
     },
     "execution_count": 153,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←+/2≤∊R\n",
    "assert 104126=Part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "695\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 154,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←1+⊃⍸{∧/1=R[⍵]}¨CL ⍝ Claim numbers are 1-indexed, so need to add 1\n",
    "assert 695=Part2          "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 4: Repose Record\n",
    "https://adventofcode.com/2018/day/4\n",
    "\n",
    "Basically a series of set operations -- sort based on date, then split and merge into chunks based on each guard's log lines. Pair up into sleep-wake pairs and expand into the corresponding minute range. We can then use key `⌸` to find the most frequent minute for the guard with the most sleep minutes.\n",
    "\n",
    "The regex\n",
    "\n",
    "   '(?|.*(#\\d+).*|.*:(\\d\\d)).*'\n",
    "   \n",
    "is a _branch reset_ `(?| ...|... )`, which means that the result of whichever of the two branches that matches can be referred to as `\\1` in the replacement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [],
   "source": [
    "'iotag'⎕CY'dfns'\n",
    "DAY4←sorted lines'data/2018/04.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [],
   "source": [
    "parsed←'(?|.*(#\\d+).*|.*:(\\d\\d)).*'⎕r'\\1'⊢DAY4 ⍝ Pick out guard number, and minutes for each sleep/wake item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [],
   "source": [
    "guards←{0⊃0⊃⍵}¨merged←(≠{⍎1↓0⊃⍵}¨grouped)⊂grouped←sorted parsed⊂⍨'#'∘(1∊⍷)¨parsed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [],
   "source": [
    "sleepiest←⊃⍒≢¨sleep←{∊{(⍎⍺) iotag ¯1+⍎⍵}/↑⍵}¨pairs¨{⊃,/{1↓⍵}¨⍵}¨merged"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">      \n",
       "138280\n",
       "      \n",
       "</span>"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←(⍎1↓sleepiest⊃guards)×⊃((⊣/⊢⍤/⍨∘(⌈/=⊢)⊢/){⍺(≢⍵)}⌸)sleepiest⊃sleep\n",
    "assert 138280=Part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, we seek the guard which has the highest minute sleep frequency. We have most of the parts already."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 412,
   "metadata": {},
   "outputs": [],
   "source": [
    "f←⊃⍒{⌈/1⌷⍉⍵}¨freq←({⍺,(≢⍵)}⌸)¨sleep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 417,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "89347\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 417,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←(⍎1↓f⊃guards)×⊃(⊣/⊢⍤/⍨∘(⌈/=⊢)⊢/)f⊃freq\n",
    "assert 89347=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 5: Alchemical Reduction\n",
    "https://adventofcode.com/2018/day/5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY5←line'data/2018/05.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 418,
   "metadata": {},
   "outputs": [],
   "source": [
    "r←∊'|'(1↓∘,,⍤0)p,⌽¨p←(⎕C⎕A),¨⎕A ⍝ Make the regex aA|Aa|bB|Bb ... etc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 433,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "9172\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 433,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←≢{r⎕r''⊢⍵}⍣≡⊢DAY5        ⍝ Apply regex replace until no change\n",
    "assert 9172=Part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 435,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "6550\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 435,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←⌊/{≢{r⎕r''⊢⍵}⍣≡⊢(⍵⎕r''⍠'IC'1)DAY5}¨⎕A ⍝ This several minutes to run\n",
    "assert 6550=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 6: Chronal Coordinates\n",
    "https://adventofcode.com/2018/day/6\n",
    "\n",
    "This problem is very suited to an array language like APL. We create a 3D matrix where each major cell is a 2D matrix holding the manhattan distances from each point to the input coordinate. We can then process this along the z-axis to pick the layer index of the smallest distance. That gives us a \"Nearest\" map. What remains is to remove any \"infinites\", defined as the numbers which occur along any edge of the \"Nearest\" map, and finally find the highest frequency. \n",
    "\n",
    "The Python [solution](https://github.com/xpqz/aoc-18/blob/master/day6.py) is considerably longer and slower."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕io←0\n",
    "DAY6←⍎¨lines'data/2018/06.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {},
   "outputs": [],
   "source": [
    "(XMAX YMAX)←⊃↓⍉↑⌈/DAY6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each of the 50 points, make an array where each value is the MHD from the point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [],
   "source": [
    "MHD←{+/|⍵-⍺}\n",
    "Dist←{YMAX XMAX⍴⍵∘MHD¨,⍳YMAX XMAX}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create the nearest distance map. A small hoop to jump through: points that are equidistant to several coordinates should be removed. We set those to ¯1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [],
   "source": [
    "Nearest←{v←⍋⍵⋄⍵[v[0]]=⍵[v[1]]:¯1⋄⊃v}¨↓[0]↑Dist¨⌽¨DAY6 ⍝ Flip each input pair so we have (y x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remove any items touching the boundaries of the array, as they're 'infinite'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "3989\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 132,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←1⊃0⌷1 sortbycol{⍺(≢⍵)}⌸(∊Nearest)~∪Nearest[⍸(⌽∨⊖)0∊¨⍳⍴Nearest]\n",
    "assert 3989=Part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, we instead seek the set of points that each have a combined MHD to all coords < 10,000."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "49715\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←+/{10000>+/⍵∘MHD¨DAY6}¨,⍳YMAX XMAX\n",
    "assert 49715=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 7: The Sum of Its Parts\n",
    "https://adventofcode.com/2018/day/7\n",
    "\n",
    "We have a graph which we need to traverse in a specific child-order - sorting the queue each iteration is a somewhat inefficient approach, but as the number of nodes is tiny it doesn't really matter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY7←'^.+?([A-Z]).*([A-Z]).*$'⎕r'\\1\\2'⊢lines'data/2018/07.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [],
   "source": [
    "(KEY PRE)←↓⍉↑(↓⊃¨,∘⊂⌸⊢/¨)↓⌽↑DAY7 ⍝ Make the graph - splitting out nodes and their ascendants"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day7p1←{0=≢⍵:⍺⋄(⍺,p)∇(⍺,p)~⍨sorted ⍵∪{KEY/⍨⍵∘{∧/⍵∊⍺}¨PRE} ⍺,p←⊃⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→─────────────────────────┐\n",
       "│BHMOTUFLCPQKWINZVRXAJDSYEG│\n",
       "└──────────────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 126,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←⍬ Day7p1 sorted KEY~⍨∪∊DAY7\n",
    "assert 'BHMOTUFLCPQKWINZVRXAJDSYEG'≡Part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2 -- process items concurrently in a worker pool of 5. Each job now takes 60 + a number corresponding to the item's position in the alphabet (A=60+1, B=60+2 etc). Replaces 200+ lines of my Python [solution](https://github.com/xpqz/aoc-18/blob/master/day7.py)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {},
   "outputs": [],
   "source": [
    "Workers←{0=slots←5-≢⍺:⍺⋄⍺,{⍵,⍨61+⎕A⍳⍵}¨(slots⌊≢⍵)↑⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day7p2←{\n",
    "    wrk←⍬ ⋄ sec←0\n",
    "    ⍬ {\n",
    "        (0=≢⍵)∧0=≢wrk:sec\n",
    "        (remains jobs)←↓⍉↑wrk⊢←¯1∘+@0¨wrk Workers ⍵ ⍝ Fill any available slots and 'tick'\n",
    "        wrk⊢←wrk/⍨0≠remains                         ⍝ Reap any dead worker processes\n",
    "        sec+←1\n",
    "        (⍺,sorted ready)∇(⍺,jobs)~⍨⍵∪{KEY/⍨⍵∘{∧/⍵∊⍺}¨PRE}⍺,ready←jobs/⍨0=remains\n",
    "    } ⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "877\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 131,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←Day7p2 sorted KEY~⍨∪∊DAY7\n",
    "assert 877=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 8: Memory Maneuver\n",
    "https://adventofcode.com/2018/day/8\n",
    "\n",
    "Release the recursions!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY8←⍎line'data/2018/08.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [],
   "source": [
    "get←{v←DAY8[CUR+⍳⍵]⋄CUR+←⍵⋄v} ⍝ Poor-man's generator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day8p1←{(chc mtc)←get 2⋄ch←⍬ {⍵=0:⍺⋄(⍺,Day8p1⍬)∇⍵-1} chc⋄⊂ch (get mtc)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "44838\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "CUR←0\n",
    "⊢Part1←+/∊TREE←Day8p1⍬\n",
    "assert 44838=Part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day8p2←{(ch mt)←⍵⋄0=≢ch:+/mt⋄ind←¯1+mt~0⋄+/∇¨ch[(ind<≢ch)/ind]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "22198\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←Day8p2 ⊃TREE\n",
    "assert 22198=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 9: Marble Mania\n",
    "https://adventofcode.com/2018/day/9\n",
    "\n",
    "This will tax systems that are O(N) for vector insert or delete. We need a structure that's O(1) for both insert and delete for part 2 at least, here in the shape of a bi-directional linked list. Ugly, but does the job."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "ELVES←430⍴0\n",
    "CIRCLE←{⍵⊣⍵.(v l r pos start)←(,0) (,0) (,0) 0 0}⎕NS'' "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "val←{⍵.pos⊃⍵.v}\n",
    "rev7←{l←⍵ ⋄ {⍵=¯1:l ⋄ l.pos←l.pos⊃l.l ⋄ ∇ ⍵-1}7}\n",
    "fwd←{⍵.pos←⍵.pos⊃⍵.r⋄⍵}\n",
    "twenty3←{v←val rev7 CIRCLE⋄_←fwd del CIRCLE⋄ELVES[⍺]+←⍵+v⋄⍬}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "add←{\n",
    "    ⍺.v,←⍵\n",
    "    ⍺.l,←⍺.pos\n",
    "    ⍺.r,←right←⍺.pos⊃⍺.r\n",
    "    ⍺.pos←⍺.l[right]←⍺.r[⍺.pos]←¯1+≢⍺.v\n",
    "    ⍺\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "del←{\n",
    "    left←⍵.pos⊃⍵.l\n",
    "    ⍵.r[left]←right←⍵.pos⊃⍵.r\n",
    "    ⍵.l[right]←left\n",
    "    ⍵.pos=⍵.start:⊢⍵.pos←⍵.start←right\n",
    "    ⍵.pos←right\n",
    "    ⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day9←{\n",
    "    max←⍵\n",
    "    0 {\n",
    "        max<⍵:⌈/ELVES\n",
    "        0=23|⍵:((≢ELVES)|⍺+1)∇(⍵+1)⊣⍺ twenty3 ⍵\n",
    "        _←fwd CIRCLE add ⍵\n",
    "        ((≢ELVES)|⍺+1)∇⍵+1\n",
    "    } 1\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">      \n",
       "422748\n",
       "      \n",
       "</span>"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←Day9 71588\n",
    "assert 422748=Part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, we're asked to increase the marble count by two orders of magnitude."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "ELVES←430⍴0\n",
    "CIRCLE←{⍵⊣⍵.(v l r pos start)←(,0) (,0) (,0) 0 0}⎕NS''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">          \n",
       "3412522480\n",
       "          \n",
       "</span>"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⎕PP←11                     ⍝ Up the precision limit for printing floats\n",
    "⊢Part2←Day9 7158800        ⍝ Takes ~15s to run\n",
    "assert 3412522480=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 10: The Stars Align\n",
    "https://adventofcode.com/2018/day/10\n",
    "\n",
    "Back on solid array footing for day 10 - a task ideally suited for APL. Repeatedly add the velocity vector until the bounding box of the points no longer decreases."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "DAY10←↑⍎¨¨'(-?\\d+)'⎕s'\\1'¨lines'data/2018/10.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "POS←,/DAY10[;0 1]⋄DELTA←,/DAY10[;2 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "Bbox←{+/|-⌿2 2⍴(⌊⌿,⌈⌿)↑⍵} ⍝ Width + height of bounding box"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "MSG←DELTA-⍨DELTA∘{⍵+⍺}⍣{(Bbox ⍺)>Bbox ⍵}⊢POS ⍝ Add velocity until bounding box no longer decreases."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "(W H)←|-⌿2 2⍴(⌊⌿,⌈⌿)↑MSG ⍝ Width and height of bounding box"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→─────────────────────────────────────────────────────────────┐\n",
       "↓******  *****   *****   *****   *****   *****   ******    **  │\n",
       "│*       *    *  *    *  *    *  *    *  *    *       *   *  * │\n",
       "│*       *    *  *    *  *    *  *    *  *    *       *  *    *│\n",
       "│*       *    *  *    *  *    *  *    *  *    *      *   *    *│\n",
       "│*****   *****   *****   *****   *****   *****      *    *    *│\n",
       "│*       *       *  *    *    *  *  *    *  *      *     ******│\n",
       "│*       *       *   *   *    *  *   *   *   *    *      *    *│\n",
       "│*       *       *   *   *    *  *   *   *   *   *       *    *│\n",
       "│*       *       *    *  *    *  *    *  *    *  *       *    *│\n",
       "│*       *       *    *  *****   *    *  *    *  ******  *    *│\n",
       "└──────────────────────────────────────────────────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⍉(-(W+1))↑⍉(-(H+1))↑'*'@(⊖¨MSG)⊢143 203⍴' ' ⍝ Prune our display: FPRBRRZA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2: how many iterations was that?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [],
   "source": [
    "I←0\n",
    "_←DELTA∘{⍵+⍺}⍣{I+←1⋄(Bbox ⍺)>Bbox ⍵}⊢POS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "10027\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←I-1\n",
    "assert 10027=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 11: Chronal Charge\n",
    "https://adventofcode.com/2018/day/11\n",
    "\n",
    "More APL home court advantage here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1        ⍝ Note: 1-based indexing\n",
    "DAY11←7803"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [],
   "source": [
    "P←{¯5+1⊃10 10 10⊤rack×DAY11+⍺×rack←⍵+10} ⍝ The power function, as defined by the question"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We apply the power function P to a 300×300 grid and then use stencil to define all 3×3 neighbourhoods which we then sum up. Note that stencil used this way creates neighbourhoods that straddle the boundaries, so we need to subtract 1,1 from the result. To be completely general we should probably have excluded these boundary neighbourhoods."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [],
   "source": [
    "G←300 300⍴P/↑,⍳300 300\n",
    "SUM←{+/,⍵}⌺3 3⊢G"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [],
   "source": [
    "MAX←⌈/,SUM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→────┐\n",
       "│20 51│\n",
       "└~────┘\n",
       "</span>"
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←¯1+⊖⊃⍸MAX⍷SUM ⍝ Question specifically asks for x,y so we flip the coordinate pair\n",
    "assert 20 51≡Part1   ⍝ Submittable result format: 20,51"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2 asks us to find the neighbourhood of any size that gives the largest sum. There are possibly smart ways to achieve this, noting that we could reuse smaller neighbourhood sums when calculating larger ones. But let's start with the simple way, looking for some probable patterns."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's consider all regions up to 50×50 -- reasonably quick:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐\n",
       "│36 55 58 70 73 75 76 99 101 117 117 116 119 125 122 113 110 96 74 81 73 71 63 64 57 62 55 43 13 6 2 ¯6 ¯32 ¯52 ¯72 ¯79 ¯101 ¯108 ¯117 ¯117 ¯117 ¯117 ¯127 ¯127 ¯136 ¯136 ¯146 ¯146 ¯151 ¯151│\n",
       "└~───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 147,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G∘{⌈/,{+/,⍵}⌺⍵ ⍵⊢⍺}¨3+⍳50"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see that the max sum (125) is at size 17, and then the values wobble downwards. So for part 2, we simply apply the same process as for part 1, but for a region size of 17×17, noting that we need to subtract 8,8 to skip the 17×17 neighbourhoods that aren't fully inside the boundary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────┐\n",
       "│230 272│\n",
       "└~──────┘\n",
       "</span>"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "SUM←{+/,⍵}⌺17 17⊢G\n",
    "MAX←⌈/,SUM\n",
    "⊢Part2←¯8+⊖⊃⍸MAX⍷SUM  ⍝ Skip all neighbourhoods straddling a boundary\n",
    "assert 230 272≡Part2  ⍝ Submittable result format: 230,272,17"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 12: Subterranean Sustainability\n",
    "https://adventofcode.com/2018/day/12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 231,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "DAY12←'#'⎕R'1'¨'\\.'⎕R'0'¨lines'data/2018/12.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 232,
   "metadata": {},
   "outputs": [],
   "source": [
    "STATE←∊0 0,(⍎¨15↓0⊃DAY12),50⍴0 ⍝ Start state, as binary vector, padded a bit to the left and right\n",
    "PATT←⍎¨¨5↑¨2↓DAY12             ⍝ Rule pattern bodies, as binary vectors\n",
    "NEW←⍎¨¯1↑¨2↓DAY12              ⍝ Rule results as binary vector\n",
    "RULES←NEW[⍋2⊥¨PATT]            ⍝ Sort rule results by the patterns converted from binary to decimal 0-31"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The generational transform is now simply each overlapping binary 5-neighbourhood converted to decimal as indices into the RULES vector."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 233,
   "metadata": {},
   "outputs": [],
   "source": [
    "Next←{RULES[2⊥¨{⊂⍵}⌺5⊢⍵]}      ⍝ Transformation function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 1: run for 20 generations and sum up the pot-numbers for pots containing live plants. Note: not the number of live plants!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 235,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "3421\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 235,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←+/¯2+⍸Next⍣20⊢STATE     ⍝ Remember to remove the left-side padding (¯2)\n",
    "assert 3421=Part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2: FIDDY BEEEEEEELLLION iterations! Obviously need to look at some data dependency trick here. Working hypothesis: check for emergent stable pattern. \n",
    "\n",
    "The two simplest potential options are:\n",
    "\n",
    "1. Constant -- sum converges to constant value\n",
    "2. Constant change -- sum _change_ converges to constant value\n",
    "\n",
    "We can confirm that that the second case is what we have - let's look at the sums over time:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 253,
   "metadata": {},
   "outputs": [],
   "source": [
    "P2STATE←∊0 0,(⍎¨15↓0⊃DAY12),200⍴0         ⍝ Give ourselves a bit more growth room to the right\n",
    "GENS←,+/¯2+⍸STATE\n",
    "_←{v←Next ⍵⋄GENS,←+/¯2+⍸v⋄v}⍣150⊢P2STATE  ⍝ 150 generations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 254,
   "metadata": {},
   "outputs": [],
   "source": [
    "DIFFS←2-/GENS ⍝ Subtract current from previous; increases will show as negative"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we inspect how the generational differences change over the generations, we can see that after the 97th generation, every subsequent step adds 51 to the value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 255,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐\n",
       "│¯48 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51 ¯51│\n",
       "└~──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 255,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "97↓DIFFS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 264,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">             \n",
       "2550000001195\n",
       "             \n",
       "</span>"
      ]
     },
     "execution_count": 264,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⎕PP←20\n",
    "⊢Part2←(98⊃GENS)+51×50000000000-98\n",
    "assert 2550000001195=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 13: Mine Cart Madness\n",
    "https://adventofcode.com/2018/day/13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 317,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY13←↑lines'data/2018/13.txt'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pick out the carts. \n",
    "\n",
    "We represent the compass bearings as 0, 1, 2, 3 for East, South, West and North respectively. The \"turn state\" for each cart defines its behaviour at intersections: left (0), straight (1), right (2)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 318,
   "metadata": {},
   "outputs": [],
   "source": [
    "⍝ row, col, heading, turn state\n",
    "WEST ←(W←⍸'<'⍷DAY13),¨⊂0 0 1 2\n",
    "SOUTH←(S←⍸'v'⍷DAY13),¨⊂1 0 1 2\n",
    "EAST ←(E←⍸'>'⍷DAY13),¨⊂2 0 1 2\n",
    "NORTH←(N←⍸'^'⍷DAY13),¨⊂3 0 1 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\"Fill in\" the tiles the carts are sitting on. No cart is starting on an intersection or turn."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 319,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY13[W,E]←'-'\n",
    "DAY13[N,S]←'|'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 1: what is the location of the first collision?\n",
    "Part 2: each time we detect a collision, remove the two \"wrecks\" and carry on - what is the location of the last remaining cart at the moment of the final collision? \n",
    "\n",
    "As most of the bits are the same for part 1 and part 2, we can solve both at once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 339,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day13←{\n",
    "    graph←⍺\n",
    "    loc←1@(↓(↑⍵)[;0 1])⊢150 150⍴0 ⍝ State: location of carts.\n",
    "    Next←{\n",
    "        dir←2⊃⍵ ⍝ Current bearing\n",
    "        Rot←{∊(4 3⍴1 0 3 2 1 0 3 2 1 0 3 2)[0⊃⍵;1⊃⍵],1⊖1↓⍵} ⍝ Return new bearing and turn state\n",
    "        \n",
    "        Step←{\n",
    "            ⍝ Move one step. Takes a left arg as a vector: dy dx turn1 turn2, and right arg a cart.\n",
    "            ⍝ Move as defined by unit vector (dy, dx). Turn1 and turn2 are \n",
    "            ⍝ the new bearings when landing on a \"/\" or \"\\\" respectively.\n",
    "            ⍝ Thus: 0 ¯1 1 3 means \"go one step east. If landing on \"/\", turn \n",
    "            ⍝ south. If \"\\\", turn north.\n",
    "            (dy dx slash backslash)←⍺\n",
    "            loc[0⊃⍵;1⊃⍵]-←1\n",
    "            pos←(dy+0⊃⍵),dx+1⊃⍵          ⍝ Step in stated direction\n",
    "            loc[0⊃pos;1⊃pos]+←1\n",
    "            tile←pos⌷graph               ⍝ Check the tile we landed on:\n",
    "            '/'=tile:∊pos,slash,3↓⍵        ⍝ Turn: /\n",
    "            '\\'=tile:∊pos,backslash,3↓⍵    ⍝ Turn: \\\n",
    "            '+'=tile:∊pos,Rot 2↓⍵          ⍝ Intersection: +\n",
    "            ∊pos,2↓⍵                       ⍝ Straight on: - or |\n",
    "        }\n",
    "        (dir⊃(0 ¯1 1 3)(1 0 0 2)(0 1 3 1)(¯1 0 2 0)) Step ⍵\n",
    "    }\n",
    "\n",
    "    crashes←⍬ ⍝ Store crash locations; only need first one for Part 1.\n",
    "    Crash←{\n",
    "        pos←2↑⍺\n",
    "        crashes,←⊂pos\n",
    "        loc[0⊃pos;1⊃pos]←0\n",
    "        ⍵/⍨~(⊂pos)≡¨2↑¨⍵\n",
    "    }\n",
    "    MoveAll←{ ⍝ ⍺ are carts that have moved, ⍵ carts yet to move\n",
    "        ⍺←⍬\n",
    "        0=≢⍵:sorted ⍺\n",
    "        cart←Next 0⊃⍵\n",
    "        pos←2↑cart\n",
    "        ⍝ If we have a 2 in the loc matrix, this cart collided with someone.\n",
    "        2∊loc:(pos Crash ⍺)∇pos Crash 1↓⍵\n",
    "        (⍺,⊂cart)∇1↓⍵\n",
    "    }\n",
    "    (⊂⊖0⊃crashes),⊂⊖2↑⊃MoveAll⍣{1=≢⍺}⊢⍵ ⍝ Repeat until only one remaining cart\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 340,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→────────────────┐\n",
       "│ ┌→─────┐ ┌→───┐ │\n",
       "│ │76 108│ │2 84│ │\n",
       "│ └~─────┘ └~───┘ │\n",
       "└∊────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 340,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Solution←DAY13 Day13 WEST,SOUTH,EAST,NORTH\n",
    "assert (76 108)(2 84)≡Solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 14: Chocolate Charts\n",
    "https://adventofcode.com/2018/day/14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 373,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY14←765071\n",
    "Mix←{new←10 10⊤+/⍺[⍵]⋄0≠0⊃new:new⋄1⊃new}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 374,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day14←{\n",
    "    acc←3 7\n",
    "    ⍵ {\n",
    "        (≢acc)≥⍺+10:⍺↓acc\n",
    "        acc,←acc Mix ⍵\n",
    "        ⍺∇(≢acc)|1+⍵+acc[⍵]\n",
    "    } 0 1\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 375,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────────────────┐\n",
       "│3 1 7 1 1 2 3 9 2 3│\n",
       "└~──────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 375,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←Day14 DAY14\n",
    "assert 3 1 7 1 1 2 3 9 2 3≡Part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2: how many recipes to the left of us once the given pattern appears? There is a small gotcha here -- we can't just check for the pattern at the end of the vector of recipes as we sometimes add one, and sometimes two new recipes -- we also need to check one step in from the end.\n",
    "\n",
    "We can try the new \"over\" operator from Dyalog v18 here: `X-⍥≢Y` gives us the difference in lengths between two vectors, which is an improvement from the fugly `(≢X)-≢Y`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 376,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day14p2←{\n",
    "    acc←3 7\n",
    "    patt←(10∘⊥⍣¯1)⍵                         ⍝ The pattern is a vector of the digits of the number\n",
    "    {\n",
    "        patt≡acc↑⍨-≢patt:acc-⍥≢patt         ⍝ Check from end\n",
    "        patt≡¯1↓acc↑⍨-1+≢patt:¯1+acc-⍥≢patt ⍝ Also check one step from end \n",
    "        acc,←acc Mix ⍵\n",
    "        ∇(≢acc)|1+⍵+acc[⍵]\n",
    "    } 0 1\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 377,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">        \n",
       "20353748\n",
       "        \n",
       "</span>"
      ]
     },
     "execution_count": 377,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←Day14p2 DAY14   ⍝ Takes ~20s to run\n",
    "assert 20353748=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 15: Beverage Bandits\n",
    "https://adventofcode.com/2018/day/15\n",
    "\n",
    "This was a very difficult problem to get right -- there are many subtle rules that govern how the pieces move.\n",
    "\n",
    "Note: when a unit moves within range of an enemy, it attacks as part of the same round:\n",
    "\n",
    "A 'turn' resolves to:\n",
    "\n",
    "1. If I am adjacent to one or more enemies, attack the first one in 'read order' (y-then-x)\n",
    "2. Otherwise, move one step along the shortest path towards an enemy, tie-breaking on 'read order'\n",
    "3. If, after a move, I am adjacent to one or more enemies, attack the first one in 'read order' (y-then-x)\n",
    "\n",
    "For the moving of creatures we do a breadth-first search until the first attackable enemy is encountered, and then use the length of that path as a cut-off, thus chopping down the search space dramatically. The question suggests a different approach: identify all attacking squares first, find the shortest path to each of these. That would enable us to use A* with a manhattan distance heuristic. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY15←↑lines'data/2018/15.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day15←{\n",
    "    (g e cave)←('G'⍷⍵)('E'⍷⍵)('.'⍷⍵)\n",
    "    elfCount←+/∊e\n",
    "    cave[(⍸g),⍸e]←1                   ⍝ Fill in tiles under feet of creatures\n",
    "    g[⍸g]←200 ⋄ e[⍸e]←¯200            ⍝ Initial hitpoints: 200\n",
    "    creatures←g+e\n",
    "    N4←(⍸cave)∘{⍵≡⍬:⍬⋄⍺∩⍵(+,-)(0 1)(1 0)}   ⍝ Valid 4-connected neighbouring tiles\n",
    "    edp←⍺ ⍝ elf damage points; for part 2\n",
    "\n",
    "    Attack←{ ⍝ Reduce creature with least hitpoints by 3, towards 0\n",
    "        0=≢⍵:⍬\n",
    "        (_ y x)←⍵⊃⍨⊃⍋|⍵     ⍝ Absolute value to ensure correct sort order\n",
    "        hp←creatures[⊂y x]  ⍝ Find original signed value\n",
    "        ⊢creatures[⊂y x]⊢←(1=×hp)⌷(⌊/0,hp+3),⌈/0,hp-edp\n",
    "    }\n",
    "\n",
    "    Select←{ ⍝ Given a set of paths to nearby enemies, pick the next square.\n",
    "        len←≢¨⍵\n",
    "        best←len[⊃⍋len]             ⍝ Shortest length\n",
    "        cand←(best≥len)/⍵           ⍝ We may have multiple\n",
    "        1⌷⊃cand[⊃⍋{⊃¯1↓¯2↑⍵}¨cand]  ⍝ Last-but-one step (attack squares), read-order\n",
    "    }\n",
    "\n",
    "    Move←{ ⍝ Move creature at ⍵ one step\n",
    "        (us them)←⍺\n",
    "\n",
    "        0≠≢them∩N4 ⍵:⍵ ⍝ In attacking position already; remain\n",
    "\n",
    "        max←⌊/⍬⋄found←⍬\n",
    "        StorePaths←{found,←⍵⋄max⊢←⌊/≢¨found⋄⍬}\n",
    "\n",
    "        BFS←{ ⍝ Search for shortest paths to enemy: basic breadth-first search\n",
    "            0=≢⍵:⍬\n",
    "            path←0⊃⍵ ⋄ queue←1↓⍵\n",
    "            max<≢path:⍺∇queue\n",
    "            neighbours←(⍺~⍨N4 ¯1↑path)~us\n",
    "            attacking←neighbours∩them\n",
    "            0≠≢attacking:(⍺,neighbours~them)∇queue⊣StorePaths path(↓,⍤1 0)attacking\n",
    "            (⍺,neighbours)∇queue,path(↓,⍤1 0)neighbours\n",
    "        }\n",
    "\n",
    "        _←(,⍵) BFS ,⊂⍵\n",
    "        0=≢found:⍬                 ⍝ No moves found\n",
    "        next←Select found\n",
    "        creatures[next]←creatures[⍵] ⋄ creatures[⍵]←0\n",
    "        next\n",
    "    }\n",
    "\n",
    "    Round←{ ⍝ Process all creatures in 'read order': move + attack\n",
    "        ⍺←⍬\n",
    "        0=≢⍵:,⍸0≠creatures\n",
    "        pos←0⌷⍵⋄tail←1↓⍵\n",
    "        pos∊⍺:⍺∇tail  ⍝ Already seen this one this round; skip\n",
    "        \n",
    "        me←×creatures[pos]\n",
    "        enemies←,⍸(¯1×me)=×creatures\n",
    "        friends←,⍸me=×creatures\n",
    "\n",
    "        newpos←(friends enemies)Move pos ⍝ Try move; stay still if attack pos\n",
    "        asquares←enemies∩N4 newpos\n",
    "        _←Attack creatures[asquares],¨asquares ⍝ Keep attacking\n",
    "\n",
    "        (⍺,newpos)∇tail\n",
    "    }\n",
    "\n",
    "    count←0\n",
    "    deadElf←0\n",
    "    Winner←{ ⍝ Winner declared if no creatures of either sign\n",
    "        count+←1\n",
    "        types←∊×creatures\n",
    "        elves←¯1=types\n",
    "        PART2∧elfCount>+/elves:1⊣deadElf⊢←1  ⍝ Part 2: terminate on first dead elf\n",
    "        (0=+/elves)∨0=+/1=×types\n",
    "    }\n",
    "\n",
    "    _←Round⍣Winner ⊢ ,⍸0≠creatures\n",
    "    count deadElf (creatures)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">      \n",
       "243390\n",
       "      \n",
       "</span>"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PART2←0\n",
    "(count deadElf creatures)←3 Day15 DAY15\n",
    "⊢Part1←(count-1)×+/|∊creatures\n",
    "assert 243390=Part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2: find the smallest damage an elf needs to inflict in order such that the elves win the battle without any casualties."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "59886\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PART2←1\n",
    "⊢Part2←{(count deadElf creatures)←⍵ Day15 DAY15⋄deadElf=0:(count-1)×+/|∊creatures⋄∇⍵+1}4\n",
    "assert 59886=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ok, that was annoyingly fiddly! In retrospect, maybe we'd been better keeping the creatures in separate matrices instead of disambiguating by sign."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 16: Chronal Classification\n",
    "https://adventofcode.com/2018/day/16\n",
    "\n",
    "We split the input file into the two obvious sections manually."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 205,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY16p1←↓774 3⍴⍎¨¨({0≠≢⍵}¨d)/d←'(\\d+)'⎕S'\\1'¨lines'data/2018/input16-1.data'\n",
    "DAY16p2←⍎¨lines'data/2018/input16-2.data'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, let's implement the various instructions. They all follow a small set of patterns - register operator register, or register operator value etc. We can exploit this with a couple of custom operators."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 206,
   "metadata": {},
   "outputs": [],
   "source": [
    "bin←{(32⍴2)⊤⍵}\n",
    "rr←{((⍵[1]⌷⍺) ⍺⍺ (⍵[2]⌷⍺))@(3⌷⍵)⊢⍺}           ⍝ reg-reg\n",
    "ri←{((⍵[1]⌷⍺) ⍺⍺ (⍵[2]))@(3⌷⍵)⊢⍺}             ⍝ reg-val\n",
    "ir←{((⍵[1]) ⍺⍺ (⍵[2]⌷⍺))@(3⌷⍵)⊢⍺}             ⍝ val-reg\n",
    "brr←{(2⊥(bin ⍵[1]⌷⍺) ⍺⍺ bin ⍵[2]⌷⍺)@(3⌷⍵)⊢⍺}  ⍝ reg-reg (binary)\n",
    "bri←{(2⊥(bin ⍵[1]⌷⍺) ⍺⍺ bin ⍵[2])@(3⌷⍵)⊢⍺}    ⍝ reg-val (binary)\n",
    "addr←+rr ⋄ addi←+ri\n",
    "mulr←×rr ⋄ muli←×ri\n",
    "banr←∧brr ⋄ bani←∧bri\n",
    "borr←∨brr ⋄ bori←∨bri\n",
    "setr←{(⍵[1]⌷⍺)@(3⌷⍵)⊢⍺} ⋄ seti←{⍵[1]@(3⌷⍵)⊢⍺}\n",
    "gtir←>ir ⋄ gtri←>ri ⋄ gtrr←>rr\n",
    "eqir←=ir ⋄ eqri←=ri ⋄ eqrr←=rr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "metadata": {},
   "outputs": [],
   "source": [
    "OPS←'addr' 'addi' 'mulr' 'muli' 'banr' 'bani' 'borr' 'bori' 'setr' 'seti' 'gtir' 'gtri' 'gtrr' 'eqir' 'eqri' 'eqrr'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {},
   "outputs": [],
   "source": [
    "Validate←{(before instr after)←⍵⋄after≡before (⍎⍺) instr}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 209,
   "metadata": {},
   "outputs": [],
   "source": [
    "MATCH←OPS∘.Validate DAY16p1 ⍝ ♥ APL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "517\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 210,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←+/2>⍨+⌿MATCH\n",
    "assert 517=Part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we need to resolve all the opcodes' names to numbers, and then execute the program, and return the final value left in register 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 211,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Opcodes←{\n",
    "    0=+/∊MATCH:⊢/↑sorted ⍵\n",
    "    single←⊃⍸1=+⌿MATCH\n",
    "    op←⊃1⊃⊃DAY16p1[single]\n",
    "    row←⊃⍸MATCH[;single]\n",
    "    MATCH[row;]←0\n",
    "    ∇⍵,⊂op (row⊃OPS)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 212,
   "metadata": {},
   "outputs": [],
   "source": [
    "OPCODES←Opcodes ⍬"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "metadata": {},
   "outputs": [],
   "source": [
    "Run←{⍺←0 0 0 0⋄0=≢⍵:0⊃⍺⋄opc←⊃instr←0⊃⍵⋄(⍺ (⍎opc⊃OPCODES) instr)∇1↓⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 214,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "667\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 214,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←Run DAY16p2\n",
    "assert 667=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 17: Reservoir Research\n",
    "https://adventofcode.com/2018/day/17\n",
    "\n",
    "Another colossal cave ⍨\n",
    "\n",
    "This problem has a simple and obvious recursive formulation, but sadly not tail-recursive. So let's use an explicit operations queue instead."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "'iotag'⎕CY'dfns'\n",
    "DAY17←lines'data/2018/17.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Parse←{\n",
    "    col←⊃'x=(\\d+), y=(\\d+)\\.\\.(\\d+)'⎕s'\\1 \\2 \\3'⊢⍵\n",
    "    0≠≢col:((1⊃⍎col)iotag 2⊃⍎col),¨0⊃⍎col\n",
    "    row←⍎⊃'y=(\\d+), x=(\\d+)\\.\\.(\\d+)'⎕s'\\1 \\2 \\3'⊢⍵\n",
    "    (0⊃row),¨(1⊃row)iotag 2⊃row\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "CLAY←⊃,/Parse¨DAY17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "CAVE←'#'@CLAY⊢(1+⊃⌈/CLAY)⍴'.'\n",
    "YMAX←¯1+⊃⍴CAVE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "Open←{3::0⋄CAVE[⊂⍵]∊'.|'}\n",
    "Closed←~Open\n",
    "Boundary←{(y x dx)←⍵⋄{(Closed y,⍵+dx)∨Open ⍵,⍨y+1:⍵⋄∇⍵+dx}x}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Down←{\n",
    "    (y x)←⍵\n",
    "    newY←YMAX⌊¯1+y+⌊/(y↓CAVE[;x])⍳'#~'\n",
    "    CAVE[y+⍳newY-y-1;x]←'|'\n",
    "    newY≠YMAX:⊂'S'newY x\n",
    "    ⍬\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Spread←{\n",
    "    (y x)←⍵\n",
    "    left←Boundary y x ¯1\n",
    "    right←Boundary y x 1\n",
    "    stretch←left+⍳right-left-1\n",
    "    CAVE[y;stretch]←'|'\n",
    "    opens←(Open right,⍨y+1)(Open left,⍨y+1)((Closed left,⍨y+1)∧Closed right,⍨y+1)\n",
    "    ops←opens/('D' y right)('D' y left)('S' (y-1) x)\n",
    "    2⊃opens:ops⊣CAVE[y;stretch]←'~'\n",
    "    ops\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Trickle←{ ⍝ ⍺ keeps track of visited nodes. ⍵ is the pending queue\n",
    "    0=≢⍵:(+/'|'=∊CAVE) (+/'~'=∊CAVE)\n",
    "    op←⊃0⌷⍵ ⋄ tail←1↓⍵\n",
    "    (⊂op)∊⍺:⍺∇tail\n",
    "    'D'=0⊃op:(⍺,⊂op)∇tail,Down 1↓op\n",
    "    (⍺,⊂op)∇tail,Spread 1↓op\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "(Wet Settled)←⍬ Trickle ,⊂'D' 0 500"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "39370\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←Wet+Settled\n",
    "assert 39370=Part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "33061\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Settled\n",
    "assert 33061=Settled"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 18: Settlers of The North Pole\n",
    "https://adventofcode.com/2018/day/18\n",
    "\n",
    "Conway's game of Lumber. This kind of problem is APL home turf.\n",
    "\n",
    "Note: when reading in the data we rely on the `∪⍳⊢` trick to convert characters to their unique index of first occurrence. This means that the map will differ with the data set. In order for the below solution to work for a different data set, we'd need to ensure that\n",
    "\n",
    "* 0 = ground (.)\n",
    "* 1 = tree (|)\n",
    "* 2 = lumber (#)\n",
    "\n",
    "Tweaking the `Display` dfn below to do this is left as an exercise for the interested reader."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY18←50 50⍴(∪⍳⊢)∊lines'data/2018/18.txt' ⍝ 50×50: 0 = ground (.), 1 = tree (|), 2 = lumber (#)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "Display←{'#'@(2∘=)⊢'|'@(1∘=)⊢'.'@(0∘=) ⍵} ⍝ Debugging dfn left for posterity/sanity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "TNG←{\n",
    "    i←⍵[⊂1 1]\n",
    "    frq←+/⍉↑(∊⍵)=⊂0 1 2 ⍝ Can't easily use ⌸ -- need missing values, too\n",
    "    (i=0)∧frq[1]≥3:1\n",
    "    (i=1)∧frq[2]≥3:2\n",
    "    i≠2:i \n",
    "    (i=2)∧(frq[2]≥2)∧(frq[1]≥1):2 ⍝ Note: frq[2]≥2 -- disregard self\n",
    "    0\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "FINAL←{TNG ⍵}⌺3 3⍣10⊢DAY18"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [],
   "source": [
    "TREES←+/1=∊FINAL ⋄ LUMBER←+/2=∊FINAL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">      \n",
       "589931\n",
       "      \n",
       "</span>"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←TREES×LUMBER\n",
    "assert 589931=Part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So for part 2, the customary AoC trap-door: now for beeeeellion iterations, which is code for that there is a data dependency or recurring pattern to exploit.\n",
    "\n",
    "For GoL-like cellular automata, especially on a fixed-size board, we know that we frequently encounter either a stable state (no changes), or a loop (a recurring pattern). We could be scientific about it, but by letting this run and visualising the state a prominent pattern quickly starts recurring. \n",
    "\n",
    "The state at 1×10^9 generations should be the same as that at 1000 generations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "FINAL←{TNG ⍵}⌺3 3⍣1000⊢DAY18"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">      \n",
       "222332\n",
       "      \n",
       "</span>"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "TREES←+/1=∊FINAL ⋄ LUMBER←+/2=∊FINAL\n",
    "⊢Part2←TREES×LUMBER\n",
    "assert 222332=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 19: Go With The Flow\n",
    "https://adventofcode.com/2018/day/19\n",
    "\n",
    "More asmbunny VMing. We can repurpose bits of Day 16 above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "rr←{((⍵[1]⌷⍺) ⍺⍺ (⍵[2]⌷⍺))@(3⌷⍵)⊢⍺}           ⍝ reg-reg\n",
    "ri←{((⍵[1]⌷⍺) ⍺⍺ (⍵[2]))@(3⌷⍵)⊢⍺}             ⍝ reg-val\n",
    "addr←+rr ⋄ addi←+ri\n",
    "mulr←×rr ⋄ muli←×ri\n",
    "setr←{(⍵[1]⌷⍺)@(3⌷⍵)⊢⍺} ⋄ seti←{⍵[1]@(3⌷⍵)⊢⍺}\n",
    "gtrr←>rr\n",
    "eqrr←=rr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY19←lines'data/2018/19.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "IPREG←⍎4↓0⊃DAY19"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "metadata": {},
   "outputs": [],
   "source": [
    "CODE←{(⊂4↑⍵),⍎4↓⍵}¨1↓DAY19"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Run←{ ⍝ ⍺ is code, ⍵ is regs\n",
    "    ip←IPREG⊃⍵\n",
    "    ip≥≢⍺:0⊃⍵\n",
    "    opc←⊃instr←ip⊃⍺\n",
    "    regs←⍵ (⍎opc) instr\n",
    "    regs[IPREG]+←1\n",
    "    ⍺∇regs\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "2640\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←CODE Run 0 0 0 0 0 0\n",
    "assert Part1=2640"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2 requires a different approach. Starting with `reg[0]←1` is a very different proposition. There are two nested loops, the key one the section at ip=3-11. In all it basically looks like this:\n",
    "\n",
    "    reg←0 1 10551432 1 1 3 ⍝ state when we enter loop\n",
    "     \n",
    "    :While reg[3]≤reg[2]\n",
    "        reg[1]←1\n",
    "        :While reg[1]≤reg[2]\n",
    "            :If (reg[3]×reg[1])=reg[2]\n",
    "                reg[0]+←reg[3]\n",
    "            :EndIf\n",
    "            reg[1]←1\n",
    "        :EndWhile\n",
    "        reg[3]+←1\n",
    "    :EndWhile\n",
    "   \n",
    "so that's two nested loops to 10,551,432 -- too much to run on this machine.\n",
    "\n",
    "However, we can optimise away the inner loop completely, as shown below, as it only modifies reg[0] whenever reg[3] divides reg[2]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day19p2←{\n",
    "    ⍵[3]>⍵[2]:⍵[0]\n",
    "    0=⍵[3]|⍵[2]:∇(⍵[0]+⍵[3]),⍵[1],⍵[2],⍵[3]+1\n",
    "    ∇1+@3⊢⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">        \n",
       "27024480\n",
       "        \n",
       "</span>"
      ]
     },
     "execution_count": 133,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←Day19p2 0 1 10551432 1\n",
    "assert 27024480=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 20: A Regular Map\n",
    "https://adventofcode.com/2018/day/20\n",
    "\n",
    "Traverse a maze and find the longest shortest path between the start point and any other point. For part 2, count the number of points reachable in at least 1000 steps. Depth-first search. Message for my future self: is there a better array programming solution to be had here?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY20←1↓¯1↓line'data/2018/20.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day20←{\n",
    "    (y x py px)←0\n",
    "    pattern←⍵\n",
    "    loc←1500⌶,⊂y x\n",
    "    dist←,0\n",
    "    Update←{ ⍝ Bleurgh. Half the kindom for a hash table!\n",
    "        (⊂y x)∊loc:dist[loc⍳⊂y x]←dist[loc⍳⊂y x]⌊1+dist[loc⍳⊂py px]\n",
    "        dist,←nd⊣loc,←(⊂y x)⊣nd←1+dist[loc⍳⊂py px]\n",
    "        ⍬\n",
    "    }\n",
    "    Move←{('NESW'⍳⍵)⊃(¯1 0)(0 1)(1 0)(0 ¯1)}\n",
    "    ⍬ { ⍝ Depth-first traverse\n",
    "        0=≢⍵:dist\n",
    "        (py px)⊢←y x\n",
    "        ch←1↑⍵\n",
    "        '('=ch:(⍺,⊂y x)∇1↓⍵            ⍝ Push\n",
    "        ')'=ch:(¯1↓⍺)∇1↓⍵⊣(y x)⊢←⊃¯1↑⍺ ⍝ Pop\n",
    "        '|'=ch:⍺∇1↓⍵⊣(y x)⊢←⊃¯1↑⍺      ⍝ Branch\n",
    "        (y x)+←Move ch                 ⍝ Move\n",
    "        ⍺∇1↓⍵⊣Update⍬                  ⍝ Store shortest path to this loc\n",
    "    } pattern\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "3930\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dist←Day20 DAY20\n",
    "⊢Part1←⌈/dist\n",
    "assert Part1=3930"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "8240\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←+/dist≥1000\n",
    "assert Part2=8240"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 21: Chronal Conversion\n",
    "https://adventofcode.com/2018/day/21\n",
    "\n",
    "Ok, the whole asmbunny thing is becoming rather tiring now."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, some hand-disassembly is required. Part 2 is not naively brute-forceable in APL. [It is a ~20s wait in C++](https://gist.github.com/xpqz/0b7a4e583f6f0080a50f0904bac900d4), and [an hour in Python](https://github.com/xpqz/aoc-18/blob/master/day21.py).\n",
    "\n",
    "Part1: looking at the data, we see that line 28 is the\n",
    "exit condition we need to trigger. Run the program until\n",
    "the first time line 28 is hit, and the answer is the value\n",
    "in register[2]\n",
    "\n",
    "    ip--inst-------A--------B-C\n",
    "    ---------------------------\n",
    "    0:  seti     123        0 2\t\t\n",
    "    1:  bani       2      456 2\n",
    "    2:  eqri       2       72 2 COND reg[2] == 72\n",
    "    3:  addr       2        1 1\n",
    "    4:  seti       0        0 1 GOTO 1\n",
    "    5:  seti       0        3 2\t\t\n",
    "    6:  bori       2    65536 5 REG 5 = REG 2 | 65536\n",
    "    7:  seti 4843319        1 2\t\t\n",
    "    8:  bani       5      255 4\n",
    "    9:  addr       2        4 2\n",
    "    10: bani       2 16777215 2     \n",
    "    11: muli       2    65899 2\t\t\n",
    "    12: bani       2 16777215 2\n",
    "    13: gtir     256        5 4 COND 256 > reg[5]\n",
    "    14: addr       4        1 1\n",
    "    15: addi       1        1 1\n",
    "    16: seti      27        4 1 GOTO 28\n",
    "    17: seti       0        7 4\t\t\n",
    "    18: addi       4        1 3\n",
    "    19: muli       3      256 3\n",
    "    20: gtrr       3        5 3 COND reg[3] > reg[5]\n",
    "    21: addr       3        1 1\n",
    "    22: addi       1        1 1\n",
    "    23: seti      25        0 1 GOTO 26\n",
    "    24: addi       4        1 4\n",
    "    25: seti      17        0 1 GOTO 18\n",
    "    26: setr       4        1 5 REG 5 = REG 4 \n",
    "    27: seti       7        3 1 GOTO 8\n",
    "    28: eqrr       2        0 4 COND reg[2] == reg[0] ⍝ Only place reg[0] is consulted\n",
    "    29: addr       4        1 1\n",
    "    30: seti       5        3 1 GOTO 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY21←lines'data/2018/21.txt'\n",
    "IPREG←⍎4↓0⊃DAY21\n",
    "CODE←{(⊂4↑⍵),⍎4↓⍵}¨1↓DAY21"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [],
   "source": [
    "bin←{(32⍴2)⊤⍵}\n",
    "rr←{((⍵[1]⌷⍺) ⍺⍺ (⍵[2]⌷⍺))@(3⌷⍵)⊢⍺}           ⍝ reg-reg\n",
    "ri←{((⍵[1]⌷⍺) ⍺⍺ (⍵[2]))@(3⌷⍵)⊢⍺}             ⍝ reg-val\n",
    "ir←{((⍵[1]) ⍺⍺ (⍵[2]⌷⍺))@(3⌷⍵)⊢⍺}             ⍝ val-reg\n",
    "brr←{(2⊥(bin ⍵[1]⌷⍺) ⍺⍺ bin ⍵[2]⌷⍺)@(3⌷⍵)⊢⍺}  ⍝ reg-reg (binary)\n",
    "bri←{(2⊥(bin ⍵[1]⌷⍺) ⍺⍺ bin ⍵[2])@(3⌷⍵)⊢⍺}    ⍝ reg-val (binary)\n",
    "addr←+rr ⋄ addi←+ri\n",
    "mulr←×rr ⋄ muli←×ri\n",
    "banr←∧brr ⋄ bani←∧bri\n",
    "borr←∨brr ⋄ bori←∨bri\n",
    "setr←{(⍵[1]⌷⍺)@(3⌷⍵)⊢⍺} ⋄ seti←{⍵[1]@(3⌷⍵)⊢⍺}\n",
    "gtir←>ir ⋄ gtri←>ri ⋄ gtrr←>rr\n",
    "eqir←=ir ⋄ eqri←=ri ⋄ eqrr←=rr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Run←{ ⍝ ⍺ is code, ⍵ is regs\n",
    "    ip←IPREG⊃⍵\n",
    "    ip≥≢⍺:⍵\n",
    "    ip=28:⍵\n",
    "    opc←⊃instr←ip⊃⍺\n",
    "    regs←⍵ (⍎opc) instr\n",
    "    regs[IPREG]+←1\n",
    "    ⍺∇regs\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">       \n",
       "8797248\n",
       "       \n",
       "</span>"
      ]
     },
     "execution_count": 160,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←2⊃CODE Run 0 0 0 0 0 0\n",
    "assert Part1=8797248"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2: the brute-force approach would be to keep recording the reg[2] values seen at ip 28 until we have a recurrence. Unfortunately, that takes a loooong time -- too long (trust me, I tried).\n",
    "\n",
    "...so we're back to actually figuring out what the asmbunny code _does_. After some long and tedious pen & paper scribbles and lots of binary bit twiddling later, we arrive at something like the below for the value in reg[2] at ip=28. We could of course have used this for part 1, too, but we'll leave the above as a warning for the unwary.\n",
    "\n",
    "On the plus side - fast af."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day21p2←{\n",
    "    SEEN,←⍵\n",
    "    a←dec ⍵ or 65536\n",
    "    b←4843319\n",
    "    b+←dec a and 255 ⋄ b←dec b and 16777215\n",
    "    b×←65899 ⋄ b←dec b and 16777215\n",
    "    b+←dec (dec 8 rs bin a) and 255 ⋄ b←dec b and 16777215\n",
    "    b×←65899 ⋄ b←dec b and 16777215\n",
    "    b+←dec (dec 16 rs bin a) and 255 ⋄ b←dec b and 16777215\n",
    "    b×←65899\n",
    "    dec b and 16777215\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "metadata": {},
   "outputs": [],
   "source": [
    "SEEN←⍬ ⋄ _←Day21p2⍣{⍺∊SEEN}⊢0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">       \n",
       "3007673\n",
       "       \n",
       "</span>"
      ]
     },
     "execution_count": 192,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←⊃¯1↑SEEN       ⍝ Last element before the recurring\n",
    "assert 3007673=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 22: Mode Maze\n",
    "https://adventofcode.com/2018/day/22\n",
    "\n",
    "This is clearly the year of colossal caves and asmbunnies..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 242,
   "metadata": {},
   "outputs": [],
   "source": [
    "DEPTH←10689\n",
    "TARGET←722 11 ⍝ Y X"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 246,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "GI←{\n",
    "    ¯1≠⊃CAVE[⊂⍵]:⊃CAVE[⊂⍵]\n",
    "    (0 0≡⍵)∨TARGET≡⍵:CAVE[⊂⍵]←0\n",
    "    (y x)←⍵\n",
    "    y=0:CAVE[⊂⍵]←x×16807\n",
    "    x=0:CAVE[⊂⍵]←y×48271\n",
    "    ⊢CAVE[⊂⍵]←(EL y,x-1)×EL x,⍨y-1\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 247,
   "metadata": {},
   "outputs": [],
   "source": [
    "EL←{20183|DEPTH + GI ⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 248,
   "metadata": {},
   "outputs": [],
   "source": [
    "CAVE←(1+TARGET)⍴¯1\n",
    "_←GI¨,⍳ 1+TARGET"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 239,
   "metadata": {},
   "outputs": [],
   "source": [
    "RISK←3|20183|DEPTH+CAVE ⍝ ♥ APL"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 240,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "8575\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 240,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←+/∊RISK\n",
    "assert 8575=Part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Well, that was nice, wasn't it?\n",
    "\n",
    "Part 2 becomes another graph path finding exercise, with a small twist: at each location we carry a bit of state which affects the neighbourhood function. This means that for each location we can move to any other location as defined by the RISK array and our state. So our neighbourhood function must include a \"stay-put-change-state\" mode, which has a cost. Other than that, should be a standard cheapest path Dijkstra effort, cut down to only keep track of path cost, not the path itself.\n",
    "\n",
    "As I recall, we have one of those on tap since a previous year of this.... ah yes, day 13, 2016. \n",
    "\n",
    "A complication is that the graph/cave is essentially unbounded. We need some kind of heuristic cut-off which we can trial-and-error by just enlarging the RISK array a bit, and cutting off coordinates that drift too far away from the target."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 241,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────────────────────────────────────────────────────────────┐\n",
       "│Linked: #.heapq → /Users/stefan/work/dyalog/AoCDyalog/src/heapq│\n",
       "└───────────────────────────────────────────────────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 241,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "]LINK.Create heapq src/heapq ⍝ All good graph algorithms need a priority queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TODO: rewrite this horror as a dfn.."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 254,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "R←N4 arg;y;x;tool;squares;s;vals;square;regionTool;newTool;cost\n",
    "(y x tool)←arg ⍝ tool → currently hefted tool\n",
    "squares←(~+/¨¯1=s)/s←(⊂y x)+(+,-)(0 1)(1 0)\n",
    "vals←⍬\n",
    ":For square :In squares\n",
    "    :If 0 0≢square≥⍴RISK\n",
    "        :Continue\n",
    "    :EndIf\n",
    "    regionTool←RISK[⊂square]\n",
    "    :For newTool :In ⍳3\n",
    "        :If regionTool≠newTool\n",
    "            cost←1\n",
    "            :If tool ≠ newTool\n",
    "                cost←8\n",
    "            :EndIf\n",
    "            vals,←⊂∊square newTool cost\n",
    "        :EndIf\n",
    "    :EndFor\n",
    ":EndFor\n",
    "R←vals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 253,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Dijkstra←{\n",
    "    ⍝ A spin on the classic Dijkstra best-first-search algorithm.\n",
    "    ⍝ Only interested in the path cost, not the path itself.\n",
    "    costKeys←1500⌶,⍵                                           \n",
    "    costVals←,0\n",
    "    Cost←{⍵∊costKeys:costVals[⊃costKeys⍳⍵] ⋄ ⌊/⍬} ⍝ Default cost is +infinity\n",
    "    _←{\n",
    "        (frontier queueItem)←##.heapq.Pop ⍵\n",
    "        (totalCost current)←queueItem\n",
    "        (⊃current)≡TARGET,1:⍬\n",
    "        frontier {\n",
    "            0=≢⍵:⍺\n",
    "            (y x tool cost)←0⊃⍵\n",
    "            newCost←cost+totalCost\n",
    "            0 0≢y x≥2×TARGET:⍺∇1↓⍵       ⍝ Heuristic cut-off at 2× TARGET\n",
    "            newCost≥Cost ⊂TARGET,1:⍺∇1↓⍵ ⍝ Too costly!\n",
    "            newCost≥Cost ⊂y x tool:⍺∇1↓⍵ ⍝ Old pos, but at worse cost; bail\n",
    "            queue←⍺ ##.heapq.Push ⊂newCost(⊂y x tool)\n",
    "            (⊂y x tool)∊costKeys:queue∇(1↓⍵)⊣costVals[⊃costKeys⍳⊂y x tool]←newCost\n",
    "            costKeys,←⊂y x tool ⋄ costVals,←newCost                            \n",
    "            queue∇1↓⍵   \n",
    "        } N4 ⊃current\n",
    "    }⍣{##.heapq.Empty ⍺} ##.heapq.Push⊂0 ⍵                    \n",
    "    ¯2+Cost ⊂TARGET,1 ⍝ Remove endpoint steps\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 249,
   "metadata": {},
   "outputs": [],
   "source": [
    "CAVE←800 25⍴¯1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 250,
   "metadata": {},
   "outputs": [],
   "source": [
    "_←GI¨,⍳ 800 25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 251,
   "metadata": {},
   "outputs": [],
   "source": [
    "RISK←3|20183|DEPTH+CAVE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 256,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "999\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 256,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←Dijkstra ⊂0 0 1\n",
    "assert 999=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 23: Experimental Emergency Teleportation\n",
    "https://adventofcode.com/2018/day/23\n",
    "\n",
    "This is a difficult problem, even if it starts easy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 278,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY23←↑⍎¨¨'-?\\d+'⎕s'&'¨lines'data/2018/23.txt'\n",
    "RADII←⊢/DAY23\n",
    "CENTRES←DAY23[;⍳3]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The strongest bot is that which has the largest radius."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 279,
   "metadata": {},
   "outputs": [],
   "source": [
    "STRONGEST←⊃⍒RADII"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 1, we seek the total number of bots whose centres fall within the radius of the strongest bot, identified above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 281,
   "metadata": {},
   "outputs": [],
   "source": [
    "MhD←{+/|⍺-⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 285,
   "metadata": {},
   "outputs": [],
   "source": [
    "BOSS←STRONGEST⌷CENTRES"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 290,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "704\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 290,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←+/(STRONGEST⊃RADII)≥BOSS∘MhD ¨↓CENTRES\n",
    "assert 704=Part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And so for part 2, we seek the point closest to the origin which is in reach of the largest number of bots. This is a hard problem, quite possibly the hardest of all AoC problems 2015-2018.\n",
    "\n",
    "After failing to solve this a lot, it turns out that problem can be reduced to a projection from 3d to 1d. A couple of joyful mathematical deep-dives on [Numberphile](https://www.youtube.com/channel/UCoxcjq-8xIDTYp3uz647V5A) give some clues as to why this works as it does:\n",
    "\n",
    "* [Balls and Cones](https://www.youtube.com/watch?v=lubGnk0UZt0)\n",
    "* [Earthquakes, Circles and Spheres](https://www.youtube.com/watch?v=2vnqSwWAn34&list=PLt5AfwLFPxWI9eDSJREzp1wvOJsjt23H_)\n",
    "\n",
    "The solution below was inspired by \n",
    "\n",
    "https://www.reddit.com/r/adventofcode/comments/a8s17l/2018_day_23_solutions/ecdqzdg/\n",
    "\n",
    "We project each sphere onto a line so that we end up with a range -radius to radius centered around the point corresponding to the manhattan distance to the centre. We then create a vector, ordered by distance, of 1 for the start of a range and ¯1 for the end of a range, indicating if the bot contributes to the nesting or not. We then find the maximum sum along the vector."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 345,
   "metadata": {},
   "outputs": [],
   "source": [
    "overlaps←{⊃,/,⊆¨⍵}⍣≡{d←+/|⍵⋄((0⌈d-⍺),1) (¯1,⍨d+⍺+1)}/RADII,⍪↓CENTRES ⍝"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 346,
   "metadata": {},
   "outputs": [],
   "source": [
    "distOrder←0(⊢⌷⍨∘⊂∘⍋⌷⍤1)↑overlaps\n",
    "closest←¯1+⌈/+\\⊢/0(⊢⌷⍨∘⊂∘⍋⌷⍤1)distOrder  ⍝ ♥ APL -- scan can be pure magic..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 347,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">         \n",
       "111960222\n",
       "         \n",
       "</span>"
      ]
     },
     "execution_count": 347,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←⊃closest⌷distOrder\n",
    "assert 111960222=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 24: Immune System Simulator 20XX\n",
    "https://adventofcode.com/2018/day/24\n",
    "\n",
    "It's starting to feel a lot like Christmas.\n",
    "\n",
    "This was annoying, too."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "'segs'⎕CY'dfns'\n",
    "DAY24←lines'data/2018/24.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Parse←{\n",
    "    team←⍺\n",
    "    types←'fire' 'bludgeoning' 'slashing' 'cold' 'radiation'\n",
    "    numbers←⍎¨'\\d+'⎕s'&'⊢⍵\n",
    "    attack←⊃types⍳'\\s([^\\s]+)\\sdamage'⎕s'\\1'⊢⍵\n",
    "    immunities←types⍳', '∘segs⊃'immune to ([^;)]+)'⎕s'\\1'⊢⍵\n",
    "    weaknesses←types⍳', '∘segs⊃'weak to ([^;)]+)'⎕s'\\1'⊢⍵\n",
    "    {⍵⊣⍵.(team units hp damage initiative attack immune weak)←team,numbers,attack,(⊂1@immunities⊢5⍴0),⊂1@weaknesses⊢5⍴0}⎕NS'' \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "Dead←{⍵.units≤0}\n",
    "EffectivePower←{⍵.units×⍵.damage}\n",
    "AttackOrder←{⍵[⍒↓⍉↑(EffectivePower ⍵)({⍵.initiative} ⍵)]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Damage←{ ⍝ ⍺ is us, ⍵ is them\n",
    "   (Dead ⍺)∨Dead ⍵:0\n",
    "   ⍵.immune[⍺.attack]:0\n",
    "   ep←EffectivePower ⍺\n",
    "   ⍵.weak[⍺.attack]:2×ep\n",
    "   ep\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Attack←{ ⍝ ⍺ attacks ⍵\n",
    "    ⍵≡⍬:0\n",
    "    ⍵.immune[⍺.attack]:0\n",
    "    damage←×/⍺.units,⍺.damage,1 2[⍵.weak[⍺.attack]]\n",
    "    killed←⌊damage÷⍵.hp\n",
    "    ⍵.units-←killed\n",
    "    killed\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Select←{\n",
    "    targets←⍵\n",
    "    ⍬ {\n",
    "        0=≢⍵:(targets,⊂⍬)[⍺] ⍝ Inject ⍬ where no target was found\n",
    "        attacker←0⊃⍵\n",
    "        damage←attacker∘.Damage targets\n",
    "        order←⍒↓⍉↑(damage)(EffectivePower targets)({⍵.initiative} targets)\n",
    "        pick←order[⍸<\\(~order∊⍺)∧0≠damage[order]]\n",
    "        ⍬≡pick:(⍺,≢targets)∇1↓⍵\n",
    "        (⍺,pick)∇1↓⍵\n",
    "    } ⍺\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day24←{\n",
    "    count←0\n",
    "    {\n",
    "        (immune infect)←⍵\n",
    "        aoim←AttackOrder immune\n",
    "        aoinf←AttackOrder infect\n",
    "        cohort←aoim,aoinf\n",
    "        initiative←⍒{⍵.initiative} cohort\n",
    "        ordered←cohort[initiative]\n",
    "        targets←((aoim Select infect),aoinf Select immune)[initiative]\n",
    "        _←Attack⌿↑(ordered)(targets)\n",
    "        count+←1\n",
    "        ⍵\n",
    "    }⍣{(immune infect)←⍺ ⋄ (∧/Dead infect)∨(∧/Dead immune)∨count>3000}⊢⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "18346\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IMMUNE←0 Parse¨DAY24[1+⍳10]\n",
    "INFECT←1 Parse¨DAY24[13+⍳10]\n",
    "_←Day24 IMMUNE INFECT\n",
    "⊢Part1←+/{0⌈⍵.units} IMMUNE,INFECT\n",
    "assert 18346=Part1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2: if we boost the immune cells' damage by the smallest integer that results in the infection being defeated, then what number of units remain?\n",
    "\n",
    "The complication here is that we need to run the fight many times. We can binary search to cut down the search space a bit. Additionally, some boost levels 'stall' -- for example where the remaining groups in one camp are immune to the attacks of the remaining attackers. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "Boost←{⍺∘{⍵.damage+←⍺} ⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day24p2←{\n",
    "    last←0\n",
    "    {\n",
    "        ⍺←1\n",
    "        immune←0 Parse¨DAY24[1+⍳10]\n",
    "        infect←1 Parse¨DAY24[13+⍳10]\n",
    "        ⍵≤⍺:last-1\n",
    "        factor←⌊2÷⍨⍵+⍺\n",
    "        _←factor Boost immune\n",
    "        _←Day24 immune infect\n",
    "        ∧/Dead immune: factor ∇ ⍵\n",
    "        ∧/Dead infect: ⍺∇factor⊣last⊢←+/{0⌈⍵.units} immune\n",
    "        (⍺+1) ∇ ⍵ ⍝ Fight ended in a draw.\n",
    "    } ⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "8698\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part2←Day24p2 50\n",
    "assert 8698=Part2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 25: Four-Dimensional Adventure\n",
    "\n",
    "https://adventofcode.com/2018/day/25\n",
    "\n",
    "Finally! Not a day too early, I'd say.\n",
    "\n",
    "We seek the number of connected components in the graph where indices are connected iff their manhattan distance is 3 or lower. \n",
    "\n",
    "[Apparently](https://math.stackexchange.com/questions/1612616/how-to-find-null-space-basis-directly-by-matrix-calculation) the connected components of a graph represented as an adjacency matrix is the basis of the kernel of the corresponding Laplacian.\n",
    "\n",
    "However, here's the punter solution: just count the clusters using breadth-first search."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "DAY25←⍎¨¨'(-?\\d+)'⎕s'\\1'¨lines'data/2018/25.txt'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "ADJ←DAY25∘.{(+/|⍺-⍵)≤3} DAY25"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "BFS←{0=≢⍵:⍺⋄(⍺,1↑⍵)∇((1↓⍵)∪⍸ADJ[⊃1↑⍵;])~⍺}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day25←{seen←⍬⋄0{0=≢⍵:⍺⋄n←1↑⍵⋄n∊seen:⍺∇1↓⍵⋄seen,←⍬ BFS n⋄(⍺+1)∇1↓⍵} ⍳⊃⍴ADJ}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "324\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢Part1←Day25⍬\n",
    "assert 324=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
}