Advent of Code 2023 Dyalog APL.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ca36f895",
   "metadata": {},
   "source": [
    "# Advent of Code, 2023\n",
    "\n",
    "My attempt at the 2023 edition.\n",
    "\n",
    "Caveats: \n",
    "1. Quite hard this year, and I didn't get to the end -- gave up after day 15\n",
    "2. Some gaps where I either didn't solve the problem, or wrote it in Python\n",
    "3. Some solutions 'inspired' by others (attributed)\n",
    "4. Fairly unedited and 'raw'\n",
    "\n",
    "## Day 1: Trebuchet?!\n",
    "\n",
    "https://adventofcode.com/2023/day/1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "09a97f1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "(⎕FR⎕PP)←1287 34"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "98037b00",
   "metadata": {},
   "outputs": [],
   "source": [
    "data← ⊃⎕NGET'data/2023/1'1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5be20dea",
   "metadata": {},
   "source": [
    "Find the first and last digit. Treat as a two-digit number. Sum. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "d8e89afe",
   "metadata": {},
   "outputs": [],
   "source": [
    "day1←{+/⍎⍕(⊣/,⊢/)¨⍵∩¨⊂⎕D}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "61c3152a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">55477\n",
       "</pre>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "day1 data ⍝ part 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f894dfe",
   "metadata": {},
   "source": [
    "For part 2, we need to replace spelled-out digits with their numerical equivalents, e.g. 'four' → 4. Added complication: overlapping spellings, 'nineight'.\n",
    "\n",
    "We can do some regexy pre-processing to tidy that up."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "b52ee8cf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">54431\n",
       "</pre>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "day1 'threeight' 'oneight' 'eightwo' 'nineight' 'twone' 'sevenine' 'eighthree' 'one' 'two' 'three' 'four' 'five' 'six' 'seven' 'eight' 'nine'⎕R (⍕¨38 18 82 98 21 79 83 1 2 3 4 5 6 7 8 9)⊢data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06dd2cab",
   "metadata": {},
   "source": [
    "## Day 2: Cube Conundrum\n",
    "\n",
    "https://adventofcode.com/2023/day/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "1459a0ba",
   "metadata": {},
   "outputs": [],
   "source": [
    "data← ⊃⎕NGET'data/2023/2'1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "4883b18e",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "p ← {\n",
    "    d ← (1+⍵⍳':')↓⍵\n",
    "\n",
    "    ⍝ Split on semicolon\n",
    "    rounds ← ';' (≠⊆⊢) d\n",
    "    \n",
    "    ⍝ return array of shape (≢rounds)3 with columns RGB\n",
    "    result ← ⍬\n",
    "    _ ← {\n",
    "        f←↓⍉(2÷⍨≢f)2⍴f←⊃↓⍉' '(≠⊆⊢)⍵~','\n",
    "        r ← 3/0\n",
    "        r['red' 'green' 'blue'⍳⊃f[2]] ← ⍎¨⊃f[1] ⍝ RGB\n",
    "        result,←⊂r\n",
    "        ⍬\n",
    "    }¨rounds\n",
    "    result\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "5ac3b1eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "r←p¨ data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "04db3bed",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">2377\n",
       "</pre>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/⍸{∧⌿,12 13 14 ≥⍤ 1 ⊢ ↑⍵}¨r ⍝ part 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "702f8d81",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">71220\n",
       "</pre>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+⌿{×⌿⌈⌿↑⍵}¨r ⍝ part 2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "740f079c",
   "metadata": {},
   "source": [
    "## Day 3\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "0497d915",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">538046\n",
       "</pre>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data←↑⊃⎕NGET'data/2023/3'1\n",
    "digits←data∊⎕D\n",
    "dd←digits+({((5⊃,⍵)∊⎕D)∧(0<≢(,⍵)~' .0123456789')})⌺3 3⊢data\n",
    "+/⍎¨(digits⊆⍤1 1⊢data)[⍸2∊¨digits⊆⍤1 1⊢dd]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "70c00bc6",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "part2 ← { ⍝ Based on a solution from Aaron Hsu\n",
    "    ⍝ Id all *s by their ravel index\n",
    "    sh ← ⍴⍵\n",
    "    stars ← sh⍴(⍳×/sh)×,'*'=⍵\n",
    "    \n",
    "    ⍝ Fill each *'s 3×3 neighbourhood with its id. If a \n",
    "    ⍝ catchment area\n",
    "    catchment ← {⌈/⌈/⍵}⌺3 3⊢stars\n",
    "\n",
    "    ⍝ Generate a mask showing the location of the numbers\n",
    "    digits ← ⍵∊⎕D\n",
    "    \n",
    "    ⍝ .. and use this to extract the numbers in ravel order.\n",
    "    numbers ← ⍎¨digits⊆⍥,⍵\n",
    "\n",
    "    ⍝ We can use the digits mask to grab from the gear\n",
    "    ⍝ catchment areas in the same way. We pick the max \n",
    "    ⍝ as we don't care if several digits of the same number\n",
    "    ⍝ may fall within the same catchment area.\n",
    "    gears ← ⌈/¨digits⊆⍥,catchment\n",
    "\n",
    "    ⍝ In order to qualify, a gear must have exactly two numbers\n",
    "    ⍝ in its catchment area\n",
    "    +/{2=≢⍵:×/numbers[⍵]⋄0}⌸gears\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "09612dfe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">81709807\n",
       "</pre>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "part2 data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbd5d790",
   "metadata": {},
   "source": [
    "## Day 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "449db046",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">21558\n",
       "</pre>"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "length ← 10\n",
    "data ← 1↓⍤1⊢'\\d+'⎕S'&'⍤1↑⊃⎕NGET'data/2023/4'1\n",
    "winners ← length↑⍤1⊢data\n",
    "mine ← length↓⍤1⊢data\n",
    "count ← +/mine∊⍤1 1⊢winners\n",
    "+⌿⌊2*¯1+count ⍝ part1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "efec62af",
   "metadata": {},
   "outputs": [],
   "source": [
    "∇ r ← part2 wins ;⎕IO;d;i\n",
    "⎕IO←0\n",
    "d ← 1⍴⍨≢wins\n",
    ":for i :in ⍳≢wins\n",
    "    idx ← (i+1) (⊣+∘⍳-⍨)i+wins[i]+1\n",
    "    d[idx] +← d[i]\n",
    ":end\n",
    "r ← +/d \n",
    "∇"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "aae47a0c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">10425665\n",
       "</pre>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "part2 count"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66af4b11",
   "metadata": {},
   "source": [
    "## Day5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba75dc2e",
   "metadata": {},
   "source": [
    "(Pythoned)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "440d060d",
   "metadata": {},
   "source": [
    "## Day6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "366b8e10",
   "metadata": {},
   "outputs": [],
   "source": [
    "data ← ⊃⎕NGET'data/2023/6'1\n",
    "day6←{+⌿⍵<rng×⍺-rng←⍳⍺}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "0bdecae8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">┌────────────────────────────────────┬────────────────────────────────────┐\n",
       "│Time:        40     92     97     90│Distance:   215   1064   1505   1100│\n",
       "└────────────────────────────────────┴────────────────────────────────────┘\n",
       "</pre>"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "63aaf5c5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">6209190\n",
       "</pre>"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(time dist) ← '\\d+'⎕S{⍎⍵.Match}¨data\n",
    "×/day6/⍉↑time dist ⍝ part1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66796ac6",
   "metadata": {},
   "source": [
    "Part 2: now a single, HUUUGE race."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "d2a29e82",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">28545089\n",
       "</pre>"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "day6/'\\d+'⎕S{⍎⍵.Match}¨{⍵~' '}¨data ⍝ part2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "665bea2f",
   "metadata": {},
   "source": [
    "## Day7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "fbc7a983",
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←1\n",
    "val←'23456789TJQKA'\n",
    "data ← ⊃⎕NGET'data/2023/7'1\n",
    "(hands bets)←↓⍉↑' '(≠⊆⊢)¨data\n",
    "bets←⍎¨bets"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "64579bd3",
   "metadata": {},
   "source": [
    "Key insight: in an ordered histogram of a hand, the first two numbers are sufficient to represent the 'type'. We can map these to a single base10 number "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "4b574e74",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "rank ← {\n",
    "    ⍝ Rank a hand (⍵) into a 'type' (4 of a kind, full house etc)\n",
    "\n",
    "⍝take 2┳┓┏sort━┓hist┓   ┏to index\n",
    "    10⊥2↑{⍵[⍒⍵]}{≢⍵}⌸val⍳⍵\n",
    "⍝   ┗━┻base 10\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5795ba3f",
   "metadata": {},
   "source": [
    "The ordinal permutation tells us where in the ordered sequence a number falls: an item with ordinal 13 means that the item is the 13th number. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "54892762",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">253638586\n",
       "</pre>"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/bets×⍋⍋{(rank ⍵),val⍳⍵}¨hands ⍝ part 1: 253638586"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4f64e418",
   "metadata": {},
   "source": [
    "Part 2: now J means Joker, not Jack. A Joker will take on the value that maximises the value of a hand, but ties are still broken with the Joker as the lowest-valued card."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "d69c44f1",
   "metadata": {},
   "outputs": [],
   "source": [
    "dejoker ← {⌈⌿val∘.{rank⍺@('J'=⊢)⍵}⍵}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "6c14cdb9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">253253225\n",
       "</pre>"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/bets×⍋⍋,⌿↑(dejoker hands)('J23456789TQKA'∘⍳¨hands) ⍝ part 2: 253253225"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "02bea512",
   "metadata": {},
   "source": [
    "## Day8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "4ce06fd4",
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "data ← ⊃⎕NGET'data/2023/8'1\n",
    "(key left right) ← ↓⍉↑'[A-Z]+'⎕S'&'¨2↓data\n",
    "ch ← left right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "e077bcb0",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "day8p1 ← { ⍺←0\n",
    "    dir ← 'R'=⍺⍺[(≢⍺⍺)|⍺]\n",
    "    elem ← (key⍳⊂⍵)⊃dir⊃ch\n",
    "    elem ≡ 'ZZZ': 1+⍺\n",
    "    elem ∇⍨ 1+⍺\n",
    "} "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "4c6047ae",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">12599\n",
       "</pre>"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(⊃data)day8p1 'AAA'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4302fd16",
   "metadata": {},
   "source": [
    "Part 2: trace all nodes ending with 'A' until they simultaneously reach nodes all ending in 'Z'. This is a big number. Find each cycle, and find the lowest common multiple. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "b0776b34",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "day8p2 ← { ⍺←0\n",
    "    dir ← 'R'=⍺⍺[(≢⍺⍺)|⍺]\n",
    "    elem ← (key⍳⊂⍵)⊃dir⊃ch\n",
    "    'Z'=⊢/elem: 1+⍺\n",
    "    elem ∇⍨ 1+⍺\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "ab82a93d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">8245452805243\n",
       "</pre>"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "∧/(⊃data)day8p2¨key/⍨'A'=⊢/¨key ⍝ lcm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7fead4f8",
   "metadata": {},
   "source": [
    "## Day 9\n",
    "\n",
    "Peter Mikkelsen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "33e0cd12",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">1789635132 913\n",
       "</pre>"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data←⍎⍤('-'⎕R'¯')¨⊃⎕NGET'data/2023/9' 1\n",
    "+/{∧⌿0=⍵:0 ⋄ ⍵+⍥⊃∇ 2-⌿⍵}⍤1⊢↑{(⌽⍵)⍵}↑data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69b37838",
   "metadata": {},
   "source": [
    "## Day 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "0d8e36de",
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "data ← ↑⊃⎕NGET'data/2023/10' 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56954be6",
   "metadata": {},
   "source": [
    "Trace a closed path starting at 'S', ignoring some junk pipes scattered through the maze."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "c958010b",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "day10 ← {⎕IO←0\n",
    "    size ← ⍴data ← ⍵\n",
    "    start ← ⍸'S'=data\n",
    "    visited ← start\n",
    "\n",
    "    val ← {\n",
    "        (⍵[0]>0)       ∧ (data[⊂⍵]∊'S|JL') ∧ (data[⊂(¯1 0)+⍵]∊'|7F') ∧ ~visited∊⍨⊂(¯1 0)+⍵ : (¯1 0)+⍵\n",
    "        (⍵[0]≤size[0]) ∧ (data[⊂⍵]∊'S|7F') ∧ (data[⊂(1 0)+⍵]∊'|JL') ∧ ~visited∊⍨⊂(1 0)+⍵: (1 0)+⍵\n",
    "        (⍵[1]>0)       ∧ (data[⊂⍵]∊'S-J7') ∧ (data[⊂(0 ¯1)+⍵]∊'-LF') ∧ ~visited∊⍨⊂(0 ¯1)+⍵: (0 ¯1)+⍵\n",
    "        (⍵[1]≤size[1]) ∧ (data[⊂⍵]∊'S-LF') ∧ (data[⊂(0 1)+⍵]∊'-J7') ∧ ~visited∊⍨⊂(0 1)+⍵: (0 1)+⍵\n",
    "        ⍬\n",
    "    }\n",
    "    \n",
    "    {\n",
    "        0=≢⍵: ∪visited\n",
    "        next ← val ⊃⍵\n",
    "        ⍬≡next:∇1↓⍵\n",
    "        ~visited∊⍨⊂next: (∇1↓⍵,⊂next)⊣visited,←⊂next\n",
    "        ∇1↓⍵\n",
    "    } start\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "2cbbdee6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">6786\n",
       "</pre>"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "path ← day10 data\n",
    "⌊2÷⍨≢path ⍝ part 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06b5db45",
   "metadata": {},
   "source": [
    "Part 2: find all tiles enclosed by the path. Complications highlighted are that path \"walls\" may touch eachother. Moreover, this also means that seemingly enclosed regions may actually still be deemed outside:\n",
    "\n",
    "```\n",
    "..........\n",
    ".S------7.\n",
    ".|F----7|.\n",
    ".||OOOO||.\n",
    ".||OOOO||.\n",
    ".|L-7F-J|.\n",
    ".|II||II|.\n",
    ".L--JL--J.\n",
    "..........\n",
    "```\n",
    "This diagram shows both issues. Here, only the tiles marked `I` are on the \"inside\". The go-to approach would be a flood-fill, but for this to work we'd need to 'stretch' the canvas a bit to ensure that we can progress the fill between touching pipes.\n",
    "\n",
    "Amazingly, this problem has a closed form solution using [Pick's Theorem](https://en.wikipedia.org/wiki/Pick%27s_theorem). Pick's theorem provides a formula for the area of a simple polygon with integer vertex coordinates, in terms of the number of integer points within it and on its boundary. This means that if we know the area, and the boundary points, we can find the interior points. Fortunately, there is another formula we can use to find the area of a polygon defined by a set of vertices, called the [Shoelace Formula](https://en.wikipedia.org/wiki/Shoelace_formula). Note, the below implementation of Pick's assumes that the number of boundary points equals the number of path vertices -- that's NOT true in general, but true in this case, as all points are at most 1 unit apart in x or y."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "0a8068c6",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "sl ← {⎕IO←0\n",
    "    ⍝ Polygon area from list of vertices using the shoelace formula\n",
    "    ⍝ https://en.wikipedia.org/wiki/Shoelace_formula\n",
    "\n",
    "    x1 ← ⊣/¨⍵\n",
    "    y1 ← ⊢/¨⍵\n",
    "\n",
    "    shift ← (≢⍵)|1+⍳≢⍵\n",
    "    x2 ← x1[shift]\n",
    "    y2 ← y1[shift]\n",
    "\n",
    "    2÷⍨|+/(x1×y2)-x2×y1\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "14441b7c",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "interior ← {\n",
    "    ⍝ Find the interior points of the polygon using Pick's theorem\n",
    "    ⍝ https://en.wikipedia.org/wiki/Pick%27s_theorem\n",
    "    ⌊1+(sl ⍵)-2÷⍨≢⍵\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "739e37b4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">495\n",
       "</pre>"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "interior path"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e4f1a2d",
   "metadata": {},
   "source": [
    "## Day 11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "0704955b",
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "'cmat'⎕CY'dfns'\n",
    "expand ← {r←1+0=+/⍵⋄c←1+0=+⌿⍵⋄c/r⌿⍵}\n",
    "data ← ↑⊃⎕NGET'data/2023/11' 1\n",
    "universe ← expand '#'=↑data\n",
    "starID ← (⍴universe)⍴(⍳×/⍴universe)×,universe\n",
    "stars ← (,universe)/,starID\n",
    "pairs ← stars[2 cmat ≢stars]\n",
    "mhd ← {+/|(⍺⍺⊤⍺)-⍺⍺⊤⍵}\n",
    "distances ← (⍴universe)mhd/pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "e37ce443",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">9536038\n",
       "</pre>"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/distances ⍝ part 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dc214ae7",
   "metadata": {},
   "source": [
    "Part 2: expand each empty row and col by a MEEEEEELIOOOON. This clearly requires a different approach. If we \"cross\" an empty row or col in our Manhattan calculation, we add a MEEEEEELIOOON instead of 1. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "37949332",
   "metadata": {},
   "outputs": [],
   "source": [
    "'cmat'⎕CY'dfns'\n",
    "⎕IO←0\n",
    "data ← ↑⊃⎕NGET'data/2023/11' 1\n",
    "universe ← '#'=↑data\n",
    "starID ← (⍴universe)⍴(⍳×/⍴universe)×,universe\n",
    "stars ← (,universe)/,starID\n",
    "pairs ← stars[2 cmat ≢stars]\n",
    "ex ← ⍸0=+⌿universe\n",
    "ey ← ⍸0=+/universe\n",
    "factor ← 1e6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "3b5599bd",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "part2 ← {⎕IO←0\n",
    "    (y1 x1) ← (⍴universe)⊤⍺\n",
    "    (y2 x2) ← (⍴universe)⊤⍵\n",
    "    \n",
    "    y ← (y1⌊y2) {⍺+⍳⍵-⍺} y1⌈y2\n",
    "    x ← (x1⌊x2) {⍺+⍳⍵-⍺} x1⌈x2\n",
    "\n",
    "    ns ← (~big_y)+factor×big_y←y∊ey\n",
    "    ew ← (~big_x)+factor×big_x←x∊ex\n",
    "\n",
    "    +/ns,ew\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "1151c0e0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">447744640566\n",
       "</pre>"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/part2/pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b6f9117",
   "metadata": {},
   "source": [
    "Of course, we can solve part 1 with the part 2 approach by setting the factor to 1."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bc00edb8",
   "metadata": {},
   "source": [
    "## Day 12"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5f8e6eb1",
   "metadata": {},
   "source": [
    "(Pythoned)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d7e290f0",
   "metadata": {},
   "source": [
    "## Day 13\n",
    "\n",
    "Aaron Hsu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "592904df",
   "metadata": {},
   "outputs": [],
   "source": [
    "⎕IO←0\n",
    "data ← ↑⊃⎕NGET'data/2023/13' 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "37bc538b",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "day13_p1←{\n",
    "    in←'.#'∘⍳¨{⍵~' '}⍤1¨1↓¨d⊂[0]⍨∧/' '=d←' '⍪⍵\n",
    "    rpt←{ax←⍺ ⋄ s←(⍴⍵)[ax] ⋄ c←1+⍳s-1 ⋄ w←c⌊s-c ⋄ I←⍵∘{(⊂⍵)⌷[ax]⍺}\n",
    "        s|1+1⍳⍨c{(⊢≡⌽[ax])I(⍺-⍵)+⍳2×⍵}¨w}\n",
    "    +⌿(100×0 rpt¨in),1 rpt¨in\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "b7ca0a42",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "day13_p2←{\n",
    "    in←'.#'∘⍳¨{⍵~' '}⍤1¨1↓¨d⊂[0]⍨∧/' '=d←' '⍪⍵\n",
    "    rpt←{ax←⍺ ⋄ s←(⍴⍵)[ax] ⋄ c←1+⍳s-1 ⋄ w←c⌊s-c ⋄ I←⍵∘{(⊂⍵)⌷[ax]⍺}\n",
    "        c{(⊢=⌽[ax])I(⍺-⍵)+⍳2×⍵}¨w\n",
    "    }\n",
    "    +⌿{∨⌿m←2=+⌿∘,¨0=0 rpt ⍵:100×1+1⍳⍨m ⋄ ∨⌿m←2=+⌿∘,¨0=1 rpt ⍵:1+1⍳⍨m}¨in\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "1ba097dc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">34821\n",
       "</pre>"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "day13_p1 data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "5a5a8da4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">36919\n",
       "</pre>"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "day13_p2 data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "45ceebf4",
   "metadata": {},
   "source": [
    "## Day 14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "bfc20aa6",
   "metadata": {},
   "outputs": [],
   "source": [
    "data ← ↑⊃⎕NGET'data/2023/14'1\n",
    "padded ← '#',('#'⍪data⍪'#'),'#' ⍝ pad boundaries with #"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "e09eecab",
   "metadata": {},
   "outputs": [],
   "source": [
    "move ← {∊{⍵[⍋'#O.'⍳⍵]}¨('#'=⍵)⊂⍵}⍤1 ⍝ Partitions starting on #, then sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "5c21017e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">105784\n",
       "</pre>"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/(⊖⍳⊃⍴r)×+/'O'=r←⍉move⍉padded"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e50d6709",
   "metadata": {},
   "source": [
    "We're asked to cycle 1_000_000_000 times, which is intractable. Look for repeats."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "8a08cc81",
   "metadata": {},
   "outputs": [],
   "source": [
    "cycle ← {⊖⌽move⍉⊖move⍉⊖move⍉move⍉⍵}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "33bab40f",
   "metadata": {},
   "source": [
    "Theory is that we'll get a recurring state sooner or later. Keep cycling until we find a state we've seen before."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "a2169fd7",
   "metadata": {},
   "outputs": [],
   "source": [
    "rec ← cycle⍣{seen∊⍨⊂⍺:1 ⋄ 0⊣seen,←⊂⍺}⊃seen←,⊂padded"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "04eb824a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">91286\n",
       "</pre>"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "+/(⊖⍳⊃⍴r)×+/'O'=seen⊃⍨pos+1e9-pos+iter×⌊(1e9-pos)÷iter←(≢seen)-pos←seen⍳⊂rec"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa740d1a",
   "metadata": {},
   "source": [
    "## Day 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "4e198c1d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">515210\n",
       "</pre>"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data ← ⊃⎕NGET'data/2023/15'1\n",
    "data ← ⊃','(≠⊆⊢)¨data\n",
    "+⌿{⍺←0 ⋄ 0=≢⍵:⍺ ⋄ (256|17×⍺+⎕UCS⊃⍵)∇1↓⍵}¨data"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "07b4f7a6",
   "metadata": {},
   "source": [
    "## Day 19\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "4efd1c97",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">clear ws\n",
       "</pre>"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    ")clear\n",
    "data ← ⊃⎕NGET'data/2023/19'1\n",
    "rules ratings←data⊂⍨1,1↓0=≢¨data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "e2155f2e",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "compile ← {\n",
    "    pos ← ¯1+⍵⍳'{'\n",
    "    body ← pos↓⍵\n",
    "    one←','⎕R'⋄'⊢body\n",
    "    two←'R'⎕R'0'⊣'A'⎕R'1'⊢one\n",
    "    three←'{'⎕R'←{(x m a s)←⍵.(x m a s)⋄'⊢two\n",
    "    ⍎(pos↑⍵),'([a-z]{2,})'⎕R'\\1⍵'⊢three\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "c4362528",
   "metadata": {},
   "outputs": [],
   "source": [
    "]dinput\n",
    "run ← {\n",
    "    n ← ⎕JSON⍠'Dialect' 'JSON5'⊢'='⎕R':'⊢⍵\n",
    "    1=in n: +/n.(x m a s)\n",
    "    0\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "b63228a9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">406934\n",
       "</pre>"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre class=\"language-APL\">clear ws\n",
       "</pre>"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "compile ¨rules\n",
    "+/run¨1↓ratings\n",
    ")clear"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ea729524",
   "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": 5
}