docs/Advent_of_Code_2017_December_3rd.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Advent of Code 2017\n",
   8     "\n",
   9     "## December 3rd\n",
  10     "\n",
  11     "You come across an experimental new kind of memory stored on an infinite two-dimensional grid.\n",
  12     "\n",
  13     "Each square on the grid is allocated in a spiral pattern starting at a location marked 1 and then counting up while spiraling outward. For example, the first few squares are allocated like this:\n",
  14     "\n",
  15     "    17  16  15  14  13\n",
  16     "    18   5   4   3  12\n",
  17     "    19   6   1   2  11\n",
  18     "    20   7   8   9  10\n",
  19     "    21  22  23---> ...\n",
  20     "\n",
  21     "While this is very space-efficient (no squares are skipped), requested data must be carried back to square 1 (the location of the only access port for this memory system) by programs that can only move up, down, left, or right. They always take the shortest path: the Manhattan Distance between the location of the data and square 1.\n",
  22     "\n",
  23     "For example:\n",
  24     "\n",
  25     "* Data from square 1 is carried 0 steps, since it's at the access port.\n",
  26     "* Data from square 12 is carried 3 steps, such as: down, left, left.\n",
  27     "* Data from square 23 is carried only 2 steps: up twice.\n",
  28     "* Data from square 1024 must be carried 31 steps.\n",
  29     "\n",
  30     "How many steps are required to carry the data from the square identified in your puzzle input all the way to the access port?"
  31    ]
  32   },
  33   {
  34    "cell_type": "markdown",
  35    "metadata": {},
  36    "source": [
  37     "### Analysis\n",
  38     "\n",
  39     "I freely admit that I worked out the program I wanted to write using graph paper and some Python doodles.  There's no point in trying to write a Joy program until I'm sure I understand the problem well enough.\n",
  40     "\n",
  41     "The first thing I did was to write a column of numbers from 1 to n (32 as it happens) and next to them the desired output number, to look for patterns directly:\n",
  42     "\n",
  43     "    1  0\n",
  44     "    2  1\n",
  45     "    3  2\n",
  46     "    4  1\n",
  47     "    5  2\n",
  48     "    6  1\n",
  49     "    7  2\n",
  50     "    8  1\n",
  51     "    9  2\n",
  52     "    10 3\n",
  53     "    11 2\n",
  54     "    12 3\n",
  55     "    13 4\n",
  56     "    14 3\n",
  57     "    15 2\n",
  58     "    16 3\n",
  59     "    17 4\n",
  60     "    18 3\n",
  61     "    19 2\n",
  62     "    20 3\n",
  63     "    21 4\n",
  64     "    22 3\n",
  65     "    23 2\n",
  66     "    24 3\n",
  67     "    25 4\n",
  68     "    26 5\n",
  69     "    27 4\n",
  70     "    28 3\n",
  71     "    29 4\n",
  72     "    30 5\n",
  73     "    31 6\n",
  74     "    32 5"
  75    ]
  76   },
  77   {
  78    "cell_type": "markdown",
  79    "metadata": {},
  80    "source": [
  81     "There are four groups repeating for a given \"rank\", then the pattern enlarges and four groups repeat again, etc.\n",
  82     "\n",
  83     "            1 2\n",
  84     "          3 2 3 4\n",
  85     "        5 4 3 4 5 6\n",
  86     "      7 6 5 4 5 6 7 8\n",
  87     "    9 8 7 6 5 6 7 8 9 10\n",
  88     "\n",
  89     "Four of this pyramid interlock to tile the plane extending from the initial \"1\" square.\n",
  90     "\n",
  91     "\n",
  92     "             2   3   |    4  5   |    6  7   |    8  9\n",
  93     "          10 11 12 13|14 15 16 17|18 19 20 21|22 23 24 25\n",
  94     "\n",
  95     "And so on."
  96    ]
  97   },
  98   {
  99    "cell_type": "markdown",
 100    "metadata": {},
 101    "source": [
 102     "We can figure out the pattern for a row of the pyramid at a given \"rank\" $k$:\n",
 103     "\n",
 104     "$2k - 1, 2k - 2, ..., k, k + 1, k + 2, ..., 2k$\n",
 105     "\n",
 106     "or\n",
 107     "\n",
 108     "$k + (k - 1), k + (k - 2), ..., k, k + 1, k + 2, ..., k + k$\n",
 109     "\n",
 110     "This shows that the series consists at each place of $k$ plus some number that begins at $k - 1$, decreases to zero, then increases to $k$.  Each row has $2k$ members."
 111    ]
 112   },
 113   {
 114    "cell_type": "markdown",
 115    "metadata": {},
 116    "source": [
 117     "Let's figure out how, given an index into a row, we can calculate the value there.  The index will be from 0 to $k - 1$. \n",
 118     "\n",
 119     " Let's look at an example, with $k = 4$:\n",
 120     "\n",
 121     "    0 1 2 3 4 5 6 7\n",
 122     "    7 6 5 4 5 6 7 8"
 123    ]
 124   },
 125   {
 126    "cell_type": "code",
 127    "execution_count": 1,
 128    "metadata": {},
 129    "outputs": [],
 130    "source": [
 131     "k = 4"
 132    ]
 133   },
 134   {
 135    "cell_type": "markdown",
 136    "metadata": {},
 137    "source": [
 138     "Subtract $k$ from the index and take the absolute value:"
 139    ]
 140   },
 141   {
 142    "cell_type": "code",
 143    "execution_count": 2,
 144    "metadata": {},
 145    "outputs": [
 146     {
 147      "name": "stdout",
 148      "output_type": "stream",
 149      "text": [
 150       "4 3 2 1 0 1 2 3\n"
 151      ]
 152     }
 153    ],
 154    "source": [
 155     "for n in range(2 * k):\n",
 156     "    print abs(n - k),"
 157    ]
 158   },
 159   {
 160    "cell_type": "markdown",
 161    "metadata": {},
 162    "source": [
 163     "Not quite. Subtract $k - 1$ from the index and take the absolute value:"
 164    ]
 165   },
 166   {
 167    "cell_type": "code",
 168    "execution_count": 3,
 169    "metadata": {},
 170    "outputs": [
 171     {
 172      "name": "stdout",
 173      "output_type": "stream",
 174      "text": [
 175       "3 2 1 0 1 2 3 4\n"
 176      ]
 177     }
 178    ],
 179    "source": [
 180     "for n in range(2 * k):\n",
 181     "    print abs(n - (k - 1)),"
 182    ]
 183   },
 184   {
 185    "cell_type": "markdown",
 186    "metadata": {},
 187    "source": [
 188     "Great, now add $k$..."
 189    ]
 190   },
 191   {
 192    "cell_type": "code",
 193    "execution_count": 4,
 194    "metadata": {},
 195    "outputs": [
 196     {
 197      "name": "stdout",
 198      "output_type": "stream",
 199      "text": [
 200       "7 6 5 4 5 6 7 8\n"
 201      ]
 202     }
 203    ],
 204    "source": [
 205     "for n in range(2 * k):\n",
 206     "    print abs(n - (k - 1)) + k,"
 207    ]
 208   },
 209   {
 210    "cell_type": "markdown",
 211    "metadata": {},
 212    "source": [
 213     "So to write a function that can give us the value of a row at a given index:"
 214    ]
 215   },
 216   {
 217    "cell_type": "code",
 218    "execution_count": 5,
 219    "metadata": {},
 220    "outputs": [],
 221    "source": [
 222     "def row_value(k, i):\n",
 223     "    i %= (2 * k)  # wrap the index at the row boundary.\n",
 224     "    return abs(i - (k - 1)) + k"
 225    ]
 226   },
 227   {
 228    "cell_type": "code",
 229    "execution_count": 6,
 230    "metadata": {},
 231    "outputs": [
 232     {
 233      "name": "stdout",
 234      "output_type": "stream",
 235      "text": [
 236       "9 8 7 6 5 6 7 8 9 10\n"
 237      ]
 238     }
 239    ],
 240    "source": [
 241     "k = 5\n",
 242     "for i in range(2 * k):\n",
 243     "    print row_value(k, i),"
 244    ]
 245   },
 246   {
 247    "cell_type": "markdown",
 248    "metadata": {},
 249    "source": [
 250     "(I'm leaving out details of how I figured this all out and just giving the relevent bits.  It took a little while to zero in of the aspects of the pattern that were important for the task.)"
 251    ]
 252   },
 253   {
 254    "cell_type": "markdown",
 255    "metadata": {},
 256    "source": [
 257     "### Finding the rank and offset of a number.\n",
 258     "Now that we can compute the desired output value for a given rank and the offset (index) into that rank, we need to determine how to find the rank and offset of a number.\n",
 259     "\n",
 260     "The rank is easy to find by iteratively stripping off the amount already covered by previous ranks until you find the one that brackets the target number.  Because each row is $2k$ places and there are $4$ per rank each rank contains $8k$ places.  Counting the initial square we have:\n",
 261     "\n",
 262     "$corner_k = 1 + \\sum_{n=1}^k 8n$\n",
 263     "\n",
 264     "I'm not mathematically sophisticated enough to turn this directly into a formula (but Sympy is, see below.)  I'm going to write a simple Python function to iterate and search:"
 265    ]
 266   },
 267   {
 268    "cell_type": "code",
 269    "execution_count": 7,
 270    "metadata": {},
 271    "outputs": [],
 272    "source": [
 273     "def rank_and_offset(n):\n",
 274     "    assert n >= 2  # Guard the domain.\n",
 275     "    n -= 2  # Subtract two,\n",
 276     "            # one for the initial square,\n",
 277     "            # and one because we are counting from 1 instead of 0.\n",
 278     "    k = 1\n",
 279     "    while True:\n",
 280     "        m = 8 * k  # The number of places total in this rank, 4(2k).\n",
 281     "        if n < m:\n",
 282     "            return k, n % (2 * k)\n",
 283     "        n -= m  # Remove this rank's worth.\n",
 284     "        k += 1"
 285    ]
 286   },
 287   {
 288    "cell_type": "code",
 289    "execution_count": 8,
 290    "metadata": {
 291     "scrolled": true
 292    },
 293    "outputs": [
 294     {
 295      "name": "stdout",
 296      "output_type": "stream",
 297      "text": [
 298       "2 (1, 0)\n",
 299       "3 (1, 1)\n",
 300       "4 (1, 0)\n",
 301       "5 (1, 1)\n",
 302       "6 (1, 0)\n",
 303       "7 (1, 1)\n",
 304       "8 (1, 0)\n",
 305       "9 (1, 1)\n",
 306       "10 (2, 0)\n",
 307       "11 (2, 1)\n",
 308       "12 (2, 2)\n",
 309       "13 (2, 3)\n",
 310       "14 (2, 0)\n",
 311       "15 (2, 1)\n",
 312       "16 (2, 2)\n",
 313       "17 (2, 3)\n",
 314       "18 (2, 0)\n",
 315       "19 (2, 1)\n",
 316       "20 (2, 2)\n",
 317       "21 (2, 3)\n",
 318       "22 (2, 0)\n",
 319       "23 (2, 1)\n",
 320       "24 (2, 2)\n",
 321       "25 (2, 3)\n",
 322       "26 (3, 0)\n",
 323       "27 (3, 1)\n",
 324       "28 (3, 2)\n",
 325       "29 (3, 3)\n",
 326       "30 (3, 4)\n",
 327       "31 (3, 5)\n",
 328       "32 (3, 0)\n",
 329       "33 (3, 1)\n",
 330       "34 (3, 2)\n",
 331       "35 (3, 3)\n",
 332       "36 (3, 4)\n",
 333       "37 (3, 5)\n",
 334       "38 (3, 0)\n",
 335       "39 (3, 1)\n",
 336       "40 (3, 2)\n",
 337       "41 (3, 3)\n",
 338       "42 (3, 4)\n",
 339       "43 (3, 5)\n",
 340       "44 (3, 0)\n",
 341       "45 (3, 1)\n",
 342       "46 (3, 2)\n",
 343       "47 (3, 3)\n",
 344       "48 (3, 4)\n",
 345       "49 (3, 5)\n",
 346       "50 (4, 0)\n"
 347      ]
 348     }
 349    ],
 350    "source": [
 351     "for n in range(2, 51):\n",
 352     "    print n, rank_and_offset(n)"
 353    ]
 354   },
 355   {
 356    "cell_type": "code",
 357    "execution_count": 9,
 358    "metadata": {
 359     "scrolled": true
 360    },
 361    "outputs": [
 362     {
 363      "name": "stdout",
 364      "output_type": "stream",
 365      "text": [
 366       "2 1\n",
 367       "3 2\n",
 368       "4 1\n",
 369       "5 2\n",
 370       "6 1\n",
 371       "7 2\n",
 372       "8 1\n",
 373       "9 2\n",
 374       "10 3\n",
 375       "11 2\n",
 376       "12 3\n",
 377       "13 4\n",
 378       "14 3\n",
 379       "15 2\n",
 380       "16 3\n",
 381       "17 4\n",
 382       "18 3\n",
 383       "19 2\n",
 384       "20 3\n",
 385       "21 4\n",
 386       "22 3\n",
 387       "23 2\n",
 388       "24 3\n",
 389       "25 4\n",
 390       "26 5\n",
 391       "27 4\n",
 392       "28 3\n",
 393       "29 4\n",
 394       "30 5\n",
 395       "31 6\n",
 396       "32 5\n",
 397       "33 4\n",
 398       "34 3\n",
 399       "35 4\n",
 400       "36 5\n",
 401       "37 6\n",
 402       "38 5\n",
 403       "39 4\n",
 404       "40 3\n",
 405       "41 4\n",
 406       "42 5\n",
 407       "43 6\n",
 408       "44 5\n",
 409       "45 4\n",
 410       "46 3\n",
 411       "47 4\n",
 412       "48 5\n",
 413       "49 6\n",
 414       "50 7\n"
 415      ]
 416     }
 417    ],
 418    "source": [
 419     "for n in range(2, 51):\n",
 420     "    k, i = rank_and_offset(n)\n",
 421     "    print n, row_value(k, i)"
 422    ]
 423   },
 424   {
 425    "cell_type": "markdown",
 426    "metadata": {},
 427    "source": [
 428     "### Putting it all together"
 429    ]
 430   },
 431   {
 432    "cell_type": "code",
 433    "execution_count": 10,
 434    "metadata": {},
 435    "outputs": [],
 436    "source": [
 437     "def row_value(k, i):\n",
 438     "    return abs(i - (k - 1)) + k\n",
 439     "\n",
 440     "\n",
 441     "def rank_and_offset(n):\n",
 442     "    n -= 2  # Subtract two,\n",
 443     "            # one for the initial square,\n",
 444     "            # and one because we are counting from 1 instead of 0.\n",
 445     "    k = 1\n",
 446     "    while True:\n",
 447     "        m = 8 * k  # The number of places total in this rank, 4(2k).\n",
 448     "        if n < m:\n",
 449     "            return k, n % (2 * k)\n",
 450     "        n -= m  # Remove this rank's worth.\n",
 451     "        k += 1\n",
 452     "\n",
 453     "\n",
 454     "def aoc20173(n):\n",
 455     "    if n <= 1:\n",
 456     "        return 0\n",
 457     "    k, i = rank_and_offset(n)\n",
 458     "    return row_value(k, i)"
 459    ]
 460   },
 461   {
 462    "cell_type": "code",
 463    "execution_count": 11,
 464    "metadata": {
 465     "scrolled": true
 466    },
 467    "outputs": [
 468     {
 469      "data": {
 470       "text/plain": [
 471        "2"
 472       ]
 473      },
 474      "execution_count": 11,
 475      "metadata": {},
 476      "output_type": "execute_result"
 477     }
 478    ],
 479    "source": [
 480     "aoc20173(23)"
 481    ]
 482   },
 483   {
 484    "cell_type": "code",
 485    "execution_count": 12,
 486    "metadata": {
 487     "scrolled": true
 488    },
 489    "outputs": [
 490     {
 491      "data": {
 492       "text/plain": [
 493        "105"
 494       ]
 495      },
 496      "execution_count": 12,
 497      "metadata": {},
 498      "output_type": "execute_result"
 499     }
 500    ],
 501    "source": [
 502     "aoc20173(23000)"
 503    ]
 504   },
 505   {
 506    "cell_type": "code",
 507    "execution_count": 13,
 508    "metadata": {
 509     "scrolled": true
 510    },
 511    "outputs": [
 512     {
 513      "data": {
 514       "text/plain": [
 515        "4572225"
 516       ]
 517      },
 518      "execution_count": 13,
 519      "metadata": {},
 520      "output_type": "execute_result"
 521     }
 522    ],
 523    "source": [
 524     "aoc20173(23000000000000)"
 525    ]
 526   },
 527   {
 528    "cell_type": "markdown",
 529    "metadata": {},
 530    "source": [
 531     "# Sympy to the Rescue\n",
 532     "### Find the rank for large numbers\n",
 533     "Using e.g. Sympy we can find the rank directly by solving for the roots of an equation.  For large numbers this will (eventually) be faster than iterating as `rank_and_offset()` does."
 534    ]
 535   },
 536   {
 537    "cell_type": "code",
 538    "execution_count": 14,
 539    "metadata": {},
 540    "outputs": [],
 541    "source": [
 542     "from sympy import floor, lambdify, solve, symbols\n",
 543     "from sympy import init_printing\n",
 544     "init_printing() "
 545    ]
 546   },
 547   {
 548    "cell_type": "code",
 549    "execution_count": 15,
 550    "metadata": {},
 551    "outputs": [],
 552    "source": [
 553     "k = symbols('k')"
 554    ]
 555   },
 556   {
 557    "cell_type": "markdown",
 558    "metadata": {},
 559    "source": [
 560     "Since\n",
 561     "\n",
 562     "$1 + 2 + 3 + ... + N = \\frac{N(N + 1)}{2}$\n",
 563     "\n",
 564     "and\n",
 565     "\n",
 566     "$\\sum_{n=1}^k 8n = 8(\\sum_{n=1}^k n) = 8\\frac{k(k + 1)}{2}$\n",
 567     "\n",
 568     "We want:"
 569    ]
 570   },
 571   {
 572    "cell_type": "code",
 573    "execution_count": 16,
 574    "metadata": {},
 575    "outputs": [
 576     {
 577      "data": {
 578       "image/png": "iVBORw0KGgoAAAANSUhEUgAAAHwAAAAUBAMAAAC9l0S6AAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAMpndu3bvImbNiRBU\nq0Qb3U6NAAAACXBIWXMAAA7EAAAOxAGVKw4bAAACAElEQVQ4EW1UzWsTQRx9NB+bzSZt6D/gHvRS\nKOZQWhAK6UHrsRShhyIW2rvBiznp0ltPxdJLDi2h9aIXc7C0emlA6k38wKKXYsA/IFZEhITG95vZ\nj5klD3bmvff7vczsMBvARsOWiSrUE26zSeD1uracGrw7Vbscqm9p99H1BWXNcNzRRZdruL7mxvi+\nDbwxtFDvE151Oec2OAz4EJt8JjrCBGd68r78YLy4pFXkltvIr9Fq7ALjfV2b49Rjr0YYBx7Q8tZs\nN19F+ZJWi/FiVdUcmQ7Dtnh1Hcd+6Ic/6vZVvFBn3PVL9yt8D58tOzj7rDut1XFgx6ky3PMRGD/t\nrPQCIMvHG+Se/IOCHd/SZvTuVL0W9y7xj0ftE+pMByj1V72AnLDj77SZuJhnd0XiN31Vy3eBsd+6\n7UWzOdts7ikhR4drQk13zAfeQuLz95akKPHM+W2hAnt1FTfdZYoPFxd/z70r50r6ZfOn3add4YQd\n/6nN2C35eCzWBgq/vEGRLBsA2zzHFhTseProeNdXpO0PyjVcSrzoA18xUWmRE3Z8SpuR69x6OS3X\n5PnwezbA8irpOPVd5G7ISRFRfPrhXgA8U17susPhUOIm5NImiOLKUTdSmOUmzcLkk0lwnFDjk7Fc\ns4NnV7e1odIfrFGKqVOLaZospo1RujHKFG/0n9V/fdOG1o/ONcUAAAAASUVORK5CYII=\n",
 579       "text/latex": [
 580        "$$4 k \\left(k + 1\\right) + 2$$"
 581       ],
 582       "text/plain": [
 583        "4⋅k⋅(k + 1) + 2"
 584       ]
 585      },
 586      "execution_count": 16,
 587      "metadata": {},
 588      "output_type": "execute_result"
 589     }
 590    ],
 591    "source": [
 592     "E = 2 + 8 * k * (k + 1) / 2  # For the reason for adding 2 see above.\n",
 593     "\n",
 594     "E"
 595    ]
 596   },
 597   {
 598    "cell_type": "markdown",
 599    "metadata": {},
 600    "source": [
 601     "We can write a function to solve for $k$ given some $n$..."
 602    ]
 603   },
 604   {
 605    "cell_type": "code",
 606    "execution_count": 17,
 607    "metadata": {},
 608    "outputs": [],
 609    "source": [
 610     "def rank_of(n):\n",
 611     "    return floor(max(solve(E - n, k))) + 1"
 612    ]
 613   },
 614   {
 615    "cell_type": "markdown",
 616    "metadata": {},
 617    "source": [
 618     "First `solve()` for $E - n = 0$ which has two solutions (because the equation is quadratic so it has two roots) and since we only care about the larger one we use `max()` to select it.  It will generally not be a nice integer (unless $n$ is the number of an end-corner of a rank) so we take the `floor()` and add 1 to get the integer rank of $n$.  (Taking the `ceiling()` gives off-by-one errors on the rank boundaries.  I don't know why.  I'm basically like a monkey doing math here.)  =-D\n",
 619     "\n",
 620     "It gives correct answers:"
 621    ]
 622   },
 623   {
 624    "cell_type": "code",
 625    "execution_count": 18,
 626    "metadata": {},
 627    "outputs": [
 628     {
 629      "name": "stdout",
 630      "output_type": "stream",
 631      "text": [
 632       "9 1\n",
 633       "10 2\n",
 634       "25 2\n",
 635       "26 3\n",
 636       "49 3\n",
 637       "50 4\n"
 638      ]
 639     }
 640    ],
 641    "source": [
 642     "for n in (9, 10, 25, 26, 49, 50):\n",
 643     "    print n, rank_of(n)"
 644    ]
 645   },
 646   {
 647    "cell_type": "markdown",
 648    "metadata": {},
 649    "source": [
 650     "And it runs much faster (at least for large numbers):"
 651    ]
 652   },
 653   {
 654    "cell_type": "code",
 655    "execution_count": 19,
 656    "metadata": {},
 657    "outputs": [
 658     {
 659      "name": "stdout",
 660      "output_type": "stream",
 661      "text": [
 662       "CPU times: user 68 ms, sys: 8 ms, total: 76 ms\n",
 663       "Wall time: 73.8 ms\n"
 664      ]
 665     },
 666     {
 667      "data": {
 668       "image/png": "iVBORw0KGgoAAAANSUhEUgAAAEcAAAAPBAMAAABElc8tAAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAIpm7MhCriUTv3c12\nVGZoascqAAAACXBIWXMAAA7EAAAOxAGVKw4bAAABkUlEQVQoFY2QPUscURSGn4l7d4y7q6ONxGqZ\ngEbSCFZWTmfpYCHEFK6CRdIoJmQaYacNBBJJ4wcqKNhYaKNYBFeCnYKLjdhNK4j5NrKbOHlnxx+Q\nAzP33nOf+77nHCy338MKXlUxPW8cMps9QcBIMMF92HOvYRT7lg4KdzyLrHla4zi+Mas8cuDCB7PP\nU5iCRU6r1HgBkzzQZSn7gWzRTE4LairSD0sw7b0NTZ06lLHB9tp2sL/CqaD3egQVXxCyMz+U1o53\njPeR/5lCA0o0YlsvxmZYllKoRB8PpXSbQvWhz0mO5t/Que7Li0oktyjxyt01IFOPWBFDS0k/e4Hc\nYaFchXGdPnH+N4Vin14Z4epTiz5XR2UPjnVoPRm6r6kGX0LIF6EdBiVC0vSGVsj+SmvaEhTBGZYj\n0Qa0p+ndNKBcKYU0PClliuSdj7DtXDqZb5D5Lrd5hp0UGlZN0BXMvuSawh+O/ecSLgjK75oD6SXD\nzM4YdVeJ4xrN7uMQ232iGyvpeNYNoXttL9K221PiP+If4oN7f8ioQFsAAAAASUVORK5CYII=\n",
 669       "text/latex": [
 670        "$$2397916$$"
 671       ],
 672       "text/plain": [
 673        "2397916"
 674       ]
 675      },
 676      "execution_count": 19,
 677      "metadata": {},
 678      "output_type": "execute_result"
 679     }
 680    ],
 681    "source": [
 682     "%time rank_of(23000000000000)  # Compare runtime with rank_and_offset()!"
 683    ]
 684   },
 685   {
 686    "cell_type": "code",
 687    "execution_count": 20,
 688    "metadata": {},
 689    "outputs": [
 690     {
 691      "name": "stdout",
 692      "output_type": "stream",
 693      "text": [
 694       "CPU times: user 308 ms, sys: 0 ns, total: 308 ms\n",
 695       "Wall time: 306 ms\n"
 696      ]
 697     },
 698     {
 699      "data": {
 700       "image/png": "iVBORw0KGgoAAAANSUhEUgAAALAAAAAUBAMAAADfFKqVAAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAIma7zZnddlTvRIky\nEKtZsEGBAAAACXBIWXMAAA7EAAAOxAGVKw4bAAADLElEQVQ4Ea2VT2hcVRjFf28yfzNzZ6ZIC9LN\nQwpSXDQahCpiYzdCqWagnYUGw4h/EAo1QkMXin0b3biYqYqkwcJsrLiQBHQMMmJm46qLeUJUumlS\nQaG0UhvHWGrT6bn3PYszuBih3+Lcf+ee993zvncfeD73PBJlSd4HO488Abvb++GH9iUKx2fabczM\nt3bVRfvNTty723jVyQ4RtL8IIL/yjbY8ZHmWfUntU5gNVptehbpv3uf+cqLf79/mgu+dhuxZMdaa\nqSk1A3GR/E0c7CS7iTnEUZKBeTFmr0GiQjEk18jcoFQrNihWUsp0g8vwCxdntyX3KGMTA6oa/AZn\nIjgVsMVYhUn2wpcxOz9HukyuRvHW+CLrU6Up8r/ndbAOPViFjITHrw+ravwRXOs4+KxpeixZ256E\nehixTYNdkNyWsBbq/voEGdv7FPMHnOo44bGGZoZjOpSwA/m1yWN2/TYsBTH7EPNuS1qZmWPklPFN\nTejkHyrjphMuHV553pGG4PVQExZ+XKZ3fr5p/pTwXMxu8YijLy3jffWCfCC5KSd858O074TXD5IL\nHGsAxv/W0MLuV0LT81nw1O8ux+w9vObYxy1+3eRp3rsB6xok57KrQSS8TcoWx1CkNzThIL9o+iHP\nfa+MJRyx32XR8lMVi7mzJE6el8cn7OjBt1Yjj0s1EtafoajasQPOhFuw73MJy4qI3Y2E58ErM6Zk\nKcrtlyKNa6HLOD1FQv4MRcbmYmEHHAhelrCvl1cPYnbXWZGtsKO0HQknNzBi2HhWO/UYFfd/ZPyO\nTcWCXDgQqOr3NScFYcw+517ed/BGboL09cRpumUKOhN7ywXVrxUuyLWGe9K/oFAhU3bwgUqj3JXH\n9gM5+g97Dy25cKw9W0v41Ocyz5iDqksrfCJc8yNhrnAh0EcwELvarV9x8ADZvygumwXSgfkYx4YZ\nzqkAdDnU+KT6OLSqTT1oQRr5qoo3dbn3s+1ehVfDAeHpfn8LB+PVI9rTmu1gVt7uxGwO2096pMiO\nyIvEPNVGZSRddIP8j9AlxMOj8X8ajRaz1tTqoh8l/FFIdzk2W88X3OPQr+kOAx0PXfbg7EwAAAAA\nSUVORK5CYII=\n",
 701       "text/latex": [
 702        "$$\\left ( 2397916, \\quad 223606\\right )$$"
 703       ],
 704       "text/plain": [
 705        "(2397916, 223606)"
 706       ]
 707      },
 708      "execution_count": 20,
 709      "metadata": {},
 710      "output_type": "execute_result"
 711     }
 712    ],
 713    "source": [
 714     "%time rank_and_offset(23000000000000)"
 715    ]
 716   },
 717   {
 718    "cell_type": "markdown",
 719    "metadata": {},
 720    "source": [
 721     "After finding the rank you would still have to find the actual value of the rank's first corner and subtract it (plus 2) from the number and compute the offset as above and then the final output, but this overhead is partially shared by the other method, and overshadowed by the time it (the other iterative method) would take for really big inputs.\n",
 722     "\n",
 723     "The fun thing to do here would be to graph the actual runtime of both methods against each other to find the trade-off point."
 724    ]
 725   },
 726   {
 727    "cell_type": "markdown",
 728    "metadata": {},
 729    "source": [
 730     "### It took me a second to realize I could do this...\n",
 731     "Sympy is a *symbolic* math library, and it supports symbolic manipulation of equations.  I can put in $y$ (instead of a value) and ask it to solve for $k$."
 732    ]
 733   },
 734   {
 735    "cell_type": "code",
 736    "execution_count": 21,
 737    "metadata": {},
 738    "outputs": [],
 739    "source": [
 740     "y = symbols('y')"
 741    ]
 742   },
 743   {
 744    "cell_type": "code",
 745    "execution_count": 22,
 746    "metadata": {},
 747    "outputs": [],
 748    "source": [
 749     "g, f = solve(E - y, k)"
 750    ]
 751   },
 752   {
 753    "cell_type": "markdown",
 754    "metadata": {},
 755    "source": [
 756     "The equation is quadratic so there are two roots, we are interested in the greater one..."
 757    ]
 758   },
 759   {
 760    "cell_type": "code",
 761    "execution_count": 23,
 762    "metadata": {},
 763    "outputs": [
 764     {
 765      "data": {
 766       "image/png": "iVBORw0KGgoAAAANSUhEUgAAAIkAAAAqBAMAAAB1gmW6AAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAEM3dMlTvq5l2ZiK7\niUTiBfEGAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAB6klEQVRIDe2Uv0vDQBTHv9eiTU2pRQdxsqLo\n4CI6CEKxo5tObqKOThYHEUEUlyKIOklFwf4J4iQ42EEQt86C6Ca62IogqKh3lzQ/nkm8BEdvuL73\nve/ny/WlDfDXayoTJdFNseW1CCk/qaMIKQClaK/2/ShF+/8UYwLuuex8eS86LTdFnpleoXafPjAl\ncedDUTkw5YS6/XqSUlzoL9vWbbsMrNwUsbIsESK12qQX1jTnpfpr7V5HHcW6l+yvXXseJcOlsMG/\nSEmWgc5N6GQOIe8S51epTiFZc19JPYUJcB/QJzeQqiimtA2L1QvI/14Nek6AfCwM82jd5bXlAIy7\nsB6BDOWF0aRE6VyPfbxrqfIt/Y6JvPOokeLWvLuZMhDP8DMtiz1iUZ9L8yAwLehUAZeRU5KfQLeg\ntUr6LXIK+0DTuqDZaundnaItPa+4lZ/d6daFFHeOY8fGKZ/Mr6tBmUZWwO2dqM+r91JaRJfsZeO3\nWZRpSGTQPCvqVG1ASqO4kp+Bm0WZLv5sEi+iTr8WpPRQysvPwM2iTFesbqZgTIFuRNtUQ0HceH0c\nWoJSYVKW96lqlSEKSo2EYG0robR1+0i9olRJHXU4CcV/92eOU8WSUuPAgSLqsBFKz90U+Ush5KJU\njL/8wqcY1Dcp15UsZrvPlwAAAABJRU5ErkJggg==\n",
 767       "text/latex": [
 768        "$$- \\frac{1}{2} \\sqrt{y - 1} - \\frac{1}{2}$$"
 769       ],
 770       "text/plain": [
 771        "    _______    \n",
 772        "  ╲╱ y - 1    1\n",
 773        "- ───────── - ─\n",
 774        "      2       2"
 775       ]
 776      },
 777      "execution_count": 23,
 778      "metadata": {},
 779      "output_type": "execute_result"
 780     }
 781    ],
 782    "source": [
 783     "g"
 784    ]
 785   },
 786   {
 787    "cell_type": "code",
 788    "execution_count": 24,
 789    "metadata": {},
 790    "outputs": [
 791     {
 792      "data": {
 793       "image/png": "iVBORw0KGgoAAAANSUhEUgAAAHgAAAAqBAMAAACKDIIdAAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAVO8Qq5l2zWYiuzKJ\nRN0MreaOAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAB9ElEQVRIDe2Vu0vDUBTGvzRNSrSNILgX3TVD\nwU2LD3DRVqgIOthF0akdXETQbi4OVXDQoTg46aCLexedCvY/aEHBRVQQfOCj3nOrmCa3ubGuHmjP\nyXe+3z1tb24K/C06rVZ4pYdR6miiFTiWeuAjM63A0P/h322Y8AfTauK4d6wthPccpmaXQni8mduh\ni2Aj6zA1u6zDqb7l3I9DK//UXpU29DTm6ve7lF8Ik0Kvv4OnVgWw34MXzglgwN/BGxCyPuFF9nSY\nT2PbalzE3+QqEFaiyDSy8sk0TE8DW1oWhz5hfgzugUKRASZ7WYE0HllW125ZXJ+w8mtyPwm3qyR0\ncIwqishGlL1vUlnJt79StoXsOyvPzHxJwDT0KGVbyGD0AkqRgAO0xSnbQgpnygjxHZpBJWcDqZTC\ng/vo4kzsfC7fCDcePHtvZ+aIX2ovWPnSp+19cW1MHbJ9UOO4KJPBeIvEKQez6jtl74ghzFxBC4Eo\nNx6H+Kc1c21pb5C6w0A3EKgiWN/WyghnIguzcpb2JnGC0MM3bDpvDa811i2CWZj1Pzx938vt7t1Z\npFWK7o5cibxxz5XcKXCYcRK1pKAll6a4ZV5uFDh0PlJJYlfQlEldMPLAKbAkc7r77UnoeRg3pVTV\n3ZQphdLZBBBiD5QW4PVa7QOfZ0qXehvwRMIAAAAASUVORK5CYII=\n",
 794       "text/latex": [
 795        "$$\\frac{1}{2} \\sqrt{y - 1} - \\frac{1}{2}$$"
 796       ],
 797       "text/plain": [
 798        "  _______    \n",
 799        "╲╱ y - 1    1\n",
 800        "───────── - ─\n",
 801        "    2       2"
 802       ]
 803      },
 804      "execution_count": 24,
 805      "metadata": {},
 806      "output_type": "execute_result"
 807     }
 808    ],
 809    "source": [
 810     "f"
 811    ]
 812   },
 813   {
 814    "cell_type": "markdown",
 815    "metadata": {},
 816    "source": [
 817     "Now we can take the `floor()`, add 1, and `lambdify()` the equation to get a Python function that calculates the rank directly."
 818    ]
 819   },
 820   {
 821    "cell_type": "code",
 822    "execution_count": 25,
 823    "metadata": {},
 824    "outputs": [
 825     {
 826      "data": {
 827       "image/png": "iVBORw0KGgoAAAANSUhEUgAAAK0AAAAqBAMAAAAzNMYQAAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAEGYiq+/dVJl2zbsy\niUT7WiApAAAACXBIWXMAAA7EAAAOxAGVKw4bAAACUUlEQVRIDe2Uv2/TQBTHv1YgsdMmRCUwdCEz\nElIHCANLqAAx0TLASpEgAwxMSGXrUImqVCJigimRqBgipHZg60D+BEZAQup/EH5ISCBKuPfsc8/2\nw2fHYuOk5L177/v9+Hw+G/ino3J9GrzV1Vz/MgU3g8ubhgu7y66Q7sfusiv+c6Ud8Gv23Ysq3Ik8\nPscuEXXFmjyNKi5IEqEWdQmC2Em8JkmEWhp3jvURRWkgMKRS4PKk3lkqupd/Lh423f3DPC3Trqok\nYm60MR+dWmdZuY9F0sOGWFbFBJekyfU6KwLAubpk5T7yfb40ya21BC7Qz8r1pUnuSRFbnPsMcJ73\ncC62vsLrXQFqlWX0Y8suwqUlej3gvDvAXnHuMf7MAO13ilVWv8bRHn6o6LzqqnFvpNJgf+ep0H1N\nBe3yz9nH4fDucLhNDZYaz61+elkVz1BnvDD7i6IxCuxD5avi3CbWJjy6hjkKcHETqNBe4A1mOiZU\n5UW4/X1UG8R7gnGLojGKcE/tYpVRzQ9PFwymStdvbbeilXCmvw/Be+xL+bmVNvZGJHO/4WUg3wxi\nStCuOJctzG2i9ptmpYN6h+KRgcNzyv8+tEtzj5tS5l4EbnDxbZVvv9ya6ZkiOdcuzY2omKvOwdKI\nyuNL3Ky/2OKY/qddIvdE9w6w0wi45fjbkEb2Xe3u/TTRAz5f3m6aJtnzXcl6WKkfhGmOxO4qd3Lg\nQqndtRFq8yRWl7eWB6e1dtcqSnxwtSNbtLpm1+Dl59pd7U/vr2Rboqmyu3Ymk++mI1ue5voDRu6s\n5n/E50UAAAAASUVORK5CYII=\n",
 828       "text/latex": [
 829        "$$\\lfloor{\\frac{1}{2} \\sqrt{y - 1} - \\frac{1}{2}}\\rfloor + 1$$"
 830       ],
 831       "text/plain": [
 832        "⎢  _______    ⎥    \n",
 833        "⎢╲╱ y - 1    1⎥    \n",
 834        "⎢───────── - ─⎥ + 1\n",
 835        "⎣    2       2⎦    "
 836       ]
 837      },
 838      "execution_count": 25,
 839      "metadata": {},
 840      "output_type": "execute_result"
 841     }
 842    ],
 843    "source": [
 844     "floor(f) + 1"
 845    ]
 846   },
 847   {
 848    "cell_type": "code",
 849    "execution_count": 26,
 850    "metadata": {},
 851    "outputs": [],
 852    "source": [
 853     "F = lambdify(y, floor(f) + 1)"
 854    ]
 855   },
 856   {
 857    "cell_type": "code",
 858    "execution_count": 27,
 859    "metadata": {},
 860    "outputs": [
 861     {
 862      "name": "stdout",
 863      "output_type": "stream",
 864      "text": [
 865       "9 1\n",
 866       "10 2\n",
 867       "25 2\n",
 868       "26 3\n",
 869       "49 3\n",
 870       "50 4\n"
 871      ]
 872     }
 873    ],
 874    "source": [
 875     "for n in (9, 10, 25, 26, 49, 50):\n",
 876     "    print n, int(F(n))"
 877    ]
 878   },
 879   {
 880    "cell_type": "markdown",
 881    "metadata": {},
 882    "source": [
 883     "It's pretty fast."
 884    ]
 885   },
 886   {
 887    "cell_type": "code",
 888    "execution_count": 28,
 889    "metadata": {
 890     "scrolled": false
 891    },
 892    "outputs": [
 893     {
 894      "name": "stdout",
 895      "output_type": "stream",
 896      "text": [
 897       "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
 898       "Wall time: 11.9 µs\n"
 899      ]
 900     },
 901     {
 902      "data": {
 903       "image/png": "iVBORw0KGgoAAAANSUhEUgAAAEcAAAAPBAMAAABElc8tAAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAIpm7MhCriUTv3c12\nVGZoascqAAAACXBIWXMAAA7EAAAOxAGVKw4bAAABkUlEQVQoFY2QPUscURSGn4l7d4y7q6ONxGqZ\ngEbSCFZWTmfpYCHEFK6CRdIoJmQaYacNBBJJ4wcqKNhYaKNYBFeCnYKLjdhNK4j5NrKbOHlnxx+Q\nAzP33nOf+77nHCy338MKXlUxPW8cMps9QcBIMMF92HOvYRT7lg4KdzyLrHla4zi+Mas8cuDCB7PP\nU5iCRU6r1HgBkzzQZSn7gWzRTE4LairSD0sw7b0NTZ06lLHB9tp2sL/CqaD3egQVXxCyMz+U1o53\njPeR/5lCA0o0YlsvxmZYllKoRB8PpXSbQvWhz0mO5t/Que7Li0oktyjxyt01IFOPWBFDS0k/e4Hc\nYaFchXGdPnH+N4Vin14Z4epTiz5XR2UPjnVoPRm6r6kGX0LIF6EdBiVC0vSGVsj+SmvaEhTBGZYj\n0Qa0p+ndNKBcKYU0PClliuSdj7DtXDqZb5D5Lrd5hp0UGlZN0BXMvuSawh+O/ecSLgjK75oD6SXD\nzM4YdVeJ4xrN7uMQ232iGyvpeNYNoXttL9K221PiP+If4oN7f8ioQFsAAAAASUVORK5CYII=\n",
 904       "text/latex": [
 905        "$$2397916$$"
 906       ],
 907       "text/plain": [
 908        "2397916"
 909       ]
 910      },
 911      "execution_count": 28,
 912      "metadata": {},
 913      "output_type": "execute_result"
 914     }
 915    ],
 916    "source": [
 917     "%time int(F(23000000000000))  # The clear winner."
 918    ]
 919   },
 920   {
 921    "cell_type": "markdown",
 922    "metadata": {},
 923    "source": [
 924     "Knowing the equation we could write our own function manually, but the speed is no better."
 925    ]
 926   },
 927   {
 928    "cell_type": "code",
 929    "execution_count": 29,
 930    "metadata": {},
 931    "outputs": [],
 932    "source": [
 933     "from math import floor as mfloor, sqrt\n",
 934     "\n",
 935     "def mrank_of(n):\n",
 936     "    return int(mfloor(sqrt(23000000000000 - 1) / 2 - 0.5) + 1)"
 937    ]
 938   },
 939   {
 940    "cell_type": "code",
 941    "execution_count": 30,
 942    "metadata": {
 943     "scrolled": true
 944    },
 945    "outputs": [
 946     {
 947      "name": "stdout",
 948      "output_type": "stream",
 949      "text": [
 950       "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
 951       "Wall time: 12.9 µs\n"
 952      ]
 953     },
 954     {
 955      "data": {
 956       "image/png": "iVBORw0KGgoAAAANSUhEUgAAAEcAAAAPBAMAAABElc8tAAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAIpm7MhCriUTv3c12\nVGZoascqAAAACXBIWXMAAA7EAAAOxAGVKw4bAAABkUlEQVQoFY2QPUscURSGn4l7d4y7q6ONxGqZ\ngEbSCFZWTmfpYCHEFK6CRdIoJmQaYacNBBJJ4wcqKNhYaKNYBFeCnYKLjdhNK4j5NrKbOHlnxx+Q\nAzP33nOf+77nHCy338MKXlUxPW8cMps9QcBIMMF92HOvYRT7lg4KdzyLrHla4zi+Mas8cuDCB7PP\nU5iCRU6r1HgBkzzQZSn7gWzRTE4LairSD0sw7b0NTZ06lLHB9tp2sL/CqaD3egQVXxCyMz+U1o53\njPeR/5lCA0o0YlsvxmZYllKoRB8PpXSbQvWhz0mO5t/Que7Li0oktyjxyt01IFOPWBFDS0k/e4Hc\nYaFchXGdPnH+N4Vin14Z4epTiz5XR2UPjnVoPRm6r6kGX0LIF6EdBiVC0vSGVsj+SmvaEhTBGZYj\n0Qa0p+ndNKBcKYU0PClliuSdj7DtXDqZb5D5Lrd5hp0UGlZN0BXMvuSawh+O/ecSLgjK75oD6SXD\nzM4YdVeJ4xrN7uMQ232iGyvpeNYNoXttL9K221PiP+If4oN7f8ioQFsAAAAASUVORK5CYII=\n",
 957       "text/latex": [
 958        "$$2397916$$"
 959       ],
 960       "text/plain": [
 961        "2397916"
 962       ]
 963      },
 964      "execution_count": 30,
 965      "metadata": {},
 966      "output_type": "execute_result"
 967     }
 968    ],
 969    "source": [
 970     "%time mrank_of(23000000000000)"
 971    ]
 972   },
 973   {
 974    "cell_type": "markdown",
 975    "metadata": {},
 976    "source": [
 977     "### Given $n$ and a rank, compute the offset.\n",
 978     "\n",
 979     "Now that we have a fast way to get the rank, we still need to use it to compute the offset into a pyramid row."
 980    ]
 981   },
 982   {
 983    "cell_type": "code",
 984    "execution_count": 31,
 985    "metadata": {},
 986    "outputs": [],
 987    "source": [
 988     "def offset_of(n, k):\n",
 989     "    return (n - 2 + 4 * k * (k - 1)) % (2 * k)"
 990    ]
 991   },
 992   {
 993    "cell_type": "markdown",
 994    "metadata": {},
 995    "source": [
 996     "(Note the sneaky way the sign changes from $k(k + 1)$ to $k(k - 1)$.  This is because we want to subract the $(k - 1)$th rank's total places (its own and those of lesser rank) from our $n$ of rank $k$.  Substituting $k - 1$ for $k$ in $k(k + 1)$ gives $(k - 1)(k - 1 + 1)$, which of course simplifies to $k(k - 1)$.)"
 997    ]
 998   },
 999   {
1000    "cell_type": "code",
1001    "execution_count": 32,
1002    "metadata": {},
1003    "outputs": [
1004     {
1005      "data": {
1006       "image/png": "iVBORw0KGgoAAAANSUhEUgAAADsAAAAOBAMAAABjvHmeAAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAIpm7MhCriUTv3c12\nVGZoascqAAAACXBIWXMAAA7EAAAOxAGVKw4bAAABIElEQVQYGTWQoU8DMRSHvwuULWNLDgwJ6jIS\nCJlcQoLaOeSKQaAwCDAsg2WCiTMI1AQIRjIBFoHFjSCwNPwDmyMYSBBAdoTjtR2iX76+X/r6WoJy\nNcajfWgg1zlCrbzE3tgi9+0xT+kXdUeFWaOuvLELPY8nw5ipiCqvcOyNSziIHU4TldINgTUYamcM\ntMQO2ObrkvIJXePM7m71BNsN0o2HRH1IfG/NpvmvCRautUpH9AMp1FvWbFzY+UfuQmWa1U05XW9Z\ns23Lsjzo6TG8n7jm1hIoRpJazEHN3EhxJKMNvcEzQegg3Wpmz56pCrQzpiOKocOZvCGsy432Wyo4\nY7Hd3Pd4o/TDTEP1KRh17o1Blo098uUlGaW5HKM6j7G3P7xTb/ft54xWAAAAAElFTkSuQmCC\n",
1007       "text/latex": [
1008        "$$223606$$"
1009       ],
1010       "text/plain": [
1011        "223606"
1012       ]
1013      },
1014      "execution_count": 32,
1015      "metadata": {},
1016      "output_type": "execute_result"
1017     }
1018    ],
1019    "source": [
1020     "offset_of(23000000000000, 2397916)"
1021    ]
1022   },
1023   {
1024    "cell_type": "markdown",
1025    "metadata": {},
1026    "source": [
1027     "So, we can compute the rank, then the offset, then the row value."
1028    ]
1029   },
1030   {
1031    "cell_type": "code",
1032    "execution_count": 33,
1033    "metadata": {},
1034    "outputs": [],
1035    "source": [
1036     "def rank_of(n):\n",
1037     "    return int(mfloor(sqrt(n - 1) / 2 - 0.5) + 1)\n",
1038     "\n",
1039     "\n",
1040     "def offset_of(n, k):\n",
1041     "    return (n - 2 + 4 * k * (k - 1)) % (2 * k)\n",
1042     "\n",
1043     "\n",
1044     "def row_value(k, i):\n",
1045     "    return abs(i - (k - 1)) + k\n",
1046     "\n",
1047     "\n",
1048     "def aoc20173(n):\n",
1049     "    k = rank_of(n)\n",
1050     "    i = offset_of(n, k)\n",
1051     "    return row_value(k, i)"
1052    ]
1053   },
1054   {
1055    "cell_type": "code",
1056    "execution_count": 34,
1057    "metadata": {
1058     "scrolled": true
1059    },
1060    "outputs": [
1061     {
1062      "data": {
1063       "image/png": "iVBORw0KGgoAAAANSUhEUgAAAAkAAAAOBAMAAAAPuiubAAAALVBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADAOrOgAAAADnRSTlMAIpm7MhCriUTv3c12VLge\nopIAAAAJcEhZcwAADsQAAA7EAZUrDhsAAABOSURBVAgdY2BUMnZgYAhjYH/BwJDKwDCTgWEWA0Oe\nA8O+ABAJBOsCgATHcxCTKwFEKoEIHgUQeYmBUYCBRYGBR4BBqrwoi4Fh37t3rxgAK5QOlzv7snYA\nAAAASUVORK5CYII=\n",
1064       "text/latex": [
1065        "$$2$$"
1066       ],
1067       "text/plain": [
1068        "2"
1069       ]
1070      },
1071      "execution_count": 34,
1072      "metadata": {},
1073      "output_type": "execute_result"
1074     }
1075    ],
1076    "source": [
1077     "aoc20173(23)"
1078    ]
1079   },
1080   {
1081    "cell_type": "code",
1082    "execution_count": 35,
1083    "metadata": {
1084     "scrolled": true
1085    },
1086    "outputs": [
1087     {
1088      "data": {
1089       "image/png": "iVBORw0KGgoAAAANSUhEUgAAAB0AAAAPBAMAAADqo9msAAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAVO8Qq5l2zWaJMt0i\nu0SCRuA9AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAArElEQVQIHWNgAAHmyM4FDOzJXIFANqMyAwO7\nAPMeBqb//ycwMJiEfGZgaGJgmM7APiUHpJYNyL/CwCBvwALiQfhfGBjeCyD4zF+B/ASWjtQFEHme\nnwwM6yfwGvD8g/KB8uuBZjPchvAh6oHs+ANw8+QF3BkY5j+A8O8yMPQbqAPlDSB8oHvCGQIYGLZD\n9DNwCzBrMRxl4NBhYGB1+u7BwDwtZQEDT6QrUDkaAADf+TCFzC1FdQAAAABJRU5ErkJggg==\n",
1090       "text/latex": [
1091        "$$105$$"
1092       ],
1093       "text/plain": [
1094        "105"
1095       ]
1096      },
1097      "execution_count": 35,
1098      "metadata": {},
1099      "output_type": "execute_result"
1100     }
1101    ],
1102    "source": [
1103     "aoc20173(23000)"
1104    ]
1105   },
1106   {
1107    "cell_type": "code",
1108    "execution_count": 36,
1109    "metadata": {},
1110    "outputs": [
1111     {
1112      "data": {
1113       "image/png": "iVBORw0KGgoAAAANSUhEUgAAAEgAAAAPBAMAAAC1npSgAAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAMpndu3bvImbNiRBU\nq0Qb3U6NAAAACXBIWXMAAA7EAAAOxAGVKw4bAAABGklEQVQoFYWQsUrDUBRAT6I1pVYJ/YLYURcH\nV9HBzS9wtjgJPnRx00XnDLq4tIhTQOjiIojiLghSKEjRxR9QUajU5715hfc2Qzi83HMgjwvQgNNu\n4y5ani8KkuZaGqA00rAEO3ZI1Vo74obab4DSSFNpwVnPEBt45Bm2ApRGov0TlVCTN2UTXlKP0ojs\njCM5vkG7K5HHOKoaifpHc9KwqmClG8CZKyRa5+BV/nYoltlhCGc6GsHkItzqgQm9oIeaeuqi+Bs2\nyqip9EDMNRLN5LodXZhsJAvhzMNg8NWbyol/mB5pdE9iPJyRcYtYLpETvctHlFExHs7I/JMk49hQ\n12ivOH8K4Axc2D67lwuQbEvUtvYjgDMy//f5A0ICeXTNG40LAAAAAElFTkSuQmCC\n",
1114       "text/latex": [
1115        "$$4572225$$"
1116       ],
1117       "text/plain": [
1118        "4572225"
1119       ]
1120      },
1121      "execution_count": 36,
1122      "metadata": {},
1123      "output_type": "execute_result"
1124     }
1125    ],
1126    "source": [
1127     "aoc20173(23000000000000)"
1128    ]
1129   },
1130   {
1131    "cell_type": "code",
1132    "execution_count": 37,
1133    "metadata": {},
1134    "outputs": [
1135     {
1136      "name": "stdout",
1137      "output_type": "stream",
1138      "text": [
1139       "CPU times: user 0 ns, sys: 0 ns, total: 0 ns\n",
1140       "Wall time: 20 µs\n"
1141      ]
1142     },
1143     {
1144      "data": {
1145       "image/png": "iVBORw0KGgoAAAANSUhEUgAAAIUAAAAPBAMAAAA43xGxAAAAMFBMVEX///8AAAAAAAAAAAAAAAAA\nAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAv3aB7AAAAD3RSTlMAIpm7MhCriUTv3c12\nVGZoascqAAAACXBIWXMAAA7EAAAOxAGVKw4bAAACa0lEQVQoFaXTT0gUYRjH8e/+mZ11d50duhWE\nw9JfvAxJQaeGIDw6eCjMg1uUUUQuInpIci6dXaGCCsvOEe2hfwfTJaKIhLYIOrqeQhLUcl3RdHve\neTfo3h6GnefzPj/e99l3ieQ6PDBHhzAODtvy+C6v3TeGgJH3HpqJO5qZ9k9W6B451+Swh9OYGxiv\naKenGpkgXTEewWvO2vQG0ZJmSLmaedioYzxgd5PDHi7CXWIOHVyG8yzCdawiZokjxFzN8MHVzMur\nNokiCUdz2MM9GPDGbdnbFoxxDOb9WJ7WWnJVapqJ/HA1k5datoS5ojnsYdaXjOMixi/45K3DeCWb\nJ7kdK0pRM2ba1Rxm9Llk1kJuFmXdU3+r803AfdnHzZ+SUe5zSP7OPhs9pFKEWUi7IQdcW9pHi+xj\nQ7PqCWRNsm5sVZmUgzC7UIeuQluBeL1vhpZKyBhlyVBc5ShtgblCekezLsrM80bD57CfLreOfZZ9\nSIajMmpEb0tGKo+JZChWmbEppvm2rflvMQebsByw9Hbs1D9nmcLakB7hrypDsSfv0VWsuc61rGZd\nzDjwWDKq4gO+zHRezbR1O1XC2gFhoxBmKE6oUcjCRK3JqghfiNjyM8s+4IVcE5Z9uRdWTW6B2ofw\n3v7+gTvlkGWc0Zp8S+ebrHrULc7YXTIPFu34qrpj7VhFoqW4zKOoGVpczVGZT8maoMvWHPawZ2Tw\nComCMclHv7dKqmLcgif0eFyip6JZrpWrOeJIVua5MYPmsIfZRkMmOnjAw8zJfTBG33lwZu6C/A9z\n8tBsnlivhsyu4f2yOhc0WRflcP/7+QN1gvGXxRfSRAAAAABJRU5ErkJggg==\n",
1146       "text/latex": [
1147        "$$2690062495969$$"
1148       ],
1149       "text/plain": [
1150        "2690062495969"
1151       ]
1152      },
1153      "execution_count": 37,
1154      "metadata": {},
1155      "output_type": "execute_result"
1156     }
1157    ],
1158    "source": [
1159     "%time aoc20173(23000000000000000000000000)  # Fast for large values."
1160    ]
1161   },
1162   {
1163    "cell_type": "markdown",
1164    "metadata": {},
1165    "source": [
1166     "# A Joy Version\n",
1167     "At this point I feel confident that I can implement a concise version of this code in Joy.  ;-)"
1168    ]
1169   },
1170   {
1171    "cell_type": "code",
1172    "execution_count": 38,
1173    "metadata": {},
1174    "outputs": [],
1175    "source": [
1176     "from notebook_preamble import J, V, define"
1177    ]
1178   },
1179   {
1180    "cell_type": "markdown",
1181    "metadata": {},
1182    "source": [
1183     "### `rank_of`\n",
1184     "\n",
1185     "       n rank_of\n",
1186     "    ---------------\n",
1187     "          k\n",
1188     "\n",
1189     "The translation is straightforward.\n",
1190     "\n",
1191     "    int(floor(sqrt(n - 1) / 2 - 0.5) + 1)\n",
1192     "\n",
1193     "    rank_of == -- sqrt 2 / 0.5 - floor ++"
1194    ]
1195   },
1196   {
1197    "cell_type": "code",
1198    "execution_count": 39,
1199    "metadata": {},
1200    "outputs": [],
1201    "source": [
1202     "define('rank_of == -- sqrt 2 / 0.5 - floor ++')"
1203    ]
1204   },
1205   {
1206    "cell_type": "markdown",
1207    "metadata": {},
1208    "source": [
1209     "### `offset_of`\n",
1210     "\n",
1211     "       n k offset_of\n",
1212     "    -------------------\n",
1213     "             i\n",
1214     "\n",
1215     "    (n - 2 + 4 * k * (k - 1)) % (2 * k)\n",
1216     "\n",
1217     "A little tricky...\n",
1218     "\n",
1219     "    n k dup 2 *\n",
1220     "    n k k 2 *\n",
1221     "    n k k*2 [Q] dip %\n",
1222     "    n k Q k*2 %\n",
1223     "\n",
1224     "    n k dup --\n",
1225     "    n k k --\n",
1226     "    n k k-1 4 * * 2 + -\n",
1227     "    n k*k-1*4     2 + -\n",
1228     "    n k*k-1*4+2       -\n",
1229     "    n-k*k-1*4+2\n",
1230     "\n",
1231     "    n-k*k-1*4+2 k*2 %\n",
1232     "    n-k*k-1*4+2%k*2\n",
1233     "\n",
1234     "Ergo:\n",
1235     "\n",
1236     "    offset_of == dup 2 * [dup -- 4 * * 2 + -] dip %"
1237    ]
1238   },
1239   {
1240    "cell_type": "code",
1241    "execution_count": 40,
1242    "metadata": {},
1243    "outputs": [],
1244    "source": [
1245     "define('offset_of == dup 2 * [dup -- 4 * * 2 + -] dip %')"
1246    ]
1247   },
1248   {
1249    "cell_type": "markdown",
1250    "metadata": {},
1251    "source": [
1252     "### `row_value`\n",
1253     "\n",
1254     "       k i row_value\n",
1255     "    -------------------\n",
1256     "            n\n",
1257     "\n",
1258     "    abs(i - (k - 1)) + k\n",
1259     "\n",
1260     "    k i over -- - abs +\n",
1261     "    k i k    -- - abs +\n",
1262     "    k i k-1     - abs +\n",
1263     "    k i-k-1       abs +\n",
1264     "    k |i-k-1|         +\n",
1265     "    k+|i-k-1|"
1266    ]
1267   },
1268   {
1269    "cell_type": "code",
1270    "execution_count": 41,
1271    "metadata": {},
1272    "outputs": [],
1273    "source": [
1274     "define('row_value == over -- - abs +')"
1275    ]
1276   },
1277   {
1278    "cell_type": "markdown",
1279    "metadata": {},
1280    "source": [
1281     "### `aoc2017.3`\n",
1282     "\n",
1283     "       n aoc2017.3\n",
1284     "    -----------------\n",
1285     "            m\n",
1286     "\n",
1287     "    n dup rank_of\n",
1288     "    n k [offset_of] dupdip\n",
1289     "    n k offset_of k\n",
1290     "    i             k swap row_value\n",
1291     "    k i row_value\n",
1292     "    m"
1293    ]
1294   },
1295   {
1296    "cell_type": "code",
1297    "execution_count": 42,
1298    "metadata": {},
1299    "outputs": [],
1300    "source": [
1301     "define('aoc2017.3 == dup rank_of [offset_of] dupdip swap row_value')"
1302    ]
1303   },
1304   {
1305    "cell_type": "code",
1306    "execution_count": 43,
1307    "metadata": {},
1308    "outputs": [
1309     {
1310      "name": "stdout",
1311      "output_type": "stream",
1312      "text": [
1313       "2\n"
1314      ]
1315     }
1316    ],
1317    "source": [
1318     "J('23 aoc2017.3')"
1319    ]
1320   },
1321   {
1322    "cell_type": "code",
1323    "execution_count": 44,
1324    "metadata": {},
1325    "outputs": [
1326     {
1327      "name": "stdout",
1328      "output_type": "stream",
1329      "text": [
1330       "105\n"
1331      ]
1332     }
1333    ],
1334    "source": [
1335     "J('23000 aoc2017.3')"
1336    ]
1337   },
1338   {
1339    "cell_type": "code",
1340    "execution_count": 45,
1341    "metadata": {},
1342    "outputs": [
1343     {
1344      "name": "stdout",
1345      "output_type": "stream",
1346      "text": [
1347       "                                                    . 23000000000000 aoc2017.3\n",
1348       "                                     23000000000000 . aoc2017.3\n",
1349       "                                     23000000000000 . dup rank_of [offset_of] dupdip swap row_value\n",
1350       "                      23000000000000 23000000000000 . rank_of [offset_of] dupdip swap row_value\n",
1351       "                      23000000000000 23000000000000 . -- sqrt 2 / 0.5 - floor ++ [offset_of] dupdip swap row_value\n",
1352       "                      23000000000000 22999999999999 . sqrt 2 / 0.5 - floor ++ [offset_of] dupdip swap row_value\n",
1353       "                   23000000000000 4795831.523312615 . 2 / 0.5 - floor ++ [offset_of] dupdip swap row_value\n",
1354       "                 23000000000000 4795831.523312615 2 . / 0.5 - floor ++ [offset_of] dupdip swap row_value\n",
1355       "                  23000000000000 2397915.7616563076 . 0.5 - floor ++ [offset_of] dupdip swap row_value\n",
1356       "              23000000000000 2397915.7616563076 0.5 . - floor ++ [offset_of] dupdip swap row_value\n",
1357       "                  23000000000000 2397915.2616563076 . floor ++ [offset_of] dupdip swap row_value\n",
1358       "                             23000000000000 2397915 . ++ [offset_of] dupdip swap row_value\n",
1359       "                             23000000000000 2397916 . [offset_of] dupdip swap row_value\n",
1360       "                 23000000000000 2397916 [offset_of] . dupdip swap row_value\n",
1361       "                             23000000000000 2397916 . offset_of 2397916 swap row_value\n",
1362       "                             23000000000000 2397916 . dup 2 * [dup -- 4 * * 2 + -] dip % 2397916 swap row_value\n",
1363       "                     23000000000000 2397916 2397916 . 2 * [dup -- 4 * * 2 + -] dip % 2397916 swap row_value\n",
1364       "                   23000000000000 2397916 2397916 2 . * [dup -- 4 * * 2 + -] dip % 2397916 swap row_value\n",
1365       "                     23000000000000 2397916 4795832 . [dup -- 4 * * 2 + -] dip % 2397916 swap row_value\n",
1366       "23000000000000 2397916 4795832 [dup -- 4 * * 2 + -] . dip % 2397916 swap row_value\n",
1367       "                             23000000000000 2397916 . dup -- 4 * * 2 + - 4795832 % 2397916 swap row_value\n",
1368       "                     23000000000000 2397916 2397916 . -- 4 * * 2 + - 4795832 % 2397916 swap row_value\n",
1369       "                     23000000000000 2397916 2397915 . 4 * * 2 + - 4795832 % 2397916 swap row_value\n",
1370       "                   23000000000000 2397916 2397915 4 . * * 2 + - 4795832 % 2397916 swap row_value\n",
1371       "                     23000000000000 2397916 9591660 . * 2 + - 4795832 % 2397916 swap row_value\n",
1372       "                      23000000000000 22999994980560 . 2 + - 4795832 % 2397916 swap row_value\n",
1373       "                    23000000000000 22999994980560 2 . + - 4795832 % 2397916 swap row_value\n",
1374       "                      23000000000000 22999994980562 . - 4795832 % 2397916 swap row_value\n",
1375       "                                            5019438 . 4795832 % 2397916 swap row_value\n",
1376       "                                    5019438 4795832 . % 2397916 swap row_value\n",
1377       "                                             223606 . 2397916 swap row_value\n",
1378       "                                     223606 2397916 . swap row_value\n",
1379       "                                     2397916 223606 . row_value\n",
1380       "                                     2397916 223606 . over -- - abs +\n",
1381       "                             2397916 223606 2397916 . -- - abs +\n",
1382       "                             2397916 223606 2397915 . - abs +\n",
1383       "                                   2397916 -2174309 . abs +\n",
1384       "                                    2397916 2174309 . +\n",
1385       "                                            4572225 . \n"
1386      ]
1387     }
1388    ],
1389    "source": [
1390     "V('23000000000000 aoc2017.3')"
1391    ]
1392   },
1393   {
1394    "cell_type": "markdown",
1395    "metadata": {},
1396    "source": [
1397     "      rank_of == -- sqrt 2 / 0.5 - floor ++\n",
1398     "    offset_of == dup 2 * [dup -- 4 * * 2 + -] dip %\n",
1399     "    row_value == over -- - abs +\n",
1400     "\n",
1401     "    aoc2017.3 == dup rank_of [offset_of] dupdip swap row_value"
1402    ]
1403   }
1404  ],
1405  "metadata": {
1406   "kernelspec": {
1407    "display_name": "Python 2",
1408    "language": "python",
1409    "name": "python2"
1410   },
1411   "language_info": {
1412    "codemirror_mode": {
1413     "name": "ipython",
1414     "version": 2
1415    },
1416    "file_extension": ".py",
1417    "mimetype": "text/x-python",
1418    "name": "python",
1419    "nbconvert_exporter": "python",
1420    "pygments_lexer": "ipython2",
1421    "version": "2.7.13"
1422   }
1423  },
1424  "nbformat": 4,
1425  "nbformat_minor": 2
1426 }