This year my nemesis are these geometry puzzles. They are not usually difficult to code but I have pretty much no applicable knowledge of how to calculate certain things based on other properties of geometrical shapes.
First part I managed to do nicely today but the second part took me a good 3.5 hours to write and another 30 minutes to clean up so it made some sense.
Read input
Our input is once again a grid so let’s build one.
from collections import namedtuple
Coordinate = namedtuple("Coordinate", ["x", "y"])
def create_grid(inputs):
grid = {}
for y, row in enumerate(inputs):
for x, cell in enumerate(row):
grid[Coordinate(x, y)] = cell
return gridIf you’re just joining in with my explanations, see for example Day 04 where I wrote more about parsing grids to dictionaries.
Part 1
Our grid is a map of garden plots.
AAAA
BBCD
BBCC
EEECEach connected area of same letters is one plot. In the above example, we have the following plots:
+-+-+-+-+
|A A A A|
+-+-+-+-+ +-+
|D|
+-+-+ +-+ +-+
|B B| |C|
+ + + +-+
|B B| |C C|
+-+-+ +-+ +
|C|
+-+-+-+ +-+
|E E E|
+-+-+-+Our job is to calculate the area and the length of the perimeter for each garden plot.
I used a recursive approach for this one:
def get_neighbours(pos):
return (
Coordinate(pos.x + 1, pos.y),
Coordinate(pos.x - 1, pos.y),
Coordinate(pos.x, pos.y + 1),
Coordinate(pos.x, pos.y - 1),
)
def find_plot(pos, grid, visited):
visited.add(pos)
new_neighbours = [
n
for n in get_neighbours(pos)
if n not in visited and grid.get(n) == grid.get(pos)
]
if not new_neighbours:
return visited
for neighbour in new_neighbours:
visited.update(find_plot(neighbour, grid, visited))
return visitedFor any given position, we find all the neighbours that share the same letter and once there are no more neighbours, we return all the coordinates for that plot. The area of that plot is then its length.
To calculate the perimeter, I did a bit of double work as I ran through the garden again and calculated the perimeter of that plot:
def find_perimeter(position, grid):
perimeter = 0
value = grid.get(position)
for neighbour in get_neighbours(position):
if grid.get(neighbour) != value:
perimeter += 1
return perimeterTo wrap it together, I go through every position in the grid and if we haven’t been there yet, we find the plot it belongs to, mark all positions of that plot as visited and add the plot to our books:
def find_plots(grid):
plots = []
processed = set()
for position in grid:
if position in processed:
continue
plot = find_plot(position, grid, set())
processed.update(plot)
plots.append(plot)
return plotsTo calculate the full cost of fencing the garden, we find all the plots and for each plot, we multiply its area with its perimeter:
def part_1():
inputs = read_input(12, str)
grid = create_grid(inputs)
plots = find_plots(grid)
cost = 0
for plot in plots:
area = len(plot)
perimeter = sum(find_perimeter(pos, grid) for pos in plot)
cost += area * perimeter
print(f"Part 1: {cost}")Part 2
The second part added a twist that almost broke me.
Instead of the full perimeter, we’re now interested in just how many sides there are in each plot. It sounds like a simple change but it was everything but.
I don’t know how to calculate the amount of sides in a shape like these plots. I tried so many approaches: at one point I tried to calculate the outer sides and then remove the amount of sides any adjacent plot had touching but that became a recursive problem where to count the sides, I needed to know how to count the sides.
I then decided to count the corners instead. It took me quite a long time to figure out how to count corners for any non-square shape. Once I figured that out, I then needed to figure out how to calculate the amount of squares of shapes inside those plots and how to combine them in a way that produces the right result.
Let’s dig in.
Once again, this final code is a result of going deep and dirty and then refactoring it to make more sense. I did not solve this in the same order as I’m explaining it. Especially the helper functions almost always arise from refactoring rather than writing them up front.
Corner detection
Let’s start with a simplified version of my final code
def is_outside_corner(pos1, pos2, area):
return not (pos1 in area or pos2 in area)
def count_corners(pos, area):
left = Coordinate(pos.x - 1, pos.y)
right = Coordinate(pos.x + 1, pos.y)
up = Coordinate(pos.x, pos.y - 1)
down = Coordinate(pos.x, pos.y + 1)
corners = 0
if is_outside_corner(left, up, area):
corners += 1
if is_outside_corner(left, down, area):
corners += 1
if is_outside_corner(right, up, area):
corners += 1
if is_outside_corner(right, down, area):
corners += 1
return cornersand let’s imagine we have a plot of
1 2
3 4If we take 1, we check if it’s a corner by checking its neighbours in a specific way:
u
l 1 r
d- If
up+leftare not part of the plot, we have one corner - If
up+rightare not part of the plot, we have another - if
left+downare not, a third corner - and if
left+upare neither, a fourth corner
In our example above, only the left + up is empty so 1 is one corner. In a 2x2 grid like this, we have four spots that are each 1 corner.
For a shape that is behaving nicely, that’s a good start.
For a more complicated shape like
1 2 3
4 5we have to account for the corners that are created by that empty space.
What I ended up doing is I took the plot and then I check for all the other, imaginary plots that fit inside the rectangle boundaries of the original shape. For example in the above example:
1 2 3
4 e 5I’ve marked another shape as e.
Or we could have
1 2 f
e 4 5where we have two imaginary plots that fill in the rectangle.
To calculate these, I added a bunch of variables to help calculate it:
def count_corners(pos, area, rev=False):
left = Coordinate(pos.x - 1, pos.y)
right = Coordinate(pos.x + 1, pos.y)
up = Coordinate(pos.x, pos.y - 1)
down = Coordinate(pos.x, pos.y + 1)
corners = 0
if rev:
if is_inside_corner(left, up, area):
corners += 1
if is_inside_corner(left, down, area):
corners += 1
if is_inside_corner(right, up, area):
corners += 1
if is_inside_corner(right, down, area):
corners += 1
else:
if is_outside_corner(left, up, area):
corners += 1
if is_outside_corner(left, down, area):
corners += 1
if is_outside_corner(right, up, area):
corners += 1
if is_outside_corner(right, down, area):
corners += 1
return cornersThe rev flag signifies if we’re dealing with these imaginary plots. For them, we want to know if they are the reverse of a corner, ie both positions are inside the original real plot:
def is_inside_corner(pos1, pos2, area):
return pos1 in area and pos2 in areaNote
I’m sweating trying to explain my convoluted code and we’re not even done yet…
We still have one corner case left. Eric was kind enough to point that out directly in the puzzle description or otherwise I would have never even thought about it being a case.
AAAAAA
AAABBA
AAABBA
ABBAAA
ABBAAA
AAAAAAFor a plot like these, we have a position where two B plots touch each other only diagonally.
The current code will count these as double corners because if we look at it from the perspective of the A plot, there are two As that are in a corner that also are corners of the B plots.
To check for these, I have a beautifully named
def is_not_double_corner(pos1, pos2, other_plots, grid):
if grid.get(pos1) is not None and grid.get(pos2) is not None:
for other in other_plots:
if pos1 in other and pos2 not in other:
return False
if pos1 not in other and pos2 in other:
return False
return TrueThat checks if any corner check lands into a situation where both of them are inside our sub grid (neither coordinate results in None) and there coordinates belong to different plots.
Let’s put all of these together for our corner counter:
def count_corners(pos, area, grid, other_plots, rev=False):
left = Coordinate(pos.x - 1, pos.y)
right = Coordinate(pos.x + 1, pos.y)
up = Coordinate(pos.x, pos.y - 1)
down = Coordinate(pos.x, pos.y + 1)
corners = 0
if rev:
if is_inside_corner(left, up, area):
corners += 1
if is_inside_corner(left, down, area):
corners += 1
if is_inside_corner(right, up, area):
corners += 1
if is_inside_corner(right, down, area):
corners += 1
else:
if is_outside_corner(left, up, area) and is_not_double_corner(
left, up, other_plots, grid
):
corners += 1
if is_outside_corner(left, down, area) and is_not_double_corner(
left, down, other_plots, grid
):
corners += 1
if is_outside_corner(right, up, area) and is_not_double_corner(
right, up, other_plots, grid
):
corners += 1
if is_outside_corner(right, down, area) and is_not_double_corner(
right, down, other_plots, grid
):
corners += 1
return cornersTo then calculate how many sides a plot has, we create a new sub grid that is the rectangle area around a plot like I showed above.
We then find all the plots in this sub grid that are not our main plot.
We calculate the corners for our main area and count the “reverse corners” for all the other positions and sum them up.
def count_sides(area):
xs = [x for x, y in area]
ys = [y for x, y in area]
min_x, max_x = min(xs), max(xs)
min_y, max_y = min(ys), max(ys)
grid = {}
for y in range(min_y, max_y + 1):
for x in range(min_x, max_x + 1):
if (x, y) in area:
grid[Coordinate(x, y)] = "x"
else:
grid[Coordinate(x, y)] = "."
other_plots = [sub_area for sub_area in find_plots(grid) if sub_area != area]
sides = 0
# Outside sides
for pos in area:
sides += count_corners(pos, area, grid, other_plots)
# Inside sides
for other in other_plots:
for pos in other:
sides += count_corners(pos, area, grid, [], rev=True)
return sidesWe finally calculate the total cost by multiplying sides with areas:
def part_2():
inputs = read_input(12, str)
grid = create_grid(inputs)
plots = find_plots(grid)
cost = 0
for area in plots:
sides = count_sides(area)
cost += sides * len(area)
print(f"Part 2: {cost}")I’m happy I finally reached the solution and just in the nick of time as after finishing writing this piece, I’m heading out as we host an Advent of Code sprint with our local Python community archipylago today.
Being able to finish my own solution before the event frees me up to host the event and help new people get into Advent of Code instead of banging my head against the wall all night.