Day 3: Gear Ratios

[andreiz]

https://adventofcode.com/2023/day/3

The engine schematic (your puzzle input) consists of a visual representation of the engine. There are lots of numbers and symbols you don't really understand, but apparently any number adjacent to a symbol, even diagonally, is a "part number" and should be included in your sum. (Periods (.) do not count as a symbol.)

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..

In this schematic, two numbers are not part numbers because they are not adjacent to a symbol: 114 (top right) and 58 (middle right). Every other number is adjacent to a symbol and so is a part number; their sum is 4361.

Of course, the actual engine schematic is much larger. What is the sum of all of the part numbers in the engine schematic?

Day 3 input: https://adventofcode.com/2023/day/3/input

[andreiz]

Going to try mostly using Copilot this time.

First, need to be able to modify the input easily. Prompted:

// Ensure that exactly one command line argument (the input file) is provided.

Result:

guard CommandLine.arguments.count == 2 else {
    print("Usage: \(CommandLine.arguments[0]) <input file>")
    exit(1)
}

Now, I think I'd rather treat the input as a 2D array, so let's do that. Boilerplate first:

func readInputFile(_ inputFile: String) -> [[Character]]? {
    do {
        let fileContents = try String(contentsOfFile: inputFile)
        // prompt
    } catch {
        print("Error reading from \(inputFile): \(error)")
        return nil
    }
}

Then prompted:

// return file contents as a 2D array of characters, skipping empty lines

Got:

return fileContents.split(separator: "\n").map { Array($0) }

Apparently, Array() converts a substring into an array of characters. Also, split() removes empty sequences (lines in this case) by default. Sensible.

[andreiz]

I could index the array contents directly, but that means I'd need to do bounds testing on every access. So, let's write a safety wrapper (with Copilot's help):

// Define a function to access the character at a given position in
// the input array, with bounds checking
func getChar(_ data: [[Character]], _ row: Int, _ col: Int) -> Character? {
    if row < 0 || row >= data.count || col < 0 || col >= data[row].count {
        return nil
    }
    return data[row][col]
}

[andreiz]

Initially I considered flipping the problem and looking for symbols first, then for each one, checking if there are numbers around, but that's involved and may require an initial pass to save all the number locations.

Instead, I'm going to do the simplest thing possible and iterate over the array checking for digits. Once one is found, start adding it to currentNumber var and also checking the neighboring cells for symbols. When we reach a period (.) or end-of-line, we have our number, and if we encountered any symbols around it along the way, we add it to the list.

[andreiz]

Copilot is great at stuff like this:

Also, instead of checking for specific symbols, I'm going to check for anything not a digit or a period (.).

advent-of-code-2023-swift/day-03/engine.swift

Lines 23 to 39 in c612f1b

	// Define a function to check neighbors of a cell for anything
	// not a digit or a period
	func checkNeighborsForSymbols(_ data: [[Character]], _ row: Int, _ col: Int) -> Bool {
	// Define a data structure to access 8 neighbors of a cell.
	let neighbors = [
	(-1, -1), (-1, 0), (-1, 1),
	(0, -1), (0, 1),
	(1, -1), (1, 0), (1, 1),
	]
	for (rowOffset, colOffset) in neighbors {
	if let char = getChar(data, row + rowOffset, col + colOffset), !(char.isNumber || char == ".") {
	return true
	}
	}
	return false
	}

[andreiz]

Now, to wrap it up, let's make a skeleton of the main loop.

Guess it's a little to eager to call checkNeighborsForSymbols. Also, I really like the ..< syntax in the loops.

[andreiz]

Implementing the logic described earlier:

advent-of-code-2023-swift/day-03/engine.swift

Lines 47 to 76 in c612f1b

	if let data = readInputFile(CommandLine.arguments[1]) {
	var numbers: [Int] = []
	for row in 0 ..< data.count {
	var currentNumber = ""
	var haveSymbolNeighbor = false
	for col in 0 ..< data[row].count {
	if let char = getChar(data, row, col), char.isNumber {
	currentNumber.append(char)
	if checkNeighborsForSymbols(data, row, col) {
	haveSymbolNeighbor = true
	}
	} else {
	if let number = Int(currentNumber), haveSymbolNeighbor {
	numbers.append(number)
	}
	currentNumber = ""
	haveSymbolNeighbor = false
	}
	}
	// Check if line ends with a number
	if let number = Int(currentNumber), haveSymbolNeighbor {
	numbers.append(number)
	}
	}
	print(numbers)
	print(numbers.reduce(0, +))
	}

[andreiz]

This passes the checker with the full input file.

[andreiz]

Part 2 cranks it (heh heh) up a bit.

A gear is any * symbol that is adjacent to exactly two part numbers. Its gear ratio is the result of multiplying those two numbers together.
This time, you need to find the gear ratio of every gear and add them all up so that the engineer can figure out which gear needs to be replaced.

467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..

In this schematic, there are two gears. The first is in the top left; it has part numbers 467 and 35, so its gear ratio is 16345. The second gear is in the lower right; its gear ratio is 451490. (The * adjacent to 617 is not a gear because it is only adjacent to one part number.) Adding up all of the gear ratios produces 467835.

[andreiz]

Maybe, in the words of Gob, "I've made a huge mistake". At first glance, it seems like it would be better to search for the stars and then check for surrounding numbers. Which means we probably need to extract numbers first and store their row,col plus length.

After messing about a bit with Copilot, the resulting solution was becoming too messy. Decided to go back to a single scan. This time we also need to save the symbols (well, just *) found around numbers.

[andreiz]

Since each number may have multiple stars, and we may encounter the same star more than once while scanning the number, we need to have a unique set of them.

// Define a struct to hold coordinates of a cell
struct Coords {
    let row: Int
    let col: Int
}

As I found when trying to use it, you either have to specify the labels in the constructor or create an initializer which omits them. I picked the latter.

// Define a struct to hold coordinates of a cell
struct Coords {
    let row: Int
    let col: Int
    init(_ row: Int, _ col: Int) {
        self.row = row
        self.col = col
    }
}

[andreiz]

I modified the checkNeighborsForSymbols to instead find all neighboring stars. Initially I was using an array of Coords, appending each found star to it, and thinking I would make it unique later, but then realized I should have just used a Set.

advent-of-code-2023-swift/day-03/engine-gear.swift

Lines 33 to 50 in 861554f

	// Define a function called findNeighborStars that checks the cell's neighbors
	// and returns a set of cells where stars are found
	func findNeighborStars(_ data: [[Character]], _ row: Int, _ col: Int) -> Set<Coords> {
	// Define a data structure to access 8 neighbors of a cell.
	let neighbors = [
	(-1, -1), (-1, 0), (-1, 1),
	(0, -1), (0, 1),
	(1, -1), (1, 0), (1, 1),
	]
	var starCoords: Set<Coords> = []
	for (rowOffset, colOffset) in neighbors {
	if let char = getChar(data, row + rowOffset, col + colOffset), char == "*" {
	starCoords.insert(Coords(row + rowOffset, col + colOffset))
	}
	}
	return starCoords

However, I at first I got this error:

error: type 'Coords' does not conform to protocol 'Hashable'
func findNeighborStars(_ data: [[Character]], _ row: Int, _ col: Int) -> Set<Coords> {

I asked ChatGPT about it and it replied:

I guess if I had more complex data types inside Coords I'd have to implement a hashing method.

[andreiz]

With that out of the way, the main number scan loop only has a few modifications. First we need a dict to keep track of stars and which number they are adjacent to. This will be updated when each number is found.

var starNumbers: [Coords: [Int]] = [:]

Also need another Set<Coords> to keep track of all found stars for each number. Turns out to merge one set into another you use formUnion.

advent-of-code-2023-swift/day-03/engine-gear.swift

Lines 63 to 88 in 861554f

	for row in 0 ..< data.count {
	var currentNumber = ""
	var starCoords: Set<Coords> = []
	for col in 0 ..< data[row].count {
	if let char = getChar(data, row, col), char.isNumber {
	currentNumber.append(char)
	// Add coordinates of any stars found to the set
	starCoords.formUnion(findNeighborStars(data, row, col))
	} else {
	if let number = Int(currentNumber), !starCoords.isEmpty {
	for coord in starCoords {
	starNumbers[coord, default: []].append(number)
	}
	}
	currentNumber = ""
	starCoords = []
	}
	}
	// Check if line ends with a number
	if let number = Int(currentNumber), !starCoords.isEmpty {
	for coord in starCoords {
	starNumbers[coord, default: []].append(number)
	}
	}
	}

[andreiz]

Now we just need to calculate the sum of gear ratios. Thankfully, Swift as a functional language makes it easy:

let gearRatiosProduct = starNumbers
        .filter { $1.count == 2 } // only consider stars adjacent to exactly 2 numbers
        .map { $1.reduce(1, *) } // multiply the 2 numbers together
        .reduce(0, +) // sum the products

Wow, got a trifecta: filter, map, AND reduce all at the same time!

[andreiz]

For bonus points I printed out the stars and their numbers sorted by rows then columns, but I let Copilot figure it out:

// print out starNumbers info with coordinates sorted by row then column
for (coords, numbers) in starNumbers.sorted(by: { $0.key.row == $1.key.row ? $0.key.col < $1.key.col : $0.key.row < $1.key.row }) {
    print("Star at (\(coords.row), \(coords.col)) is adjacent to \(numbers)")
}

[andreiz]

Running the program on test input:

Star at (1, 3) is adjacent to [467, 35]
Star at (4, 3) is adjacent to [617]
Star at (8, 5) is adjacent to [755, 598]
467835

Which is correct. The full input passes too.