2023-12-3
Created on Monday, December 23, 2024.
Day 3
Let's look at this, it looks horrendous at first glance.
We've got a grid of numbers, symbols and dots, and we're looking for all the numbers that are not adjacent to any symbol.
That's not a terribly easy thing to work out, because numbers have arbitrary widths.
My first thought is that we'll need to find each number in the grid, and then scan around it for a symbol. Scanning around it might be as simple as having a lookup table of number widths to neighbouring adjancies or similar?
i.e. a two digit number would have adjancies (from the first digit) of [(-1,0), (-1,1), (0, 1), (1, 1), (2,1), (2,0) etc. I can probably generate that?
But an alternative might be to iterate through every square on the grid, if it's a digit, explore it's surroundings to see if you can find a symbol. We'd have to handle finding other digits in the same number, but if we assume that my model of numbers starting at the first number, we can start to hold a database of all the numbers we've found.
## Import ipytest and get it setup for use in Python Notebook
import pytest
import ipytest
ipytest.autoconfig()grid = [line.strip() for line in """467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..""".split("\n")]
expected = {
(0,0):{"total":467, "adjacent":True},
(5,0):{"total":114, "adjacent":False},
(2,2):{"total":35, "adjacent":True},
(6,2):{"total":633, "adjacent":True},
(0,4):{"total":617, "adjacent":True},
(7,5):{"total":58, "adjacent":False},
(2,6):{"total":592, "adjacent":True},
(6,7):{"total":755, "adjacent":True},
(1,9):{"total":664, "adjacent":True},
(5,9):{"total":598, "adjacent":True}}
def grid_get(grid, coord):
x,y = coord
if y < 0 or y >= len(grid): return "."
if x < 0 or x >= len(grid[y]): return "."
return grid[y][x]
assert grid_get(grid, (0,0)) == "4"
assert grid_get(grid, (3,0)) == "."
assert grid_get(grid, (99,0)) == "."
assert grid_get(grid, (-1,-1)) == "."
assert grid_get(grid, (5,0)) == "1"
assert grid_get(grid, (6,0)) == "1"
assert grid_get(grid, (3,1)) == "*"
def find_numbers(grid):
numbers = {}
for y,line in enumerate(grid):
for x,cell in enumerate(line):
if cell.isdigit():
# We've found a digit, if we're not the first, then add to existing
startx = x
if not grid_get(grid, (x-1,y)).isdigit():
numbers[(x,y)] = {"total": int(cell), "adjacent":False}
else:
# find the start of the number
while grid_get(grid, (startx-1,y)).isdigit():
startx -= 1
numbers[(startx,y)]["total"] = numbers[(startx,y)]["total"]*10 + int(cell)
# Check Adjacency
for dy in range(-1,2):
for dx in range(-1,2):
if (dx,dy) != (0,0):
test = grid_get(grid, (x+dx,y+dy))
if not test.isdigit() and not test == ".":
numbers[(startx,y)]["adjacent"] = True
return numbers
assert find_numbers(grid) == expectedWhat a horrible function. Let's look at what it does.
Firstly, it looks at each cell in the grid in turn. It checks whether it's a digit, if it is, then it needs to find out if this is part of an existing number. If it's part of an existing number, it tries to find where it starts, and then it multiplies the total by 10, adds itself. That means that when it's at a line on y0 that reads .12, when it looks at x=1, it'll not find an earlier digit and set 1,0 to 1. Then at x=2, it'll find the number, look at x=1, find another digit, look at x=0 and not find one, so it'll set 1,0 (instead of 2,0) to 1*10+2.
Then comes the even more awkward bit, it looks at all the surrounding grid squares to see if there's a symbol adjacent. If there is, set the number adjacency to true. We could probably optimise that and only do it if it's not already adjacent and stop once it finds the first adjacent symbol, but that feels like premature optimisation.
Let's give it a go at producing our sum
def sum_numbers(grid):
return sum([match["total"] for match in find_numbers(grid).values() if match["adjacent"]])
assert sum_numbers(grid) == 4361Ok, that seems to work, let's try on real data
real_grid = [line.strip() for line in open("day3.txt").readlines()]
print(sum_numbers(real_grid))532445
Part 2
Oh my, what an extension to Part 1!
So this time, we're less interested in the numbers, but far more interested in gears, which are specific symbols.
Luckily, from our side, our mechanism for searching the space should still work, we just need to also look for gears, and put them into the dataset as well.
I talked about shortuctting the adjacency search before, which would have been a mistake. We now need to count adjacency, but only for gears.
However, we should probably refactor a few things out first
Let's give it a bit of a go
def find_first_number(grid, x, y):
startx = x
while grid_get(grid, (startx-1,y)).isdigit():
startx -= 1
return startx,y
def find_adjacent(grid, x, y, test_func):
neighbours = []
for dy in range(-1,2):
for dx in range(-1,2):
if (dx,dy) != (0,0):
cell = grid_get(grid, (x+dx,y+dy))
if test_func(cell):
neighbours.append((x+dx, y+dy))
return neighbours
def find_numbers(grid):
numbers = {}
for y,line in enumerate(grid):
for x,cell in enumerate(line):
if cell.isdigit():
# We've found a digit, if we're not the first, then add to existing
numx,numy = find_first_number(grid, x, y)
if (x,y) == (numx,numy):
numbers[(x,y)] = {"total": int(cell), "adjacent":False}
else:
numbers[(numx,numy)]["total"] = numbers[(numx,numy)]["total"]*10 + int(cell)
# Check Adjacency
neighbours = find_adjacent(grid, x, y, lambda cell: not cell.isdigit() and not cell == ".")
if neighbours:
numbers[(numx,numy)]["adjacent"] = True
return numbers
assert find_numbers(grid) == expected
def sum_numbers(grid):
return sum([match["total"] for match in find_numbers(grid).values() if match["adjacent"]])
assert sum_numbers(grid) == 4361Right, if that works, let's tweak it to count gears as well.
Interesting tidbit. my first attempt at this didn't work. The reason is that we don't calculate the totals for numbers until we read them, but when a gear has a number below it, we haven't worked out what the total is yet. So we now go through the grid twice, which feels wasteful, but I couldn't think of a better way to do this
gears = {
(3,1): { "adjacents":[35, 467], "ratio":16345 },
(3,4): { "adjacents":[617] },
(5,8): { "adjacents": [598, 755], "ratio":451490 }
}
def find_numbers(grid):
numbers = {}
gears = {}
for y,line in enumerate(grid):
for x,cell in enumerate(line):
if cell.isdigit():
# We've found a digit, if we're not the first, then add to existing
numx,numy = find_first_number(grid, x, y)
if (x,y) == (numx,numy):
numbers[(x,y)] = {"total": int(cell), "adjacent":False}
else:
numbers[(numx,numy)]["total"] = numbers[(numx,numy)]["total"]*10 + int(cell)
# Check Adjacency
neighbours = find_adjacent(grid, x, y, lambda cell: not cell.isdigit() and not cell == ".")
if neighbours:
numbers[(numx,numy)]["adjacent"] = True
for y,line in enumerate(grid):
for x,cell in enumerate(line):
if cell == "*":
# We've found a gear, so find the neighbouring numbers
neighbours = set([find_first_number(grid, n[0], n[1]) for n in find_adjacent(grid, x, y, lambda cell: cell.isdigit())])
adjacents = sorted([numbers[neighbour[0], neighbour[1]]["total"] for neighbour in neighbours])
if len(adjacents) == 2:
gears[(x,y)] = {"adjacents":adjacents, "ratio": adjacents[0]*adjacents[1]}
else:
gears[(x,y)] = {"adjacents":adjacents}
return numbers,gears
assert find_numbers(grid)[0] == expected
def sum_numbers(grid):
return sum([match["total"] for match in find_numbers(grid)[0].values() if match["adjacent"]])
assert sum_numbers(grid) == 4361
assert find_numbers(grid)[0] == expected
assert find_numbers(grid)[1] == gearsOk, that works, looks horrendous, but works.
Let's see if we can get the sums working
def sum_gears(grid):
return sum([numbers["ratio"] for numbers in find_numbers(grid)[1].values() if "ratio" in numbers])
assert sum_gears(grid) == 467835Phew!
Let's try that on real data
print(sum_gears(real_grid))79842967
Previous