7 You come across an experimental new kind of memory stored on an infinite
10 Each square on the grid is allocated in a spiral pattern starting at a
11 location marked 1 and then counting up while spiraling outward. For
12 example, the first few squares are allocated like this:
22 While this is very space-efficient (no squares are skipped), requested
23 data must be carried back to square 1 (the location of the only access
24 port for this memory system) by programs that can only move up, down,
25 left, or right. They always take the shortest path: the Manhattan
26 Distance between the location of the data and square 1.
30 - Data from square 1 is carried 0 steps, since it's at the access port.
31 - Data from square 12 is carried 3 steps, such as: down, left, left.
32 - Data from square 23 is carried only 2 steps: up twice.
33 - Data from square 1024 must be carried 31 steps.
35 How many steps are required to carry the data from the square identified
36 in your puzzle input all the way to the access port?
41 I freely admit that I worked out the program I wanted to write using
42 graph paper and some Python doodles. There's no point in trying to write
43 a Joy program until I'm sure I understand the problem well enough.
45 The first thing I did was to write a column of numbers from 1 to n (32
46 as it happens) and next to them the desired output number, to look for
84 There are four groups repeating for a given "rank", then the pattern
85 enlarges and four groups repeat again, etc.
95 Four of this pyramid interlock to tile the plane extending from the
100 2 3 | 4 5 | 6 7 | 8 9
101 10 11 12 13|14 15 16 17|18 19 20 21|22 23 24 25
105 We can figure out the pattern for a row of the pyramid at a given "rank"
108 :math:`2k - 1, 2k - 2, ..., k, k + 1, k + 2, ..., 2k`
112 :math:`k + (k - 1), k + (k - 2), ..., k, k + 1, k + 2, ..., k + k`
114 This shows that the series consists at each place of :math:`k` plus some
115 number that begins at :math:`k - 1`, decreases to zero, then increases
116 to :math:`k`. Each row has :math:`2k` members.
118 Let's figure out how, given an index into a row, we can calculate the
119 value there. The index will be from 0 to :math:`k - 1`.
121 Let's look at an example, with :math:`k = 4`:
132 Subtract :math:`k` from the index and take the absolute value:
136 for n in range(2 * k):
152 Not quite. Subtract :math:`k - 1` from the index and take the absolute
157 for n in range(2 * k):
158 print(abs(n - (k - 1)), end=' ')
165 Great, now add :math:`k`...
169 for n in range(2 * k):
170 print(abs(n - (k - 1)) + k, end=' ')
177 So to write a function that can give us the value of a row at a given
183 i %= (2 * k) # wrap the index at the row boundary.
184 return abs(i - (k - 1)) + k
189 for i in range(2 * k):
190 print(row_value(k, i), end=' ')
197 (I'm leaving out details of how I figured this all out and just giving
198 the relevent bits. It took a little while to zero in of the aspects of
199 the pattern that were important for the task.)
201 Finding the rank and offset of a number.
202 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
204 Now that we can compute the desired output value for a given rank and
205 the offset (index) into that rank, we need to determine how to find the
206 rank and offset of a number.
208 The rank is easy to find by iteratively stripping off the amount already
209 covered by previous ranks until you find the one that brackets the
210 target number. Because each row is :math:`2k` places and there are
211 :math:`4` per rank each rank contains :math:`8k` places. Counting the
212 initial square we have:
214 :math:`corner_k = 1 + \sum_{n=1}^k 8n`
216 I'm not mathematically sophisticated enough to turn this directly into a
217 formula (but Sympy is, see below.) I'm going to write a simple Python
218 function to iterate and search:
222 def rank_and_offset(n):
223 assert n >= 2 # Guard the domain.
224 n -= 2 # Subtract two,
225 # one for the initial square,
226 # and one because we are counting from 1 instead of 0.
229 m = 8 * k # The number of places total in this rank, 4(2k).
231 return k, n % (2 * k)
232 n -= m # Remove this rank's worth.
237 for n in range(2, 51):
238 print(n, rank_and_offset(n))
296 for n in range(2, 51):
297 k, i = rank_and_offset(n)
298 print(n, row_value(k, i))
354 Putting it all together
355 ~~~~~~~~~~~~~~~~~~~~~~~
360 return abs(i - (k - 1)) + k
363 def rank_and_offset(n):
364 n -= 2 # Subtract two,
365 # one for the initial square,
366 # and one because we are counting from 1 instead of 0.
369 m = 8 * k # The number of places total in this rank, 4(2k).
371 return k, n % (2 * k)
372 n -= m # Remove this rank's worth.
379 k, i = rank_and_offset(n)
380 return row_value(k, i)
410 aoc20173(23000000000000)
424 Find the rank for large numbers
425 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
427 Using e.g. Sympy we can find the rank directly by solving for the roots
428 of an equation. For large numbers this will (eventually) be faster than
429 iterating as ``rank_and_offset()`` does.
433 from sympy import floor, lambdify, solve, symbols
434 from sympy import init_printing
443 :math:`1 + 2 + 3 + ... + N = \frac{N(N + 1)}{2}`
447 :math:`\sum_{n=1}^k 8n = 8(\sum_{n=1}^k n) = 8\frac{k(k + 1)}{2}`
453 E = 2 + 8 * k * (k + 1) / 2 # For the reason for adding 2 see above.
462 \displaystyle 4 k \left(k + 1\right) + 2
466 We can write a function to solve for :math:`k` given some :math:`n`...
471 return floor(max(solve(E - n, k))) + 1
473 First ``solve()`` for :math:`E - n = 0` which has two solutions (because
474 the equation is quadratic so it has two roots) and since we only care
475 about the larger one we use ``max()`` to select it. It will generally
476 not be a nice integer (unless :math:`n` is the number of an end-corner
477 of a rank) so we take the ``floor()`` and add 1 to get the integer rank
478 of :math:`n`. (Taking the ``ceiling()`` gives off-by-one errors on the
479 rank boundaries. I don't know why. I'm basically like a monkey doing
482 It gives correct answers:
486 for n in (9, 10, 25, 26, 49, 50):
500 And it runs much faster (at least for large numbers):
504 %time rank_of(23000000000000) # Compare runtime with rank_and_offset()!
509 CPU times: user 27.8 ms, sys: 5 µs, total: 27.8 ms
517 \displaystyle 2397916
523 %time rank_and_offset(23000000000000)
528 CPU times: user 216 ms, sys: 89 µs, total: 216 ms
536 \displaystyle \left( 2397916, \ 223606\right)
540 After finding the rank you would still have to find the actual value of
541 the rank's first corner and subtract it (plus 2) from the number and
542 compute the offset as above and then the final output, but this overhead
543 is partially shared by the other method, and overshadowed by the time it
544 (the other iterative method) would take for really big inputs.
546 The fun thing to do here would be to graph the actual runtime of both
547 methods against each other to find the trade-off point.
549 It took me a second to realize I could do this...
550 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
552 Sympy is a *symbolic* math library, and it supports symbolic
553 manipulation of equations. I can put in :math:`y` (instead of a value)
554 and ask it to solve for :math:`k`.
562 g, f = solve(E - y, k)
564 The equation is quadratic so there are two roots, we are interested in
576 \displaystyle - \frac{\sqrt{y - 1}}{2} - \frac{1}{2}
589 \displaystyle \frac{\sqrt{y - 1}}{2} - \frac{1}{2}
593 Now we can take the ``floor()``, add 1, and ``lambdify()`` the equation
594 to get a Python function that calculates the rank directly.
605 \displaystyle \left\lfloor{\frac{\sqrt{y - 1}}{2} - \frac{1}{2}}\right\rfloor + 1
611 F = lambdify(y, floor(f) + 1)
615 for n in (9, 10, 25, 26, 49, 50):
633 %time int(F(23000000000000)) # The clear winner.
638 CPU times: user 60 µs, sys: 4 µs, total: 64 µs
646 \displaystyle 2397916
650 Knowing the equation we could write our own function manually, but the
655 from math import floor as mfloor, sqrt
658 return int(mfloor(sqrt(n - 1) / 2 - 0.5) + 1)
662 %time mrank_of(23000000000000)
667 CPU times: user 7 µs, sys: 1 µs, total: 8 µs
675 \displaystyle 2397916
679 Given :math:`n` and a rank, compute the offset.
680 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
682 Now that we have a fast way to get the rank, we still need to use it to
683 compute the offset into a pyramid row.
688 return (n - 2 + 4 * k * (k - 1)) % (2 * k)
690 (Note the sneaky way the sign changes from :math:`k(k + 1)` to
691 :math:`k(k - 1)`. This is because we want to subract the
692 :math:`(k - 1)`\ th rank's total places (its own and those of lesser
693 rank) from our :math:`n` of rank :math:`k`. Substituting :math:`k - 1`
694 for :math:`k` in :math:`k(k + 1)` gives :math:`(k - 1)(k - 1 + 1)`,
695 which of course simplifies to :math:`k(k - 1)`.)
699 offset_of(23000000000000, 2397916)
710 So, we can compute the rank, then the offset, then the row value.
715 return int(mfloor(sqrt(n - 1) / 2 - 0.5) + 1)
719 return (n - 2 + 4 * k * (k - 1)) % (2 * k)
723 return abs(i - (k - 1)) + k
729 return row_value(k, i)
759 aoc20173(23000000000000)
766 \displaystyle 4572225
772 %time aoc20173(23000000000000000000000000) # Fast for large values.
777 CPU times: user 22 µs, sys: 2 µs, total: 24 µs
785 \displaystyle 2690062495969
792 At this point I feel confident that I can implement a concise version of
793 this code in Joy. ;-)
797 from notebook_preamble import J, V, define
808 The translation is straightforward.
812 int(floor(sqrt(n - 1) / 2 - 0.5) + 1)
814 rank_of == -- sqrt 2 / 0.5 - floor ++
818 define('rank_of -- sqrt 2 / 0.5 - floor ++')
829 (n - 2 + 4 * k * (k - 1)) % (2 * k)
854 offset_of == dup 2 * [dup -- 4 * * 2 + -] dip %
858 define('offset_of dup 2 * [dup -- 4 * * 2 + -] dip %')
880 define('row_value over -- - abs +')
892 n k [offset_of] dupdip
900 define('aoc2017.3 dup rank_of [offset_of] dupdip swap row_value')
924 V('23000000000000 aoc2017.3')
929 • 23000000000000 aoc2017.3
930 23000000000000 • aoc2017.3
931 23000000000000 • dup rank_of [offset_of] dupdip swap row_value
932 23000000000000 23000000000000 • rank_of [offset_of] dupdip swap row_value
933 23000000000000 23000000000000 • -- sqrt 2 / 0.5 - floor ++ [offset_of] dupdip swap row_value
934 23000000000000 22999999999999 • sqrt 2 / 0.5 - floor ++ [offset_of] dupdip swap row_value
935 23000000000000 4795831.523312615 • 2 / 0.5 - floor ++ [offset_of] dupdip swap row_value
936 23000000000000 4795831.523312615 2 • / 0.5 - floor ++ [offset_of] dupdip swap row_value
937 23000000000000 2397915.7616563076 • 0.5 - floor ++ [offset_of] dupdip swap row_value
938 23000000000000 2397915.7616563076 0.5 • - floor ++ [offset_of] dupdip swap row_value
939 23000000000000 2397915.2616563076 • floor ++ [offset_of] dupdip swap row_value
940 23000000000000 2397915 • ++ [offset_of] dupdip swap row_value
941 23000000000000 2397916 • [offset_of] dupdip swap row_value
942 23000000000000 2397916 [offset_of] • dupdip swap row_value
943 23000000000000 2397916 • offset_of 2397916 swap row_value
944 23000000000000 2397916 • dup 2 * [dup -- 4 * * 2 + -] dip % 2397916 swap row_value
945 23000000000000 2397916 2397916 • 2 * [dup -- 4 * * 2 + -] dip % 2397916 swap row_value
946 23000000000000 2397916 2397916 2 • * [dup -- 4 * * 2 + -] dip % 2397916 swap row_value
947 23000000000000 2397916 4795832 • [dup -- 4 * * 2 + -] dip % 2397916 swap row_value
948 23000000000000 2397916 4795832 [dup -- 4 * * 2 + -] • dip % 2397916 swap row_value
949 23000000000000 2397916 • dup -- 4 * * 2 + - 4795832 % 2397916 swap row_value
950 23000000000000 2397916 2397916 • -- 4 * * 2 + - 4795832 % 2397916 swap row_value
951 23000000000000 2397916 2397915 • 4 * * 2 + - 4795832 % 2397916 swap row_value
952 23000000000000 2397916 2397915 4 • * * 2 + - 4795832 % 2397916 swap row_value
953 23000000000000 2397916 9591660 • * 2 + - 4795832 % 2397916 swap row_value
954 23000000000000 22999994980560 • 2 + - 4795832 % 2397916 swap row_value
955 23000000000000 22999994980560 2 • + - 4795832 % 2397916 swap row_value
956 23000000000000 22999994980562 • - 4795832 % 2397916 swap row_value
957 5019438 • 4795832 % 2397916 swap row_value
958 5019438 4795832 • % 2397916 swap row_value
959 223606 • 2397916 swap row_value
960 223606 2397916 • swap row_value
961 2397916 223606 • row_value
962 2397916 223606 • over -- - abs +
963 2397916 223606 2397916 • -- - abs +
964 2397916 223606 2397915 • - abs +
965 2397916 -2174309 • abs +
972 rank_of == -- sqrt 2 / 0.5 - floor ++
973 offset_of == dup 2 * [dup -- 4 * * 2 + -] dip %
974 row_value == over -- - abs +
976 aoc2017.3 == dup rank_of [offset_of] dupdip swap row_value