[Day 3] Gear Ratios // Advent of Code 2023 (Python)

Gear Ratios ⚙️ (via DALL-E 3)

Advent of Code
You and the Elf eventually reach a gondola lift station; he says the gondola lift will take you up to the water source…adventofcode.com

Part One

# --- Day 3: Gear Ratios ---

## --- Part One ---

You and the Elf eventually reach a gondola lift station; he says the gondola lift will take you up to the water source, but this is as far as he can bring you. You go inside.

It doesn't take long to find the gondolas, but there seems to be a problem: they're not moving.

"Aaah!"

You turn around to see a slightly-greasy Elf with a wrench and a look of surprise. "Sorry, I wasn't expecting anyone! The gondola lift isn't working right now; it'll still be a while before I can fix it." You offer to help.

The engineer explains that an engine part seems to be missing from the engine, but nobody can figure out which one. If you can add up all the part numbers in the engine schematic, it should be easy to work out which part is missing.

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.)

Here is an example engine schematic:

```
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?

💭 Giving it a quick read, we can establish that we need to find the sum of all part numbers where a part number is defined as a number in engine schematic that is:

• adjacent to a symbol (including diagnols)
• periods . DO NOT count as a symbol!

This looks like a cookie cutter template problem for a Nearest neighbour first approach, where we can have a greedy algo right:

1. Find a symbol (except .)
2. Look for a digit in all 8 directions, i.e.: ⬅️↖️⬆️↗️➡️↘️⬇️↙️
3. If found, fan out on ⬅️ and ➡️ directions to build the full number.
4. Add to the sum.

Let’s write the given base test case first and try to solve problem for that.

Then I played around a bit to understand how to traverse the data quickly, looks like we can just convert it into a grid (2D array) for ease of calculation.

some quick ipython3 scripting

for my own sanity

💡While looking at the data sample, it stuck me that instead of looking for symbol first and then trying to find a number around it, I can just traverse each row, column to column and once I find a digit, I can try to build the number by moving right and then see if those digit[] have any symbol around them!

So, I wrote a quick prototype and…..

:(

💡 An interesting edge case here can be where we can land on to same subset of the number we have included in our calculation before, so we need to store the location (idx) of already used part numbers (columns?)

So after a series of print(...) statements and errors, we are able to see this:

[Running] python -u "/Users/jmalik/github/advent-of-code-2023/day_3/part_1_gear_ratios.py"
Found a number: 467
No symbol adjacent to 4 at 0,0
No symbol adjacent to 6 at 0,1
Found a symbol adjacent to 7 at 0,2
Skipping already processed location 0,1
Skipping already processed location 0,2
Found a number: 114
No symbol adjacent to 1 at 0,5
No symbol adjacent to 1 at 0,6
No symbol adjacent to 4 at 0,7
Skipping already processed location 0,6
Skipping already processed location 0,7
Found a number: 35
Found a symbol adjacent to 3 at 2,2
Skipping already processed location 2,3
Found a number: 633
Found a symbol adjacent to 6 at 2,6
Skipping already processed location 2,7
Skipping already processed location 2,8
Found a number: 617
No symbol adjacent to 6 at 4,0
No symbol adjacent to 1 at 4,1
Found a symbol adjacent to 7 at 4,2
Skipping already processed location 4,1
Skipping already processed location 4,2
Found a number: 58
No symbol adjacent to 5 at 5,7
No symbol adjacent to 8 at 5,8
Skipping already processed location 5,8
Found a number: 592
No symbol adjacent to 5 at 6,2
No symbol adjacent to 9 at 6,3
Found a symbol adjacent to 2 at 6,4
Skipping already processed location 6,3
Skipping already processed location 6,4
Found a number: 755
Found a symbol adjacent to 7 at 7,6
Skipping already processed location 7,7
Skipping already processed location 7,8
Found a number: 664
No symbol adjacent to 6 at 9,1
Found a symbol adjacent to 6 at 9,2
Skipping already processed location 9,2
Skipping already processed location 9,3
Found a number: 598
Found a symbol adjacent to 5 at 9,5
Skipping already processed location 9,6
Skipping already processed location 9,7

All tests passed successfully! # <------ YESSS!!!

[Done] exited with code=0 in 0.213 seconds

Our base case is working! Let’s try to load the input.txt in main() and call our helper function sum_of_part_numbers(). Here’s the code:

And, we get an answer -> 539061.

Let’s input this into our answer box and…

Well, nope!

Looking at the logs, it does seem like we are doing everything correct! What could be the bug? Time to wear debugging hat again.

🤔

Oh! I got it. Since we are using a global processed_locations set, if we run our test_sum_of_part_numbers() method before main() it ends up corrupting our set with test data example and then starts to process the engine schematics from input.txt 🤦‍♂

So, let’s just comment it out and our final code is:

class EngineSchematicAnalyzer:
    DIRECTIONS = [
        (-1, -1), # Top-left
        (-1, 0),  # Up
        (-1, 1),  # Top-right
        (0, -1),  # Left
        (0, 1),   # Right
        (1, -1),  # Bottom-left
        (1, 0),   # Down
        (1, 1)    # Bottom-right
    ]

    def __init__(self, schematic):
        self.schematic = [list(line) for line in schematic.split('\n')]
        self.processed_locations = set()

    def is_valid_symbol(self, char):
        return not (char.isdigit() or char == '.')

    def is_adjacent_to_symbol(self, row, col):
        for dx, dy in self.DIRECTIONS:
            if 0 <= row + dx < len(self.schematic) and 0 <= col + dy < len(self.schematic[row + dx]):
                if self.is_valid_symbol(self.schematic[row + dx][col + dy]):
                    return True
        return False

    def calculate_sum_of_part_numbers(self):
        total_sum = 0
        for i, row in enumerate(self.schematic):
            j = 0
            while j < len(row):
                if row[j].isdigit() and (i, j) not in self.processed_locations:
                    number, init_j = row[j], j
                    while j + 1 < len(row) and row[j + 1].isdigit():
                        number += row[j + 1]
                        j += 1
                    
                    for col_index in range(init_j, j + 1):
                        self.processed_locations.add((i, col_index))
                        if self.is_adjacent_to_symbol(i, col_index):
                            total_sum += int(number)
                            break
                j += 1
            
        return total_sum

def main():
    with open("day_3/input.txt") as file:
        engine_schematic = file.read()

    analyzer = EngineSchematicAnalyzer(engine_schematic)
    total_sum = analyzer.calculate_sum_of_part_numbers()
    print(f"Sum of part numbers is {total_sum}")

def test_sum_of_part_numbers():
    engine_schematic = """467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..
"""

    analyzer = EngineSchematicAnalyzer(engine_schematic)
    calculated_sum = analyzer.calculate_sum_of_part_numbers()
    assert calculated_sum == 4361, f"sum of part numbers is {calculated_sum}"
    print("All tests passed successfully!")

if __name__ == "__main__":
    # test_sum_of_part_numbers()
    main()

We run this and we get an answer! Let’s put this into the answer box in our puzzle: https://adventofcode.com/2023/day/3 and….

🎉🎉🎉

---

Awesome! let’s move on to the…

Part Two

## -- Part Two --
The engineer finds the missing part and installs it in the engine! As the engine springs to life, you jump in the closest gondola, finally ready to ascend to the water source.

You don't seem to be going very fast, though. Maybe something is still wrong? Fortunately, the gondola has a phone labeled "help", so you pick it up and the engineer answers.

Before you can explain the situation, she suggests that you look out the window. There stands the engineer, holding a phone in one hand and waving with the other. You're going so slowly that you haven't even left the station. You exit the gondola.

The missing part wasn't the only issue - one of the gears in the engine is wrong. 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.

Consider the same engine schematic again:

```
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.

What is the sum of all of the gear ratios in your engine schematic?

So, this might seem a bit tricky in first glace!

But if we observe the example carefully, we can observe that a valid gear ratio is the one with:

• a multiple of exactly 2 part numbers adjacent to a gear i.e. *

💭 This allows us to think about this problem in a more pragmatic way, as we can resuse some part of our method is_adjacent_to_symbol() to create a new method calculate_gear_ratio() where we can pass a gear * when we encouter it while traversing over schematic.

Looks like we can go back to our initial thought when we were discussing about how to solve part 1, now instead of looking for a number and then finding a surrounding gear, we can do the opposite like:

1. Find a gear *
2. Look for a digit in all 8 directions, i.e.: ⬅️↖️⬆️↗️➡️↘️⬇️↙️
3. If found, fan out on ⬅️ and ➡️ directions to build the full part_number_1
4. Go back to step 2, and keep looking for another digit that is not in part_number_1
5. If, found, repeat step 3, to build the full part_number_2
6. Calculate gear_ratio_1 = part_number_1 * part_number_2
7. Repeat Steps 1 to 6, and do return sum(gear_ratio_1...gear_ratio_n).

Let’s write the base test case first to run our code against:

And now let’s write some code based on our algo design above!

💡Edge case: Important step to note above is Step 3, where we have to fan out in both directions to ensure we capture the full part number as * can be adjacent to any digit of the number!

I see an opportunity for taking out 👆fan out logic into a util private method internally. Will do that as well!

I have writen a quick dirty implementation of calculate_sum_of_all_gear_ratios() to quickly test against my base case:

[Running] python -u "/Users/jmalik/github/advent-of-code-2023/day_3/gear_ratios.py"
test_sum_of_all_gear_ratios passed successfully!

Awesome! Let’s now make it a bit more pythonic, and add a part2() method to orchestrate the process of input.txt with the new method to calculate sum of all gear ratios.

Here’s the final code:

class EngineSchematicAnalyzer:
    DIRECTIONS = [
        (-1, -1), # Top-left
        (-1, 0),  # Up
        (-1, 1),  # Top-right
        (0, -1),  # Left
        (0, 1),   # Right
        (1, -1),  # Bottom-left
        (1, 0),   # Down
        (1, 1)    # Bottom-right
    ]

    def __init__(self, schematic):
        self.schematic = [list(line) for line in schematic.split('\n')]
        self.processed_locations = set()

    def calculate_sum_of_part_numbers(self):
        total_sum = 0
        for i, row in enumerate(self.schematic):
            j = 0
            while j < len(row):
                if row[j].isdigit() and (i, j) not in self.processed_locations:
                    part_number = self._get_full_part_number(i, j)
                    self.processed_locations.update(
                        (i, col_index) for col_index in range(j, j + len(str(part_number)))
                    )

                    if any(self._is_adjacent_to_symbol(i, col_index) for col_index in range(j, j + len(str(part_number)))):
                        total_sum += part_number
                    j += len(str(part_number)) - 1
                j += 1
            
        return total_sum
    
    def calculate_sum_of_all_gear_ratios(self):
        total_sum = 0
        for i, row in enumerate(self.schematic):
            for j, char in enumerate(row):
                total_sum += self._get_gear_ratio(i, j) if char == '*' else 0
        
        return total_sum

    def _get_gear_ratio(self, row, col):
        adjacent_numbers = []
        for dx, dy in self.DIRECTIONS:
            adjacent_row, adjacent_col = row + dx, col + dy
            if 0 <= adjacent_row < len(self.schematic) and 0 <= adjacent_col < len(self.schematic[adjacent_row]):
                if self.schematic[adjacent_row][adjacent_col].isdigit():
                    part_number = self._get_full_part_number(adjacent_row, adjacent_col)
                    if part_number not in adjacent_numbers:
                        adjacent_numbers.append(part_number)

        if len(adjacent_numbers) == 2:
            return adjacent_numbers[0] * adjacent_numbers[1]
        return 0

    def _get_full_part_number(self, row, col):
        # start with the digit at (row, col)
        number_str = self.schematic[row][col]

        # fan out to the left
        left_col = col - 1
        while left_col >= 0 and self.schematic[row][left_col].isdigit():
            number_str = self.schematic[row][left_col] + number_str
            left_col -= 1

        # fan out to the right
        right_col = col + 1
        while right_col < len(self.schematic[row]) and self.schematic[row][right_col].isdigit():
            number_str += self.schematic[row][right_col]
            right_col += 1

        return int(number_str)

    def _is_valid_symbol(self, char):
        return not (char.isdigit() or char == '.')

    def _is_adjacent_to_symbol(self, row, col):
        for dx, dy in self.DIRECTIONS:
            if 0 <= row + dx < len(self.schematic) and 0 <= col + dy < len(self.schematic[row + dx]):
                if self._is_valid_symbol(self.schematic[row + dx][col + dy]):
                    return True
        return False

# solves the Part 1 of the problem
def part_1():
    with open("day_3/input.txt") as file:
        engine_schematic = file.read()

    analyzer = EngineSchematicAnalyzer(engine_schematic)
    total_sum = analyzer.calculate_sum_of_part_numbers()
    print(f"Sum of part numbers is {total_sum}")

# solves the Part 2 of the problem
def part_2():
    with open("day_3/input.txt") as file:
        engine_schematic = file.read()
    
    analyzer = EngineSchematicAnalyzer(engine_schematic)
    total_sum = analyzer.calculate_sum_of_all_gear_ratios()
    print(f"Sum of all gear ratios is {total_sum}")

def test_sum_of_part_numbers():
    engine_schematic = """467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..
"""

    analyzer = EngineSchematicAnalyzer(engine_schematic)
    calculated_sum = analyzer.calculate_sum_of_part_numbers()
    assert calculated_sum == 4361, f"sum of part numbers is {calculated_sum}"
    print("test_sum_of_part_numbers passed successfully!")

def test_sum_of_all_gear_ratios():
    engine_schematic = """467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..
"""
    analyzer = EngineSchematicAnalyzer(engine_schematic)
    calculated_sum = analyzer.calculate_sum_of_all_gear_ratios()
    assert calculated_sum == 467835, f"sum of all gear ratios is {calculated_sum}"
    print("test_sum_of_all_gear_ratios passed successfully!")

if __name__ == "__main__":
    # base test cases
    test_sum_of_part_numbers()
    test_sum_of_all_gear_ratios()

    # run the main function using the input file
    part_1() 
    part_2()

# I know there's still some scope of improvement in the code above
# that I might pick later, but it's 1AM, I want to sleep as I have 
# work tomorrow! Feel free to raise a PR. 😅

Looks good! So, let’s run this!

It does give us a large number, and as soon as we input it in Day 3, Part 2 answer box, we get… 🤞

---

Yay! 🥳

---

With this, we wrap Day 3 of #AdventOfCode2023. This was quite an interesting problem to solve!

Here’s a snap of my rough notes to structure my thoughts around Part 1 and Part 2:

This is my favorite way to solve a problem!

---

p.s: I am deliberating NOT adding puzzle answers here so you can actually spend some time trying to understand how we solved the problem!

Feel free to checkout code on my Github repo and try to set it up and run on your machine 👇

GitHub - jatinkrmalik/advent-of-code-2023: Advent of Code is an Advent calendar of small…
Advent of Code is an Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can…github.com