By Eric Burden | December 13, 2023
It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Kotlin. I’ll post my solutions and code to GitHub as well. If you haven’t given AoC a try, I encourage you to do so along with me!
Day 13 - Point of Incidence
Find the problem description HERE.
The Input - Mirror, Mirror
Well, the input is interesting today, but only because it’s one of the few times I can recall getting an input with multiple grids separated by a blank line. What’s really interesting is that each row/columns is a list of what essentially amounts to true/false values… or… 1’s and 0’s? Yep, each row/column can be represented as a number where the set bits are ‘#’ characters and the unset bits are ‘.’ characters (or, the other way around, really). At first I just left them as strings, but I found that converting them to numbers actually made debugging easier in this puzzle.
/**
* Transposes a rectangular matrix
*
* This function extends the functionality of a [List<List<T>>] by adding a
* `transpose` function which returns a transposed copy of the original
* list of lists. All the sub-lists must be the same length. For example:
*
* [[1, 2, 3], [[1, 4, 7],
* [4, 5, 6], -> [2, 5, 8],
* [7, 8, 9]] [3, 6, 9]]
*
* @return The transposed list of lists.
*/
fun <T> List<List<T>>.transpose(): List<List<T>> {
if (isEmpty() || this.any { it.size != this[0].size }) {
throw IllegalArgumentException("Inner lists must have the same size")
}
return List(this[0].size) { col ->
List(size) { row ->
this[row][col]
}
}
}
/**
* Converts a String to an Integer by interpreting it as a binary value
*
* This function extends the functionality of [String] by adding a `toBinary`
* function that interprets the characters in the string as 1's and 0's then
* converts it to the [Int] represented by the binary string.
*
* @param one The character to interpret as 1.
* @param zero The character to interpret as 0.
* @return The String as binary and converted to an Int.
*/
fun String.toBinary(one: Char = '#', zero: Char = '.'): Int =
toList().joinToString("") { char ->
when (char) {
one -> "1"
zero -> "0"
else -> {
throw Exception("$char has not be specified as either '1' or '0'!")
}
}
}.toInt(radix = 2)
/**
* The class represents one of the patterns of the landscape with a mirror
*
* @property rows Integer representations of the rows in the pattern.
* @property cols Integer representations of the columns in the pattern.
*/
data class LandscapePattern(val rows: List<Int>, val cols: List<Int>) {
companion object {
/**
* Parses a [LandscapePattern] from a chunk of the input file
*
* @param input A chunk of the input file.
* @return A [LandscapePattern].
*/
fun fromInputChunk(input: List<String>): LandscapePattern {
// Each row and column is represented as an integer where the binary
// of the integer corresponds to the input string (either row-wise
// or column-wise), with '#' -> 1 and '.' -> 0. This honestly
// was as much to make debugging easier as for efficiency.
val rows = input.map { it.toBinary() }
val cols = input.map { it.toList() }.transpose()
.map { it.joinToString("").toBinary() }
return LandscapePattern(rows, cols)
}
}
}
class Day13(input: List<List<String>>) {
// Parse each grid in the input file into a [LandscapePattern]
private val parsed =
input.filter { it.isNotEmpty() }.map(LandscapePattern::fromInputChunk)
}
As a note, sometimes when I write helper functions like the ones above that seem really useful, I’ll try to make them as generic as possible so that they can possibly be re-used in a future day’s puzzle.
Part One - Walk This Way
From steampunk to post-apocalyptic. To think, this all began because we wanted more snow. Remember that? Yep, we’re still on the same fetch-quest. For today’s puzzle, we need to identify which bits of the landscape are being reflected from giant mirrors in a land of ash and rocks so we can find our way through. Let’s do it!
data class LandscapePattern(val rows: List<Int>, val cols: List<Int>) {
companion object {
// fun fromInputChunk(input: List<String>): LandscapePattern { ... }
/**
* Checks for a line of symmetry in a list of lines
*
* Each `line` is a row or column from one of the inputs. This function
* checks `checkIdx` to determine whether it represents the left (or
* top) row (or column) in a line of symmetry, meaning the lines on one
* side of the line are a mirror image of the other side, all the way
* to the edge of the input chunk.
*
* @param lines A list of rows or columns (as integers).
* @param checkIdx The index in the list to check for symmetry.
* @return A flag indicating whether the indicated index sits to
* the left (or top) of a line of symmetry.
*/
private fun hasLineOfSymmetry(
lines: List<Int>,
checkIdx: Int
): Boolean {
require(0 <= checkIdx && checkIdx < lines.size) {
throw Exception("There is no row $checkIdx in ${lines}!")
}
// Last line can't be a line of symmetry
if (checkIdx == lines.size - 1) return false
// If there is a line of symmetry, the given index will be to the
// left of it in the list of lines.
var leftIdx = checkIdx
var rightIdx = checkIdx + 1
// So long as the two lines being checked are the same, we expand
// the mirrored region until one side of it reaches past the
// beginning or end of the list of lines.
while (lines[leftIdx] == lines[rightIdx]) {
leftIdx--; rightIdx++ // Step the indices out by one
if (leftIdx < 0 || rightIdx >= lines.size) return true
}
// If we reach a point where the two lines being checked aren't
// equal, and we're still inside the list of lines, then we know
// this index isn't where the line of symmetry is.
return false
}
}
/**
* Summarize this [LandscapePattern] for my notes
*
* A pattern is summarized by finding the line of symmetry, counting the
* number of rows to the left (or columns above) and returning that number
* (* 100 for rows).
*
* @return The summary value for this [LandscapePattern].
*/
fun summarize(): Int {
// Search for a horizontal line of symmetry, returning the
// number of lines above it * 100 if found.
for (idx in rows.indices) {
val adjacentToMirror = hasLineOfSymmetry(rows, idx)
if (adjacentToMirror) return (idx + 1) * 100
}
// Search for a vertical line of symmetry, returning the number of
// lines to the left of it if found.
for (idx in cols.indices) {
val adjacentToMirror = hasLineOfSymmetry(cols, idx)
if (adjacentToMirror) return idx + 1
}
// Pitch a fit if no mirror is found.
throw Exception("Could not find a mirror for $this!")
}
}
class Day13(input: List<List<String>>) {
// Parse each grid in the input file into a [LandscapePattern]
// private val parsed = ...
// For each [LandscapePattern] find the mirror, calculate the summary
// value, and return the sum.
fun solvePart1(): Int = parsed.sumOf { it.summarize() }
}
The basic strategy here is to pick an index (row or column) and just walk
outwards a pair of values at a time, checking to be sure the values are equal
(aka, “mirrored”). This wasn’t the first strategy I tried. Early on, I was being
too clever and trying to detect mirrors in an O(n) way whereas this approach is
more O(n^2) per LandscapePattern, but the patterns themselves are small enough
that this still runs pretty quickly and, importantly, it actually works!
Part Two - Achilles Smudge
After bashing our face into a mirror, we realize that each and every grid contains exactly one flaw. That’s oddly specific, but we can figure out how to deal with it. As it turns out, this was an especially infuriating twist, not because it was hard to deal with, but when I was inspecting the input grids to figure out why my code wasn’t working initially, I kept finding these “off-by-one” reflections and throwing myself off. Turns out, it was intentional!
enum class MirrorDetectionStrategy { ALL_MIRRORED, ONE_SMUDGE }
data class LandscapePattern(val rows: List<Int>, val cols: List<Int>) {
companion object {
// fun fromInputChunk(input: List<String>): LandscapePattern { ... }
// private fun hasLineOfSymmetry(lines: List<Int>, checkIdx: Int): Boolean { ... }
/**
* Checks for a line of symmetry, accounting for one smudge
*
* The difference between this function and `hasLineOfSymmetry` is that
* this function allows one, and only one, pair of lines to differ by
* one bit.
*
* @param lines A list of rows or columns (as integers).
* @param checkIdx The index in the list to check for symmetry.
* @return A flag indicating whether the indicated index sits to
* the left (or top) of a line of symmetry.
*/
private fun hasLineOfSymmetryWithSmudge(
lines: List<Int>,
checkIdx: Int
): Boolean {
require(0 <= checkIdx && checkIdx < lines.size) {
throw Exception("There is no row $checkIdx in ${lines}!")
}
if (checkIdx == lines.size - 1) return false
var leftIdx = checkIdx
var rightIdx = checkIdx + 1
// Need to keep track of whether we've already cleaned a smudge
var cleanedSmudge = false
// The `bitdiff` result is the number of bits different between the
// two lines being examined. A value of zero would mean the two are
// the same and a value of one is an acceptable smudge.
// As long as the two lines being checked have zero or one smudges...
while (lines[leftIdx] bitdiff lines[rightIdx] <= 1) {
// This pair contains a smudge
if (lines[leftIdx] bitdiff lines[rightIdx] == 1) {
// If we've already cleaned a smudge, there's no line of
// symmetry here.
if (cleanedSmudge) break
// Note the cleaned smudge. This can't happen again.
cleanedSmudge = true
}
leftIdx--; rightIdx++ // Step the indices out by one
// If we reach either end of the lines, return whether or
// not we cleaned one smudge. If no smudges were cleaned,
// there is no line of symmetry.
if (leftIdx < 0 || rightIdx >= lines.size) return cleanedSmudge
}
return false
}
}
/**
* Summarize this [LandscapePattern] for my notes
*
* A pattern is summarized by finding the line of symmetry, counting the
* number of rows to the left (or columns above) and returning that number
* (* 100 for rows).
*
* @param strategy The strategy to use when determining whether or not a
* particular row/column is adjacent to a mirror.
* @return The summary value for this [LandscapePattern].
*/
fun summarize(strategy: MirrorDetectionStrategy): Int {
// Search for a horizontal line of symmetry, returning the
// number of lines above it * 100 if found.
for (idx in rows.indices) {
val adjacentToMirror = when (strategy) {
MirrorDetectionStrategy.ALL_MIRRORED -> hasLineOfSymmetry(
rows,
idx
)
MirrorDetectionStrategy.ONE_SMUDGE -> hasLineOfSymmetryWithSmudge(
rows,
idx
)
}
if (adjacentToMirror) return (idx + 1) * 100
}
// Search for a vertical line of symmetry, returning the number of
// lines to the left of it if found.
for (idx in cols.indices) {
val adjacentToMirror = when (strategy) {
MirrorDetectionStrategy.ALL_MIRRORED -> hasLineOfSymmetry(
cols,
idx
)
MirrorDetectionStrategy.ONE_SMUDGE -> hasLineOfSymmetryWithSmudge(
cols,
idx
)
}
if (adjacentToMirror) return idx + 1
}
// Pitch a fit if no mirror is found.
throw Exception("Could not find a mirror for $this!")
}
}
class Day13(input: List<List<String>>) {
// Parse each grid in the input file into a [LandscapePattern]
// private val parsed = ...
// For each [LandscapePattern] find the mirror, calculate the summary
// value, and return the sum. The ALL_MIRRORED pattern means that
// mirrors are detected by having a perfect reflection across a line of
// symmetry all the way to one edge of the grid.
fun solvePart1(): Int =
parsed.sumOf { it.summarize(MirrorDetectionStrategy.ALL_MIRRORED) }
// For each [LandscapePattern] find the mirror, calculate the summary
// value, and return the sum The ONE_SMUDGE pattern means that
// mirrors are detected by having a reflection _with exactly one incorrect
// value_ (a smudge) across a line of symmetry all the way to one edge of
// the grid.
fun solvePart2(): Int =
parsed.sumOf { it.summarize(MirrorDetectionStrategy.ONE_SMUDGE) }
}
In a rare move, I actually modified my part one code a bit to accommodate the forced application of the strategy pattern to this puzzle. Why? Because it seemed like a fun thing to practice!
Wrap Up
I really enjoyed today’s puzzle, in part because (through my own tunnel vision) it threw me down a bit of a rabbit hole trying to debug an algorithm that I just couldn’t get to work. So, I had a chance to step back and re-consider my approach. It ended up being a good reminder that premature optimization can be a bad thing and end up costing you valuable time. I’m also pretty please with how this code turned out, so there’s that as well.