docs/Advent_of_Code_2017_December_2nd.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Advent of Code 2017\n",
   8     "\n",
   9     "## December 2nd\n",
  10     "\n",
  11     "For each row, determine the difference between the largest value and the smallest value; the checksum is the sum of all of these differences.\n",
  12     "\n",
  13     "For example, given the following spreadsheet:\n",
  14     "\n",
  15     "    5 1 9 5\n",
  16     "    7 5 3\n",
  17     "    2 4 6 8\n",
  18     "\n",
  19     "* The first row's largest and smallest values are 9 and 1, and their difference is 8.\n",
  20     "* The second row's largest and smallest values are 7 and 3, and their difference is 4.\n",
  21     "* The third row's difference is 6.\n",
  22     "\n",
  23     "In this example, the spreadsheet's checksum would be 8 + 4 + 6 = 18."
  24    ]
  25   },
  26   {
  27    "cell_type": "code",
  28    "execution_count": 1,
  29    "metadata": {},
  30    "outputs": [],
  31    "source": [
  32     "from notebook_preamble import J, V, define"
  33    ]
  34   },
  35   {
  36    "cell_type": "markdown",
  37    "metadata": {},
  38    "source": [
  39     "I'll assume the input is a Joy sequence of sequences of integers.\n",
  40     "\n",
  41     "    [[5 1 9 5]\n",
  42     "     [7 5 3]\n",
  43     "     [2 4 6 8]]\n",
  44     "\n",
  45     "So, obviously, the initial form will be a `step` function:\n",
  46     "\n",
  47     "    AoC2017.2 == 0 swap [F +] step"
  48    ]
  49   },
  50   {
  51    "cell_type": "markdown",
  52    "metadata": {},
  53    "source": [
  54     "This function `F` must get the `max` and `min` of a row of numbers and subtract.  We can define a helper function `maxmin` which does this:"
  55    ]
  56   },
  57   {
  58    "cell_type": "code",
  59    "execution_count": 2,
  60    "metadata": {},
  61    "outputs": [],
  62    "source": [
  63     "define('maxmin [max] [min] cleave')"
  64    ]
  65   },
  66   {
  67    "cell_type": "code",
  68    "execution_count": 3,
  69    "metadata": {},
  70    "outputs": [
  71     {
  72      "name": "stdout",
  73      "output_type": "stream",
  74      "text": [
  75       "3 1\n"
  76      ]
  77     }
  78    ],
  79    "source": [
  80     "J('[1 2 3] maxmin')"
  81    ]
  82   },
  83   {
  84    "cell_type": "markdown",
  85    "metadata": {},
  86    "source": [
  87     "Then `F` just does that then subtracts the min from the max:\n",
  88     "\n",
  89     "    F == maxmin -\n",
  90     "\n",
  91     "So:"
  92    ]
  93   },
  94   {
  95    "cell_type": "code",
  96    "execution_count": 4,
  97    "metadata": {},
  98    "outputs": [],
  99    "source": [
 100     "define('AoC2017.2 [maxmin - +] step_zero')"
 101    ]
 102   },
 103   {
 104    "cell_type": "code",
 105    "execution_count": 5,
 106    "metadata": {},
 107    "outputs": [
 108     {
 109      "name": "stdout",
 110      "output_type": "stream",
 111      "text": [
 112       "18\n"
 113      ]
 114     }
 115    ],
 116    "source": [
 117     "J('''\n",
 118     "\n",
 119     "[[5 1 9 5]\n",
 120     " [7 5 3]\n",
 121     " [2 4 6 8]] AoC2017.2\n",
 122     "\n",
 123     "''')"
 124    ]
 125   },
 126   {
 127    "cell_type": "markdown",
 128    "metadata": {},
 129    "source": [
 130     "...find the only two numbers in each row where one evenly divides the other - that is, where the result of the division operation is a whole number. They would like you to find those numbers on each line, divide them, and add up each line's result.\n",
 131     "\n",
 132     "For example, given the following spreadsheet:\n",
 133     "\n",
 134     "    5 9 2 8\n",
 135     "    9 4 7 3\n",
 136     "    3 8 6 5\n",
 137     "\n",
 138     "*    In the first row, the only two numbers that evenly divide are 8 and 2; the result of this division is 4.\n",
 139     "*    In the second row, the two numbers are 9 and 3; the result is 3.\n",
 140     "*    In the third row, the result is 2.\n",
 141     "\n",
 142     "In this example, the sum of the results would be 4 + 3 + 2 = 9.\n",
 143     "\n",
 144     "What is the sum of each row's result in your puzzle input?"
 145    ]
 146   },
 147   {
 148    "cell_type": "code",
 149    "execution_count": 6,
 150    "metadata": {},
 151    "outputs": [
 152     {
 153      "name": "stdout",
 154      "output_type": "stream",
 155      "text": [
 156       "[9 8 5 2]\n"
 157      ]
 158     }
 159    ],
 160    "source": [
 161     "J('[5 9 2 8] sort reverse')"
 162    ]
 163   },
 164   {
 165    "cell_type": "code",
 166    "execution_count": 7,
 167    "metadata": {},
 168    "outputs": [
 169     {
 170      "name": "stdout",
 171      "output_type": "stream",
 172      "text": [
 173       "[8 5 2] [9 divmod] [8 5 2]\n"
 174      ]
 175     }
 176    ],
 177    "source": [
 178     "J('[9 8 5 2] uncons [swap [divmod] cons] dupdip')"
 179    ]
 180   },
 181   {
 182    "cell_type": "markdown",
 183    "metadata": {},
 184    "source": [
 185     "\n",
 186     "    [9 8 5 2] uncons [swap [divmod] cons F] dupdip G\n",
 187     "      [8 5 2]            [9 divmod]      F [8 5 2] G\n",
 188     "\n"
 189    ]
 190   },
 191   {
 192    "cell_type": "code",
 193    "execution_count": 8,
 194    "metadata": {},
 195    "outputs": [
 196     {
 197      "name": "stdout",
 198      "output_type": "stream",
 199      "text": [
 200       "                                      • [8 5 2] [9 divmod] [uncons swap] dip dup [i not] dip\n",
 201       "                              [8 5 2] • [9 divmod] [uncons swap] dip dup [i not] dip\n",
 202       "                   [8 5 2] [9 divmod] • [uncons swap] dip dup [i not] dip\n",
 203       "     [8 5 2] [9 divmod] [uncons swap] • dip dup [i not] dip\n",
 204       "                              [8 5 2] • uncons swap [9 divmod] dup [i not] dip\n",
 205       "                              8 [5 2] • swap [9 divmod] dup [i not] dip\n",
 206       "                              [5 2] 8 • [9 divmod] dup [i not] dip\n",
 207       "                   [5 2] 8 [9 divmod] • dup [i not] dip\n",
 208       "        [5 2] 8 [9 divmod] [9 divmod] • [i not] dip\n",
 209       "[5 2] 8 [9 divmod] [9 divmod] [i not] • dip\n",
 210       "                   [5 2] 8 [9 divmod] • i not [9 divmod]\n",
 211       "                              [5 2] 8 • 9 divmod not [9 divmod]\n",
 212       "                            [5 2] 8 9 • divmod not [9 divmod]\n",
 213       "                            [5 2] 1 1 • not [9 divmod]\n",
 214       "                        [5 2] 1 False • [9 divmod]\n",
 215       "             [5 2] 1 False [9 divmod] • \n"
 216      ]
 217     }
 218    ],
 219    "source": [
 220     "V('[8 5 2] [9 divmod] [uncons swap] dip dup [i not] dip')"
 221    ]
 222   },
 223   {
 224    "cell_type": "markdown",
 225    "metadata": {},
 226    "source": [
 227     "## Tricky\n",
 228     "\n",
 229     "Let's think.\n",
 230     "\n",
 231     "Given a *sorted* sequence (from highest to lowest) we want to \n",
 232     "* for head, tail in sequence\n",
 233     "    * for term in tail:\n",
 234     "        * check if the head % term == 0\n",
 235     "            * if so compute head / term and terminate loop\n",
 236     "            * else continue"
 237    ]
 238   },
 239   {
 240    "cell_type": "markdown",
 241    "metadata": {},
 242    "source": [
 243     "### So we want a `loop` I think\n",
 244     "\n",
 245     "    [a b c d] True [Q] loop\n",
 246     "    [a b c d] Q    [Q] loop\n",
 247     "\n",
 248     "`Q` should either leave the result and False, or the `rest` and True.\n",
 249     "\n",
 250     "       [a b c d] Q\n",
 251     "    -----------------\n",
 252     "        result 0\n",
 253     "\n",
 254     "       [a b c d] Q\n",
 255     "    -----------------\n",
 256     "        [b c d] 1"
 257    ]
 258   },
 259   {
 260    "cell_type": "markdown",
 261    "metadata": {},
 262    "source": [
 263     "This suggests that `Q` should start with:\n",
 264     "\n",
 265     "    [a b c d] uncons dup roll<\n",
 266     "    [b c d] [b c d] a\n",
 267     "\n",
 268     "Now we just have to `pop` it if we don't need it.\n",
 269     "\n",
 270     "    [b c d] [b c d] a [P] [T] [cons] app2 popdd [E] primrec\n",
 271     "    [b c d] [b c d] [a P] [a T]                 [E] primrec\n",
 272     "\n",
 273     "-------------------\n",
 274     "\n",
 275     "    w/ Q == [% not] [T] [F] primrec\n",
 276     "\n",
 277     "            [a b c d] uncons\n",
 278     "            a [b c d] tuck\n",
 279     "    [b c d] a [b c d] uncons\n",
 280     "    [b c d] a b [c d] roll>\n",
 281     "    [b c d] [c d] a b Q\n",
 282     "    [b c d] [c d] a b [% not] [T] [F] primrec\n",
 283     "\n",
 284     "    [b c d] [c d] a b T\n",
 285     "    [b c d] [c d] a b / roll> popop 0\n",
 286     "\n",
 287     "    [b c d] [c d] a b F                   Q\n",
 288     "    [b c d] [c d] a b pop swap uncons ... Q\n",
 289     "    [b c d] [c d] a       swap uncons ... Q\n",
 290     "    [b c d] a [c d]            uncons ... Q\n",
 291     "    [b c d] a c [d]                   roll> Q\n",
 292     "    [b c d] [d] a c Q\n",
 293     "\n",
 294     "    Q == [% not] [/ roll> popop 0] [pop swap uncons roll>] primrec\n",
 295     "    \n",
 296     "    uncons tuck uncons roll> Q"
 297    ]
 298   },
 299   {
 300    "cell_type": "code",
 301    "execution_count": 9,
 302    "metadata": {},
 303    "outputs": [
 304     {
 305      "name": "stdout",
 306      "output_type": "stream",
 307      "text": [
 308       "[8 5 3 2] [9 swap] [9 % not]\n"
 309      ]
 310     }
 311    ],
 312    "source": [
 313     "J('[8 5 3 2] 9 [swap] [% not] [cons] app2 popdd')"
 314    ]
 315   },
 316   {
 317    "cell_type": "markdown",
 318    "metadata": {},
 319    "source": [
 320     "-------------------\n",
 321     "\n",
 322     "            [a b c d] uncons\n",
 323     "            a [b c d] tuck\n",
 324     "    [b c d] a [b c d] [not] [popop 1] [Q] ifte\n",
 325     "\n",
 326     "    [b c d] a [] popop 1\n",
 327     "    [b c d] 1\n",
 328     "\n",
 329     "    [b c d] a [b c d] Q \n",
 330     "\n",
 331     "\n",
 332     "       a [...] Q\n",
 333     "    ---------------\n",
 334     "       result 0\n",
 335     "\n",
 336     "       a [...] Q\n",
 337     "    ---------------\n",
 338     "           1\n",
 339     "\n",
 340     "\n",
 341     "    w/ Q == [first % not] [first / 0] [rest [not] [popop 1]] [ifte]\n",
 342     "\n",
 343     "\n",
 344     "\n",
 345     "    a [b c d] [first % not] [first / 0] [rest [not] [popop 1]] [ifte]\n",
 346     "    a [b c d]  first % not\n",
 347     "    a b % not\n",
 348     "    a%b not\n",
 349     "    bool(a%b)\n",
 350     "\n",
 351     "    a [b c d] [first % not] [first / 0] [rest [not] [popop 1]] [ifte]\n",
 352     "    a [b c d]                first / 0\n",
 353     "    a b / 0\n",
 354     "    a/b 0\n",
 355     "\n",
 356     "    a [b c d] [first % not] [first / 0] [rest [not] [popop 1]]   [ifte]\n",
 357     "    a [b c d]                            rest [not] [popop 1] [Q] ifte\n",
 358     "    a [c d]                                   [not] [popop 1] [Q] ifte\n",
 359     "    a [c d]                                   [not] [popop 1] [Q] ifte\n",
 360     "\n",
 361     "    a [c d] [not] [popop 1] [Q] ifte\n",
 362     "    a [c d]  not\n",
 363     "\n",
 364     "    a [] popop 1\n",
 365     "    1\n",
 366     "\n",
 367     "    a [c d] Q\n",
 368     "\n",
 369     "\n",
 370     "    uncons tuck [first % not] [first / 0] [rest [not] [popop 1]] [ifte]\n",
 371     "    \n",
 372     "    \n"
 373    ]
 374   },
 375   {
 376    "cell_type": "markdown",
 377    "metadata": {},
 378    "source": [
 379     "### I finally sat down with a piece of paper and blocked it out.\n",
 380     "\n",
 381     "First, I made a function `G` that expects a number and a sequence of candidates and return the result or zero:\n",
 382     "\n",
 383     "       n [...] G\n",
 384     "    ---------------\n",
 385     "        result\n",
 386     "\n",
 387     "       n [...] G\n",
 388     "    ---------------\n",
 389     "           0\n",
 390     "\n",
 391     "It's a recursive function that conditionally executes the recursive part of its recursive branch\n",
 392     "\n",
 393     "    [Pg] [E] [R1 [Pi] [T]] [ifte] genrec\n",
 394     "\n",
 395     "The recursive branch is the else-part of the inner `ifte`:\n",
 396     "\n",
 397     "    G == [Pg] [E] [R1 [Pi] [T]]   [ifte] genrec\n",
 398     "      == [Pg] [E] [R1 [Pi] [T] [G] ifte] ifte\n",
 399     "\n",
 400     "But this is in hindsight.  Going forward I derived:\n",
 401     "\n",
 402     "    G == [first % not]\n",
 403     "         [first /]\n",
 404     "         [rest [not] [popop 0]]\n",
 405     "         [ifte] genrec\n",
 406     "\n",
 407     "The predicate detects if the `n` can be evenly divided by the `first` item in the list.  If so, the then-part returns the result.  Otherwise, we have:\n",
 408     "\n",
 409     "    n [m ...] rest [not] [popop 0] [G] ifte\n",
 410     "    n [...]        [not] [popop 0] [G] ifte\n",
 411     "\n",
 412     "This `ifte` guards against empty sequences and returns zero in that case, otherwise it executes `G`."
 413    ]
 414   },
 415   {
 416    "cell_type": "code",
 417    "execution_count": 10,
 418    "metadata": {},
 419    "outputs": [],
 420    "source": [
 421     "define('G [first % not] [first /] [rest [not] [popop 0]] [ifte] genrec')"
 422    ]
 423   },
 424   {
 425    "cell_type": "markdown",
 426    "metadata": {},
 427    "source": [
 428     "Now we need a word that uses `G` on each (head, tail) pair of a sequence until it finds a (non-zero) result.  It's going to be designed to work on a stack that has some candidate `n`, a sequence of possible divisors, and a result that is zero to signal to continue (a non-zero value implies that it is the discovered result):\n",
 429     "\n",
 430     "       n [...] p find-result\n",
 431     "    ---------------------------\n",
 432     "              result\n",
 433     "\n",
 434     "It applies `G` using `nullary` because if it fails with one candidate it needs the list to get the next one (the list is otherwise consumed by `G`.)\n",
 435     "\n",
 436     "    find-result == [0 >] [roll> popop] [roll< popop uncons [G] nullary] tailrec\n",
 437     "\n",
 438     "    n [...] p [0 >] [roll> popop] [roll< popop uncons [G] nullary] tailrec\n",
 439     "\n",
 440     "The base-case is trivial, return the (non-zero) result.  The recursive branch...\n",
 441     "\n",
 442     "    n [...] p roll< popop uncons [G] nullary find-result\n",
 443     "    [...] p n       popop uncons [G] nullary find-result\n",
 444     "    [...]                 uncons [G] nullary find-result\n",
 445     "    m [..]                       [G] nullary find-result\n",
 446     "    m [..] p                                 find-result\n",
 447     "\n",
 448     "The puzzle states that the input is well-formed, meaning that we can expect a result before the row sequence empties and so do not need to guard the `uncons`."
 449    ]
 450   },
 451   {
 452    "cell_type": "code",
 453    "execution_count": 11,
 454    "metadata": {},
 455    "outputs": [],
 456    "source": [
 457     "define('find-result [0 >] [roll> popop] [roll< popop uncons [G] nullary] tailrec')"
 458    ]
 459   },
 460   {
 461    "cell_type": "code",
 462    "execution_count": 12,
 463    "metadata": {},
 464    "outputs": [
 465     {
 466      "name": "stdout",
 467      "output_type": "stream",
 468      "text": [
 469       "3.0\n"
 470      ]
 471     }
 472    ],
 473    "source": [
 474     "J('[11 9 8 7 3 2] 0 tuck find-result')"
 475    ]
 476   },
 477   {
 478    "cell_type": "markdown",
 479    "metadata": {},
 480    "source": [
 481     "In order to get the thing started, we need to `sort` the list in descending order, then prime the `find-result` function with a dummy candidate value and zero (\"continue\") flag."
 482    ]
 483   },
 484   {
 485    "cell_type": "code",
 486    "execution_count": 13,
 487    "metadata": {},
 488    "outputs": [],
 489    "source": [
 490     "define('prep-row sort reverse 0 tuck')"
 491    ]
 492   },
 493   {
 494    "cell_type": "markdown",
 495    "metadata": {},
 496    "source": [
 497     "Now we can define our program."
 498    ]
 499   },
 500   {
 501    "cell_type": "code",
 502    "execution_count": 14,
 503    "metadata": {},
 504    "outputs": [],
 505    "source": [
 506     "define('AoC20017.2.extra [prep-row find-result +] step_zero')"
 507    ]
 508   },
 509   {
 510    "cell_type": "code",
 511    "execution_count": 15,
 512    "metadata": {},
 513    "outputs": [
 514     {
 515      "name": "stdout",
 516      "output_type": "stream",
 517      "text": [
 518       "9.0\n"
 519      ]
 520     }
 521    ],
 522    "source": [
 523     "J('''\n",
 524     "\n",
 525     "[[5 9 2 8]\n",
 526     " [9 4 7 3]\n",
 527     " [3 8 6 5]] AoC20017.2.extra\n",
 528     "\n",
 529     "''')"
 530    ]
 531   }
 532  ],
 533  "metadata": {
 534   "kernelspec": {
 535    "display_name": "Python 2",
 536    "language": "python",
 537    "name": "python2"
 538   },
 539   "language_info": {
 540    "codemirror_mode": {
 541     "name": "ipython",
 542     "version": 3
 543    },
 544    "file_extension": ".py",
 545    "mimetype": "text/x-python",
 546    "name": "python",
 547    "nbconvert_exporter": "python",
 548    "pygments_lexer": "ipython3",
 549    "version": "3.8.3"
 550   }
 551  },
 552  "nbformat": 4,
 553  "nbformat_minor": 2
 554 }