Advent of Code 2017 Dyalog APL.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Advent of Code 2017, 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%202017%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": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→─────────────────────────────────────┐\n",
       "│Was ON -style=max -trains=tree -fns=on│\n",
       "└──────────────────────────────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────┐\n",
       "│Was OFF│\n",
       "└───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⎕IO←1\n",
    "]box on -style=max -trains=tree -fns=on\n",
    "]rows on"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 1: Inverse Captcha\n",
    "https://adventofcode.com/2017/day/1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY1←⊃⊃⎕NGET'data/2017/01.txt'1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tack on the first item to the end, as per the problem statement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "DATA←DAY1,1⌷DAY1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We use a length-2 windowed reduction using equality to find all location where item n is equal to item n+1 as a binary map. We convert this to position (`⍸`) and pick the corresponding items. As we're still dealing with characters, we need to convert to integers (`⍎¨`) and then just sum them up."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "1341\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/⍎¨DATA[⍸2=/DATA] ⍝ Part 1: 1341"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, we create a matrix where column 1 is the input and column 2 is the data rotated by half its length. Then compare the elements of each row to produce the binary map, and the rest is as per part 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "1348\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/⍎¨DAY1[⍸=/⍉↑(DAY1)(DAY1⊖⍨2÷⍨≢DAY1)] ⍝ Part 2: 1348"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 2: Corruption Checksum\n",
    "https://adventofcode.com/2017/day/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY2←16 16⍴⍎¨'\\d+'⎕S'&'⊢⊃⎕NGET'data/2017/02.txt'1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 1 -- sum max-min for every row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "39126\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/(⌈/-⌊/)DAY2 ⍝ Part 1: 39126"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In part 2 we're looking for the single pair of items per row that divides cleanly. For each row we generate all combinations, and try both ways of modular division, looking for a zero (not two) using \n",
    "\n",
    "    {≠/0=⍺(|,|⍨)⍵}\n",
    "    \n",
    "Finally, return the larger÷smaller and sum up everything."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day2←{target←1↑⍸{≠/0=⍺(|,|⍨)⍵}/¨cmb←,⍵∘.,⍵⋄÷/pair[⍒pair←target⊃cmb]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "258\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/Day2¨↓DAY2 ⍝ Part 2: 258"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 3: Spiral Memory\n",
    "https://adventofcode.com/2017/day/3\n",
    "\n",
    "This [spiral](http://www.mathrecreation.com/2011/06/sequences-on-spiral.html) has a number of interesting properties. See http://oeis.org/A080335\n",
    "\n",
    "We can exploit that we have perfect squares on the SE diagonal, which allows us to identify the size of the square which has the target number along one of its edges. We can then identify which edge, and count backwards from the next corner of the square (anti-clockwise)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "DAY3←325489"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [],
   "source": [
    "Square←{r←⍵*0.5⋄⍵=2*⍨⌊r:r⋄0≠2|⌈r:⌈r⋄1+⌈r} ⍝ Smallest odd number < the square root, unless perfect square"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day3p1←{\n",
    "    val←⍵\n",
    "    width←Square ⍵                    ⍝ The width of the square in which the value is found\n",
    "    edge←⌊((width*2)-val)÷(width-1)   ⍝ The side of the square: S E N W ← 0 1 2 3\n",
    "    pos←edge⊃,size,-size∘.,-size,size←⌊width÷2  ⍝ Grid coords of corner\n",
    "    _←(edge⊃,¯1 0∘.,0 ¯1)∘{pos+←⍺⋄⍵-1}⍣{⍺=val} (width*2)-edge×width-1  ⍝ Sequence at the nearest corner, acw\n",
    "    +/|¨pos                           ⍝ Manhattan distance to centre\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "552\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day3p1 DAY3 ⍝ 552"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, we work our way outwards following the same spiral pattern, but this time the value of each point is the sum of the values of its 8-connected neighbours _at the time of visit_. The APL solution isn't pretty."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Coords←{\n",
    "    ⍝ Generate all coordinate pairs for the circumference of a square ⍵\n",
    "    pos←(⌊⍵÷2),(-⌊⍵÷2)+1\n",
    "    \n",
    "    E←(⊂pos)+0,¨⍳⍵-1\n",
    "    N←(¯1↑E)+(-⍳⍵),¨0\n",
    "    W←(¯1↑N)+0,¨-⍳⍵\n",
    "    S←(¯1↑W)+(⍳⍵),¨0\n",
    "    ∪E, N, W, S\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "metadata": {},
   "outputs": [],
   "source": [
    "Neighbours←{(⊂⍵)+(0 1)(1 1)(1 0)(1 ¯1)(0 ¯1)(¯1 ¯1)(¯1 0)(¯1 1)} ⍝ 8-neighbours"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day3p2←{\n",
    "    target←⍵\n",
    "    seen←,⊂0 0 ⋄ vals←,1\n",
    "    { ⍝ Move outwards one square at a time (i.e. odd numbers)\n",
    "        found←{ ⍝ Walk circumference, adding up values from visible neighbours\n",
    "            0=≢⍵:0\n",
    "            pos←⊃1↑⍵\n",
    "            old←seen⍳Neighbours pos\n",
    "            newVal←+/vals[((≢seen)>old)/old]\n",
    "            newVal>target:newVal\n",
    "            vals,←newVal\n",
    "            seen,←⊂pos\n",
    "            ∇1↓⍵\n",
    "        } Coords ⍵\n",
    "        found>0:found\n",
    "        ∇⍵+2\n",
    "    } 3\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">      \n",
       "330785\n",
       "      \n",
       "</span>"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day3p2 325489 ⍝ 330785"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 4: High-Entropy Passphrases\n",
    "https://adventofcode.com/2017/day/4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "DAY4←' '(≠⊆⊢)¨⊃⎕NGET'data/2017/04.txt'1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find phrases which don't match themselves with dupes removed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "325\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/(∪≡⊢)¨DAY4 ⍝ Part 1: 325"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2: apply the same process, but sort all words first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "119\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 151,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/(∪≡⊢)¨{⍵[⍋⍵]}¨¨DAY4 ⍝ Part 2: 119"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 5: A Maze of Twisty Trampolines, All Alike\n",
    "https://adventofcode.com/2017/day/5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "DAY5←⍎¨⊃⎕NGET'data/2017/05.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day5←{\n",
    "    instr←⍵\n",
    "    modifier←⍺⍺\n",
    "    1 {\n",
    "        ip←1↑⍵\n",
    "        jmp←ip⌷instr\n",
    "        (ip+jmp)>≢instr:⍺\n",
    "        instr[ip]+←modifier jmp\n",
    "        (⍺+1)∇ip+jmp\n",
    "    } 1\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">      \n",
       "372671\n",
       "      \n",
       "</span>"
      ]
     },
     "execution_count": 167,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{1} Day5 DAY5 ⍝ Part 1: 372671"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">        \n",
       "25608480\n",
       "        \n",
       "</span>"
      ]
     },
     "execution_count": 168,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{⍵≥3:¯1⋄1} Day5 DAY5 ⍝ Part 2: 25608480 (takes a minute or so)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 6: Memory Reallocation\n",
    "https://adventofcode.com/2017/day/6\n",
    "\n",
    "Part 1 and 2 differs only in the end condition and the start value. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 219,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "DAY6←2 8 8 5 4 2 3 1 5 5 1 2 15 13 5 14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 229,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Redist←{\n",
    "    (0@m⊢⍵) {                        ⍝ Zero out the current bin\n",
    "        0=⊃⍵:⍺                       ⍝ Return end state\n",
    "        (1∘+@n⊢⍺)∇(⊃⍵-1),n←16|1+⊢/⍵  ⍝ Move one index on, mod size and add 1. Decrease value to distribute.\n",
    "    } ⍵[m],m←(⊢⍳⌈/)⍵                 ⍝ Value and index of the largest element\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 230,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day6p1←{seen←⊂⍵⋄e←Redist⍣{seen∊⍨⊂⍺:1⋄0⊣seen,←⊂⍺} ⍵⋄(⊂e),≢seen} ⍝ Stop if we've seen a state before."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 231,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "3156\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 231,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(elem seen)←Day6p1 DAY6\n",
    "seen ⍝ 3156"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 232,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day6p2←{count←0⋄target←⍵⋄_←Redist⍣{count+←1⋄⍺≡target} ⍵⋄count} ⍝ Stop when we revisit end state of part 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 233,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "1610\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 233,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day6p2 elem ⍝ Part 2: 1610"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 7: Recursive Circus\n",
    "https://adventofcode.com/2017/day/7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 238,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "'segs'⎕CY'dfns'\n",
    "DAY7←⊃⎕NGET'data/2017/07.txt'1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to create a tree structure from the data. We'll create three vectors, the first being a list of the nodes themselves, the second holding their corresponding weights, and the third a nested vector containing any child-nodes. The 'dfns' workspace contains a handy function 'segs' that can slice up strings on a set of separators."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 243,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Parse←{\n",
    "    ⍺←⍬ ⍬ ⍬\n",
    "    0=≢⍵:⍺\n",
    "    items←'() ,->' segs ⊃1↑⍵\n",
    "    (⍺,¨(⊂1⊃items)(⍎2⊃items)(⊂2↓items))∇1↓⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 245,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────┐\n",
       "│xegshds│\n",
       "└───────┘\n",
       "</span>"
      ]
     },
     "execution_count": 245,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(nodes weights children)←Parse DAY7\n",
    "⊃nodes~{⊃,/,⊆¨⍵}⍣≡children ⍝ Part 1: xegshds"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we are to identify a single weight tweak to make the tree balanced in the sense that every child tree of any given node has equal weights. The first part of that is to be able to calculate the weight of the tree from a specific start node:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 246,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "SubTreeWeight←{              ⍝ (nodes weights children) SubTreeWeight 'node'\n",
    "    idx←(1⊃⍺)⍳⊂⍵             ⍝ Find the node's index\n",
    "    0=≢idx⊃3⊃⍺:idx⊃2⊃⍺       ⍝ If node has no children -- return the weight\n",
    "    (idx⊃2⊃⍺)++/⍺∘∇¨idx⊃3⊃⍺  ⍝ Add own weight to sum of child tree weights recursively\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now drill down from the root, looking for the first node that is balanced. The tweak needs to happen at the parent level of this node. We descend recursively following the odd one out of the child nodes until all child nodes have the same weight."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 281,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "FindAnomaly←{ ⍝ Find first key where its child trees all have the same weight\n",
    "    idx←(1⊃⍺)⍳⊂⍵\n",
    "    ch←idx⊃3⊃⍺\n",
    "    0=≢ch:⍬\n",
    "    chw←⍺∘SubTreeWeight¨ch\n",
    "    (1≥≢∘∪)chw:⍵ (idx)      ⍝ Child tree weights all equal - we're done\n",
    "    ⍺∇⊃ch[∊{∩/⍵}⌸chw]       ⍝ Intersect-reduce over unique indexes only returns non-empty for singles.\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 282,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→──────────────┐\n",
       "│ ┌→──────┐     │\n",
       "│ │fabacam│ 982 │\n",
       "│ └───────┘     │\n",
       "└∊──────────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 282,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢ANOMALY←(nodes weights children) FindAnomaly 'xegshds'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The size of the tweak we need to make to the anomaly is the difference of its parent's child weights."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 283,
   "metadata": {},
   "outputs": [],
   "source": [
    "PARENT←⍸{ANOMALY[1]∊⍵}¨children"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 279,
   "metadata": {},
   "outputs": [],
   "source": [
    "TWEAK←|-/∪(nodes weights children)∘SubTreeWeight¨⊃children[PARENT]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 280,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "299\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 280,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "weights[2⊃ANOMALY]-TWEAK ⍝ Part 2: 299"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 8: I Heard You Like Registers\n",
    "https://adventofcode.com/2017/day/8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 340,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "'segs'⎕CY'dfns'\n",
    "DAY8←⊃⎕NGET'data/2017/08.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 341,
   "metadata": {},
   "outputs": [],
   "source": [
    "DATA←' ' segs¨DAY8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 361,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day8←{\n",
    "    regs←∪{⊃,/,⊆¨⍵}⍣≡(↑⍵)[;1 5]\n",
    "    R←regs∘⍳                       ⍝ By binding an operator, the static 'regs' vector is hashed\n",
    "    vals←0⍴⍨≢regs\n",
    "    Reg←{vals[R ⊂,⍵]}\n",
    "    Set←{vals[R ⊂,⍺]←⍵⋄⍬}\n",
    "    inc←{⍺ Set (Reg ⍺)+⍎⍵}\n",
    "    dec←{⍺ Set (Reg ⍺)-⍎⍵}\n",
    "    0 {\n",
    "        0=≢⍵:(⌈/vals) ⍺\n",
    "        max←⌈/vals,⍺\n",
    "        instr←1⊃⍵\n",
    "        rv←Reg 5⊃instr\n",
    "        f←⍎2⊃instr\n",
    "        ((,'>')≡6⊃instr)∧rv>⍎7⊃instr:max∇1↓⍵⊣(1⊃instr) f 3⊃instr\n",
    "        ((,'<')≡6⊃instr)∧rv<⍎7⊃instr:max∇1↓⍵⊣(1⊃instr) f 3⊃instr\n",
    "        ('=='≡6⊃instr)∧rv=⍎7⊃instr:max∇1↓⍵⊣(1⊃instr) f 3⊃instr\n",
    "        ('>='≡6⊃instr)∧rv≥⍎7⊃instr:max∇1↓⍵⊣(1⊃instr) f 3⊃instr\n",
    "        ('<='≡6⊃instr)∧rv≤⍎7⊃instr:max∇1↓⍵⊣(1⊃instr) f 3⊃instr\n",
    "        ('!='≡6⊃instr)∧rv≠⍎7⊃instr:max∇1↓⍵⊣(1⊃instr) f 3⊃instr\n",
    "        max∇1↓⍵\n",
    "    } ⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 362,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→────────┐\n",
       "│3745 4644│\n",
       "└~────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 362,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day8 DATA ⍝ Part 1: 3745 Part2: 4644"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 9: Stream Processing\n",
    "https://adventofcode.com/2017/day/9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 366,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "DAY9←⊃⊃⎕NGET'data/2017/09.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 376,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day9←{\n",
    "    pos←0\n",
    "    str←⍵\n",
    "    Yield←{pos+←1⋄pos⊃str}\n",
    "    Skip←{⍺←0⋄c←Yield⍬⋄c='>':⍺⋄c='!':⍺∇⍬⊣Yield⍬⋄(⍺+1)∇⍬}\n",
    "    (0 0 0) {\n",
    "        3::1↓⍺  ⍝ Catch index error at end of input\n",
    "        (depth total skipped)←⍺\n",
    "        c←Yield⍬\n",
    "        c='{':((1+depth),total,skipped)∇⍬\n",
    "        c='}':((¯1+depth),(total+depth),skipped)∇⍬\n",
    "        c='<':(depth,total,skipped+Skip⍬)∇⍬\n",
    "        c='!':⍺∇⍬⊣Yield⍬\n",
    "        ⍺∇⍬\n",
    "    }⍬\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 377,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌→─────────┐\n",
       "│10050 4482│\n",
       "└~─────────┘\n",
       "</span>"
      ]
     },
     "execution_count": 377,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day9 DAY9 ⍝ Part 1: 10050 Part 2: 4482"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 10: Knot Hash\n",
    "https://adventofcode.com/2017/day/10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "'iotag'⎕CY'dfns'\n",
    "DAY10←147 37 249 1 31 2 226 0 161 71 254 243 183 255 30 70"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Rot←{\n",
    "    (skip pos len)←⍵\n",
    "    0=len:(skip+1) (256|pos+len+skip) ⍺\n",
    "    (skip+1) (256|pos+len+skip) (⊖@(256|pos iotag pos+len-1)⊢⍺)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "Round←{0=≢⍵:⍺⋄((2⊃⍺) Rot (0⊃⍺) (1⊃⍺) (0⊃⍵))∇1↓⍵}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 1 is a single round of the knot hash algorithm, with the answer sought is the product of the two first numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 436,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">     \n",
       "37230\n",
       "     \n",
       "</span>"
      ]
     },
     "execution_count": 436,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "×/2↑2⊃(0 0,⊂⍳256)Round DAY10 ⍝ Part 1: 37230"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, we apply the knot hash round 64 times. The lengths are now a byte array derived from a string representation of the data (including commas!) and 5 additional bytes added at the end.\n",
    "\n",
    "After the 64 rounds, we partition the result into blocks of 16:\n",
    "\n",
    "    ↓16 16 ⍴ sparse\n",
    "    \n",
    "and XOR-reduce each block:\n",
    "\n",
    "    {2⊥⊃≠/(8⍴2)∘⊤¨⍵}¨\n",
    "    \n",
    "and finally convert to hexadecimal:\n",
    "\n",
    "    ↓⍉{(⎕D,⎕A)[16⊥⍣¯1⊢⍵]}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Knot←{\n",
    "    lengths←(⎕UCS¨' '⎕R','⍕⍵),17 31 73 47 23\n",
    "    sparse←(0 0,⊂⍳256) {\n",
    "        0=⍵:2⊃⍺\n",
    "        (⍺ Round lengths)∇⍵-1\n",
    "    } 64\n",
    "    ↓⍉{(⎕D,⎕A)[16⊥⍣¯1⊢⍵]} {2⊥⊃≠/(8⍴2)∘⊤¨⍵}¨↓16 16 ⍴ sparse\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐\n",
       "│70│B8│56│A2│4D│58│61│94│33│13│98│C7│FC│FA│0A│AF│\n",
       "└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘\n",
       "</span>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Knot DAY10 ⍝ 70b856a24d586194331398c7fcfa0aaf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 11: Hex Ed\n",
    "https://adventofcode.com/2017/day/11\n",
    "\n",
    "Cube coordinates for hex grids; see https://www.redblobgames.com/grids/hexagons/#coordinates\n",
    "\n",
    "Map N-S axis to y, NE-SW to z and NW-SE to x\n",
    "\n",
    "Manhattan distance on the hex grid is half that on the cube grid.\n",
    "\n",
    "We start with splitting the input on comma, and then converting strings to the index of their first occurrance. Note that this ordering needs to be mirrored in the DELTA variable of offsets -- it's not general for all inputs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 474,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "DAY11←(∪⍳⊢)','(≠⊆⊢)⊃⊃⎕NGET'data/2017/11.txt'1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 478,
   "metadata": {},
   "outputs": [],
   "source": [
    "HexMHD←{⌊2÷⍨+/|⍵} ⍝ Manhattan distance on a hex grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 476,
   "metadata": {},
   "outputs": [],
   "source": [
    "DELTA←(¯1 0 1)(0 ¯1 1)(1 ¯1 0)(¯1 1 0)(1 0 ¯1)(0 1 ¯1) ⍝ SW S SE NW NE N -- order of index of first occurrance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All we need to do is sum it up - but as Dyalog's reduce goes R-L we need to reverse."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 479,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "643\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 479,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HexMHD ⊃+/⊖DELTA[DAY11] ⍝ Part 1: 643"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, find the max MHD attained whilst walking the path. Dyalog's scan reduction operator goes left to right and maintains the running total."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 491,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">    \n",
       "1471\n",
       "    \n",
       "</span>"
      ]
     },
     "execution_count": 491,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⌈/HexMHD¨+\\DELTA[DAY11] ⍝ Part 2: 1471"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 12: Digital Plumber\n",
    "https://adventofcode.com/2017/day/12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 503,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "'segs'⎕CY'dfns'\n",
    "DAY12←1↓¨⍎¨¨' <->,'∘segs¨⊃⎕NGET'data/2017/12.txt'1 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Discover all nodes reachable from the root by means of a classic breadth-first search."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 515,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "BFS←{              ⍝ nodes BFS node\n",
    "    graph←⍺\n",
    "    ⍬{\n",
    "        0=≢⍵:⍺\n",
    "        node←1↑⍵ ⋄ queue←1↓⍵\n",
    "        ch←node⊃graph\n",
    "        (⍺,node)∇(queue∪ch)~⍺\n",
    "    }⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 516,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "175\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 516,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "≢DAY12 BFS 0 ⍝ Part 1: 175"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2: find the number of connected components. We repeatedly apply the BFS routine above and mark visited nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 518,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "ConnectedComponents←{\n",
    "    graph←⍵\n",
    "    seen←⍬\n",
    "    0 {\n",
    "        root←⍵\n",
    "        root≥≢graph:⍺\n",
    "        root∊seen:⍺∇⍵+1\n",
    "        seen,←graph BFS root\n",
    "        (⍺+1)∇⍵+1\n",
    "    } 0\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 520,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">   \n",
       "213\n",
       "   \n",
       "</span>"
      ]
     },
     "execution_count": 520,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ConnectedComponents DAY12 ⍝ 213"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 13: Packet Scanners\n",
    "https://adventofcode.com/2017/day/13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "'segs'⎕CY'dfns'\n",
    "DAY13←⍎¨¨' :'∘segs¨⊃⎕NGET'data/2017/13.txt'1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "MAX←⊃⊃1↑¯1↑DAY13\n",
    "IDX←⊣/↑DAY13\n",
    "LEN←⊢/↑DAY13"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `Pos` function returns the location of the scanner for a given picosecond and layer depth."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "Pos←{cycle←⍺-1⋄1=2|⌊⍵÷cycle:cycle-cycle|⍵⋄cycle|⍵} ⍝ depth Pos pico - the index at pico, for given depth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 1 we traverse through once, keeping track of each layer where we got caught. The cost of getting caught is the layer index times its depth."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day13p1←{fw←⍵⋄0{⍵≥≢fw:⍺⋄0=fw[⍵] Pos ⍵:(⍺+fw[⍵]×⍵)∇⍵+1⋄⍺∇⍵+1}0}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2384\n",
       "</span>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/Day13p1 LEN@IDX⊢(1+MAX)⍴0 ⍝ Part 1: 2384"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In part 2, we need to find a delay that would enable us to traverse through all the layers without getting caught at all."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day13p2←{\n",
    "    fw←⍵\n",
    "    0 {                         ⍝ Current delay is ⍺\n",
    "        ⍵≥≢fw:⍺\n",
    "        0=fw[⍵]:⍺∇⍵+1           ⍝ Skip gaps\n",
    "        0=fw[⍵] Pos ⍵+⍺:(⍺+1)∇0 ⍝ Caught! Increase delay and re-start from layer 0\n",
    "        ⍺∇⍵+1                   ⍝ Still going: try the next layer\n",
    "    } 0                         ⍝ Current layer\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">3921270\n",
       "</span>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day13p2 LEN@IDX⊢(1+MAX)⍴0  ⍝ Part 2: 3921270"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 14: Disk Defragmentation\n",
    "https://adventofcode.com/2017/day/14\n",
    "\n",
    "This makes use of the 'Knot' function, defined in Day 10."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "'dec'⎕CY'dfns'   ⍝ Hex to dec helper function\n",
    "DAY14←'jzgqcdpd'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">8074\n",
       "</span>"
      ]
     },
     "execution_count": 95,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ADJ←↑{∊{(8⍴2)⊤⍵}¨dec¨Knot DAY14,'-',⍕⍵}¨⍳128\n",
    "+/∊ADJ  ⍝ Part 1: 8074"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we need to find connected components, just like we did in Day 12. With a bit of tweaking we could have re-used the same functions for days 12 and 14, but here are specific versions again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [],
   "source": [
    "Bfs←{⍺←⍬⋄0=≢⍵:⍺⋄(⍺,1↑⍵)∇((1↓⍵)∪⍺⍺ 1↑⍵)~⍺}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [],
   "source": [
    "Components←{⍺←0⋄0=≢⍵:⍺⋄(⍺+1)∇(1↓⍵)~⍺⍺ Bfs⊢1↑⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Connected←{\n",
    "    valid←({(⍵[0]≥0)∧(⍵[1]≥0)∧(⍵[0]<128)∧(⍵[1]<128)}¨n)/n←⍵+(¯1 0)(1 0)(0 1)(0 ¯1)\n",
    "    (1=⍺[valid])/valid\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1212\n",
       "</span>"
      ]
     },
     "execution_count": 143,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ADJ∘Connected Components ⊢ ⍸ADJ ⍝ Part 2: 1212"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 15: Dueling Generators\n",
    "https://adventofcode.com/2017/day/15\n",
    "\n",
    "- Generator A uses a factor 16807 and a start state of 679.\n",
    "- Generator B uses a factor of 48271 and a start state of 771\n",
    "\n",
    "A \"generator\" in this case is a function that remembers a bit of state between invocations. We achieve this by making an operator that takes a namespace as the operand."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [],
   "source": [
    "Part1←{⊢⍺⍺.prev←2147483647|⍺⍺.prev×⍺⍺.fact}\n",
    "GA←({⍵⊣⍵.(prev fact)←679 16807}⎕NS'') Part1\n",
    "GB←({⍵⊣⍵.(prev fact)←771 48271}⎕NS'') Part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">626\n",
       "</span>"
      ]
     },
     "execution_count": 160,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{⍺←0⋄0=⍵:⍺⋄(⍺+≡/{(16⍴2)⊤⍵}¨(GA⍬) (GB⍬))∇⍵-1} 40000000 ⍝ Part 1: 626 -- takes a good few mins to run"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, the generator functions need to spin until they find a value that's divisible by 4 or 8 respectively. Mercifully, we only need to consider 5M iterations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [],
   "source": [
    "Part2←{0=⍺⍺.multiple|⍺⍺.prev←2147483647|⍺⍺.prev×⍺⍺.fact:⍺⍺.prev⋄∇⍬}\n",
    "GA2←({⍵⊣⍵.(prev fact multiple)←679 16807 4}⎕NS'') Part2\n",
    "GB2←({⍵⊣⍵.(prev fact multiple)←771 48271 8}⎕NS'') Part2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">306\n",
       "</span>"
      ]
     },
     "execution_count": 158,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "{⍺←0⋄0=⍵:⍺⋄(⍺+≡/{(16⍴2)⊤⍵}¨(GA2⍬) (GB2⍬))∇⍵-1} 5000000 ⍝ Part 2: 306 -- also takes a good few mins to run"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 16: Permutation Promenade\n",
    "https://adventofcode.com/2017/day/16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "'segs'⎕CY'dfns'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY16←',' segs⊢⊃⊃⎕NGET'data/2017/16.txt'1\n",
    "Spin←{(-⍺)⊖⍵}\n",
    "Exchange←{(a b)←⍺⋄⍵[b a]@a b⊢⍵}\n",
    "Pair←{(⍵⍳⍺)Exchange ⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day16←{\n",
    "    ⍺←'abcdefghijklmnop'\n",
    "    0=≢⍵:⍺\n",
    "    cmd←⊃1↑⍵\n",
    "    's'=cmd[0]:((⍎1↓cmd) Spin ⍺)∇1↓⍵\n",
    "    'x'=cmd[0]:((⊃1↓'/'⎕VFI 1↓cmd) Exchange ⍺)∇1↓⍵\n",
    "    ((∊'/'(≠⊆⊢)1↓cmd) Pair ⍺)∇1↓⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">kbednhopmfcjilag\n",
       "</span>"
      ]
     },
     "execution_count": 178,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day16 DAY16 ⍝ Part 1: kbednhopmfcjilag"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, a _beeeellion_ iterations is obviously too much to brute, so we look for recurring patterns instead. End-of-dance state quickly recurs. The value at 100 is the value at 1,000 is the value at 1,000,000,000..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">fbmcgdnjakpioelh\n",
       "</span>"
      ]
     },
     "execution_count": 182,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'abcdefghijklmnop' {0=⍵:⍺⋄(⍺ Day16 DAY16)∇⍵-1} 100 ⍝ Part 2: fbmcgdnjakpioelh"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 17: Spinlock\n",
    "https://adventofcode.com/2017/day/17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 220,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "DAY17←356"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 227,
   "metadata": {},
   "outputs": [],
   "source": [
    "Insert←{(v cur st)←⍵⋄c←1+(≢⍺)|cur+st⋄c≥≢⍺:c (⍺,v)⋄c ((c↑⍺),v,c↓⍺)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 228,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day17p1←{2018=⍵:⍺⋄(cur buf)←⍺⋄(buf Insert ⍵ cur DAY17)∇⍵+1}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 229,
   "metadata": {},
   "outputs": [],
   "source": [
    "(cur buf)←0 (,0)Day17p1 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 231,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">808\n",
       "</span>"
      ]
     },
     "execution_count": 231,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "buf⌷⍨cur+1 ⍝ Part 1: 808"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we're looking for a value at a given index rather than a particular value. This means we don't need to actually maintain the circular buffer at all."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 225,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day17p2←{(cur target st)←⍵⋄cur←1+st|cur+DAY17⋄1=cur:cur,st,st+1⋄cur,target,st+1}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">47465686\n",
       "</span>"
      ]
     },
     "execution_count": 226,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1⊃Day17p2⍣50000000⊢0 ¯1 1 ⍝ Part 2: 47465686 -- takes a minute or so to run"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 18: Duet\n",
    "https://adventofcode.com/2017/day/18"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "DAY18←{6::⍵⋄⍎⍵}¨¨' '(≠⊆⊢)¨⊃⎕NGET'data/2017/18.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day18←{\n",
    "    mem←⍵\n",
    "    ri←{'abfips'⍳⍵}         \n",
    "    val←{(1=2|⎕DR)⍵:⍵⋄⍺[ri ⍵]}                     \n",
    "    set←{(x y)←⍵⋄1∘+@7⊢(⍺ val y)@(ri x)⊢⍺}\n",
    "    mul←{(x y)←⍵⋄1∘+@7⊢(⍺ val y)∘×@(ri x)⊢⍺}\n",
    "    add←{(x y)←⍵⋄1∘+@7⊢(⍺ val y)∘+@(ri x)⊢⍺}\n",
    "    mod←{(x y)←⍵⋄1∘+@7⊢(⍺ val y)∘|@(ri x)⊢⍺}\n",
    "    rcv←{0≠⍺ val ⊃⍵:99∘+@7⊢⍺⋄1∘+@7⊢⍺}\n",
    "    snd←{⍺ set 's' (⊃⍵)}\n",
    "    jgz←{(x y)←⍵⋄(⍺ val x)>0:(⍺ val y)∘+@7⊢⍺⋄1∘+@7⊢⍺}\n",
    "    {\n",
    "        ip←¯1↑⍵\n",
    "        instr←ip⊃mem⋄op←⊃instr\n",
    "        ⍵ (⍎op) 1↓instr         \n",
    "    }⍣{(¯1↑⍺)>≢mem}⍺\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">3423\n",
       "</span>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "6⊃0 0 0 0 0 0 1 Day18 DAY18 ⍝ Part 1: 3423"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2, it turns out the `snd` and `rcv` have nothing to do with audio, but are an IPC mechanism! We'll need two separate \"processes\" and message queues. We expand the registers a bit:\n",
    "    \n",
    "    1 2 3 4 5    6        7       8\n",
    "    a b f i p blocked send-count ip\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "MSG←{⍵⊣⍵.Queue←⍬ ⍬}⎕NS''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Step←{\n",
    "    pid←⍺\n",
    "    mem←DAY18\n",
    "    ri←{'abfip'⍳⍵}         \n",
    "    val←{(1=2|⎕DR)⍵:⍵⋄⍺[ri ⍵]}                     \n",
    "    set←{(x y)←⍵⋄1∘+@8⊢(⍺ val y)@(ri x)⊢⍺}\n",
    "    mul←{(x y)←⍵⋄1∘+@8⊢(⍺ val y)∘×@(ri x)⊢⍺}\n",
    "    add←{(x y)←⍵⋄1∘+@8⊢(⍺ val y)∘+@(ri x)⊢⍺}\n",
    "    mod←{(x y)←⍵⋄1∘+@8⊢(⍺ val y)∘|@(ri x)⊢⍺}\n",
    "    jgz←{(x y)←⍵⋄(⍺ val x)>0:(⍺ val y)∘+@8⊢⍺⋄1∘+@8⊢⍺}\n",
    "    snd←{MSG.Queue[1+~pid],←⍺ val ⊃⍵⋄1∘+@7 8⊢⍺} ⍝ Add item to other's queue, and 1 to send-count and ip\n",
    "    \n",
    "    rcv←{                        ⍝ Pull item from message queue\n",
    "        data←⊃MSG.Queue[1+pid]   \n",
    "        0=≢data:1@6⊢⍺            ⍝ Blocked! Ip stays unchanged.\n",
    "        val←1⊃data\n",
    "        MSG.Queue[1+pid]←⊂1↓data ⍝ Pop queue\n",
    "        0@6⊢⍺ set (⊃⍵) val       ⍝ Set reg with value from queue, and make note that we're not blocked\n",
    "    }\n",
    "    \n",
    "    ip←¯1↑⍵\n",
    "    ip>≢mem:⍵                    ⍝ Already terminated\n",
    "    instr←ip⊃mem⋄op←⊃instr\n",
    "    ⍵ (⍎⊃instr) 1↓instr\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "Deadlocked←{(p0 p1)←⍵⋄(p0[6]=1)∧p1[6]=1}\n",
    "Terminated←{(p0 p1)←⍵⋄(p0[8]≥≢DAY18)∧p1[8]≥≢DAY18}\n",
    "Done←{(Deadlocked ⍵)∨Terminated ⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">7493\n",
       "</span>"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "7⊃2⊃{⊃↓Step/0 1,⍪⍵}⍣{Done ⍺} (0 0 0 0 0 0 0 1)(0 0 0 0 1 0 0 1) ⍝ 'p' reg holds process id -- Part 2: 7493"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 19: A Series of Tubes\n",
    "https://adventofcode.com/2017/day/19\n",
    "\n",
    "After eyeballing the data we make the following data-dependent assumptions:\n",
    "\n",
    "- No letter sits on a junction\n",
    "- Path ends on the letter 'Y'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">Was ON\n",
       "</span>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⎕IO←1\n",
    "DAY19←↑⊃⎕NGET'data/2017/19.txt'1\n",
    "]rows on"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Turn←{\n",
    "    graph←⍺\n",
    "    (prev cur)←⍵\n",
    "    Valid←{({(⍵[1]>0)∧(⍵[2]>0)∧(⍵[1]≤≢graph)∧⍵[2]≤≢graph}¨⍵)/⍵}\n",
    "    ⊃(' '≠graph[coords])/coords←Valid (⊂prev)~⍨{cur+⍵}¨(¯1 0)(1 0)(0 ¯1)(0 1)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Next←{ \n",
    "    (prev cur)←⍵\n",
    "    dir←v÷(2*∘÷⍨+.×⍨)v←cur-prev          ⍝ Unit-vector in the direction of travel\n",
    "    next←cur+dir\n",
    "    ⍺[⊂cur]='+':cur (⍺ Turn prev cur) 1  ⍝ On a jct\n",
    "    ⍺[⊂next]∊⎕A,⍺[⊂cur],'+':cur (next) 1 ⍝ Straight or coming to jct\n",
    "    ⍺[⊂next]=' ':cur (cur) 0             ⍝ End of the track\n",
    "    cur (next+dir) 2                     ⍝ Underpass\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day19←{\n",
    "    graph←⍺\n",
    "    (⍬ 1) {\n",
    "        (letters count)←⍺\n",
    "        (prev cur delta)←graph Next ⍵\n",
    "        graph[⊂cur]='Y':(letters,'Y') (count+delta)\n",
    "        graph[⊂cur]∊⎕A:((letters,graph[⊂cur]) (count+delta))∇prev (cur)\n",
    "        (letters (count+delta))∇prev (cur)\n",
    "    } ⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">16\n",
       "</span>"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊢START←DAY19[1;]⍳'|'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">┌─────────┬─────┐\n",
       "│GPALMJSOY│16204│\n",
       "└─────────┴─────┘\n",
       "</span>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "DAY19 Day19 (0 START) (1 START) ⍝ Part 1: GPALMJSOY Part 2: 16204"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 20: Particle Swarm\n",
    "https://adventofcode.com/2017/day/20\n",
    "\n",
    "Convergence for some number of itereations -- not converged at 300, but converged at 500. Part 1 is simply a sum-scan: acc vel pos → acc (acc+vel) (acc+vel+pos). We can do the whole lot as just:\n",
    "\n",
    "    +⍀⍣500\n",
    "    \n",
    "Gotta love APL. We create a matrix with the shape 3 × 1000 × 3 holding acceleration, velocity and position in that order -- the use of dyadic `⍉` is explained in depth here: https://stackoverflow.com/questions/62634746/how-do-i-convert-a-vector-of-triplets-to-a-3xnx3-matrix-in-dyalog-apl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "DAY20←⊖1 0 2⍉(9÷⍨≢DATA)3 3⍴DATA←⍎¨'-?\\d+'⎕S'&'⊢⊃⎕NGET'data/2017/20.txt'1 ⍝ 3 x 1000 x 3: acc vel pos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can get the state after 500 iterations simply by `+⍀⍣500`. What remains is to find the index of the point which has the smallest (`⊃⍋`) Manhattan distance (`+/|`) from the origin."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">170\n",
       "</span>"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "⊃⍋+/|2⌷+⍀⍣500⊢DAY20 ⍝ Part 1: 170"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2, remove all collisions. We can make good use of key `⌸` here."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [],
   "source": [
    "Day20p2←{state←+⍀⍵⋄hist←{⍵ (2>≢⍵)}⌸2⌷state⋄state[;∊(hist[;1])/hist[;0];]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">571\n",
       "</span>"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "≢2⌷Day20p2⍣500⊢DAY20 ⍝ Part 2: 571"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 21: Fractal Art\n",
    "https://adventofcode.com/2017/day/21\n",
    "\n",
    "Most of the work here is setting up the lookup table. We expand all possible rotations and flips of each pattern key, and stay in the \"matrix domain\" rather than the unfolded strings.\n",
    "\n",
    "The `Tile` dfn divides up its argument matrix into a set of either 2×2 or 3×3 sub-matrices using key `⌸`. The curious expression `(⍴×⍴∘⊃)⍴0 2 1 3⍉↑` in `Day21` uses a dyadic transpose to merge the sub-matrices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 291,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "'segs'⎕CY'dfns'\n",
    "DAY21←⍉↑'/'⎕R''¨↓⍉↑' =>'∘segs¨⊃⎕NGET'data/2017/21.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 299,
   "metadata": {},
   "outputs": [],
   "source": [
    "Rot←{(⍵)(⌽⍉⍵)(⌽⊖⍵)(⊖⍉⍵)}\n",
    "Fold←{s←.5*⍨≢⍵⋄s s⍴⍵}\n",
    "Trn←{m←Fold ⍵⋄∪(Rot m),(Rot⌽m),(Rot⊖m)}\n",
    "Expand←{⍺←⍬⋄0=≢⍵:⍺⋄(k v)←⊃⍵⋄fv←Fold v⋄(⍺,{⍵ fv}¨Trn k)∇ 1↓⍵}\n",
    "Tile←{2=⍺:,⊢∘⊂⌺(2 2⍴2 2)⊢⍵⋄1 1↓⊢∘⊂⌺(2 2⍴3 3)⊢0⍪0⍪0,0,⍵}\n",
    "Day21←{s←2+2|≢⍵⋄tiles←,s Tile ⍵⋄dim←s÷⍨≢⍵⋄((⍴×⍴∘⊃)⍴0 2 1 3⍉↑)dim dim⍴{Find ⊂⍵}¨tiles}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 300,
   "metadata": {},
   "outputs": [],
   "source": [
    "TABLE←Expand ↓DAY21"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 301,
   "metadata": {},
   "outputs": [],
   "source": [
    "Find←(⊣/↑TABLE)∘{⊃⊢/⊃TABLE[⍺⍳⍵]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 302,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">162\n",
       "</span>"
      ]
     },
     "execution_count": 302,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/∊'#'=Day21⍣5⊢3 3⍴'.#...####' ⍝ Part 1: 162"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 303,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2264586\n",
       "</span>"
      ]
     },
     "execution_count": 303,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/∊'#'=Day21⍣18⊢3 3⍴'.#...####' ⍝ Part 2: 2264586"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 22: Sporifica Virus\n",
    "https://adventofcode.com/2017/day/22\n",
    "\n",
    "We don't know our data size up-front, as the grid extends 'infinitely' in all directions. Trial and error soon lets us pick a finite size. This is arguably a bit wasteful as the grid will be pretty sparse."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "Make←{s←(2÷⍨⍺)-2÷⍨≢⍵⋄ctr←⊂s s⋄1@(ctr+⍸⍵)⊢⍺ ⍺⍴0} ⍝ Center data in larger array of shape ⍺ ⍺"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [],
   "source": [
    "DAY22←429 Make 25 25⍴(∪⍳⊢)∊⊃⎕NGET'data/2017/22.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day22p1←{\n",
    "    m←⍺\n",
    "    start←⌊2÷⍨≢m\n",
    "    {\n",
    "        (row col infected count dir)←⍵\n",
    "        cur←m[row;col]\n",
    "        m[row;col]←~cur\n",
    "        newDir←cur {1=⍺:¯1∘⌽ ⍵⋄1∘⌽ ⍵} dir \n",
    "        newPos←(⊃newDir)⌷(⊂row col)(-,+)(1 0)(0 1)\n",
    "        (⊃newPos),(infected+~cur) (count-1) (newDir)\n",
    "    }⍣⍵⊢start start 0 ⍵ (⍳4)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">5261\n",
       "</span>"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2⊃DAY22 Day22p1 10000 ⍝ Part 1: 5261"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For part 2 we're doing a hundred million iterations and have more states to deal with, but code-wise there are not a lot of changes.\n",
    "\n",
    "The new state transitions are: clean, weakened, infected, flagged for 0 1 2 3, so we need to set the initial state to 2 for all infected cells."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day22p2←{\n",
    "    m←0 2[⍺]     ⍝ Infected cells should have value 2\n",
    "    start←⌊2÷⍨≢m\n",
    "    {\n",
    "        (row col infected count dir)←⍵\n",
    "        cur←m[row;col]\n",
    "        m[row;col]←cur⊃1 2 3 0\n",
    "        newDir←cur {0=⍺:1⌽⍵⋄1=⍺:⍵⋄2=⍺:¯1⌽⍵⋄¯2⌽⍵} dir\n",
    "        newPos←(⊃newDir)⌷(⊂row col)(-,+)(1 0)(0 1)\n",
    "        (⊃newPos),(infected+2=m[row;col]) (count-1) (newDir)\n",
    "    }⍣⍵⊢start start 0 ⍵ (⍳4)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">2511927\n",
       "</span>"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2⊃DAY22 Day22p2 10000000 ⍝ Part 2: 2511927 -- takes around 90s to run"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 23: Coprocessor Conflagration\n",
    "https://adventofcode.com/2017/day/23\n",
    "\n",
    "Moar messy ASM to un-mess. Same-ish as Day 18 above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "DAY23←{6::⍵⋄⍎⍵}¨¨' '(≠⊆⊢)¨⊃⎕NGET'data/2017/23.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day23←{\n",
    "    mem←⍵\n",
    "    ri←{'abcdefgh'⍳⍵}         \n",
    "    val←{(1=2|⎕DR)⍵:⍵⋄⊃⍺[ri ⍵]}                     \n",
    "    set←{(x y)←⍵⋄1∘+@10⊢(⍺ val y)@(ri x)⊢⍺}\n",
    "    mul←{(x y)←⍵⋄1∘+@9⊢⍺ set x,(⍺ val x)×⍺ val y}\n",
    "    sub←{(x y)←⍵⋄⍺ set x,(⍺ val x)-⍺ val y}\n",
    "    jnz←{(x y)←⍵⋄(⍺ val x)≠0:(⍺ val y)∘+@10⊢⍺⋄1∘+@10⊢⍺}\n",
    "    {\n",
    "        ip←¯1↑⍵\n",
    "        instr←ip⊃mem⋄op←⊃instr\n",
    "        ⍵ (⍎op) 1↓instr         \n",
    "    }⍣{(¯1↑⍺)>≢mem}⍺\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">5929\n",
       "</span>"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "9⊃0 0 0 0 0 0 0 0 0 1 Day23 DAY23 ⍝ Part 1: 5929"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part 2 - set 'a' to 1 and run again, right? No, sadly.\n",
    "\n",
    "The ASM code contains a multitude of nested loops that means that the program will not complete before the heat death of the universe. So let's look at the actual code.\n",
    "\n",
    "```\n",
    "{{ init a = 1 }}\n",
    "\n",
    "1:  set b 79\n",
    "2:  set c b\n",
    "3:  jnz a 2         IF a != 0: GOTO L1\n",
    "4:  jnz 1 5         GOTO L2\n",
    "5:  mul b 100       L1\n",
    "6:  sub b -100000\n",
    "7:  set c b\n",
    "8:  sub c -17000\n",
    "9:  set f 1         L2\n",
    "10:  set d 2\n",
    "11: set e 2         L5\n",
    "\n",
    "12: set g d         L4\n",
    "13: mul g e\n",
    "14: sub g b\n",
    "15: jnz g 2         IF g != 0: GOTO L3\n",
    "16: set f 0\n",
    "17: sub e -1        L3\n",
    "18: set g e\n",
    "19: sub g b\n",
    "20: jnz g -8        IF g != 0: GOTO L4\n",
    "\n",
    "21: sub d -1\n",
    "22: set g d\n",
    "23: sub g b         L6\n",
    "24: jnz g -13       IF g != 0: GOTO L5\n",
    "25: jnz f 2         IF f != 0: GOTO L6\n",
    "26: sub h -1\n",
    "27: set g b         L7\n",
    "28: sub g c\n",
    "29: jnz g 2         IF g != 0: GOTO L8\n",
    "30: jnz 1 3         GOTO END\n",
    "31: sub b -17       L8\n",
    "32: jnz 1 -23       GOTO L2\n",
    "\n",
    "END\n",
    "\n",
    "The innermost (L4) loop (addresses 12-20) can be directly\n",
    "translated to pseudo code as:\n",
    "\n",
    "def L4(regs):\n",
    "    while True:\n",
    "        regs[\"g\"] = regs[\"d\"]\n",
    "        regs[\"g\"] *= regs[\"e\"]\n",
    "        regs[\"g\"] -= regs[\"b\"]\n",
    "\n",
    "        if regs[\"g\"] == 0:\n",
    "            regs[\"f\"] = 0\n",
    "        regs[\"e\"] += 1\n",
    "\n",
    "        regs[\"g\"] = regs[\"e\"]\n",
    "        regs[\"g\"] -= regs[\"b\"]\n",
    "\n",
    "        if regs[\"g\"] == 0:\n",
    "            break\n",
    "\n",
    "where only g, f and e changes. The g value is always 0\n",
    "after the loop terminates. The value of e is always b.\n",
    "The f value is either unchanged, or set to 0.\n",
    "\n",
    "If we refactor the code a bit further, we get to\n",
    "\n",
    "def L4(regs):\n",
    "    while True:\n",
    "        regs[\"g\"] = regs[\"d\"] * regs[\"e\"] - regs[\"b\"]\n",
    "\n",
    "        if regs[\"g\"] == 0:\n",
    "            regs[\"f\"] = 0\n",
    "\n",
    "        regs[\"e\"] += 1\n",
    "\n",
    "        regs[\"g\"] = regs[\"e\"] - regs[\"b\"]\n",
    "\n",
    "        if regs[\"g\"] == 0:\n",
    "            break\n",
    "\n",
    "which means that f is 0 if and only if d*e = b, or in other\n",
    "words if b/d is an integer in the range [1, b). The whole L4\n",
    "loop can be removed and replaced with:\n",
    "\n",
    "def L4(regs):\n",
    "    if regs[\"b\"] % regs[\"d\"] == 0:\n",
    "        v = regs[\"b\"] // regs[\"d\"]\n",
    "        if v >= regs[\"e\"] and v < regs[\"b\"]:\n",
    "            regs[\"f\"] = 0\n",
    "\n",
    "    regs[\"e\"] = regs[\"b\"]\n",
    "    regs[\"g\"] = 0\n",
    "\n",
    "We could optimise out the L5 loop the same way, but with L4\n",
    "removed the program runs in a few minutes.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hideous, crude, ugly - pick any three. Direct tradfn translation of the ASM code, with the L4 hack described above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "r←Day23p2 ;b;c;h;d;f;e;g;v\n",
    "(b c d e f g h)←107900 124900 0 0 0 0 0\n",
    ":While 1\n",
    "    (f d)←1 2\n",
    "\n",
    "    :While 1\n",
    "        e←2\n",
    "\n",
    "        :If 0=d|b         ⍝ L4 hack\n",
    "            v←⌊b÷d\n",
    "            :If (v≥e)∧v<b\n",
    "                f←0\n",
    "            :EndIf\n",
    "        :EndIf\n",
    "\n",
    "        e←b\n",
    "        d+←1\n",
    "        g←d-b\n",
    "\n",
    "        :If g=0\n",
    "            :Leave\n",
    "        :EndIf\n",
    "    :EndWhile\n",
    "\n",
    "    :If f=0\n",
    "        h+←1\n",
    "    :EndIf\n",
    "    g←b-c\n",
    "\n",
    "    :If g=0\n",
    "        :Leave\n",
    "    :EndIf\n",
    "\n",
    "    b-←¯17\n",
    ":EndWhile\n",
    "r←h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">907\n",
       "</span>"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Day23p2 ⍝ Part 2: 907"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 24: Electromagnetic Moat\n",
    "https://adventofcode.com/2017/day/24\n",
    "\n",
    "Recursicve descent. Reasonably quick (~6s for part 1), despite not being tail-recursive. Part 2 is very similar, and we could probably have combined both parts at a loss of some clarity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "DAY24←⍎¨'/'⎕R','¨⊃⎕NGET'data/2017/24.txt'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "Find←{(a b)←↓⍉↑↑⍺⋄⍺[(⍸⍵=a)∪⍸⍵=b]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "r←components Day24p1 args;path;pins;strongest;c;bridge\n",
    "(path pins)←args\n",
    "strongest←path\n",
    ":For c :In (components~path) Find pins\n",
    "    bridge←(components~c)Day24p1 (⊂(path,⊂c)),c {r←⍺~⍵⋄0=≢r:⊃⍺⋄⊃r} pins ⍝ Handle when both pins are equal\n",
    "    :If (+/∊bridge)>+/∊strongest\n",
    "        strongest←bridge\n",
    "    :EndIf\n",
    ":EndFor\n",
    "r←strongest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1511\n",
       "</span>"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/∊DAY24 Day24p1 (⊂0 0) 0 ⍝ Part 1: 1511"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "r←components Day24p2 args;path;pins;longest;c;bridge\n",
    "(path pins)←args\n",
    "longest←path\n",
    ":For c :In (components~path) Find pins\n",
    "    bridge←(components~c)Day24p2 (⊂(path,⊂c)),c {r←⍺~⍵⋄0=≢r:⊃⍺⋄⊃r} pins ⍝ Handle when both pins are equal\n",
    "    :If (≢bridge)>≢longest\n",
    "        longest←bridge\n",
    "    :ElseIf ((≢bridge)=≢longest)∧(+/∊bridge)>+/∊longest\n",
    "        longest←bridge\n",
    "    :EndIf\n",
    ":EndFor\n",
    "r←longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1471\n",
       "</span>"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/∊DAY24 Day24p2 (⊂0 0) 0 ⍝ Part 2: 1471"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After some discussion on the APL Orchard forum, @ngn offered up the follwing version for part 1, which is significantly faster, shorter and no tradfn:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1511\n",
       "</span>"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s←+/↑DAY24⋄n←1+⌈/∊DAY24⋄g←(⍳n)∘.∊DAY24⋄u←∘.≠⍨⍳≢DAY24\n",
    "0{∨/c←⍵∧⍺⌷g:⌈/t+(-⍺-t←c/s)∇¨↓⍵∧⍤1⊢c⌿u⋄0}≡¨DAY24"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we un-golf it a bit, it's a bit easier to see how that works:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "STRENGTHS←+/↑DAY24      \n",
    "COUNT←1+⌈/∊DAY24        \n",
    "GRAPH←(⍳COUNT)∘.∊DAY24  \n",
    "INVIDM←∘.≠⍨⍳≢DAY24      ⍝ Inverted identity matrix used to exclude the current item"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "D24p1←{\n",
    "    candidates←⍵∧⍺⌷GRAPH\n",
    "    t←candidates/STRENGTHS\n",
    "    ∨/candidates:⌈/t+(-⍺-t)∇¨↓⍵∧⍤1⊢candidates⌿INVIDM\n",
    "    0\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">1511\n",
       "</span>"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "0 D24p1 ≡¨DAY24"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Day 25: The Halting Problem\n",
    "https://adventofcode.com/2017/day/25\n",
    "\n",
    "All I want for Christmas is a Turing Machine.\n",
    "\n",
    "Our given state machine looks like so:\n",
    "\n",
    "```\n",
    "+---+-------+-------+\n",
    "|   |   0   |   1   |\n",
    "+---+-------+-------+\n",
    "| A | 1 R B | 0 L C |\n",
    "| B | 1 L A | 1 R D |\n",
    "| C | 1 R A | 0 L E |\n",
    "| D | 1 R A | 0 R B |\n",
    "| E | 1 L F | 1 L C |\n",
    "| F | 1 R D | 1 R A |\n",
    "+---+-------+-------+\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "STATE←6 6⍴1 1 1 0 ¯1 2 1 ¯1 0 1 1 3 1 1 0 0 ¯1 4 1 1 0 0 1 1 1 ¯1 5 1 ¯1 2 1 1 3 1 1 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "Day25←{\n",
    "    (pos state)←⍵\n",
    "    args←(0 3[pos⊃TAPE])+⍳3\n",
    "    (nv m ns)←STATE[state;args]\n",
    "    TAPE[pos]←nv\n",
    "    (pos+m) ns\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<span style=\"white-space:pre; font-family: monospace\">4287\n",
       "</span>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "TAPE←12919244⍴0⋄_←Day25⍣12919244⊢6459622 0⋄+/TAPE ⍝ 4287"
   ]
  },
  {
   "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
}