By Eric Burden | December 3, 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 3 - Gear Ratios
Find the problem description HERE.
The Input - All The Horsepower
And, it looks like we’ve gone right back to “parsing is the puzzle” for today’s Advent of Code. Well, more or less. I suspect I could have shifted some of the workload out of the parsing phase, but I’m kind of a fan of trying to model the inputs in such a way as to make the operations more tractable. So, here’s a bunch of input parsing!
import kotlin.collections.mutableMapOf
// There are two possible items on the schematic, either a number that
// may span multiple grid spaces, or a non-numeric character called a
// 'symbol'. Each number needs to be uniquely identified, so we can have
// numbers with duplicate values in the schematic representation below.
sealed class SchematicItem {
data class Number(val id: Int, val number: Int) : SchematicItem()
data class Symbol(val char: Char) : SchematicItem()
}
// Convenience!
typealias Coordinate = Pair<Int, Int>
/**
* This class represents the engine schematic
*
* @property map A mapping of coordinates to schematic items
* @property numbers A list allowing for easy iteration over numeric schematic items
* @property symbols A list allowing for easy iteration over symbol schematic items
*/
data class EngineSchematic
private constructor(
val map: MutableMap<Coordinate, SchematicItem>,
val numbers: List<Pair<SchematicItem.Number, List<Coordinate>>>,
val symbols: List<Pair<SchematicItem.Symbol, Coordinate>>
) {
companion object {
/**
* This factory function serves as the constructor
*
* Parses an [EngineSchematic] from the input string
*
* @param input The input string
* @return An [EngineSchematic] represented by the input string
*/
fun fromString(input: String): EngineSchematic {
val map = mutableMapOf<Coordinate, SchematicItem>()
val numbers = mutableListOf<Pair<SchematicItem.Number, List<Coordinate>>>()
val symbols = mutableListOf<Pair<SchematicItem.Symbol, Coordinate>>()
// Iterate over the lines with support for skipping forward when
// a multi-digit number is encountered.
for ((row, line) in input.trimEnd().split("\n").withIndex()) {
var col = 0
while (col < line.length) {
when (line[col]) {
'.' -> col += 1 // Skip periods
in '0'..'9' -> {
// If the current character is a numeric digit, parse the full
// number, add it to the [map], and skip ahead to the end of the
// number string
var buffer = StringBuilder()
val first_col = col
val id = (row * line.length) + col // The ID for this number
while (col < line.length && line[col].isDigit()) {
buffer.append(line[col])
col += 1
}
// No need to check the string, we guaranteed it only contains digits
val partNumber = SchematicItem.Number(id, buffer.toString().toInt())
// We'll also keep a list of numbers and the coordinates
// associated with all the digits of that number.
var numberCoords = mutableListOf<Coordinate>()
for (digit_col in first_col until col) {
val coordinate = Coordinate(row, digit_col)
map.put(coordinate, partNumber)
numberCoords.add(coordinate)
}
numbers.add(partNumber to numberCoords)
}
else -> {
// Otherwise, we're dealing with a symbol. A symbol gets added to
// the map and to the list of symbols and their coordinates.
val symbol = SchematicItem.Symbol(line[col])
val coordinate = Coordinate(row, col)
map.put(coordinate, symbol)
symbols.add(symbol to coordinate)
col += 1
}
}
}
}
return EngineSchematic(map, numbers, symbols)
}
}
}
class Day03(input: String) {
// The real work is done here
private val schematic = EngineSchematic.fromString(input)
}
That’s kind of a lot of parsing for Day 3, but the gist of it is that we end up with a data structure that maps all the “filled” grid coordinates to either the number of symbol found there and contains lists of both the numbers and symbols associated with their coordinates for efficient iteration of either.
Part One - When is a Number not a Number?
When it’s apart! Ok, fine, that wasn’t a good joke. I couldn’t help myself. In part 1 of today’s puzzle (fine, I’ll stop), we are tasked with reviewing a gondola schematic and deciding which numbers are real-life part numbers and which ones we can safely ignore. The part numbers are all adjacent (counting diagonally) to “symbols” on the schematic which likely represent some sort of fancy widget or dongle or somesuch. Doesn’t matter to us, though, we’re all about those numbers!
data class EngineSchematic
private constructor(
val map: MutableMap<Coordinate, SchematicItem>,
val numbers: List<Pair<SchematicItem.Number, List<Coordinate>>>,
val symbols: List<Pair<SchematicItem.Symbol, Coordinate>>
) {
// companion_object { ... }
/**
* Extract the true part numbers from the schematic
*
* Just because there's a number in the schematic doesn't mean it's a
* _part_ number. Which is weird. A real part number is adjacent to a symbol.
* This function checks around each number for a symbol and returns all
* [SchematicItem.Number]s with an adjacent symbol.
*
* @return A list of [SchematicItem.Number] objects
*/
fun partNumbers(): List<SchematicItem.Number> {
val offsets = listOf(
-1 to -1, -1 to 0, -1 to 1, 0 to -1,
0 to 1, 1 to -1, 1 to 0, 1 to 1
)
val partNumbers = mutableListOf<SchematicItem.Number>()
// For each number/list of coordinates pair in the [numbers] list,
// check all around the number for a symbol. Technically, we're
// re-checking several indices for numbers with multiple digits.
// It's possible to keep track of coordinates checked, but I'm not
// convinced it's worth the extra effort.
for ((number, coordinates) in numbers) {
number@ for (coordinate in coordinates) {
for (offset in offsets) {
// Get the neighboring coordinate to check
val row = coordinate.first + offset.first
val col = coordinate.second + offset.second
val checkAt = Coordinate(row, col)
// If there's a value at that coordinate and that value is
// a [SchematicItem.Symbol], then this number really is
// a part number! Add it to our list and move on.
val maybeSymbol = map.get(checkAt) as? SchematicItem.Symbol
if (maybeSymbol != null) {
partNumbers.add(number)
break@number
}
}
}
}
return partNumbers
}
}
class Day03(input: String) {
// The real work is done here
private val schematic = EngineSchematic.fromString(input)
// In part one, we figure out which numbers really represent parts
// and return the sum of all of them.
fun solvePart1(): Int = schematic.partNumbers().sumOf { it.number }
}
There we go, not too stressful. Just check around each number for a symbol, and if we find one then it’s a part number. The tricky bit is that each number may take up more than one space on the grid. It might also be adjacent to more than one symbol (a quick scan of my input doesn’t reveal any, but I’m too paranoid to trust that). So, we need to make sure we consider each digit of each number and include or reject it only once.
Part Two - That’s What Grinds My Gears
You know, I had a feeling that it would actually matter what those symbols meant eventually. Sure enough, any ‘*’ that’s adjacent to two (and only two) numbers is a gear, and we kind of need to know what those numbers are so we can calculate the gear ratio. Also, I’m pretty sure that’s not how most people use the term “gear ratio”, but what do I know?
data class EngineSchematic
private constructor(
val map: MutableMap<Coordinate, SchematicItem>,
val numbers: List<Pair<SchematicItem.Number, List<Coordinate>>>,
val symbols: List<Pair<SchematicItem.Symbol, Coordinate>>
) {
// companion_object { ... }
// fun partNumbers(): List<SchematicItem.Number> { ... }
/**
* Calculate and return all gear ratios in the schematic
*
* Some symbols are gears. Each gear is associated with two numbers, and the
* 'gear ratio' is the product of those two numbers.
*
* @return A list of all gear ratios represeted on the schematic
*/
fun gearRatios(): List<Int> {
val offsets = listOf(
-1 to -1, -1 to 0, -1 to 1, 0 to -1,
0 to 1, 1 to -1, 1 to 0, 1 to 1
)
val ratios = mutableListOf<Int>()
// For each symbol/coordinate pair in the symbols list, check around that
// symbol for exactly two numbers. If two numbers are found, add their
// product to the gear ratio list.
symbol@ for ((symbol, coordinate) in symbols) {
if (symbol.char != '*') continue // skip it, not a gear
// We _do_ need to keep track of which numbers we've already seen,
// since each number can have multiple digits and the symbol may
// be adjacent to more than one of them.
var numbersSeen = mutableSetOf<Int>()
var numbersAdded = 0
var ratio = 1
// Check all around the symbol...
for (offset in offsets) {
val row = coordinate.first + offset.first
val col = coordinate.second + offset.second
val checkAt = Coordinate(row, col)
// If the neighboring coordinate contains a value that can be
// coerced to a [SchematicItem.Number], we haven't added that
// number to the gear ratio yet, and it's not the third (or
// greater) number we've found, then we add (by multiplying) that
// number to the gear ratio and add the number's ID to the set
// of seen numbers.
val maybeNumber = map.get(checkAt) as? SchematicItem.Number
if (maybeNumber != null && !numbersSeen.contains(maybeNumber.id)) {
if (numbersAdded >= 2) continue@symbol // more than two numbers
ratio *= maybeNumber.number
numbersSeen.add(maybeNumber.id)
numbersAdded += 1
}
}
// Only add the raio to ratios if we saw two numbers
if (numbersAdded == 2) ratios.add(ratio)
}
return ratios
}
}
class Day03(input: String) {
// The real work is done here
private val schematic = EngineSchematic.fromString(input)
// In part one, we figure out which numbers really represent parts
// and return the sum of all of them.
fun solvePart1(): Int = schematic.partNumbers().sumOf { it.number }
// In part two, we find the gears (which are a bit trickier) and return
// the sum of all the gear ratios.
fun solvePart2(): Int = schematic.gearRatios().sum()
}
Here, we iterate over the list of symbols and check around them for any number. If we find one number, that goes in the ‘gear ratio’. Same for the second one. A third one, though, and we’re out; that’s not a gear. Calculating the gear ratio for all the ‘*’ that are really gears, we just need to sum them and we’re good to go.
Wrap Up
I’ve heard this year (so far) being referred to as the “Advent of Parsing”, and
there’s a certain truth to that. Granted, there’s a certain truth to that
every year, but these first three days have been pretty heavy with it. It may
have something to do with these first few days falling on a weekend. Regardless,
it’s certainly given me an opportunity to write a decent amount of code in
Kotlin, which is helping the learning process. I was delighted to find the
mechanism for tagging loops and choosing which one to break/continue for
the loops within loops of today’s solutions. I’d like to be writing these
in a more “functional” style as opposed to the “initialize then loop” pattern
I’ve got here, but I’m not sure how to do that with all the side-effects I’m
engaging here. Probably just need to spend a bit more time on it, reduce with
a data structure, etc.
Lastly, I’ll point out the JetBrains Livestreams for Advent of Code. I’ve found them really helpful for hearing how other people have approached these problems in the same language who have a much greater breadth of knowledge about what’s in the standard library and ecosystem. It really helps me to listen in after I’ve solved the problem (or at least worked on it) so I can more easily follow along. Give it a watch/listen!