docs/Advent_of_Code_2017_December_1st.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Advent of Code 2017\n",
   8     "\n",
   9     "## December 1st\n",
  10     "\n",
  11     "\\[Given\\] a sequence of digits (your puzzle input) and find the sum of all digits that match the next digit in the list. The list is circular, so the digit after the last digit is the first digit in the list.\n",
  12     "\n",
  13     "For example:\n",
  14     "\n",
  15     "* 1122 produces a sum of 3 (1 + 2) because the first digit (1) matches the second digit and the third digit (2) matches the fourth digit.\n",
  16     "* 1111 produces 4 because each digit (all 1) matches the next.\n",
  17     "* 1234 produces 0 because no digit matches the next.\n",
  18     "* 91212129 produces 9 because the only digit that matches the next one is the last digit, 9."
  19    ]
  20   },
  21   {
  22    "cell_type": "code",
  23    "execution_count": 1,
  24    "metadata": {},
  25    "outputs": [],
  26    "source": [
  27     "from notebook_preamble import J, V, define"
  28    ]
  29   },
  30   {
  31    "cell_type": "markdown",
  32    "metadata": {},
  33    "source": [
  34     "I'll assume the input is a Joy sequence of integers (as opposed to a string or something else.)\n",
  35     "\n",
  36     "We might proceed by creating a word that makes a copy of the sequence with the first item moved to the last, and zips it with the original to make a list of pairs, and a another word that adds (one of) each pair to a total if the pair matches.\n",
  37     "\n",
  38     "    AoC2017.1 == pair_up total_matches\n",
  39     "\n",
  40     "Let's derive `pair_up`:\n",
  41     "\n",
  42     "         [a b c] pair_up\n",
  43     "    -------------------------\n",
  44     "       [[a b] [b c] [c a]]\n"
  45    ]
  46   },
  47   {
  48    "cell_type": "markdown",
  49    "metadata": {},
  50    "source": [
  51     "Straightforward (although the order of each pair is reversed, due to the way `zip` works, but it doesn't matter for this program):\n",
  52     "\n",
  53     "    [a b c] dup\n",
  54     "    [a b c] [a b c] uncons swap\n",
  55     "    [a b c] [b c] a unit concat\n",
  56     "    [a b c] [b c a] zip\n",
  57     "    [[b a] [c b] [a c]]"
  58    ]
  59   },
  60   {
  61    "cell_type": "code",
  62    "execution_count": 2,
  63    "metadata": {},
  64    "outputs": [],
  65    "source": [
  66     "define('pair_up dup uncons swap unit concat zip')"
  67    ]
  68   },
  69   {
  70    "cell_type": "code",
  71    "execution_count": 3,
  72    "metadata": {},
  73    "outputs": [
  74     {
  75      "name": "stdout",
  76      "output_type": "stream",
  77      "text": [
  78       "[[2 1] [3 2] [1 3]]\n"
  79      ]
  80     }
  81    ],
  82    "source": [
  83     "J('[1 2 3] pair_up')"
  84    ]
  85   },
  86   {
  87    "cell_type": "code",
  88    "execution_count": 4,
  89    "metadata": {
  90     "scrolled": true
  91    },
  92    "outputs": [
  93     {
  94      "name": "stdout",
  95      "output_type": "stream",
  96      "text": [
  97       "[[2 1] [2 2] [3 2] [1 3]]\n"
  98      ]
  99     }
 100    ],
 101    "source": [
 102     "J('[1 2 2 3] pair_up')"
 103    ]
 104   },
 105   {
 106    "cell_type": "markdown",
 107    "metadata": {},
 108    "source": [
 109     "Now we need to derive `total_matches`.  It will be a `step` function:\n",
 110     "\n",
 111     "    total_matches == 0 swap [F] step\n",
 112     "\n",
 113     "Where `F` will have the pair to work with, and it will basically be a `branch` or `ifte`.\n",
 114     "\n",
 115     "    total [n m] F\n",
 116     "\n",
 117     "It will probably be easier to write if we dequote the pair:\n",
 118     "\n",
 119     "       total [n m] i F′\n",
 120     "    ----------------------\n",
 121     "         total n m F′\n",
 122     "\n",
 123     "Now `F′` becomes just:\n",
 124     "\n",
 125     "    total n m [=] [pop +] [popop] ifte\n",
 126     "\n",
 127     "So:\n",
 128     "\n",
 129     "    F == i [=] [pop +] [popop] ifte\n",
 130     "\n",
 131     "And thus:\n",
 132     "\n",
 133     "    total_matches == 0 swap [i [=] [pop +] [popop] ifte] step"
 134    ]
 135   },
 136   {
 137    "cell_type": "code",
 138    "execution_count": 5,
 139    "metadata": {},
 140    "outputs": [],
 141    "source": [
 142     "define('total_matches 0 swap [i [=] [pop +] [popop] ifte] step')"
 143    ]
 144   },
 145   {
 146    "cell_type": "code",
 147    "execution_count": 6,
 148    "metadata": {},
 149    "outputs": [
 150     {
 151      "name": "stdout",
 152      "output_type": "stream",
 153      "text": [
 154       "0\n"
 155      ]
 156     }
 157    ],
 158    "source": [
 159     "J('[1 2 3] pair_up total_matches')"
 160    ]
 161   },
 162   {
 163    "cell_type": "code",
 164    "execution_count": 7,
 165    "metadata": {},
 166    "outputs": [
 167     {
 168      "name": "stdout",
 169      "output_type": "stream",
 170      "text": [
 171       "2\n"
 172      ]
 173     }
 174    ],
 175    "source": [
 176     "J('[1 2 2 3] pair_up total_matches')"
 177    ]
 178   },
 179   {
 180    "cell_type": "markdown",
 181    "metadata": {},
 182    "source": [
 183     "Now we can define our main program and evaluate it on the examples."
 184    ]
 185   },
 186   {
 187    "cell_type": "code",
 188    "execution_count": 8,
 189    "metadata": {},
 190    "outputs": [],
 191    "source": [
 192     "define('AoC2017.1 pair_up total_matches')"
 193    ]
 194   },
 195   {
 196    "cell_type": "code",
 197    "execution_count": 9,
 198    "metadata": {},
 199    "outputs": [
 200     {
 201      "name": "stdout",
 202      "output_type": "stream",
 203      "text": [
 204       "3\n"
 205      ]
 206     }
 207    ],
 208    "source": [
 209     "J('[1 1 2 2] AoC2017.1')"
 210    ]
 211   },
 212   {
 213    "cell_type": "code",
 214    "execution_count": 10,
 215    "metadata": {},
 216    "outputs": [
 217     {
 218      "name": "stdout",
 219      "output_type": "stream",
 220      "text": [
 221       "4\n"
 222      ]
 223     }
 224    ],
 225    "source": [
 226     "J('[1 1 1 1] AoC2017.1')"
 227    ]
 228   },
 229   {
 230    "cell_type": "code",
 231    "execution_count": 11,
 232    "metadata": {},
 233    "outputs": [
 234     {
 235      "name": "stdout",
 236      "output_type": "stream",
 237      "text": [
 238       "0\n"
 239      ]
 240     }
 241    ],
 242    "source": [
 243     "J('[1 2 3 4] AoC2017.1')"
 244    ]
 245   },
 246   {
 247    "cell_type": "code",
 248    "execution_count": 12,
 249    "metadata": {
 250     "scrolled": false
 251    },
 252    "outputs": [
 253     {
 254      "name": "stdout",
 255      "output_type": "stream",
 256      "text": [
 257       "9\n"
 258      ]
 259     }
 260    ],
 261    "source": [
 262     "J('[9 1 2 1 2 1 2 9] AoC2017.1')"
 263    ]
 264   },
 265   {
 266    "cell_type": "code",
 267    "execution_count": 13,
 268    "metadata": {
 269     "scrolled": false
 270    },
 271    "outputs": [
 272     {
 273      "name": "stdout",
 274      "output_type": "stream",
 275      "text": [
 276       "9\n"
 277      ]
 278     }
 279    ],
 280    "source": [
 281     "J('[9 1 2 1 2 1 2 9] AoC2017.1')"
 282    ]
 283   },
 284   {
 285    "cell_type": "markdown",
 286    "metadata": {},
 287    "source": [
 288     "          pair_up == dup uncons swap unit concat zip\n",
 289     "    total_matches == 0 swap [i [=] [pop +] [popop] ifte] step\n",
 290     "\n",
 291     "        AoC2017.1 == pair_up total_matches"
 292    ]
 293   },
 294   {
 295    "cell_type": "code",
 296    "execution_count": null,
 297    "metadata": {},
 298    "outputs": [],
 299    "source": []
 300   },
 301   {
 302    "cell_type": "markdown",
 303    "metadata": {},
 304    "source": [
 305     "Now the paired digit is \"halfway\" round.\n",
 306     "\n",
 307     "    [a b c d] dup size 2 / [drop] [take reverse] cleave concat zip"
 308    ]
 309   },
 310   {
 311    "cell_type": "code",
 312    "execution_count": 14,
 313    "metadata": {},
 314    "outputs": [
 315     {
 316      "name": "stdout",
 317      "output_type": "stream",
 318      "text": [
 319       "[[3 1] [4 2] [1 3] [2 4]]\n"
 320      ]
 321     }
 322    ],
 323    "source": [
 324     "J('[1 2 3 4] dup size 2 / [drop] [take reverse] cleave concat zip')"
 325    ]
 326   },
 327   {
 328    "cell_type": "markdown",
 329    "metadata": {},
 330    "source": [
 331     "I realized that each pair is repeated..."
 332    ]
 333   },
 334   {
 335    "cell_type": "code",
 336    "execution_count": 15,
 337    "metadata": {},
 338    "outputs": [
 339     {
 340      "name": "stdout",
 341      "output_type": "stream",
 342      "text": [
 343       "[1 2 3 4] [[1 3] [2 4]]\n"
 344      ]
 345     }
 346    ],
 347    "source": [
 348     "J('[1 2 3 4] dup size 2 / [drop] [take reverse] cleave  zip')"
 349    ]
 350   },
 351   {
 352    "cell_type": "code",
 353    "execution_count": 16,
 354    "metadata": {},
 355    "outputs": [],
 356    "source": [
 357     "define('AoC2017.1.extra dup size 2 / [drop] [take reverse] cleave  zip swap pop total_matches 2 *')"
 358    ]
 359   },
 360   {
 361    "cell_type": "code",
 362    "execution_count": 17,
 363    "metadata": {},
 364    "outputs": [
 365     {
 366      "name": "stdout",
 367      "output_type": "stream",
 368      "text": [
 369       "6\n"
 370      ]
 371     }
 372    ],
 373    "source": [
 374     "J('[1 2 1 2] AoC2017.1.extra')"
 375    ]
 376   },
 377   {
 378    "cell_type": "code",
 379    "execution_count": 18,
 380    "metadata": {},
 381    "outputs": [
 382     {
 383      "name": "stdout",
 384      "output_type": "stream",
 385      "text": [
 386       "0\n"
 387      ]
 388     }
 389    ],
 390    "source": [
 391     "J('[1 2 2 1] AoC2017.1.extra')"
 392    ]
 393   },
 394   {
 395    "cell_type": "code",
 396    "execution_count": 19,
 397    "metadata": {},
 398    "outputs": [
 399     {
 400      "name": "stdout",
 401      "output_type": "stream",
 402      "text": [
 403       "4\n"
 404      ]
 405     }
 406    ],
 407    "source": [
 408     "J('[1 2 3 4 2 5] AoC2017.1.extra')"
 409    ]
 410   },
 411   {
 412    "cell_type": "markdown",
 413    "metadata": {},
 414    "source": [
 415     "# Refactor FTW\n",
 416     "\n",
 417     "With Joy a great deal of the heuristics from Forth programming carry over nicely.  For example, refactoring into small, well-scoped commands with mnemonic names...\n",
 418     "\n",
 419     "             rotate_seq == uncons swap unit concat\n",
 420     "                pair_up == dup rotate_seq zip\n",
 421     "           add_if_match == [=] [pop +] [popop] ifte\n",
 422     "          total_matches == [i add_if_match] step_zero\n",
 423     "\n",
 424     "              AoC2017.1 == pair_up total_matches\n",
 425     "\n",
 426     "           half_of_size == dup size 2 /\n",
 427     "               split_at == [drop] [take reverse] cleave\n",
 428     "          pair_up.extra == half_of_size split_at zip swap pop\n",
 429     "\n",
 430     "        AoC2017.1.extra == pair_up.extra total_matches 2 *\n"
 431    ]
 432   }
 433  ],
 434  "metadata": {
 435   "kernelspec": {
 436    "display_name": "Python 2",
 437    "language": "python",
 438    "name": "python2"
 439   },
 440   "language_info": {
 441    "codemirror_mode": {
 442     "name": "ipython",
 443     "version": 3
 444    },
 445    "file_extension": ".py",
 446    "mimetype": "text/x-python",
 447    "name": "python",
 448    "nbconvert_exporter": "python",
 449    "pygments_lexer": "ipython3",
 450    "version": "3.8.3"
 451   }
 452  },
 453  "nbformat": 4,
 454  "nbformat_minor": 2
 455 }