4 "cell_type": "markdown",
7 "# Advent of Code 2017\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",
13 "For example, given the following spreadsheet:\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",
23 "In this example, the spreadsheet's checksum would be 8 + 4 + 6 = 18.\n",
25 "I'll assume the input is a Joy sequence of sequences of integers.\n",
31 "So, obviously, the initial form will be a `step` function:\n",
33 " AoC2017.2 == 0 swap [F +] step\n",
35 "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:"
45 "output_type": "stream",
50 "[maxmin [max] [min] cleave] inscribe"
60 "output_type": "stream",
71 "cell_type": "markdown",
74 "Then `F` just does that then subtracts the min from the max:\n",
88 "output_type": "stream",
95 "[AoC2017.2 [maxmin - +] step_zero] inscribe"
100 "execution_count": 4,
105 "output_type": "stream",
116 " [2 4 6 8]] AoC2017.2"
120 "cell_type": "markdown",
123 "...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",
125 "For example, given the following spreadsheet:\n",
131 "* In the first row, the only two numbers that evenly divide are 8 and 2; the result of this division is 4.\n",
132 "* In the second row, the two numbers are 9 and 3; the result is 3.\n",
133 "* In the third row, the result is 2.\n",
135 "In this example, the sum of the results would be 4 + 3 + 2 = 9.\n",
137 "What is the sum of each row's result in your puzzle input?"
142 "execution_count": 24,
147 "output_type": "stream",
157 "execution_count": 25,
162 "output_type": "stream",
174 "execution_count": 26,
179 "output_type": "stream",
181 "[5 8 9] [2 mod not]"
186 "uncons swap [mod not] cons"
191 "execution_count": 23,
196 "output_type": "stream",
208 "execution_count": 27,
213 "output_type": "stream",
225 "execution_count": 28,
230 "output_type": "stream",
237 "[P 2 mod not] inscribe"
242 "execution_count": 31,
247 "output_type": "stream",
260 "execution_count": 30,
265 "output_type": "stream",
267 "[true false true false]"
277 "execution_count": 32,
282 "output_type": "stream",
294 "execution_count": 33,
299 "output_type": "stream",
311 "execution_count": 34,
316 "output_type": "stream",
323 "[P][swons][pop]ifte"
328 "execution_count": 35,
333 "output_type": "stream",
345 "execution_count": 36,
350 "output_type": "stream",
357 "[P][swons][pop]ifte"
362 "execution_count": null,
369 "execution_count": 37,
374 "output_type": "stream",
387 "execution_count": 38,
392 "output_type": "stream",
399 "[] swap [[P][swons][pop]ifte] step"
403 "cell_type": "markdown",
406 " [...] [P] filter\n",
407 " -----------------------------------------\n",
408 " [] [...] [[P][swons][pop]ifte] step\n",
410 "But that `[]` could get in the way of `P`, no?"
415 "execution_count": null,
422 "execution_count": null,
429 "execution_count": null,
436 "execution_count": null,
443 "execution_count": null,
450 "execution_count": 9,
455 "output_type": "stream",
457 "[8 5 2] [9 divmod] [8 5 2]"
462 "uncons [swap [divmod] cons] dupdip"
466 "cell_type": "markdown",
470 " [9 8 5 2] uncons [swap [divmod] cons F] dupdip G\n",
471 " [8 5 2] [9 divmod] F [8 5 2] G\n",
477 "execution_count": 8,
482 "output_type": "stream",
484 " • [8 5 2] [9 divmod] [uncons swap] dip dup [i not] dip\n",
485 " [8 5 2] • [9 divmod] [uncons swap] dip dup [i not] dip\n",
486 " [8 5 2] [9 divmod] • [uncons swap] dip dup [i not] dip\n",
487 " [8 5 2] [9 divmod] [uncons swap] • dip dup [i not] dip\n",
488 " [8 5 2] • uncons swap [9 divmod] dup [i not] dip\n",
489 " 8 [5 2] • swap [9 divmod] dup [i not] dip\n",
490 " [5 2] 8 • [9 divmod] dup [i not] dip\n",
491 " [5 2] 8 [9 divmod] • dup [i not] dip\n",
492 " [5 2] 8 [9 divmod] [9 divmod] • [i not] dip\n",
493 "[5 2] 8 [9 divmod] [9 divmod] [i not] • dip\n",
494 " [5 2] 8 [9 divmod] • i not [9 divmod]\n",
495 " [5 2] 8 • 9 divmod not [9 divmod]\n",
496 " [5 2] 8 9 • divmod not [9 divmod]\n",
497 " [5 2] 1 1 • not [9 divmod]\n",
498 " [5 2] 1 False • [9 divmod]\n",
499 " [5 2] 1 False [9 divmod] • \n"
504 "V('[8 5 2] [9 divmod] [uncons swap] dip dup [i not] dip')"
508 "cell_type": "markdown",
515 "Given a *sorted* sequence (from highest to lowest) we want to \n",
516 "* for head, tail in sequence\n",
517 " * for term in tail:\n",
518 " * check if the head % term == 0\n",
519 " * if so compute head / term and terminate loop\n",
524 "cell_type": "markdown",
527 "### So we want a `loop` I think\n",
529 " [a b c d] True [Q] loop\n",
530 " [a b c d] Q [Q] loop\n",
532 "`Q` should either leave the result and False, or the `rest` and True.\n",
535 " -----------------\n",
539 " -----------------\n",
544 "cell_type": "markdown",
547 "This suggests that `Q` should start with:\n",
549 " [a b c d] uncons dup roll<\n",
550 " [b c d] [b c d] a\n",
552 "Now we just have to `pop` it if we don't need it.\n",
554 " [b c d] [b c d] a [P] [T] [cons] app2 popdd [E] primrec\n",
555 " [b c d] [b c d] [a P] [a T] [E] primrec\n",
557 "-------------------\n",
559 " w/ Q == [% not] [T] [F] primrec\n",
561 " [a b c d] uncons\n",
563 " [b c d] a [b c d] uncons\n",
564 " [b c d] a b [c d] roll>\n",
565 " [b c d] [c d] a b Q\n",
566 " [b c d] [c d] a b [% not] [T] [F] primrec\n",
568 " [b c d] [c d] a b T\n",
569 " [b c d] [c d] a b / roll> popop 0\n",
571 " [b c d] [c d] a b F Q\n",
572 " [b c d] [c d] a b pop swap uncons ... Q\n",
573 " [b c d] [c d] a swap uncons ... Q\n",
574 " [b c d] a [c d] uncons ... Q\n",
575 " [b c d] a c [d] roll> Q\n",
576 " [b c d] [d] a c Q\n",
578 " Q == [% not] [/ roll> popop 0] [pop swap uncons roll>] primrec\n",
580 " uncons tuck uncons roll> Q"
585 "execution_count": 9,
590 "output_type": "stream",
592 "[8 5 3 2] [9 swap] [9 % not]\n"
597 "J('[8 5 3 2] 9 [swap] [% not] [cons] app2 popdd')"
601 "cell_type": "markdown",
604 "-------------------\n",
606 " [a b c d] uncons\n",
608 " [b c d] a [b c d] [not] [popop 1] [Q] ifte\n",
610 " [b c d] a [] popop 1\n",
613 " [b c d] a [b c d] Q \n",
617 " ---------------\n",
621 " ---------------\n",
625 " w/ Q == [first % not] [first / 0] [rest [not] [popop 1]] [ifte]\n",
629 " a [b c d] [first % not] [first / 0] [rest [not] [popop 1]] [ifte]\n",
630 " a [b c d] first % not\n",
635 " a [b c d] [first % not] [first / 0] [rest [not] [popop 1]] [ifte]\n",
636 " a [b c d] first / 0\n",
640 " a [b c d] [first % not] [first / 0] [rest [not] [popop 1]] [ifte]\n",
641 " a [b c d] rest [not] [popop 1] [Q] ifte\n",
642 " a [c d] [not] [popop 1] [Q] ifte\n",
643 " a [c d] [not] [popop 1] [Q] ifte\n",
645 " a [c d] [not] [popop 1] [Q] ifte\n",
654 " uncons tuck [first % not] [first / 0] [rest [not] [popop 1]] [ifte]\n",
660 "cell_type": "markdown",
663 "### I finally sat down with a piece of paper and blocked it out.\n",
665 "First, I made a function `G` that expects a number and a sequence of candidates and return the result or zero:\n",
668 " ---------------\n",
672 " ---------------\n",
675 "It's a recursive function that conditionally executes the recursive part of its recursive branch\n",
677 " [Pg] [E] [R1 [Pi] [T]] [ifte] genrec\n",
679 "The recursive branch is the else-part of the inner `ifte`:\n",
681 " G == [Pg] [E] [R1 [Pi] [T]] [ifte] genrec\n",
682 " == [Pg] [E] [R1 [Pi] [T] [G] ifte] ifte\n",
684 "But this is in hindsight. Going forward I derived:\n",
686 " G == [first % not]\n",
688 " [rest [not] [popop 0]]\n",
691 "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",
693 " n [m ...] rest [not] [popop 0] [G] ifte\n",
694 " n [...] [not] [popop 0] [G] ifte\n",
696 "This `ifte` guards against empty sequences and returns zero in that case, otherwise it executes `G`."
701 "execution_count": 10,
705 "define('G [first % not] [first /] [rest [not] [popop 0]] [ifte] genrec')"
709 "cell_type": "markdown",
712 "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",
714 " n [...] p find-result\n",
715 " ---------------------------\n",
718 "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",
720 " find-result == [0 >] [roll> popop] [roll< popop uncons [G] nullary] tailrec\n",
722 " n [...] p [0 >] [roll> popop] [roll< popop uncons [G] nullary] tailrec\n",
724 "The base-case is trivial, return the (non-zero) result. The recursive branch...\n",
726 " n [...] p roll< popop uncons [G] nullary find-result\n",
727 " [...] p n popop uncons [G] nullary find-result\n",
728 " [...] uncons [G] nullary find-result\n",
729 " m [..] [G] nullary find-result\n",
730 " m [..] p find-result\n",
732 "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`."
737 "execution_count": 11,
741 "define('find-result [0 >] [roll> popop] [roll< popop uncons [G] nullary] tailrec')"
746 "execution_count": 12,
751 "output_type": "stream",
758 "J('[11 9 8 7 3 2] 0 tuck find-result')"
762 "cell_type": "markdown",
765 "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."
770 "execution_count": 13,
774 "define('prep-row sort reverse 0 tuck')"
778 "cell_type": "markdown",
781 "Now we can define our program."
786 "execution_count": 14,
790 "define('AoC20017.2.extra [prep-row find-result +] step_zero')"
795 "execution_count": 15,
800 "output_type": "stream",
811 " [3 8 6 5]] AoC20017.2.extra\n",
819 "display_name": "Joypy",
824 "file_extension": ".joy",
825 "mimetype": "text/plain",