I liked today's puzzle because I thought it was going to be very grid-focused, and it turned out not to be. Plus even though I'm quite convinced there are ways to simplify my implementation, doing things with a little brute force seems to be just fine for the data set.
We are given a list of "patterns," being grids with ash and rocks (periods and hash signs). Each pattern has either a vertical mirror (lines to the left of it are mirror images to the ones on the right) or a horizontal mirror (lines above it are mirror images to the ones below). The mirror always exists between our rows and columns, never on them, so we don't have to worry about those off-by-one errors. Our task is to do a little math on the numbers of rows to the left or above the mirrors.
Other than calling split-blank-line-groups to break the input into groups of lines that are separated by a blank
line, there's no parsing to do. So let's get right to the basis of everything else - the mirror? function.
(defn mirror? [line idx]
(let [[left right] (split-at idx line)]
(every? identity (map = (reverse left) right))))This function takes a line (initially a string but later a vector of characters) and an index. It then breaks the line
into two segments at the given index, reverses the first (left), and checks that it's equal to the right. We reverse
the left because the two segments aren't identical, but rather are mirror images. So if we compare the first character
of the right segment against the last character of the first, they might be mirrors. The other interesting thing to
see is that (map = list1 list2) does a lot of work. First, it executes the = mapping function against each zipped
up element of the two lists without making us create a merged tuple ourselves. And second, it only maps when there are
elements from both lists to apply; if we ran (map + [1 2 3] [10 11 12 13 14]), it would only combine [1 2 3] and
[10 11 12] giving us the output (11 13 15).
Now let's implement vertical-mirror-indexes, which takes in pattern and returns all indexes of that pattern such that
all rows can mirror along the index. We only expect up to one index will be a vertical mirror, but I have a hunch that
allowing for more than one will benefit us soon. Foreshadowing!
(defn vertical-mirror-indexes [pattern]
(filter (fn [idx] (every? #(mirror? % idx) pattern))
(range 1 (count (first pattern)))))This function creates a range of all possible indexes that could be mirrors, namely starting from 1 and going to right
before the last character. There's no reason to look at index 0, since nothing is to the left. Given this index range,
we filter them to find the one such that every line in the pattern says that index is a mirror.
The horizontal-mirror-indexes is almost the same, except we need to do a little work to read columns instead of rows.
(defn horizontal-mirror-indexes [pattern]
(let [columns (map (fn [idx] (map #(get % idx) pattern)) (range (count (first pattern))))]
(filter (fn [idx] (every? #(mirror? % idx) columns))
(range 1 (count (first columns))))))First, we create the binding columns by mapping each indexed character in the first row of the pattern to that
value mapped on every line; this returns the nth index in each row of the pattern. Once we have that, it's pretty
much a copy-paste job from vertical-mirror-indexes.
Did someone say copy-paste? That's completely unacceptable. Let's bring those two functions together using a common
mirror-indexes function, recognizing that it's actually identical to vertical-mirror-indexes. I could instead just have
horizontal-mirror-indexes call vertical-mirror-indexes, or call mirror-indexes directly instead of
horizontal-mirror-indexes, but I think both aren't as readable as having one extra, somewhat silly function.
(defn mirror-indexes [lines]
(filter (fn [idx] (every? #(mirror? % idx) lines))
(range 1 (count (first lines)))))
(defn vertical-mirror-indexes [pattern]
(mirror-indexes pattern))
(defn horizontal-mirror-indexes [pattern]
(mirror-indexes (map (fn [idx] (map #(get % idx) pattern)) (range (count (first pattern))))))Finally, we need to implement pattern-points. Now since both vertical-mirror-indexes and horizontal-mirror-indexes
return collections of indexes (again, we expect at most 1 value), we need to make this a tiny bit more complex than if
the values were scalars.
(defn points-for [v-indexes h-indexes]
(apply + (concat v-indexes (map #(* 100 %) h-indexes))))
(defn pattern-points [pattern]
(points-for (vertical-mirror-indexes pattern) (horizontal-mirror-indexes pattern)))We actually make two small functions, because in part 2 we'll reuse one of them. points-for takes in the sequence
of vertical and horizontal indexes. After multiplying each horizontal index by 100, it concatenates them with the
vertical indexes, and adds them together. Then pattern-points just calls points-for with the return values from
vertical-mirror-indexes and horizontal-mirror-indexes.
Now we can knock out part1 with our friendly neighborhood transduce function.
(defn part1 [input]
(transduce (map pattern-points) + (split-blank-line-groups input)))There's nothing fancy here - input the collection of patterns, then map each to its points, and add the points together.
In part 2, we need to identify for each pattern which point should switch from either a period to a hash or vice versa,
find the new mirror (ignoring the old one if it still applies), and compute the new pattern points. Now I'm sure there
is a super clever way to do this, but the dataset is reasonable, so I went with the simpler, perhaps dumber solution.
To that end, let's see the all-smudges function.
(defn all-smudges [pattern]
(for [x (range (count pattern))
y (range (count (first pattern)))]
(update-in pattern [x y] {\. \#, \# \.})))Using list comprehension again, we pair every line number (x) with its character number (y), and then update that
one value in the pattern, flipping values between periods and hash signs. Now how does update-in work in this
context? Well there are two ways it won't work. First, if the pattern is a sequence of lines, it won't do anything
because vectors are indexed but sequences aren't. Second, even if the pattern were a vector, we can's update or
assoc a String (even though I think it would be a fine language extension), so we need to instead deal with more
indexable vectors. We'll see in a moment that all-smudges will be called with a vector of character vectors, instead
of a sequence of strings. Because Clojure is awesome with its collection functions, everything else already written
will work just fine.
Armed with all-smudges, let's implement smudgy-pattern-points.
(defn smudgy-pattern-points [pattern]
(let [h (set (horizontal-mirror-indexes pattern))
v (set (vertical-mirror-indexes pattern))]
(->> (all-smudges (mapv vec pattern))
(keep (fn [smudge] (let [h' (-> (horizontal-mirror-indexes smudge) set (set/difference h))
v' (-> (vertical-mirror-indexes smudge) set (set/difference v))]
(when (or (seq h') (seq v'))
(points-for v' h')))))
first)))First, we record the horizontal and vertical mirror indexes from the pattern as we read it; these are the values that
should not be correct after we update the correct character. Then we call (all-smudges (mapv vec pattern)) to get
our list of all possible permutations of the pattern; vec turns each line of the pattern into a character vector,
and mapv maps vec onto each line, creating a vector instead of a sequence. Then we call the keep function on each
smudged pattern. We calculate its horizontal and vertical mirror images, but then remove all values from the original
mirror indexes to determine what's new in this smudge. If we still have any new mirror indexes, then we calculate the
point values using the silly points-for function we created earlier. And once we've found the first smudge that
generates a point total, we can return it.
And we can implement part2 now. Though I could combine this with part1 because only the transformation function
changes from pattern-points to smudgy-pattern-points, I'm fine with it as it is.
(defn part2 [input]
(transduce (map smudgy-pattern-points) + (split-blank-line-groups input)))