2023 Advent of Code: Day 3

AoC_2023_03.py

#!/usr/bin/env python3

lines=[]
with open("input.txt",'r') as input:
	lines=[line.strip() for line in input.read().strip().split('\n')]
max_lines=len(lines)
max_length=0
ratios: dict[tuple[int,int],list[int]]={} # position of the gear is the key, list of adjacent parts is the value
gear='*'
no_gear=(-1,-1)
empty='.'

# This is our bounds checker. There will be a lot of rechecking taking place here, but since
# we're not worried about performance, it'll suffice.
def worth_checking(line_number: int,cursor: int)->bool:
	if line_number < 0 or line_number >= max_lines or cursor < 0 or cursor >= max_length:
		return False
	return True

# Blow up the current position in the grid to 3x3 and check all cells
# for symbols. If a symbol is a gear, capture the position; we'll need
# that later in the main loop.
def check_for_symbols(line_number: int,cursor: int)->tuple[bool,tuple[int,int]]:
	symbol_found=False
	gear_position=no_gear
	for line in range(line_number-1,line_number+2):
		for character in range(cursor-1,cursor+2):
			if worth_checking(line,character):
				candidate=lines[line][character]
				if candidate.isdigit() or candidate == empty:
					continue
				else:
					if candidate == gear:
						gear_position=(line,character)
					symbol_found=True
	return symbol_found,gear_position

# Use "two-pointer" technique to scan the line for a "word" of numbers.
# Check each letter for surrounding symbols. This function calls itself
# recursively until it runs out of digits to chomp.
def search_for_words(line_number: int,head: int,tail: int,word: str="",is_part_number: bool=False,gear_position: tuple[int,int]=no_gear)->tuple[int,int,str,bool,tuple[int,int]]:
	if tail >= max_length:
		return tail,tail,word,is_part_number,gear_position
	candidate=lines[line_number][tail]
	if not candidate.isdigit():
		return tail+1,tail+1,word,is_part_number,gear_position
	else:
		symbol_found,next_gear_position=check_for_symbols(line_number,tail)
		return search_for_words(line_number,head,tail+1,word+candidate,True if is_part_number else symbol_found,gear_position if gear_position != no_gear else next_gear_position)

## Main Loop ##
words=[]
# For each line, pass the line into the string scanner to look for words
for line_number in range(len(lines)):
	head=0
	tail=0
	max_length=len(lines)
	# Keep calling the string scanner until it no longer returns a word or
	# reaches the end of the line.
	while head < max_length and tail < max_length:
		head,tail,word,is_part_number,gear_position=search_for_words(line_number,head,tail)
		if len(word) > 0 and is_part_number:
			words.append(word)
			# If the word was adjacent to a gear, place it in the dictionary of ratios
			# under the position of that gear.
			if gear_position != no_gear:
				if gear_position in ratios:
					ratios[gear_position].append(int(word))
				else:
					ratios[gear_position]=[int(word)]

ratio=0
# The dictionary of ratios now contains all the parts adjacent to each
# gear. Multiply the parts together for any gear that has two adjacent
# parts and add the result to the total ratio.
for parts in ratios.values():
	if len(parts) == 2:
		ratio+=parts[0]*parts[1]

## Boom! Done. ##
print("Part: "+str(sum([int(word) for word in words])))
print("Ratio: "+str(ratio))