This problem reminds me of day 11, where we're given a set of points within a space, and we perform a generational calculation on it some number of times. As I've done a few times, I'm going to cheat a little bit by having seen what part 2 looks like, but honestly the level of effort to go from part 1 to part 2 was very small this time, so I feel comfortable showing them both at once.
We are given as input a 2-dimensional grid of points, where the ones marked with # signs are considered
"active." For every point in infinite directions, we define that point to be active if it was active in
the last generation and it has 2-3 active neighbors, or if it was inactive and has exactly 3 active
neighbors. In part 1, an "active neighbor" looks at the 26 points up to one distance away in the
3-dimensional [x y z] space. In part 2, an "active neighbor" looks at the 80 points up to one distance
away in the 4-dimensional [x y z w] space. Everything else is the same, so we know how parts 1 and 2
will differ!
As always, let's think about the shape of the data we want, so we can decide how to parse the input. One
option is to think of nested vectors, so a vector of vectors of vectors for part 1, and the very exciting
vector of vectors of vectors of vectors for part 2. My brain doesn't like that sort of thinking, so I went
another way. The neighbor calculation is going to look only at the number of active neighbors, so I'll
parse the input into a set of [x y z w] points, and work with a simple set. Since the input data is
defined to be two-dimensional, my z and w coordinates all start at zero.
(defn parse-input [input]
(->> (str/split-lines input)
(map-indexed (fn [y row] (map-indexed (fn [x c] [[x y 0 0] c])
row)))
(apply concat)
(keep (fn [[coords v]] (when (= v \#) coords)))
(into #{})))Quick note: I recognized something that I did not leverage in my solution. Because we started from
active nodes all in a 2-dimensional space where z=0, it stands to reason that there is going to be
symmetry. Whatever exists at z=-1 should also exist at z=1. I suppose I could leverage this by
only calculating positive z values and then doubling the results for the negative zs, but I didn't
do that. The same is probably true for the w axis. Meh; the performance was fine without it.
The most important part of this problem is calculating all of the neighbors of a given point. Rather
than use 3D points for part one and 4D points for part 2, after reading the part2 instructions, I
treated all points as 4D. My neighbors-of function looks at all points whose x, y, and z values
are offset by a value in [-1 0 1]; the w axis will also be off by one of those values if we look in
4D, but will always have an offset of 0 if we're only in 3D. As a result, I made two helper defs
to show how we think about the problem set.
(defn neighbors-of [four-d? [x y z w]]
(for [new-w (if four-d? [-1 0 1] [0])
new-x [-1 0 1]
new-y [-1 0 1]
new-z [-1 0 1]
:when (some #(not= 0 %) [new-x new-y new-z new-w])]
[(+ x new-x) (+ y new-y) (+ z new-z) (+ w new-w)]))
(def neighbors-3d (partial neighbors-of false))
(def neighbors-4d (partial neighbors-of true))Next, I defined bounding-cube to identify the range of x, y, z, and w coordinates that we
need to look at, given the previous generation. Because a point only considers the number of active
neighbors, we can find the min and max values in each dimension, and look at the points one below
the min and one above the max. This function returns a four-element vector of tuple vectors, representing
the min and max values we need to scan in the x, y, z, and w dimensions.
(defn bounding-cube [active-points]
(mapv (fn [offset]
(let [values (map #(get % offset) active-points)]
[(dec (apply min values)) (inc (apply max values))]))
[0 1 2 3]))With these ranges ready, let's identify all of the points in the bounding cube that we'll need to
inspect on each generation. This is simply the Cartesian product of all points within the above
ranges. Now the ranges out of bounding-cube are inclusive, but the range function is open on
the start and closed on the end. Rather than make a top-level function, I use the seldom-used
letfn function, to define a locally scoped function inclusive-range, which returns a range
that's inclusive of both the start and end values.
(defn points-in-cube [[cube-x cube-y cube-z cube-w]]
(letfn [(inclusive-range [[low high]] (range low (inc high)))]
(for [x (inclusive-range cube-x)
y (inclusive-range cube-y)
z (inclusive-range cube-z)
w (inclusive-range cube-w)]
[x y z w]))) Let's keep stepping back. We can return all neighbors of a point in 3 or 4 dimensions, and we
can take a generation (set of active points) and return the points in the cube that we need to
inspect in the next generation. We want to build a function called next-point, which calculates
whether a point will be active or inactive in the next generation. For this, we need to calculate
the number of active neighbors, where we find all neighbors of that point and count the number
that are currently active. Then we use the logic of looking for 2 or 3 neighbors based on the
current state.
(defn num-active-neighbors [active-points neighbor-fn point]
(->> (neighbor-fn point)
(filter #(active-points %))
count))
(defn next-point [active-points neighbor-fn point]
(let [actives (num-active-neighbors active-points neighbor-fn point)]
(if (active-points point)
(contains? #{2 3} actives)
(= 3 actives))))Almost done. next-board takes in a board and returns the next set of active points, and this
is now just a coordinator of other functions. Starting from the current board, we identify the
bounding cube, translate that into all of the points within the cube, keep only the points that
are active in the next generation, and wrap those points up into a new set.
(defn next-board [active-points neighbor-fn]
(->> active-points
bounding-cube
points-in-cube
(keep #(when (next-point active-points neighbor-fn %) %))
set))Finally, we have our solve function and the tiny part1 and part2 functions. In solve,
we set up a sequence of all generations of boards, using (iterate next-board). Then we grab
the 6th generation and count up the number of active points.
(defn solve [input neighbor-fn]
(let [active-seq (->> input
parse-input
(iterate #(next-board % neighbor-fn)))]
(count (nth active-seq 6))))
(defn part1 [input] (solve input neighbors-3d))
(defn part2 [input] (solve input neighbors-4d))