Advent of Code - 2023
This is a solution to Day 3 of Advent of Code 2023.
Day 3: Gear Ratios
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?
Read input
This time, reading the input has two parts: first one is to read the schematics from the raw input and second is constructing the engine.
Today's puzzle is one where it is possible to write it more efficient by not separating parsing from calculations but calculate as you go along. Here, that was not needed in either part, so I'll continue with my approach of first parsing to a useful data structure and then working with it.
I turn each line in the input into a list so I end up with a list of lists with each character as its own item.
I then create the engine as a dictionary with key of (x,y) position and value as the character.
from utils import read_input
EMPTY = '.'
def transformer(line):
return list(line)
def create_engine(schematics):
engine = {}
for y, row in enumerate(schematics):
for x, value in enumerate(row):
engine[(x,y)] = value
return engine
schematics = read_input(3, transformer)
engine = create_engine(schematics)
Part 1
I created a helper tuple Number to keep track of all the numbers, their start positions and lengths.
from collections import namedtuple
Number = namedtuple('Number', ['value', 'start_position', 'length'])
My function to find neighboring coordinates is a very naive one: it goes through all positions the number's digits are in and finds neighboring coordinates for all of them. This means it finds coordinates that are beyond the original grid and it finds coordinates that are occupied by parts of the number itself.
The first part I tackle by using dictionary's .get(key, [default]) method in is_valid_part_number function and the second one doesn't matter because it doesn't matter if a number is connected to another number.
A "symbol" in this puzzle is anything that is not a . (or EMPTY in my code) nor a digit. So to find out if a number is a part number, I go through all of its neighbors and check if any of them is a symbol.
def find_neighbors(number):
neighbors = []
start_x = number.start_position[0]
y = number.start_position[1]
for x in range(start_x, start_x + number.length):
neighbors.extend([
(x-1, y-1),
(x, y-1),
(x+1, y-1),
(x-1, y),
(x+1, y),
(x-1, y+1),
(x, y+1),
(x+1, y+1)
])
return neighbors
def is_symbol(character):
return character != EMPTY and not character.isdigit()
def is_valid_part_number(number, engine):
for neighbor in find_neighbors(number):
if is_symbol(engine.get(neighbor, EMPTY)):
return True
return False
To find all numbers in the grid, I have a find_numbers function that takes engine as its only argument.
I go through each position and there are five cases we could be in:
- We are not currently reading a number and the current character is not a digit -> we do nothing
- We encounter first digit -> we start reading a number and save the starting position
- We are in the middle of reading a number and encounter a digit -> we append the new digit to number
- We were reading a number but current character is not one -> we finish reading a number and store it to a list
- We switch rows while reading a number (one row finishes with number and next starts with one) -> we finish reading a number and start reading a new one
Dictionaries in Python are currently (at the time of writing) read in insertion order. This wasn't a case in the past and is not guaranteed to be the case in the future so it shouldn't be relied on. To make sure our coordinates are gone through in right order (row by row, column by column), I use a lambda function to sort first by y-coordinate and then x-coordinate.
sort_by_rows_then_columns = lambda x: (x[0][1], x[0][0])
def find_numbers(engine):
numbers = []
reading_number = ''
start_position = None
for pos, value in sorted(engine.items(), key=sort_by_rows_then_columns):
if value.isdigit():
# We are currently in the middle of a number
if reading_number:
# If we wrap to new line, we need to stop old number and start new
if pos[0] == 0:
numbers.append(
Number(
value=int(reading_number),
start_position=start_position,
length=len(reading_number)
)
)
reading_number = value
start_position = pos
else:
reading_number += value
# We start to read a number
if not reading_number:
start_position = pos
reading_number = value
# We finished reading a number
elif reading_number:
numbers.append(
Number(
value=int(reading_number),
start_position=start_position,
length=len(reading_number)
)
)
reading_number = ""
start_pos = None
return numbers
To calculate the result, I first find all the numbers from the engine and then check for each, if they are a valid part number or not. Finally, I sum up all the valid numbers.
def calculate_sum(engine):
numbers = find_numbers(engine)
valid_numbers = []
for number in numbers:
if is_valid_part_number(number, engine):
valid_numbers.append(number)
return sum(n.value for n in valid_numbers)
part_1 = calculate_sum(engine)
print(f'Solution: {part_1}')
assert part_1 == 537832
Part 2
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?
My solution for this second part is not very optimized but it's readable and easy to follow.
In calculate_gear_ratio_sum main function, I find all the numbers as before and then iterate over each character in the grid (this time the order doesn't matter). For each GEAR (*), I find all the numbers connected to it (by inefficiently iterating through all the numbers for each gear and generating all neighbors for those numbers) and checking if the gear is within those neighboring positions.
If a gear has exactly two connected numbers, I calculate the product of them and finally sum them all up.
import math
GEAR = '*'
def find_neighboring_numbers(gear_position, numbers):
connected = []
for number in numbers:
number_neighbors = find_neighbors(number)
if gear_position in number_neighbors:
connected.append(number)
return connected
def calculate_gear_ratio_sum(engine):
gear_ratios = []
numbers = find_numbers(engine)
for position, value in engine.items():
if value != GEAR:
continue
connected_numbers = find_neighboring_numbers(position, numbers)
if len(connected_numbers) == 2:
gear_ratios.append(math.prod((n.value for n in connected_numbers)))
return sum(gear_ratios)
part_2 = calculate_gear_ratio_sum(engine)
print(f'Solution: {part_2}')
assert part_2 == 81939900
Two stars!
6 out of 50 done, we're making great progress!