Advent of Code 2016 Dyalog APL.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Advent of Code 2016, 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%202016%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": 159,
   "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": 159,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→────────────────┐\n",
       "│Was OFF -fold=off│\n",
       "└─────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 159,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⎕IO←1\n",
    "]box on -style=max -trains=tree -fns=on\n",
    "]rows on -fold=3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 1: No Time for a Taxicab\n",
    "https://adventofcode.com/2016/day/1\n",
    "\n",
    "Given a set of relative directions (\"turn right, travel 45 units\"), what is the final [Manhattan](https://en.wikipedia.org/wiki/Taxicab_geometry) distance from origin?\n",
    "\n",
    "There are many different ways to solve this. Here we simply trace out the full path, converting relative directions to absolute positions, and check the last point for the answer.\n",
    "\n",
    "We can convert from relative to absolute direction using a simple vector `1 2 3 4` for north, east, south, west respectively. Turning right corresponds to a vector rotation of 1, and turning left a rotation of ¯1.\n",
    "\n",
    "Key insight is that we need to \"connect the dots\" between the points referred to in the input data, which only contains the turning points."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY1←,{(1↑⍵),⍎1↓⍵}¨⎕CSV'data/2016/01.txt'     ⍝ Convert strings to numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "ExpandPath←{\n",
    "    pos←0 0 ⋄ dir←1 2 3 4\n",
    "    {⊃,/,⊆¨⍵}⍣≡{                              ⍝ Flatten returned list\n",
    "        (rl mag)←⍵\n",
    "        dir {⍵='R':(1⊖dir)⋄¯1⊖dir}←rl         ⍝ Rotate direction vector \n",
    "        unitv←dir[1]⊃(0 ¯1)(1 0)(0 1)(¯1 0)   ⍝ Find corresponding unit vector in new direction\n",
    "        points←pos∘+¨↓(⍳mag)∘.×unitv          ⍝ Expand the \"gaps\"\n",
    "        pos+←mag×unitv                        ⍝ Update the turning point\n",
    "        points\n",
    "    }¨⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our start state is `dir←1 2 3 4 ⋄ pos←0 0`, which is \"north-facing\" and our origin. For the answer we're only interested in the final position, and the Manhattan distance is simply the sum of the absolute values of x and y of the final position."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "239\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day1p1←{+/|⊃¯1↑ExpandPath ⍵}     ⍝ Sum absolute values of x and y for last position\n",
    "Day1p1 DAY1 ⍝ 239        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we need to find the first position visited twice. We can use the built-in [key](http://help.dyalog.com/17.1/index.htm#Language/Primitive%20Operators/Key.htm?Highlight=%E2%8C%B8) function (`⌸`) to build a frequency table, which will be ordered in the same way as the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day1p2←{firstRepeat←1⌷⍸{⍵[2]=2}¨↓{⍺,≢⍵}⌸path←ExpandPath ⍵⋄+/⊃|path[firstRepeat]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "141\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 122,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day1p2 DAY1 ⍝ 141"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 2: Bathroom Security\n",
    "https://adventofcode.com/2016/day/2\n",
    "\n",
    "Create a matrix where the row number is the starting digit, and cols 1-4 corresponding to the values for a move URDL respectively. We can then map the letters URDL to numbers 1 2 3 and 4 respectively.\n",
    "\n",
    "Parts 1 and 2 are basically identical, bar the initial setup of this matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 376,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY2←⊃⎕NGET'data/2016/02.txt'1\n",
    "KEYMAP←9 4 ⍴ 1 2 4 1 2 3 5 1 3 3 6 2 1 5 7 4 2 6 8 4 3 6 9 5 4 8 7 7 5 9 8 7 6 9 9 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 377,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day2←{⍺←5⋄0=≢⍵:1↓⍺⋄(⍺,((⊃¯1↑⍺) {⍵≡⍬:⍺⋄KEYMAP[⍺;1⊃⍵]∇1↓⍵} 'URDL'⍳1⊃⍵))∇1↓⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 383,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→────────┐\n",
       "│3 5 7 4 9│\n",
       "└~────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 383,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day2 DAY2 ⍝ 35749"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we have a different shape keypad, and a few more keys: A, B, C and D. We map those to 10-13 and tediously construct a new key map (by hand)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "metadata": {},
   "outputs": [],
   "source": [
    "KEYMAP←13 4 ⍴ 1 1 3 1 2 3 6 2 1 4 7 2 4 4 8 3 5 6 5 5 2 7 10 5 3 8 11 6 4 9 12 7 9 9 9 8 6 11 10 10 7 12 13 10 8 12 12 11 11 13 13 13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→────────┐\n",
       "│9 3 6 5 C│\n",
       "└+────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 187,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "('ABCD',⍨⍳9)[Day2 DAY2] ⍝ 9365C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 3: Squares With Three Sides\n",
    "https://adventofcode.com/2016/day/3\n",
    "\n",
    "Not much to do here apart from massaging the input array into the right shape."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY3←⍎¨⊃⎕NGET'data/2016/03.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "1050\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 202,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Valid←{(a b c)←⍵⋄((a+b)>c)∧((a+c)>b)∧((c+b)>a)}\n",
    "+/Valid¨DAY3 ⍝ 1050"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "1921\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 207,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PART2←⍉↑DAY3\n",
    "+/Valid¨↓(3÷⍨≢∊PART2) 3 ⍴ ∊PART2 ⍝ 1921"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 4: Security Through Obscurity\n",
    "https://adventofcode.com/2016/day/4\n",
    "\n",
    "A set of strings, consisting of letters and hyphens (the \"encrypted name\"), followed by digits (the \"sector id\"), followed by more letters enclosed in square brackets (the \"checksum\").\n",
    "\n",
    "A string is valid iff the checksum is the five most common letters in the encrypted name, in order, with ties broken by alphabetization."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "metadata": {},
   "outputs": [],
   "source": [
    "RegexGroups←{⍺⎕S{⍵.(1↓Lengths↑¨Offsets↓¨⊂Block)} ⊢ ⍵}\n",
    "DAY4←'^([^\\d]+)(\\d+)\\[([^\\]]+)\\]$' RegexGroups ⊃⎕NGET'data/2016/04.txt'1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To validate a given string, we do the following:\n",
    "\n",
    "1. Remove all hyphens\n",
    "2. Create a letter histogram mapping each letter to its frequency\n",
    "3. Sort the histogram in descending order on frequency and separate keys and values into vectors\n",
    "4. Partition the keys vector based on neighbouring letters with the same frequencies\n",
    "5. Sort each partition alphabetically, and flatten to single character vector\n",
    "6. If the first 5 letters match the checksum, return the sector id (converted to number).\n",
    "7. Else return 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 240,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day4p1←{\n",
    "    (keys vals)←↓⍉{⍵[⍒⍵[;2];]}{⍺,≢⍵}⌸(~∘'-')1⊃⍵  ⍝ Remove hyphens, make frq table ordered by descending frq\n",
    "    p←5↑∊{(⊂⍋⍵)⌷⍵}¨keys⊂⍨1,2≠/vals               ⍝ Partition, sort, merge, pick first 5\n",
    "    p≡3⊃⍵:⍎2⊃⍵⋄0\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 241,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">      \n",
       "245102\n",
       "      \n",
       "</span>"
      ]
     },
     "execution_count": 241,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/Day4p1¨DAY4 ⍝ 245102"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we are asked to 'decrypt' the string, meaning a circular shift of each letter by the sector id. We can achieve this easily using the dyadic form of [⊖](http://help.dyalog.com/17.1/index.htm#Language/Symbols/Circle%20Bar.htm?Highlight=%E2%8A%96) and the system function [⎕A](http://help.dyalog.com/17.1/index.htm#Language/System%20Functions/a.htm) which holds the upper case letters. \n",
    "\n",
    "1. Convert string to upper-case\n",
    "2. For each letter, rotate ⎕A until the letter is first\n",
    "3. Rotate by the sector id\n",
    "\n",
    "For the answer, we're searching for 'NORTHPOLE' amongst the decrypted strings. We can achieve this succinctly using a sequence of maps. However, would be more efficient by stopping after the target string was found.\n",
    "\n",
    "The odd-looking [819⌶](http://help.dyalog.com/17.1/index.htm#Language/Primitive%20Operators/Case%20Convert.htm?Highlight=819%E2%8C%B6) is a system function to convert a string to uppercase."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 242,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day4p2←{R←⍎2⊃⍵⋄∊{⍵='-':' '⋄1↑(R+¯1+⎕A⍳⍵)⊖⎕A}¨1(819⌶)1⊃⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 243,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "324\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 243,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⍎2⊃DAY4⊃⍨⊃⍸0≠⊃¨'NORTHPOLE'∘(⍸⍷)¨Day4p2¨DAY4 ⍝ 324"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 5: How About a Nice Game of Chess?\n",
    "https://adventofcode.com/2016/day/5\n",
    "\n",
    "Skipping this, as needs MD5 which isn't available for Dyalog on a Mac :("
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 6: Signals and Noise\n",
    "https://adventofcode.com/2016/day/6\n",
    "\n",
    "Transpose input array. For each row, create a letter histogram, sort based on descending (part 1) and ascending (part 2) frequency, and pick the first letter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 266,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→───────┐\n",
       "│qrqlznrl│\n",
       "└────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 266,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→───────┐\n",
       "│kgzdfaon│\n",
       "└────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 266,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DAY6←↓⍉↑⊃⎕NGET'data/2016/06.txt'1\n",
    "∊{1 1⌷⍵[⍒⍵[;2];]}¨{⍺,≢⍵}⌸¨DAY6 ⍝ Part 1: qrqlznrl\n",
    "∊{1 1⌷⍵[⍋⍵[;2];]}¨{⍺,≢⍵}⌸¨DAY6 ⍝ Part 2: kgzdfaon"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 7: Internet Protocol Version 7\n",
    "https://adventofcode.com/2016/day/7\n",
    "\n",
    "Some medium-level regexing required. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 272,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY7←⊃⎕NGET'data/2016/07.txt'1\n",
    "RegexGroups←{⍺⎕S{⍵.(1↓Lengths↑¨Offsets↓¨⊂Block)} ⊢ ⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 273,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Abba←{\n",
    "    matches←'(.)(.)\\2\\1'⎕S'&'⊢⍵\n",
    "    0=≢matches:0\n",
    "    invalid←≢'(.)\\1\\1\\1'⎕S'&'⊢matches\n",
    "    0≠invalid-⍨≢matches\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 274,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day7p1←{(Abba ⍵)∧~Abba '\\[.+?\\]'⎕S'&'⊢⍵}  ⍝ ABBAs in body, and no ABBAs in hypernet sections"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 275,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "115\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 275,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/Day7p1¨DAY7 ⍝ 115"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, in the aba captures, we place the capture groups in an unanchored positive lookahead in order to see any overlapping matches, like in the example given: `zazbz[bzb]cdb`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 276,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day7p2←{\n",
    "    hypernets←∊'\\[.+?\\]'⎕S'&'⊢⍵\n",
    "    rest←'\\[.+?\\]'⎕R''⊢⍵\n",
    "    aba←'(?=(.)(.)\\1)' RegexGroups rest    \n",
    "    0=≢aba:0\n",
    "    bab←∊{(∊⍵)[2 1 2]⎕S'&'⊢hypernets}¨aba\n",
    "    (≢bab)>0\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 277,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "231\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 277,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/Day7p2¨DAY7 ⍝ 231"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 8: Two-Factor Authentication\n",
    "https://adventofcode.com/2016/day/8\n",
    "\n",
    "Some more array-wrangling -- APL home court advantage. The coordinates given are 0-based, so we switch to using `⎕IO←0` to avoid arithmetic. We can create the three functions referred to (rect, row, col) and treat the input data as a ready to go program. Note that the abuse of [⍎](http://help.dyalog.com/17.1/index.htm#Language/Symbols/Execute%20Symbol.htm?Highlight=%E2%8D%8E) here (in the absense of Scheme-y macros) is both unsafe and unsavoury."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 334,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "DISPLAY←6 50⍴0\n",
    "rect←{(cols rows)←⍵ ⋄ 1@(⊂⍤0,⍳rows cols)⊢⍺}\n",
    "row←{(A B)←⍵⋄((-B)⊖⍺[A;])@A⊢⍺}\n",
    "col←{⍉(⍉⍺)row⍵}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `Compile` function converts the input rows into strings containing valid APL in terms of the three functions `rect`, `row` and `col`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 335,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Compile←{ \n",
    "    row←⊃'rotate row y=(\\d+) by (\\d+)'⎕R'⍺ row \\1 \\2'¨↓⍵\n",
    "    col←'rotate column x=(\\d+) by (\\d+)'⎕R'⍺ col \\1 \\2'¨row\n",
    "    'rect (\\d+)x(\\d+)'⎕R'⍺ rect \\1 \\2'¨col\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 336,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY8←Compile⊃⎕NGET'data/2016/08.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 337,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day8←{0=≢⍵:⍺⋄(⍎0⊃⍵)∇1↓⍵} ⍝ Run the 'program', top to bottom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 338,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "121\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 338,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/∊DISPLAY Day8 DAY8  ⍝ Part 1: 121"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The display shows a message! Let's highlight it a bit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 346,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→─────────────────────────────────────────────────────────────────────────────────────────────────┐\n",
       "↓0 0 0     0     0   0 0 0     0     0     0 0     0 0 0 0     0 0     0 0 0 0    0 0 0   0        │\n",
       "│0     0   0     0   0     0   0     0   0     0   0         0     0   0            0     0        │\n",
       "│0     0   0     0   0     0   0     0   0         0 0 0     0     0   0 0 0        0     0        │\n",
       "│0 0 0     0     0   0 0 0     0     0   0         0         0     0   0            0     0        │\n",
       "│0   0     0     0   0   0     0     0   0     0   0         0     0   0            0     0        │\n",
       "│0     0     0 0     0     0     0 0       0 0     0 0 0 0     0 0     0 0 0 0    0 0 0   0 0 0 0  │\n",
       "└+─────────────────────────────────────────────────────────────────────────────────────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 346,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(' '@⊢)0=DISPLAY Day8 DAY8 ⍝ Part 2: RURUCEOEIL"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 9: Explosives in Cyberspace\n",
    "https://adventofcode.com/2016/day/9\n",
    "\n",
    "Decompress simple runlength-encoding scheme. Can be succinctly formulated in terms of recursion. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 271,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "DAY9←⊃⊃⎕NGET'data/2016/09.txt'1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A run-length marker is two ints separated by an \"x\" and enclosed in brackets, e.g. (8x2). Let's write a utility function that gets these numbers out (assuming the beginning of the string), and also tacks on the end index -- where the string starts again after the marker. We use `⎕VFI` -- [Verify and Fix Input](http://help.dyalog.com/17.1/index.htm#Language/System%20Functions/vfi.htm?Highlight=%E2%8E%95VFI) -- to convert strings to numbers. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 272,
   "metadata": {},
   "outputs": [],
   "source": [
    "Marker←{(2⊃'x'⎕VFI 1↓¯1↓end↑⍵),end←⍵⍳')'} "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The decompressed length is 1 for each non-compressed character plus the length×count of any encoded sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 368,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day9p1←{\n",
    "    0=≢⍵:⍺\n",
    "    '('≠⊃1↑⍵:(⍺+1)∇1↓⍵               ⍝ Uncompressed character -- add 1 and move on\n",
    "    (length count end)←Marker ⍵\n",
    "    (⍺+length×count)∇(end+length)↓⍵  ⍝ Add length×count and skip the marker and the length when carrying on\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 369,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "74532\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 369,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "0 Day9p1 DAY9 ⍝ 74532"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we need [big int support](http://dfns.dyalog.com/n_big.htm), which we can find in the 'dfns' workspace."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 278,
   "metadata": {},
   "outputs": [],
   "source": [
    "'big'⎕CY'dfns'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Simiar to part 1, but we need an extra recursive step to expand already expanded chunks. Note that this means we're no longer tail-recursive, but the recursive depth is pretty modest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 276,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day9p2←{\n",
    "    0=≢⍵:⍺\n",
    "    '('≠⊃1↑⍵:(⍺ +big 1)∇1↓⍵\n",
    "    (length count end)←Marker ⍵\n",
    "    total←count ×big 0∇length↑end↓⍵  ⍝ Find length of expansion, including any embedded markers\n",
    "    (⍺ +big total)∇(end+length)↓⍵    ⍝ Next, as per part 1\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 277,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────────┐\n",
       "│11558231665│\n",
       "└───────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 277,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "0 Day9p2 DAY9 ⍝ 11558231665"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 10: Balance Bots\n",
    "https://adventofcode.com/2016/day/10\n",
    "\n",
    "Note: as the bots are 0-indexed, we use 0-based indexing.\n",
    "\n",
    "This turned out a bit messier than I had hoped."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 506,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0   \n",
    "DAY10←⊃⎕NGET'data/2016/10.txt'1\n",
    "RegexGroups←{⍺⎕S{⍵.(1↓Lengths↑¨Offsets↓¨⊂Block)}⊢⍵}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to do some massaging to turn the input data into a matrix we can use. Our matrix will consist of rows where the row number is the bot index, and the fields:\n",
    "\n",
    "    type low-target type high-target low high\n",
    "    \n",
    "The `type` fields are booleans where 0 represents another bot, and 1 represents the output register."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 507,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "MakeBots←{\n",
    "    bots←↑'bot (\\d+) gives low to (output|bot) (\\d+) and high to (output|bot) (\\d+)' RegexGroups ⍵\n",
    "    bots[;0]←⍎¨bots[;0]      ⍝ Col 0 to numbers\n",
    "    bots[;1]←(∪⍳⊢)bots[;1]   ⍝ Col 1: 'bot' -> 0, 'output' -> 1\n",
    "    bots[;2]←⍎¨bots[;2]      ⍝ Col 2 to numbers\n",
    "    bots[;3]←(∪⍳⊢)bots[;3]   ⍝ Col 3: 'bot' -> 0, 'output' -> 1\n",
    "    bots[;4]←⍎¨bots[;4]      ⍝ Col 2 to numbers\n",
    "    \n",
    "    bots←(({⍵[⍋⍵[;0];]}bots)[;1 2 3 4],0),0  ⍝ Order by bot-id, drop first col, add two 0 cols for inputs\n",
    "    \n",
    "    ⍝ Set the known values\n",
    "    (vals rows)←↓⍉↑⍎¨¨'value (\\d+) goes to bot (\\d+)' RegexGroups ⍵\n",
    "    bots←vals@(rows,¨4)⊢bots    ⍝ Pretend no dupes\n",
    "    dupe←⊃{({1≠≢⍵}⌸⍵)⌿∪⍵}rows   ⍝ Assume single dupe\n",
    "    bots[dupe;5]←vals[⊃1↑dupe(⍸⍷)rows]\n",
    "    bots (0 0 0) ⍝ Tack on the output register state\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main guts is to distribute the low and high value to other bots (or output registers, part 2) according to the spec. We can use the same function for the low and high transfer as they only differ in which index to look at."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 508,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Give←{\n",
    "    Output←{(1⊃⍵)>2:⍺⋄(0⊃⍵)@(1⊃⍵)⊢⍺}\n",
    "    (bots outv)←⍺ ⋄ (bid offset)←⍵             ⍝ Offest: 0 = low, 1 = high\n",
    "    bot←bid⌷bots\n",
    "    val←bots[bid;4+offset]\n",
    "    tid←bot[1+2×offset] \n",
    "    bots[bid;4+offset]←0                       ⍝ Zero the value we're giving away\n",
    "    bot[2×offset]=1:bots (outv Output val tid)\n",
    "    vals←(tid⌷bots)[4 5],bot[4+offset] \n",
    "    bots[tid;4 5]←1↓vals[⍋vals]                ⍝ Maintain ordering\n",
    "    bots outv\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can only run bots which have two values, so find those, and apply their instruction sets."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 509,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Run←{\n",
    "    Ready←{⍸~(0=⍵[;4])∨0=⍵[;5]}\n",
    "    ⍵ {\n",
    "        0=≢⍵:⍺ \n",
    "        (⍺{(⍺ Give ⍵ 0)Give ⍵ 1}0⊃⍵)∇ 1↓⍵\n",
    "    } Ready 0⊃⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 1, our stopping criterion is that a bot has low=17 and high=61."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 512,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day10p1←{bots←0⊃⍵⋄(⊃⍸17=bots[;4])=⊃⍸61=bots[;5]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 513,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">  \n",
       "54\n",
       "  \n",
       "</span>"
      ]
     },
     "execution_count": 513,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(BOTS OUTV)←Run⍣Day10p1⊢MakeBots DAY10\n",
    "⊃⍸17=BOTS[;4] ⍝ 54"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we stop once we've got data in the first three slots of the output register."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 516,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day10p2←{3=+/0∘<1⊃⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 517,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "7847\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 517,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(BOTS OUTV)←Run⍣Day10p2⊢MakeBots DAY10\n",
    "×/OUTV ⍝ 7847"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 11: Radioisotope Thermoelectric Generators\n",
    "https://adventofcode.com/2016/day/11\n",
    "\n",
    "This problem is somewhat involved to solve for the general case with an A* heuristic search, but let's not go there. The problem is actually solvable with a pen and paper if we make a few observations -- firstly, we're only asked to count the number of steps required for a solution, not actually show any of the actual path steps required. Secondly, by some pen and paper noodling, it can be shown that to move n items up one level requires \n",
    "\n",
    "    2×(n-1)-1\n",
    "    \n",
    "steps. Assuming there is a solution, we can count the number of steps required considering only the _number of elements_, rather than the elements themselves. Instead of generating all possible states, ordering them in terms of fitness etc, we assume that we pick only the optimal state, as we know the cost. Simply empty one floor at a time, moving upwards. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 518,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 524,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day11←{\n",
    "    moves←0 ⋄ elems←+/⍵\n",
    "    _←{\n",
    "        lowest←⊃1↑⍸0∘<⍵ ⍝ Find first non-empty floor\n",
    "        moves+←¯1+2×¯1+lowest⌷⍵\n",
    "        0@lowest⊢⍵[lowest]∘+@(1+lowest)⊢⍵\n",
    "    }⍣{elems=⊃¯1↑⍺}⊢⍵\n",
    "    moves\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 525,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">  \n",
       "33\n",
       "  \n",
       "</span>"
      ]
     },
     "execution_count": 525,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">  \n",
       "61\n",
       "  \n",
       "</span>"
      ]
     },
     "execution_count": 525,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day11 5 1 4 0 ⍝ Part 1: 33\n",
    "Day11 8 5 1 0 ⍝ Part 2: 61"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 12: Leonardo's Monorail\n",
    "https://adventofcode.com/2016/day/12\n",
    "\n",
    "Not much to this -- essentially the same as https://adventofcode.com/2015/day/23. Part 2 is a bit slow, as the input code has some deliberate crude loops that are easily refactored out if we wanted to."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "DAY12←↑{6::⍵⋄⍎⍵}¨¨' '(≠⊆⊢)¨⊃⎕NGET'data/2016/12.txt'1 ⍝ Split on space and convert numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day12←{\n",
    "    mem←⍵\n",
    "    ri←{'abcd'⍳⍵}                               ⍝ Map register name to index\n",
    "    val←{(1=2|⎕DR)⍵:⍵⋄⍺[ri ⍵]}                  ⍝ If ⍵ is an int literal, return it. Otherwise reg lookup\n",
    "    cpy←{(x y)←⍵⋄1∘+@5⊢(⍺ val x)@(ri y)⊢⍺}\n",
    "    jnz←{(x y)←⍵⋄(0>⍨⍺ val x):(⍺ val y)∘+@5⊢⍺⋄1∘+@5⊢⍺}\n",
    "    inc←{x←ri ⊃⍵⋄1∘+@5⊢1∘+@x⊢⍺}\n",
    "    dec←{x←ri ⊃⍵⋄1∘+@5⊢¯1∘+@x⊢⍺}\n",
    "    {\n",
    "        ip←¯1↑⍵\n",
    "        instr←ip⌷mem⋄op←⊃instr\n",
    "        ⍵ (⍎op) 1↓instr         \n",
    "    }⍣{(¯1↑⍺)>≢mem}⍺\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">318003\n",
       "</span>"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1↑0 0 0 0 1 Day12 DAY12 ⍝ Part 1: 318003"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">9227657\n",
       "</span>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1↑0 0 1 0 1 Day12 DAY12 ⍝ Part 2: 9227657 -- note: this takes several minutes to run"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 13: A Maze of Twisty Little Cubicles\n",
    "https://adventofcode.com/2016/day/13\n",
    "\n",
    "Shortest path in a graph. The graph is defined in terms of a neighbourhood function. Once this is formulated, the path can be found using [Dijkstra's shortest path algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm), which is a useful tool to have in the Advent of Code toolbox. The `heapq` namespace can be found in the same repo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">\n",
       "\n",
       "\n",
       "Linked: #.heapq → /Users/stefan/work/dyalog/AoCDyalog/src/heapq\n",
       "</span>"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "]LINK.Create heapq src/heapq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each location is classified as either \"floor\" or \"wall\". We encode this as the function `F`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "F←{(⍺<0)∨⍵<0:0⋄0=2|+/(2∘⊥⍣¯1)1364+(⍺×⍺)+(3×⍺)+⍵+(2×⍺×⍵)+⍵×⍵}     ⍝ The magic function given in the problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The neighbourhood function gives the valid subset of the 4-connected neighbours of a point:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "Neighbours←{(x y)←⊃⍵⋄(F/↑n)/n←(⊂x y)+(¯1 0) (1 0) (0 ¯1) (0 1)}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dijkstra's shortest path algorithm is a form of best-first search. It considers the neighbourhood of the current node, recording best so far total path lengths. Our version assumes that graph edges are unweighed, meaning that the cost of traversing an edge is uniform at 1. By using a heap queue we ensure that we prioritise lower-cost paths."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day13p1←{                   ⍝ Naive Dijkstra's shortest path search, uniform cost 1\n",
    "    start←⍺⋄end←⍵\n",
    "    costKeys←1500⌶,start\n",
    "    costVals←,0\n",
    "    Cost←{⍵∊costKeys:costVals[⊃costKeys⍳⍵] ⋄ ⌊/⍬}\n",
    "    cameFromKeys←1500⌶,start\n",
    "    cameFromVals←,start\n",
    "\n",
    "    _←{\n",
    "        (frontier queueItem)←##.heapq.Pop ⍵\n",
    "        newCost←1+Cost (current←2⊃queueItem)\n",
    "        current≡end:⍬\n",
    "        valid←{newCost<Cost⊂⍵}¨neighbours←Neighbours current\n",
    "        frontier {\n",
    "            0=≢⍵:⍺\n",
    "            vertex←1↑⍵\n",
    "            queue←⍺ ##.heapq.Push ⊂newCost(vertex)\n",
    "            cameFromKeys,←vertex\n",
    "            cameFromVals,←current\n",
    "            vertex∊costKeys:queue∇(1↓⍵)⊣costVals[⊃costKeys⍳vertex]←newCost\n",
    "            costKeys,←vertex ⋄ costVals,←newCost\n",
    "            queue∇1↓⍵   \n",
    "        } valid/neighbours\n",
    "    }⍣{##.heapq.Empty ⍺} ##.heapq.Push⊂0 start\n",
    "\n",
    "    ⍝ Reconstruct the path\n",
    "    path←⍬\n",
    "    _←{path,←⍵⋄cameFromVals[⊃cameFromKeys⍳⍵]}⍣{start≡⍺} end\n",
    "    ⊖path\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">86\n",
       "</span>"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "≢(⊂1 1) Day13p1 ⊂31 39"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, we want to find the number of distinct locations that can be reached in maximum 50 steps. For this we can simplify our above Dijkstra implementation in that we no longer need to keep track of the path itself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day13p2←{\n",
    "    costKeys←1500⌶,⍵                                           ⍝ Make this array a hash table                            \n",
    "    costVals←,0\n",
    "    Cost←{⍵∊costKeys:costVals[⊃costKeys⍳⍵] ⋄ ⌊/⍬}              ⍝ Default cost is +infinity\n",
    "    _←{\n",
    "        (frontier queueItem)←##.heapq.Pop ⍵\n",
    "        newCost←1+Cost (current←2⊃queueItem)    \n",
    "        newCost>50:frontier                                    ⍝ Cut-off at 50 steps\n",
    "        valid←{newCost<Cost⊂⍵}¨neighbours←Neighbours current   ⍝ Find neighbours either new or at lower cost\n",
    "        frontier {\n",
    "            0=≢⍵:⍺\n",
    "            vertex←1↑⍵\n",
    "            queue←⍺ ##.heapq.Push ⊂newCost(vertex)\n",
    "            vertex∊costKeys:queue∇(1↓⍵)⊣costVals[⊃costKeys⍳vertex]←newCost  ⍝ Old, but lower-cost\n",
    "            costKeys,←vertex ⋄ costVals,←newCost                            ⍝ New vertex\n",
    "            queue∇1↓⍵   \n",
    "        } valid/neighbours\n",
    "    }⍣{##.heapq.Empty ⍺} ##.heapq.Push⊂0 ⍵                     ⍝ Repeat until queue is empty\n",
    "    ≢costKeys\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">127\n",
       "</span>"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day13p2 ⊂1 1 ⍝ 127"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 14: One-Time Pad\n",
    "https://adventofcode.com/2016/day/14\n",
    "\n",
    "Skipping this, as no native MD5 on Dyalog for MacOS :("
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 15: Timing is Everything\n",
    "https://adventofcode.com/2016/day/15\n",
    "\n",
    "Back to the regular schedule of one-liners."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 232,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This shrank down nicely. The key parts are:\n",
    "\n",
    "    {⍵|⍵-⍳≢⍵}          ⍝ Given the disk sizes, calculate the end state - the first digit of every disk we need\n",
    "    SIZES {⍵⊖⍳⍺}¨STATE ⍝ Rotate the disks to their given start states\n",
    "    1∘⊖¨              ⍝ \"Tick\" all disks by one position\n",
    "    \n",
    "Basically it's `Tick⍣{first digits matches end state}`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 233,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day15←{e←{⍵|⍵-⍳≢⍵}⍺⋄c←¯1⋄_←1∘⊖¨⍣{c+←1⋄e≡⊃¨⍺}⊢⍺{⍵⊖⍳⍺}¨⍵⋄c}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 234,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">317371\n",
       "</span>"
      ]
     },
     "execution_count": 234,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2080951\n",
       "</span>"
      ]
     },
     "execution_count": 234,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "17 7 19 5 3 13    Day15 1 0 2 0 0 5   ⍝ Part 1: 317371\n",
    "17 7 19 5 3 13 11 Day15 1 0 2 0 0 5 0 ⍝ Part 2: 2080951"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 16: Dragon Checksum\n",
    "https://adventofcode.com/2016/day/16\n",
    "\n",
    "[Dragon](https://en.wikipedia.org/wiki/Dragon_curve) curve."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">\n",
       "Rebuilding user command cache... done\n",
       "</span>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⎕IO←1\n",
    "Dragon←{⍵,0,~⊖⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "Checksum←{=/(2÷⍨≢⍵)2⍴⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day16←{size←⍺⋄Checksum⍣{2|≢⍺} size↑Dragon⍣{size≤≢⍺} ⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 0\n",
       "</span>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 0 0 0 1 1 0 1 0 1 0 0 0 0 1 0 1\n",
       "</span>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "272      Day16 1 0 1 1 1 1 0 0 1 1 0 0 0 1 1 1 1 ⍝ Part 1: 11100110111101110\n",
    "35651584 Day16 1 0 1 1 1 1 0 0 1 1 0 0 0 1 1 1 1 ⍝ Part 2: 10001101010000101"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 17: Two Steps Forward\n",
    "https://adventofcode.com/2016/day/17\n",
    "\n",
    "More MD5, sadly lacking for Dyalog on MacOS :("
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 18: Like a Rogue\n",
    "https://adventofcode.com/2016/day/18\n",
    "\n",
    "We have what amounts to a binary map of safe (1) and unsafe (0) tiles. To generate the next row, we centre a length 3 window on each digit, convert the bits to a decimal number, and if it's 1, 3, 4 or 6, the resulting bit is 1, else 0.\n",
    "\n",
    "We can use the handy stencil operator (`⌺`) to generate the windowed regions, but it has a small quirk we need to work around -- at the edges it uses the standard fill element, in our case 0, whereas in the problem statement it is clear that elements outside the specified region should be considered 'safe' -- i.e. 1. There is no way to tell stencil to use an arbitrary element as the fill.\n",
    "\n",
    "The solution is to negate the vector before applying the stencil, and then 'flip' the condition when we convert our decimal numbers back to a binary bit. Instead of making 1, 3, 4 and 6 into 1, we make 0, 2, 5 and 7 to 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY18←'.'='.^^^.^.^^^^^..^^^..^..^..^^..^.^.^.^^.^^....^.^...^.^^.^^.^^..^^..^.^..^^^.^^...^...^^....^^.^^^^^^^'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day18←{\n",
    "    iter←⍺-1\n",
    "    sum←+/⍵\n",
    "    _←{r←0 2 5 7∊⍨2⊥⍉⊢⌺3~⍵⋄sum+←+/r⋄r}⍣iter⊢⍵\n",
    "    sum\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1939\n",
       "</span>"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "40 Day18 DAY18 ⍝ Part 1: 1939"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">19999535\n",
       "</span>"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "400000 Day18 DAY18 ⍝ Part 1: 19999535  (takes about 30s to run)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 19: An Elephant Named Joseph\n",
    "https://adventofcode.com/2016/day/19\n",
    "\n",
    "This is the so-called [Josephus problem](https://en.wikipedia.org/wiki/Josephus_problem), hence the title. There is an excellent deep-dive on the [Numberphile YouTube channel](https://www.youtube.com/watch?v=uCsD3ZGzMgE).\n",
    "\n",
    "The Josephus probem has clever solutions. Part 1 is given in the Numberphile video above: convert to binary, drop the first digit, append a 1, and convert back to decimal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1834903\n",
       "</span>"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2⊥1,⍨1↓(2∘⊥⍣¯1)3014603 ⍝ Part 1: 1834903  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2: Analytical solution to the generic Josephus problem. \n",
    "See Wikipedia page https://en.wikipedia.org/wiki/Josephus_problem towards the end for the recurrence used here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day19p2←{n←⍵⋄p←{⍵×3}⍣{n<3×⍺}⊢1⋄n-p+0⌈n-2×p}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1420280\n",
       "</span>"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day19p2 3014603 ⍝ 1420280"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 20: Firewall Rules\n",
    "https://adventofcode.com/2016/day/20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "DAY20←↑{2⊃'-'⎕VFI ⍵}¨⊃⎕NGET'data/2016/20.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "Merge←{(a b)←⍺⋄(c d)←⍵⋄c≤(b+1):a,b⌈d⋄⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "RANGES←Merge\\↓DAY20[⍋DAY20[;1];] ⍝ Sort, then merge the ranges pair-wise, preserving intermediate results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 1: the first gap is found where the first element of the merged range is not zero. Add 1 to the upper limit of the last merged range with a lower limit of zero."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">22887907\n",
       "</span>"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1+2⌷⊃RANGES[¯1+⍸<\\{0≠1⊃⍵}¨RANGES] ⍝ Part 1: 22887907"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we need to find, and add up the sizes of all gaps. In our RANGES vector, gaps are found where the lower limit changes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "GAPS←⍸2≠/⊣/RMAT←↑RANGES           ⍝ Flag locations where the first component changes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">109\n",
       "</span>"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/{¯1+RMAT[⍵+1;1]-RMAT[⍵;2]}¨GAPS ⍝ Part 2: 109"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 21: Scrambled Letters and Hash\n",
    "https://adventofcode.com/2016/day/21"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "'iotag'⎕CY'dfns'\n",
    "DAY21←⊃⎕NGET'data/2016/21.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [],
   "source": [
    "SwapPos←{⍺[⊖⍵]@⍵⊢⍺}\n",
    "SwapLet←{⍺ SwapPos(⊃⍺⍳0⊃⍵)(⊃⍺⍳1⊃⍵)}\n",
    "Rev←{i←⊃iotag/⍵⋄⍺[⊖i]@i⊢⍺}\n",
    "Move←{(from to)←⍵⋄⍺[from](to{⍺⍺(↑⍪⍺⍪↓)⍵})(from↑⍺),(-¯1+(≢⍺)-from)↑⍺}\n",
    "Rot←{⍵⊖⍺}\n",
    "RotPos←{i←⊃⍺⍳⍵⋄i>3:(-i+2)⊖⍺⋄(-i+1)⊖⍺}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day21←{\n",
    "     0=≢⍵:⍺\n",
    "     instr←' '(≠⊆⊢)⊃1↑⍵\n",
    "     ('rotate'≡0⊃instr)∧'right'≡1⊃instr:(⍺ Rot -⍎2⊃instr)∇ 1↓⍵\n",
    "     ('rotate'≡0⊃instr)∧'left'≡1⊃instr:(⍺ Rot ⍎2⊃instr)∇ 1↓⍵\n",
    "     ('rotate'≡0⊃instr)∧'based'≡1⊃instr:(⍺ RotPos 6⊃instr)∇ 1↓⍵\n",
    "     ('swap'≡0⊃instr)∧'letter'≡1⊃instr:(⍺ SwapLet ∊instr[2 5])∇ 1↓⍵\n",
    "     'swap'≡0⊃instr:(⍺ SwapPos ⍎¨instr[2 5])∇ 1↓⍵\n",
    "     'reverse'≡0⊃instr:(⍺ Rev ⍎¨instr[2 4])∇ 1↓⍵\n",
    "     (⍺ Move ⍎¨instr[2 5])∇ 1↓⍵\n",
    " }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">dbfgaehc\n",
       "</span>"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'abcdefgh' Day21 DAY21 ⍝ Part 1: dbfgaehc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, we need to take a string scrambled using the above, and unscramble it back to its original state. For this we need to do two things:\n",
    "\n",
    "1. Create inverses for our scramble functions\n",
    "2. Apply the whole rule-set backwards.\n",
    "\n",
    "Several of the functions are already symmetric: SwapPos, SwapLet, Rev. We can trivially write inverses for Move and Rot. RotPos requires a bit of thought.\n",
    "\n",
    "Note: by redefining the Move, Rot and RotPos functions we can leave the Day21 function as-is, but if we wanted to re-run part 1, we'd need to put the originals back first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [],
   "source": [
    "Move←{(to from)←⍵⋄⍺[from](to{⍺⍺(↑⍪⍺⍪↓)⍵})(from↑⍺),(-¯1+(≢⍺)-from)↑⍺}  ⍝ Swap to and from\n",
    "Rot←{⍺⊖⍨-⍵}                                                           ⍝ Negate rotation direction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For RotPos, the forward function is a rightwards rotation a number of steps as a function of the index. This has no calculatable inverse, but has to be tested for using the forward function:\n",
    "\n",
    "    {i←⊃⍺⍳⍵⋄i>3:(-i+2)⊖⍺⋄(-i+1)⊖⍺}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [],
   "source": [
    "RotPos←{s←⍺⋄l←⍵⋄{test←⍵⊖s⋄s≡test {i←⊃⍺⍳⍵⋄i>3:(-i+2)⊖⍺⋄(-i+1)⊖⍺} l:test⋄∇(⍵+1)} 0}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">aghfcdeb\n",
       "</span>"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'fbgdceah' Day21 ⊖DAY21 ⍝ Part 2: aghfcdeb"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 22: Grid Computing\n",
    "https://adventofcode.com/2016/day/22"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→─────┐\n",
       "│Was ON│\n",
       "└──────┘\n",
       "</span>"
      ]
     },
     "execution_count": 179,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⎕IO←0\n",
    "]rows off\n",
    "DAY22←⍎¨¨'-?\\d+'⎕S'&'¨2↓⊃⎕NGET'data/2016/22.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "934\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 170,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/∊DAY22 ∘.{(⍺≢⍵)∧(⍺[3]>0)∧⍺[3]<⍵[4]} DAY22 ⍝ Part 1: 934"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2 has either a very complex or a very simple solution. With a few data-specific assumptions, we can reduce the dimensionality and solve this by hand if we choose:\n",
    "\n",
    "1. A single node exists that has 0 usage.\n",
    "1. We only need to consider moves that involve this empty node.\n",
    "1. A set of large nodes exist that form \"barriers\" to be avoided.\n",
    "\n",
    "If we render the grid we can see it has very few nodes of actual interest:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "metadata": {},
   "outputs": [],
   "source": [
    "UNMOVABLE←200∘<(↑DAY22)[;3]\n",
    "GRID←31 31⍴ '.'@(⍸~UNMOVABLE)⊢('#'@⊢)⊢UNMOVABLE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────────────┐\n",
       "│13 27 92 0 92 0│\n",
       "└~──────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 222,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "EMPTY←⊃⍸0=(↑DAY22)[;3]\n",
    "⎕←ER←⊃DAY22[EMPTY]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 223,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────────────────────────────┐\n",
       "↓T.............................G│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│.....##########################│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│.............E.................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "│...............................│\n",
       "└───────────────────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 223,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'G'@(⊂0 30)⊢'T'@(⊂0 0)⊢'E'@(⊂⊖2↑ER)⊢⍉GRID"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can recast the problem as shuffling the node marked as 'E'. The shortest path to in front of the node marked 'G' is obvious. After that, each move of G is followed by the following sequence:\n",
    "\n",
    "    ..EG    ..GE    ..G.    ..G.    ..G.   .EG.\n",
    "    ....    ....    ...E    ..E..   .E..   ....\n",
    "    \n",
    "We need to move G 29 steps, each of which needs 5 shuffles, giving us 5×29=145, once we have the E adjacent to G, which takes 62 steps, giving us 207 which is the answer we wanted."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 23: Safe Cracking\n",
    "https://adventofcode.com/2016/day/23\n",
    "\n",
    "This is the `asmbunny` VM from Day 12 above, with one extra instruction added.\n",
    "\n",
    "Part 2 benefits from some hand-disassembly. We'll make the code an operator so that it can be used for both part 1 and 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 280,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "DAY23←↑{6::⍵⋄⍎⍵}¨¨' '(≠⊆⊢)¨⊃⎕NGET'data/2016/23.txt'1 ⍝ Split on space and convert numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 284,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day23←{\n",
    "    mem←⍵\n",
    "    ri←{'abcd'⍳⍵}                                  \n",
    "    int←{(1=2|⎕DR)⍵}\n",
    "    val←{int ⍵:⍵⋄⍺[ri ⍵]}                          \n",
    "    cpy←{(x y)←⍵⋄(int x)∧int y:1∘+@5⊢⍺⋄1∘+@5⊢(⍺ val x)@(ri y)⊢⍺}\n",
    "    jnz←{(x y)←⍵⋄(0>⍨⍺ val x):(⍺ val y)∘+@5⊢⍺⋄1∘+@5⊢⍺}\n",
    "    inc←{x←ri ⊃⍵⋄1∘+@5⊢1∘+@x⊢⍺}\n",
    "    dec←{x←ri ⊃⍵⋄1∘+@5⊢¯1∘+@x⊢⍺}\n",
    "    \n",
    "    ops←⍉↑('cpy' 'jnz' 'inc' 'dec' 'tgl') ('jnz' 'cpy' 'dec' 'inc' 'inc') ⍝ The tgl transform table\n",
    "    tglop←{row←ops[;1]⍳⍵⋄ops[row;2]}\n",
    "    hack←⍺⍺                                         ⍝ See part 2\n",
    "    \n",
    "    tgl←{                                           ⍝ Who thought self-modifying code was a good idea?\n",
    "        v←(¯1↑⍺)+⊃⍺ val ⊃⍵\n",
    "        v>≢mem:1∘+@5⊢⍺                              ⍝ Overflow; ignore\n",
    "        1∘+@5⊢⍺⊣mem[v;1]←tglop mem[v;1]\n",
    "    }\n",
    "        \n",
    "    {\n",
    "        regs←hack ⍵                                 ⍝ See part 2\n",
    "        ip←¯1↑regs\n",
    "        instr←ip⌷mem⋄op←⊃instr\n",
    "        regs (⍎op) 1↓instr         \n",
    "    }⍣{(¯1↑⍺)>≢mem}⍺\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 285,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "12000\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 285,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1⌷7 0 0 0 1 (⊢ Day23) DAY23  ⍝ Part 1: 12000"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So far, so good. Unfortunately, the asmbunny code will run around some unnecessary loops in part 2, making running it longwinded. We can optimise it a bit. Looking at the code in the data, the suspect bit looks like so:\n",
    "\n",
    "    ⍝ This is where all the time is spent (lines 4-9)\n",
    "    4:  cpy b c      ⍝ L2\n",
    "        5:  inc a        ⍝ L1\n",
    "        6:  dec c\n",
    "        7:  jnz c -2     ⍝ if c goto L1\n",
    "        8:  dec d\n",
    "    9:  jnz d -5     ⍝ if d goto L2\n",
    "    \n",
    "which can be replaced with `a+←b×d`, assuming that this bit of code is beyond reach for the self-modifying `tgl` instruction further down."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 286,
   "metadata": {},
   "outputs": [],
   "source": [
    "Hack←{4=¯1↑⍵:(⍵[1]+⍵[2]×⍵[4]),⍵[2],0,0,9⋄⍵}  ⍝ Optimise out silly loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 287,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">          \n",
       "2874016560\n",
       "          \n",
       "</span>"
      ]
     },
     "execution_count": 287,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1⌷12 0 0 0 1 (Hack Day23) DAY23 ⍝ Part 2: 2874016560"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 24: Air Duct Spelunking\n",
    "https://adventofcode.com/2016/day/24\n",
    "\n",
    "[Travelling Salesperson-ish](https://en.wikipedia.org/wiki/Travelling_salesman_problem). Lots of classic algorithms.\n",
    "\n",
    "First part of this problem divides into two parts:\n",
    "\n",
    "1. Create a costed, fully connected graph of the numbered nodes.\n",
    "Costs are the lengths of the shortest paths in the maze.\n",
    "1. Find the cheapest [Hamiltonian path](https://en.wikipedia.org/wiki/Hamiltonian_path), starting at node 0.\n",
    "\n",
    "For (1) we repeatedly apply the [A*](https://en.wikipedia.org/wiki/A*_search_algorithm) search algorithm, using the [manhattan distance](https://en.wikipedia.org/wiki/Taxicab_geometry) as the heuristic.\n",
    "\n",
    "For (2) we find the [MST](https://en.wikipedia.org/wiki/Prim%27s_algorithm), and do a pre-order traversal, visiting child nodes in order of number of children and edge cost. This isn't guaranteed to be correct for all graphs - it's a factor-2 approximation worst case.\n",
    "\n",
    "Part two of the problem closes the loop: find the cheapest Hamiltonian\n",
    "_cycle_. Only difference is that we now want to visit nodes with\n",
    "more children first.\n",
    "\n",
    "But really ---  the correct path is trivially visible by eye-balling\n",
    "the MST:\n",
    "\n",
    "             0\n",
    "            / \\\n",
    "        30 /   \\ 44\n",
    "          /     \\\n",
    "         1       7   (7-1: 54)\n",
    "         |\n",
    "     30  |\n",
    "         |\n",
    "         3\n",
    "         |\n",
    "     66  |\n",
    "         |\n",
    "         6\n",
    "         |\n",
    "    168  |\n",
    "         |\n",
    "         4\n",
    "        / \\\n",
    "    54 /   \\ 56\n",
    "      /     \\\n",
    "     5       2  (5-2: 74)\n",
    "\n",
    "\n",
    "For the Hamiltonian path we need:  [0, 7, 1, 3, 6, 4, 5, 2]\n",
    "\n",
    "For the Hamiltonian cycle we need: [0, 1, 3, 6, 4, 5, 2, 7, 0]\n",
    "\n",
    "But let's do the work, starting with implementing the A* and Prim's algorithms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">\n",
       "Rebuilding user command cache... done\n",
       "</span>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">\n",
       "\n",
       "\n",
       "Linked: #.heapq → /Users/stefan/work/dyalog/AoCDyalog/src/heapq\n",
       "</span>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⎕IO←1\n",
    "DAY24←↑⊃⎕NGET'data/2016/24.txt'1\n",
    "]LINK.Create heapq src/heapq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For A* then -- it's very similar to our Dijkstra implementation from Day 13 above. In fact, we can view Dijkstra as A* with a constant heuristic function. In A* we pass in a heuristic function that is used to weight potential steps in favour of the likelihood that they're in some way better. In our case, the heuristic function should be dyadic, and will be called with the current vertex to the left and the target vertex to the right."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "AStar←{  \n",
    "    ⍺≡⍵:⍬\n",
    "    start←⊂⍺⋄end←⊂⍵\n",
    "    costKeys←1500⌶,start\n",
    "    costVals←,0\n",
    "    Cost←{⍵∊costKeys:costVals[⊃costKeys⍳⍵] ⋄ ⌊/⍬}\n",
    "    cameFromKeys←1500⌶,start\n",
    "    cameFromVals←,start\n",
    "    Next←⍺⍺ ⋄ Heuristic←⍵⍵\n",
    "    _←{\n",
    "        (frontier queueItem)←##.heapq.Pop ⍵\n",
    "        newCost←1+Cost (current←2⊃queueItem)\n",
    "        current≡end:⍬\n",
    "        valid←{newCost<Cost ⍵}¨neighbours←Next current\n",
    "        frontier {\n",
    "            0=≢⍵:⍺\n",
    "            vertex←⊃1↑⍵\n",
    "            queue←⍺ ##.heapq.Push ⊂(newCost+vertex Heuristic end)(vertex)\n",
    "            cameFromKeys,←vertex\n",
    "            cameFromVals,←current\n",
    "            vertex∊costKeys:queue∇(1↓⍵)⊣costVals[⊃costKeys⍳vertex]←newCost\n",
    "            costKeys,←vertex ⋄ costVals,←newCost\n",
    "            queue∇1↓⍵   \n",
    "        } valid/neighbours\n",
    "    }⍣{##.heapq.Empty ⍺} ##.heapq.Push ⊂0 start\n",
    "\n",
    "    ⍝ Reconstruct the path - start vertex not included. Return ⍬ if no path exists.\n",
    "    path←⍬\n",
    "    _←{3::⍬⋄path,←⍵⋄cameFromVals[⊃cameFromKeys⍳⍵]}⍣{start≡⍺} end\n",
    "    ⊖path\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "Neighbours←{⊂⍤0⊢('#'≠⍺[n])/n←⍵+(¯1 0) (1 0) (0 ¯1) (0 1)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "Manhattan←{+/|(⊃⍺)-⊃⍵}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can test this a bit to see if it functions. Let's find the shortest path between items \"1\" and \"3\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">12 14\n",
       "</span>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2 34\n",
       "</span>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃⍸'1'⍷DAY24\n",
    "⊃⍸'3'⍷DAY24"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">Was ON -style=mid\n",
       "</span>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">Was ON -fold=3\n",
       "</span>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐\n",
       "│12 15│12 16│12 17│12 18│12 19│12 20│12 21│12 22│12 23│12 24│11 24│10 24│10 25│10 26│10 27│10 28│9 28│8 28│7 28│6 28│6 29│6 30│5 30│4 30│4 31│4 32│4 33│4 34│3 34│2 34│\n",
       "└~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~──→┴~──→┴~──→┴~──→┴~──→┴~──→┴~──→┴~──→┴~──→┴~──→┴~──→┴~──→┴~──→┴~──→┘\n",
       "</span>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "]box on -style=mid\n",
    "]rows on -fold=3\n",
    "12 14 (DAY24∘Neighbours AStar Manhattan) 2 34"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looking at the top left corner of our maze, we can see that this looks plausible:\n",
    "\n",
    "```\n",
    "###################################\n",
    "#.........#...#.............#...#3#\n",
    "#.#.#.#.#.#.#########.#.#.###.#.#.#\n",
    "#...#...#...#.......#...#.#.#.....#\n",
    "#.###.#.#.#####.###.###.#.#.#.#.###\n",
    "#.......#.........#.#.#...#...#...#\n",
    "#.###.#.#.#########.#.#.#.#.#.#.#.#\n",
    "#...#.#...#...#...#...#.#...#.....#\n",
    "#.#.#.###.###.#.#.#######.#.#.#.#.#\n",
    "#.......#.......#...........#...#.#\n",
    "#.#.#.###.#####.#.#####.#.###.#.#.#\n",
    "#.#.#.....#.#1..........#.#...#...#\n",
    "#.#.###.#.#.#####.#.#.#.###.#####.#\n",
    "```\n",
    "\n",
    "What we need to do now is to build a weighted graph of the numbered tiles in the data. We'll make this an adjacency matrix, where the weights are the shortest path length, as discovered by the AStar algorithm.\n",
    "\n",
    "So let's find the locations of the numbers -- they must be single digits:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→───┬─────┬─────┬────┬──────┬──────┬─────┬────┬───┬───┐\n",
       "│22 2│12 14│4 178│2 34│20 146│34 170│42 48│40 8│0 0│0 0│\n",
       "└~──→┴~───→┴~───→┴~──→┴~────→┴~────→┴~───→┴~──→┴~─→┴~─→┘\n",
       "</span>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{⊃⍸(⍕⍵)⍷DAY24}¨0,⍳9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "MakeGraph←{\n",
    "    data←⍵\n",
    "    tiles←⊂⍤0{⊃⍸(⍕⍵)⍷data}¨0,⍳7\n",
    "    8 8⍴≢¨(data∘Neighbours AStar Manhattan)/↑,tiles∘.,tiles\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">  0  30 258  56 214 256 106  44\n",
       " 30   0 232  30 188 230  80  54\n",
       "258 232   0 218  56  74 212 278\n",
       " 56  30 218   0 174 216  66  80\n",
       "214 188  56 174   0  54 168 234\n",
       "256 230  74 216  54   0 210 276\n",
       "106  80 212  66 168 210   0 126\n",
       " 44  54 278  80 234 276 126   0\n",
       "</span>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⎕←GRAPH←MakeGraph DAY24 ⍝ Wasteful, due to the symmetry -- each path calculated twice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we need to find the minimum cost spanning tree. Many algorithms for this exist. Let's try Prim's, which bears some passing resemblance to the Dijkstra algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "PrimsMST←{\n",
    "    visited←1500⌶,⍵\n",
    "    Next←⍺⍺\n",
    "    (⊃¨{⊂⍺⍵}⌸⊢/¨) ⍬ {\n",
    "        ##.heapq.Empty ⍵:⍺\n",
    "        (edges queueItem)←##.heapq.Pop ⍵\n",
    "        (from to)←2⊃queueItem\n",
    "        to∊visited:⍺∇edges\n",
    "        visited,←to\n",
    "        newEdges←Next to ⍝ cost-vertex pairs (cost (from to))\n",
    "        unseen←~(⊣/↑newEdges)∊visited\n",
    "        ((⊂from (to)),⍺)∇edges ##.heapq.Push unseen/newEdges\n",
    "    } ##.heapq.Push ⍺⍺ ⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The operand function needs to return a vector of costed pairs for the matrix - (cost (from to))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "Connected←{⍺[⍵;idx],¨⊂⍤1¨⍵,¨idx←⍵~⍨⍸0≠⍵⌷⍺}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→───────┬─────────┬────────┬─────────┬─────────┬─────────┬────────┐\n",
       "│┌→─┬───┐│┌→──┬───┐│┌→─┬───┐│┌→──┬───┐│┌→──┬───┐│┌→──┬───┐│┌→─┬───┐│\n",
       "││30│1 2│││258│1 3│││56│1 4│││214│1 5│││256│1 6│││106│1 7│││44│1 8││\n",
       "│└~─┴~─→┘│└~──┴~─→┘│└~─┴~─→┘│└~──┴~─→┘│└~──┴~─→┘│└~──┴~─→┘│└~─┴~─→┘│\n",
       "└───────→┴────────→┴───────→┴────────→┴────────→┴────────→┴───────→┘\n",
       "</span>"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "GRAPH Connected 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────┬─────┬─────┬───────┬─────┐\n",
       "│┌→┬───┐│┌→┬─┐│┌→┬─┐│┌→┬───┐│┌→┬─┐│\n",
       "││5│3 6│││7│5│││4│7│││1│8 2│││2│4││\n",
       "│└─┴~─→┘│└─┴→┘│└─┴→┘│└─┴~─→┘│└─┴→┘│\n",
       "└──────→┴────→┴────→┴──────→┴────→┘\n",
       "</span>"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢MST←GRAPH∘Connected PrimsMST⊢1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally! What remains is to traverse the MST, visiting child nodes in order of increasing number of children, and if equal, cheaper first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "Traverse←{⍺←⍬⋄0=≢⍵:⍺⋄(⍺,⊃1↑⍵)∇(⍺⍺ ⊃1↑⍵),1↓⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "FewerChildren←{\n",
    "    (graph mst)←⍺\n",
    "    tree←↑mst\n",
    "    keys←⊣/tree\n",
    "    ~⍵∊keys:⍬\n",
    "    ch←⊃tree[keys⍳⍵;2]\n",
    "    1=≢ch:ch\n",
    "    counts←{~⍵∊keys:0⋄≢⊃tree[keys⍳⍵;2]}¨ch\n",
    "    costs←graph[⍵,¨ch]\n",
    "    ch[⍋↓⍉↑counts costs]\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1 8 2 4 7 5 6 3\n",
       "</span>"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢PATH←((GRAPH MST)∘FewerChildren Traverse) ,1 ⍝ Hamiltonian path"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Last step: cost the path."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">490\n",
       "</span>"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/GRAPH[{⊂⍵}⌺2 ⊢ PATH] ⍝ Part 1: 490 EPIC"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, we need to return to our starting point. Traverse the MST again, this time visiting nodes in descenting child-count order and ascending cost, and then appending the start node. The rest is the same."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "MoreChildren←{\n",
    "    (graph mst)←⍺\n",
    "    tree←↑mst\n",
    "    keys←⊣/tree\n",
    "    ~⍵∊keys:⍬\n",
    "    ch←⊃tree[keys⍳⍵;2]\n",
    "    1=≢ch:ch\n",
    "    counts←{~⍵∊keys:2⋄2-≢⊃tree[keys⍳⍵;2]}¨ch   ⍝ Not generic, but life's too short -- max two child nodes\n",
    "    costs←graph[⍵,¨ch]\n",
    "    ch[⍋↓⍉↑counts costs]\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "PATH2←((GRAPH MST)∘MoreChildren Traverse) ,1 ⍝ Hamiltonian cycle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">744\n",
       "</span>"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/GRAPH[{⊂⍵}⌺2 ⊢ PATH2,1] ⍝ Part 2: 744"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 25: Clock Signal\n",
    "https://adventofcode.com/2016/day/25\n",
    "\n",
    "More `ambunny` code, this time pretty hard-core. It's not tractable to run (on my machine at least) as it stands. So we have a few options:\n",
    "\n",
    "1. Hack the asmbunny code a bit to bypass worst loops and run the program, like we did for part 2 of Day 23.\n",
    "1. Figure out what the program actually _does_ and solve that problem.\n",
    "\n",
    "It turns out that it's actually solvable by hand more or less.\n",
    "\n",
    "```\n",
    "STEP 1: Annotate loops\n",
    "\n",
    "0:  cpy a d\n",
    "1:  cpy 11 c\n",
    "\n",
    "2:  cpy 231 b <---+             BLOCK ONE\n",
    "3:  inc d    <--+ |\n",
    "4:  dec b       | |\n",
    "5:  jnz b -2 ---+ |\n",
    "6:  dec c         |\n",
    "7:  jnz c -5 -----+\n",
    "\n",
    "8:  cpy d a\n",
    "9:  jnz 0 0\n",
    "10: cpy a b\n",
    "\n",
    "11: cpy 0 a                      BLOCK TWO\n",
    "12: cpy 2 c  <-----------+\n",
    "13: jnz b 2  --------+   | <-+\n",
    "14: jnz 1 6  --> ..  |   |   |    exit loops: goto 20\n",
    "15: dec b    <-------+   |   |\n",
    "16: dec c                |   |\n",
    "17: jnz c -4 ------------|---+\n",
    "18: inc a                |\n",
    "19: jnz 1 -7  -----------+\n",
    "\n",
    "20: cpy 2 b                      BLOCK THREE\n",
    "21: jnz c 2  ---+\n",
    "22: jnz 1 4  ---|--+ <-+\n",
    "23: dec b    <--+  |   |\n",
    "24: dec c          |   |\n",
    "25: jnz 1 -4  -----|---+\n",
    "26: jnz 0 0  <-----+\n",
    "\n",
    "\n",
    "27: out b                 ^\n",
    "                          |  ^\n",
    "28: jnz a -19 ------------+  |\n",
    "29: jnz 1 -21 ---------------+\n",
    "\n",
    "STEP 2: Resolve BLOCK ONE\n",
    "\n",
    "Two nested loops, amounting to a multiplication:\n",
    "\n",
    "while True:\n",
    "    b = 231           # 2\n",
    "    while True:\n",
    "        d += 1        # 3\n",
    "        b -= 1        # 4\n",
    "        if b == 0:    # 5\n",
    "            break\n",
    "    c -= 1\n",
    "    if c == 0:\n",
    "        break\n",
    "\n",
    "which simplifies to:\n",
    "\n",
    "while c != 0:\n",
    "    b = 231\n",
    "    while b != 0:\n",
    "        d += 1\n",
    "        b -= 1\n",
    "    c -= 1\n",
    "\n",
    "and finally\n",
    "\n",
    "d = a + 231 * 11\n",
    "\n",
    "b = 0\n",
    "c = 0\n",
    "\n",
    "STEP 3: Resolve BLOCK TWO\n",
    "\n",
    "8:  cpy d a\n",
    "9:  jnz 0 0\n",
    "10: cpy a b\n",
    "\n",
    "done = False\n",
    "while True:\n",
    "    c = 2\n",
    "    while True:\n",
    "        if b == 0:\n",
    "            done = True\n",
    "            break\n",
    "        b -= 1\n",
    "        c -= 1\n",
    "\n",
    "        if c == 0:\n",
    "            break\n",
    "    if done:\n",
    "        break\n",
    "    a += 1\n",
    "\n",
    "which is a long-winded way of saying\n",
    "\n",
    "a = a // 2\n",
    "c = 2 - a%2\n",
    "\n",
    "STEP 4: Resolve BLOCK THREE\n",
    "\n",
    "20: cpy 2 b                BLOCK THREE\n",
    "21: jnz c 2  ---+\n",
    "22: jnz 1 4  ---|--+ <-+\n",
    "23: dec b    <--+  |   |\n",
    "24: dec c          |   |\n",
    "25: jnz 1 -4  -----|---+\n",
    "26: jnz 0 0  <-----+\n",
    "\n",
    "b = 2\n",
    "while True:\n",
    "    if c == 0:\n",
    "        break\n",
    "    b -= 1\n",
    "    c -= 1\n",
    "\n",
    "which is\n",
    "\n",
    "b = 2 - c\n",
    "\n",
    "but by this stage c = 2 - a%2 so BLOCK THREE becomes\n",
    "\n",
    "b = a % 2\n",
    "\n",
    "The last two loops are straight-forward. The whole program becomes:\n",
    "\n",
    "d = a + 2541\n",
    "while True:\n",
    "    a = d\n",
    "    while a != 0:\n",
    "        b = a % 2\n",
    "        a //= 2\n",
    "        print(f\"{b} \", end=\"\")\n",
    "    print()\n",
    "\n",
    "So what's going on here? It's basically computing the binary representation of d, over and over.\n",
    "\n",
    "For a = 1 we get:\n",
    "\n",
    "0 1 1 1  0 1 1 1  1 0 0 1\n",
    "0 1 1 1  0 1 1 1  1 0 0 1\n",
    "0 1 1 1  0 1 1 1  1 0 0 1\n",
    "0 1 1 1  0 1 1 1  1 0 0 1\n",
    "0 1 1 1  0 1 1 1  1 0 0 1\n",
    "0 1 1 1  0 1 1 1  1 0 0 1\n",
    "0 1 1 1  0 1 1 1  1 0 0 1\n",
    "...\n",
    "\n",
    "So we need a positive number that added to 2541 produces the following three LS bytes in binary:\n",
    "\n",
    "0 1 0 1  0 1 0 1  0 1 0 1  (0x555)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day25←{v←⍬⋄_←{v,←2|⍵⋄2(⌊÷⍨)⍵}⍣{⍺=0}⍵+2541⋄v≡⍺:⍵⋄⍺∇⍵+1}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">189\n",
       "</span>"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "0 1 0 1 0 1 0 1 0 1 0 1 Day25 1"
   ]
  },
  {
   "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
}