andreiz / advent-of-code-2023-swift

Copilot and ChatGPT assisted Advent of Code 2023 to learn Swift.
0 stars 0 forks source link

Day 3: Gear Ratios #3

Open andreiz opened 11 months ago

andreiz commented 11 months ago

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 commented 11 months ago

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 commented 11 months ago

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 commented 11 months ago

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 commented 11 months ago

Copilot is great at stuff like this:

image

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

https://github.com/andreiz/advent-of-code-2023-swift/blob/c612f1b6235c74549d662e08c3dede8d8d39ae1c/day-03/engine.swift#L23-L39

andreiz commented 11 months ago

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

image

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

andreiz commented 11 months ago

Implementing the logic described earlier:

https://github.com/andreiz/advent-of-code-2023-swift/blob/c612f1b6235c74549d662e08c3dede8d8d39ae1c/day-03/engine.swift#L47-L76

andreiz commented 11 months ago

This passes the checker with the full input file.

andreiz commented 11 months ago

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 commented 11 months ago

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 commented 11 months ago

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 commented 11 months ago

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.

https://github.com/andreiz/advent-of-code-2023-swift/blob/861554fc6e956c1025fefd363524f4e34ba6e932/day-03/engine-gear.swift#L33-L50

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:

image

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

andreiz commented 11 months ago

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.

https://github.com/andreiz/advent-of-code-2023-swift/blob/861554fc6e956c1025fefd363524f4e34ba6e932/day-03/engine-gear.swift#L63-L88

andreiz commented 11 months ago

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 commented 11 months ago

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 commented 11 months ago

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.