docs/Advent_of_Code_2017_December_6th.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Advent of Code 2017\n",
   8     "\n",
   9     "## December 6th\n",
  10     "\n",
  11     "\n",
  12     "    [0 2 7 0] dup max\n"
  13    ]
  14   },
  15   {
  16    "cell_type": "code",
  17    "execution_count": 1,
  18    "metadata": {},
  19    "outputs": [],
  20    "source": [
  21     "from notebook_preamble import D, J, V, define"
  22    ]
  23   },
  24   {
  25    "cell_type": "code",
  26    "execution_count": 2,
  27    "metadata": {
  28     "scrolled": true
  29    },
  30    "outputs": [
  31     {
  32      "name": "stdout",
  33      "output_type": "stream",
  34      "text": [
  35       "[0 2 7 0] 7\n"
  36      ]
  37     }
  38    ],
  39    "source": [
  40     "J('[0 2 7 0] dup max')"
  41    ]
  42   },
  43   {
  44    "cell_type": "code",
  45    "execution_count": 3,
  46    "metadata": {},
  47    "outputs": [],
  48    "source": [
  49     "from joy.library import SimpleFunctionWrapper\n",
  50     "from joy.utils.stack import list_to_stack\n",
  51     "\n",
  52     "\n",
  53     "@SimpleFunctionWrapper\n",
  54     "def index_of(stack):\n",
  55     "    '''Given a sequence and a item, return the index of the item, or -1 if not found.\n",
  56     "\n",
  57     "    E.g.:\n",
  58     "\n",
  59     "       [a b c] a index_of\n",
  60     "    ------------------------\n",
  61     "               0\n",
  62     "\n",
  63     "       [a b c] d index_of\n",
  64     "    ------------------------\n",
  65     "            -1\n",
  66     "\n",
  67     "    '''\n",
  68     "    item, (sequence, stack) = stack\n",
  69     "    i = 0\n",
  70     "    while sequence:\n",
  71     "        term, sequence = sequence\n",
  72     "        if term == item:\n",
  73     "            break\n",
  74     "        i += 1\n",
  75     "    else:\n",
  76     "        i = -1\n",
  77     "    return i, stack\n",
  78     "\n",
  79     "\n",
  80     "D['index_of'] = index_of"
  81    ]
  82   },
  83   {
  84    "cell_type": "code",
  85    "execution_count": 4,
  86    "metadata": {},
  87    "outputs": [
  88     {
  89      "name": "stdout",
  90      "output_type": "stream",
  91      "text": [
  92       "2\n"
  93      ]
  94     }
  95    ],
  96    "source": [
  97     "J('[0 2 7 0] 7 index_of')"
  98    ]
  99   },
 100   {
 101    "cell_type": "code",
 102    "execution_count": 5,
 103    "metadata": {},
 104    "outputs": [
 105     {
 106      "name": "stdout",
 107      "output_type": "stream",
 108      "text": [
 109       "-1\n"
 110      ]
 111     }
 112    ],
 113    "source": [
 114     "J('[0 2 7 0] 23 index_of')"
 115    ]
 116   },
 117   {
 118    "cell_type": "markdown",
 119    "metadata": {},
 120    "source": [
 121     "Starting at `index` distribute `count` \"blocks\" to the \"banks\" in the sequence.\n",
 122     "\n",
 123     "    [...] count index distribute\n",
 124     "    ----------------------------\n",
 125     "               [...]\n",
 126     "\n",
 127     "This seems like it would be a PITA to implement in Joypy..."
 128    ]
 129   },
 130   {
 131    "cell_type": "code",
 132    "execution_count": 6,
 133    "metadata": {},
 134    "outputs": [],
 135    "source": [
 136     "from joy.utils.stack import iter_stack, list_to_stack\n",
 137     "\n",
 138     "\n",
 139     "@SimpleFunctionWrapper\n",
 140     "def distribute(stack):\n",
 141     "    '''Starting at index+1 distribute count \"blocks\" to the \"banks\" in the sequence.\n",
 142     "\n",
 143     "    [...] count index distribute\n",
 144     "    ----------------------------\n",
 145     "               [...]\n",
 146     "\n",
 147     "    '''\n",
 148     "    index, (count, (sequence, stack)) = stack\n",
 149     "    assert count >= 0\n",
 150     "    cheat = list(iter_stack(sequence))\n",
 151     "    n = len(cheat)\n",
 152     "    assert index < n\n",
 153     "    cheat[index] = 0\n",
 154     "    while count:\n",
 155     "        index += 1\n",
 156     "        index %= n\n",
 157     "        cheat[index] += 1\n",
 158     "        count -= 1\n",
 159     "    return list_to_stack(cheat), stack\n",
 160     "\n",
 161     "\n",
 162     "D['distribute'] = distribute"
 163    ]
 164   },
 165   {
 166    "cell_type": "code",
 167    "execution_count": 7,
 168    "metadata": {},
 169    "outputs": [
 170     {
 171      "name": "stdout",
 172      "output_type": "stream",
 173      "text": [
 174       "[2 4 1 2]\n"
 175      ]
 176     }
 177    ],
 178    "source": [
 179     "J('[0 2 7 0] dup max [index_of] nullary distribute')"
 180    ]
 181   },
 182   {
 183    "cell_type": "code",
 184    "execution_count": 8,
 185    "metadata": {},
 186    "outputs": [
 187     {
 188      "name": "stdout",
 189      "output_type": "stream",
 190      "text": [
 191       "[3 1 2 3]\n"
 192      ]
 193     }
 194    ],
 195    "source": [
 196     "J('[2 4 1 2] dup max [index_of] nullary distribute')"
 197    ]
 198   },
 199   {
 200    "cell_type": "code",
 201    "execution_count": 9,
 202    "metadata": {},
 203    "outputs": [
 204     {
 205      "name": "stdout",
 206      "output_type": "stream",
 207      "text": [
 208       "[0 2 3 4]\n"
 209      ]
 210     }
 211    ],
 212    "source": [
 213     "J('[3 1 2 3] dup max [index_of] nullary distribute')"
 214    ]
 215   },
 216   {
 217    "cell_type": "code",
 218    "execution_count": 10,
 219    "metadata": {},
 220    "outputs": [
 221     {
 222      "name": "stdout",
 223      "output_type": "stream",
 224      "text": [
 225       "[1 3 4 1]\n"
 226      ]
 227     }
 228    ],
 229    "source": [
 230     "J('[0 2 3 4] dup max [index_of] nullary distribute')"
 231    ]
 232   },
 233   {
 234    "cell_type": "code",
 235    "execution_count": 11,
 236    "metadata": {},
 237    "outputs": [
 238     {
 239      "name": "stdout",
 240      "output_type": "stream",
 241      "text": [
 242       "[2 4 1 2]\n"
 243      ]
 244     }
 245    ],
 246    "source": [
 247     "J('[1 3 4 1] dup max [index_of] nullary distribute')"
 248    ]
 249   },
 250   {
 251    "cell_type": "markdown",
 252    "metadata": {},
 253    "source": [
 254     "### Recalling \"Generator Programs\"\n",
 255     "\n",
 256     "    [a F] x\n",
 257     "    [a F] a F \n",
 258     "    \n",
 259     "    [a F] a swap [C] dip rest cons\n",
 260     "    a   [a F]    [C] dip rest cons\n",
 261     "    a C [a F]            rest cons\n",
 262     "    a C   [F]                 cons\n",
 263     "\n",
 264     "    w/ C == dup G\n",
 265     "\n",
 266     "    a dup G [F] cons\n",
 267     "    a a   G [F] cons\n",
 268     "\n",
 269     "    w/ G == dup max [index_of] nullary distribute"
 270    ]
 271   },
 272   {
 273    "cell_type": "code",
 274    "execution_count": 12,
 275    "metadata": {},
 276    "outputs": [],
 277    "source": [
 278     "define('direco dip rest cons')"
 279    ]
 280   },
 281   {
 282    "cell_type": "code",
 283    "execution_count": 13,
 284    "metadata": {},
 285    "outputs": [],
 286    "source": [
 287     "define('G [direco] cons [swap] swoncat cons')"
 288    ]
 289   },
 290   {
 291    "cell_type": "code",
 292    "execution_count": 14,
 293    "metadata": {},
 294    "outputs": [],
 295    "source": [
 296     "define('make_distributor [dup dup max [index_of] nullary distribute] G')"
 297    ]
 298   },
 299   {
 300    "cell_type": "code",
 301    "execution_count": 15,
 302    "metadata": {},
 303    "outputs": [
 304     {
 305      "name": "stdout",
 306      "output_type": "stream",
 307      "text": [
 308       "[0 2 7 0] [2 4 1 2] [3 1 2 3] [0 2 3 4] [1 3 4 1] [2 4 1 2]\n"
 309      ]
 310     }
 311    ],
 312    "source": [
 313     "J('[0 2 7 0] make_distributor 6 [x] times pop')"
 314    ]
 315   },
 316   {
 317    "cell_type": "markdown",
 318    "metadata": {},
 319    "source": [
 320     "### A function to drive a generator and count how many states before a repeat.\n",
 321     "First draft:\n",
 322     "\n",
 323     "    [] [GEN] x [pop index_of 0 >=] [pop size --] [[swons] dip x] tailrec\n",
 324     "\n",
 325     "(?)\n",
 326     "\n",
 327     "    []       [GEN] x [pop index_of 0 >=] [pop size --] [[swons] dip x] tailrec\n",
 328     "    [] [...] [GEN]   [pop index_of 0 >=] [pop size --] [[swons] dip x] tailrec\n",
 329     "    [] [...] [GEN]    pop index_of 0 >=\n",
 330     "    [] [...]              index_of 0 >=\n",
 331     "                                -1 0 >=\n",
 332     "                                 False\n",
 333     "\n",
 334     "Base case\n",
 335     "\n",
 336     "    [] [...] [GEN] [pop index_of 0 >=] [pop size --] [[swons] dip x] tailrec\n",
 337     "    [] [...] [GEN]                      pop size --\n",
 338     "    [] [...]                                size --\n",
 339     "    [] [...]                                size --\n",
 340     "\n",
 341     "A mistake, `popop` and no need for `--`\n",
 342     "\n",
 343     "    [] [...] [GEN] popop size\n",
 344     "    []                   size\n",
 345     "    n\n",
 346     "\n",
 347     "Recursive case\n",
 348     "\n",
 349     "    [] [...] [GEN] [pop index_of 0 >=] [popop size] [[swons] dip x] tailrec\n",
 350     "    [] [...] [GEN]                                   [swons] dip x  F\n",
 351     "    [] [...] swons [GEN]                                         x  F\n",
 352     "    [[...]]        [GEN]                                         x  F\n",
 353     "    [[...]] [...]  [GEN]                                            F\n",
 354     "\n",
 355     "    [[...]] [...] [GEN] F\n",
 356     "\n",
 357     "What have we learned?\n",
 358     "\n",
 359     "    F == [pop index_of 0 >=] [popop size] [[swons] dip x] tailrec"
 360    ]
 361   },
 362   {
 363    "cell_type": "code",
 364    "execution_count": 16,
 365    "metadata": {},
 366    "outputs": [],
 367    "source": [
 368     "define('count_states [] swap x [pop index_of 0 >=] [popop size] [[swons] dip x] tailrec')"
 369    ]
 370   },
 371   {
 372    "cell_type": "code",
 373    "execution_count": 17,
 374    "metadata": {},
 375    "outputs": [],
 376    "source": [
 377     "define('AoC2017.6 make_distributor count_states')"
 378    ]
 379   },
 380   {
 381    "cell_type": "code",
 382    "execution_count": 18,
 383    "metadata": {},
 384    "outputs": [
 385     {
 386      "name": "stdout",
 387      "output_type": "stream",
 388      "text": [
 389       "5\n"
 390      ]
 391     }
 392    ],
 393    "source": [
 394     "J('[0 2 7 0] AoC2017.6')"
 395    ]
 396   },
 397   {
 398    "cell_type": "code",
 399    "execution_count": 19,
 400    "metadata": {
 401     "scrolled": false
 402    },
 403    "outputs": [
 404     {
 405      "name": "stdout",
 406      "output_type": "stream",
 407      "text": [
 408       "4\n"
 409      ]
 410     }
 411    ],
 412    "source": [
 413     "J('[1 1 1] AoC2017.6')"
 414    ]
 415   },
 416   {
 417    "cell_type": "code",
 418    "execution_count": 20,
 419    "metadata": {
 420     "scrolled": false
 421    },
 422    "outputs": [
 423     {
 424      "name": "stdout",
 425      "output_type": "stream",
 426      "text": [
 427       "15\n"
 428      ]
 429     }
 430    ],
 431    "source": [
 432     "J('[8 0 0 0 0 0] AoC2017.6')"
 433    ]
 434   }
 435  ],
 436  "metadata": {
 437   "kernelspec": {
 438    "display_name": "Python 2",
 439    "language": "python",
 440    "name": "python2"
 441   },
 442   "language_info": {
 443    "codemirror_mode": {
 444     "name": "ipython",
 445     "version": 3
 446    },
 447    "file_extension": ".py",
 448    "mimetype": "text/x-python",
 449    "name": "python",
 450    "nbconvert_exporter": "python",
 451    "pygments_lexer": "ipython3",
 452    "version": "3.8.3"
 453   }
 454  },
 455  "nbformat": 4,
 456  "nbformat_minor": 2
 457 }