Link to the code: https://github.com/dfuenzalida/adventofcode/blob/master/advent2017/clojure/src/advent/day03.clj
The problem statement is the following:
You come across an experimental new kind of memory stored on an infinite two-dimensional grid.
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:
17 16 15 14 13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23---> ...
Part 1 of the problem can be summed as:
- You will be given a number as input. You need to know the location of the given number in the grid above.
- Once you determine the location of the number, you compute the Manhattan distance to the "origin" of the plane, that is, the absolute number of the X coordinate + the absolute number of the Y coordinate.
The part that took me the most was to figure that the sequence of positions for the numbers for an arbitrary number.
If you start from the 1 in the center, let's tabulate how to get from the center to the other numbers, moving along the spiral in horizonal or vertical changes:
-------+------------------------------
Number | Path from center
-------+------------------------------
2 right
3 right, up
4 right, up, left
5 right, up, left, left
6 right, up, left, left, down
7 right, up, left, left, down, down
...
To produce this sequence, we use the function path that takes the number and produces a sequence of moves (as Clojure keywords):
$ lein repl
...
advent.core=> (require '[advent.day03])
nil
advent.core=> (in-ns 'advent.day03)
#object[clojure.lang.Namespace 0x1a5fd821 "advent.day03"]
advent.day03=> (path 2)
(:right)
advent.day03=> (path 3)
(:right :up)
advent.day03=> (path 4)
(:right :up :left)
advent.day03=> (path 7)
(:right :up :left :left :down :down)Internally, path uses another function, moves that computes sequences of going left, up, down and right; but we generate a long path and only take N-1 steps out of the sequence (eg. (path 7) produces a list of 6 movements).
path uses a style that I like where I create a "pipeline" of functions that take a value or result, transform it in a certain way and pass it for the next step of the pipeline. A commented version would be like this:
(defn path [n]
(->> (range) ;; All integers starting from 0
(drop 1) ;; Drop the first so, it's integers starting on 1
(map moves) ;; Sequences of movements :right, :up, and so on
(apply concat) ;; Concatenate the sequences into a long list
(take (dec n)))) ;; Take (N-1) movements (number 1 is the origin)moves was the hardest part for me to figure, but you can spot a pattern by seeing where to put the numbers: one right, one up, two lefts, two downs, three rights, three ups and so on, layering numbers in the spiral.
The next step is using the movements to produce coordinates. I use a map/dictionary called shifts that translates a direction into a pair of displacements on the X and Y axis of the cartesian plane (e.g. :left maps to [-1 0]).
Once we have a trail of movements, Clojure has this convenience where you can apply a hashmap as a function, so we can compute the displacements for any arbitrary number:
advent.day03=> (path 7)
(:right :up :left :left :down :down)
advent.day03=> (map shifts (path 7))
([1 0] [0 1] [-1 0] [-1 0] [0 -1] [0 -1])Finally, we compute the distance on each axis by taking the first or second component of each pair and summing them all:
advent.day03=> (map first (map shifts (path 7)))
(1 0 -1 -1 0 0)
advent.day03=> (map second (map shifts (path 7)))
(0 1 0 0 -1 -1)The function distance sums the numbers for each axis, takes the absolute value and sums the X and Y distances, computing the Manhattan distance from the number to the center:
advent.day03=> (distance 7)
2
;; You are given this in the problem statement:
;; "Data from square 1024 must be carried 31 steps"
advent.day03=> (distance 1024)
31Let's review the problem statement:
As a stress test on the system, the programs here clear the grid and then store the value 1 in square 1. Then, in the same allocation order as shown above, they store the sum of the values in all adjacent squares, including diagonals.
So, the first few squares' values are chosen as follows:
- Square 1 starts with the value 1.
- Square 2 has only one adjacent filled square (with value 1), so it also stores 1.
- Square 3 has both of the above squares as neighbors and stores the sum of their values, 2.
- Square 4 has all three of the aforementioned squares as neighbors and stores the sum of their values, 4.
- Square 5 only has the first and fourth squares as neighbors, so it gets the value 5.
Once a square is written, its value does not change. Therefore, the first few squares would receive the following values:
147 142 133 122 59
304 5 4 2 57
330 10 1 1 54
351 11 23 25 26
362 747 806---> ...
What is the first value written that is larger than your puzzle input? (some 6-digit number)
The function all-moves is the same as path without trimming the collection, it's an infinite sequence with all of the moves, because I didn't know in advance how fast the sequence will grow.
coords-plus takes two pairs of coordinates and sums the components on each axis, returning another pair. My solution actually takes a coordinate and sums some displacement around it, in order to compute the coordinates of the vecinity of a given point.
compute-grid takes a current grid, a pair of coordinates and computes the value that should go in the coordinate based on the values currently present in the grid. The grid itself is a hashmap from coordinates to values.
(defn compute-grid [grid [x y]]
(reduce +
(for [i [-1 0 1]
j [-1 0 1]
:when (and (not= 0 i j)
(some? (grid [(+ x i) (+ y j)])))]
(grid [(+ x i) (+ y j)]))))To compute the values, I use a for expression and two indexes: i and j that go from -1 to 1 to look up the neighbour positions for a given coordinate.
Note that you are not interested in adding (0, 0) to the coordinates to look up because you'll be looking the value of the same coordinate you want to compute. You also want the locations of the grid that already have some value, so we use some? to validate (skip the nil values). I could also have used a :let element on the for to give names to (+ x i) and (+ y j), but forgot to do.
Once you have all of the values, you sum all up and you can compute the value of any given location if you have filled the spiral in the right order, which is what fill-grid does:
(defn fill-grid [grid [x y] moves-seq limit]
(let [curr (compute-grid grid [x y])]
(if (>= curr limit)
curr
(let [new-grid (assoc grid [x y] curr)
curr-move (first moves-seq)
new-coord (coords-plus [x y] (shifts curr-move))]
(fill-grid new-grid new-coord (rest moves-seq) limit)))))We start with an grid that only contains the number 1 at the center ([0 0]) and build, the rest of the elements starting with coordinate [1 0].
On each step, we check if the currently computed value exceeds a limit that is our problem input (the 6-digit number), if so, we return such value.
Otherwise, we compute a new version of the grid by associating in the grid at the [x y] position the currently computed value, pick a new direction by obtianing the first element of the moves sequence and compute the new coordinate that needs to be computed in the next cycle.
There's a bug here because the function simply calls itself recursively, so in the last line, instead of
(fill-grid new-grid new-coord (rest moves-seq) limit)... it should be:
(recur new-grid new-coord (rest moves-seq) limit)... so we're not at risk of exhausting the call stack for very large numbers.
Now we can try it:
If we were interested to know what's the first value greater than 80 in the new spiral:
advent.day03=> (fill-grid {[0 0] 1} [1 0] (drop 1 all-moves) 80)
122Looking at the spiral again:
147 142 133 122 59
304 5 4 2 57
330 10 1 1 54
351 11 23 25 26
362 747 806---> ...
That's right, 122 is the next value after 59, which is greater or equal than 80.