Advent of code 2024 - Day 12 of 25
Table of Contents
The twelfth day of Advent of Code was yesterday 12/12/2024! If you’re here for the first time today, don’t forget to read the posts about Day 1, Day 2, Day 3, Day 4, Day 5, Day 6, Day 7, Day 8, Day 9, Day 10 and Day 11.
I classified the twelfth problem as easy (part 1) and medium (part 2).
Tips#
- Another problem with mazes or character maps.
- You can build a zone by looking for identical elements in positions above, below, left, and right of the current node.
- Try to visualize the character map as a matrix. Now imagine each element as a node in a graph, connected to its neighbors.
- Remember to mark nodes already visited
- You can build a fence whenever the element in the direction being explored is different from the current element.
- In part 1, the area equals the number of elements in the same zone. To calculate the perimeter, you need to know how many barriers you placed in each position.
- Part 2 brings a different way to calculate the price, but the problem is very similar to part 1. Now, you need to look at all zone barriers and check how many are contiguous lines and columns.
- You can organize the lines by the y coordinate of their fences. Contiguous lines will have the same y coordinate value. If properly sorted, the next segment will be the next with an x position just 1 element larger than the previous one. This way, you can count contiguous lines.
- Columns follow the same principle, but now you need to sort the fences by x coordinate. Similarly, a column is contiguous if the next segment is in the next line.
- It’s easier to organize the data if horizontal and vertical fences are separated.
How much Python do you need to know?#
The chapters refer to my book Introduction to Programming with Python.
- Lists, dictionaries - Chapter 6
- Strings - Chapter 7
- Recursive functions - Chapter 8
- Classes - Chapter 10
- Part 2 requires some creativity to detect contiguous lines and columns.
Answer#
The answer to part 1 can be calculated by the Garden class. Part 2 is implemented by the GardenPart2 class, which is very similar to the first class but adds the complexity of knowing fence direction, counting lines and columns. With some effort, you could use the GardenPart2 class to solve both parts, but I think it’s more interesting to show a simple solution and then a more complex one.
Several maze drawing and dump functions were implemented; you can save the result of the zones with barriers to disk if you want.
import sys
import math
from helpers import (
string_to_list,
Vector2d,
Maze,
read_file_without_blank_lines,
)
INPUT = """
AAAA
BBCD
BBCC
EEEC
"""
TEST_INPUT_2 = """
OOOOO
OXOXO
OOOOO
OXOXO
OOOOO
"""
TEST_INPUT_3 = """
RRRRIICCFF
RRRRIICCCF
VVRRRCCFFF
VVRCCCJFFF
VVVVCJJCFE
VVIVCCJJEE
VVIIICJJEE
MIIIIIJJEE
MIIISIJEEE
MMMISSJEEE
"""
TEST_INPUT_PART_2_1 = """
EEEEE
EXXXX
EEEEE
EXXXX
EEEEE
"""
TEST_INPUT_PART_2_2 = """
AAAAAA
AAABBA
AAABBA
ABBAAA
ABBAAA
AAAAAA
"""
class Garden(Maze):
DIRECTIONS = [Vector2d(0, 1), Vector2d(1, 0), Vector2d(0, -1), Vector2d(-1, 0)]
def create_zones(self):
visited = set()
price = 0
for y, line in enumerate(self.maze):
for x, value in enumerate(line):
if (current := Vector2d(y, x)) in visited:
continue
visited.add(current)
area_perimeter = Vector2d(1, 0)
for direction in self.DIRECTIONS:
area_perimeter += self.visit(
value,
current + direction,
visited,
)
price += area_perimeter.x * area_perimeter.y
return price
def visit(
self, zone: str, position: Vector2d, visited: set[Vector2d]
) -> Vector2d:
area_perimeter = Vector2d(0, 0)
valid = self.valid_position(position)
if not valid or self[position] != zone:
area_perimeter += Vector2d(0, 1)
elif valid and self[position] == zone and position not in visited:
area_perimeter += Vector2d(1, 0)
visited.add(position)
for direction in self.DIRECTIONS:
area_perimeter += self.visit(
zone,
position + direction,
visited,
)
return area_perimeter
class Fence:
def __init__(self, position: Vector2d, direction: Vector2d):
self.position = position
self.direction = direction
def __hash__(self):
return hash(
f"{self.position.x},{self.position.y},{self.direction.x},{self.direction.y}"
)
def __str__(self):
return f"{self.position} D:{self.direction}"
def __repr__(self):
return f"<Fence {self}>"
def sort_key_x(self, max):
return f"{self.direction.x:0{max}}{self.direction.y:0{max}}{self.position.x:0{max}}{self.position.y:0{max}}"
def sort_key_y(self, max):
return f"{self.direction.x:0{max}}{self.direction.y:0{max}}{self.position.y:0{max}}{self.position.x:0{max}}"
class GardenPart2(Garden):
def __init__(self, maze: list[str]):
super().__init__(maze)
self.max = int(math.log10(max(self.max_x, self.max_y))) + 2
def lines(self, horizontal_fences: set[Vector2d]):
lines = 1
fences = sorted(list(horizontal_fences), key=lambda c: c.sort_key_y(self.max))
line = fences[0]
for i in range(1, len(fences)):
if (
fences[i].position.y != line.position.y
or fences[i].position.x - line.position.x > 1
or line.direction != fences[i].direction
):
lines += 1
line = fences[i]
return lines
def columns(self, vertical_fences: set[Vector2d]):
columns = 1
fences = sorted(
list(vertical_fences),
key=lambda c: c.sort_key_x(self.max),
)
column = fences[0]
for i in range(1, len(fences)):
if (
fences[i].position.x != column.position.x
or fences[i].position.y - column.position.y > 1
or column.direction != fences[i].direction
):
columns += 1
column = fences[i]
return columns
def create_zones(self):
visited = set()
price = 0
for y, line in enumerate(self.maze):
for x, value in enumerate(line):
if (current := Vector2d(y, x)) in visited:
continue
visited.add(current)
horizontal_fences = set()
vertical_fences = set()
area_perimeter = Vector2d(1, 0)
for direction in self.DIRECTIONS:
area_perimeter += self.visit(
value,
current + direction,
visited,
horizontal_fences,
vertical_fences,
direction,
)
price += area_perimeter.y * (
self.columns(vertical_fences) + self.lines(horizontal_fences)
)
return price
def visit(
self,
zone: str,
position: Vector2d,
visited: set[Vector2d],
horizontal_fences: set[Vector2d],
vertical_fences: set[Vector2d],
direction: Vector2d,
) -> Vector2d:
area_perimeter = Vector2d(0, 0)
valid = self.valid_position(position)
if not valid or self[position] != zone:
area_perimeter += Vector2d(0, 1)
if direction in [Vector2d(0, 1), Vector2d(0, -1)]:
vertical_fences.add(Fence(position, direction))
else:
horizontal_fences.add(Fence(position, direction))
elif valid and self[position] == zone and position not in visited:
area_perimeter += Vector2d(1, 0)
visited.add(position)
for direction in self.DIRECTIONS:
area_perimeter += self.visit(
zone,
position + direction,
visited,
horizontal_fences,
vertical_fences,
direction,
)
return area_perimeter
def draw(self):
self.my = 3
self.mx = 3
self.drawing = []
for _ in range(self.my * (self.max_y)):
self.drawing.append([" "] * (self.mx * (self.max_x)))
for y, line in enumerate(self.maze):
for x, value in enumerate(line):
self.drawing[y * self.my + 1][x * self.mx + 1] = value
def draw_fences(self, fences: set[Fence]):
for fence in fences:
py = fence.position.y - fence.direction.y
px = fence.position.x - fence.direction.x
cx = (px * self.mx + 1) + fence.direction.x
cy = (py * self.my + 1) + fence.direction.y
self.drawing[cy][cx] = (
"|" if fence.direction in [Vector2d(0, 1), Vector2d(0, -1)] else "―"
)
def dump_drawing(self, output=sys.stdout):
for line in self.drawing:
print("".join(line), file=output)
garden = Garden(string_to_list(INPUT))
price = garden.create_zones()
print("Price - input part 1 - test 1:", price)
assert price == 140
garden = Garden(string_to_list(TEST_INPUT_2))
price = garden.create_zones()
print("Price - input part 1 - test 2:", price)
assert price == 772
garden = Garden(string_to_list(TEST_INPUT_3))
price = garden.create_zones()
print("Price - input part 1 - test 3:", price)
assert price == 1930
input_part_1 = read_file_without_blank_lines("12/input.txt")
garden = Garden(string_to_list(input_part_1))
price = garden.create_zones()
print("Price - input part 1:", price)
assert price == 1396298
# Part 2
print()
garden = GardenPart2(string_to_list(INPUT))
price = garden.create_zones()
print("Price - input - part 2 - test 1:", price)
assert price == 80
garden = GardenPart2(string_to_list(TEST_INPUT_2))
price = garden.create_zones()
print("Price - input - part 2 - test 2:", price)
assert price == 436
garden = GardenPart2(string_to_list(TEST_INPUT_PART_2_1))
price = garden.create_zones()
print("Price - input - part 2 - test 2_1:", price)
assert price == 236
garden = GardenPart2(string_to_list(TEST_INPUT_PART_2_2))
price = garden.create_zones()
print("Price - input - part 2 - test 2_2:", price)
assert price == 368
garden = GardenPart2(string_to_list(TEST_INPUT_3))
price = garden.create_zones()
print("Price - input - part 2 - test 3:", price)
assert price == 1206
garden = GardenPart2(string_to_list(input_part_1))
price = garden.create_zones()
print("Price - input - part 2:", price)
assert price == 853588
Helper Module#
The unchanged parts were omitted.
from .files import one_list_per_line, read_file_without_blank_lines
from functools import total_ordering
def signal(x: int) -> int:
return 1 if x > 0 else -1 if x < 0 else 0
def string_to_list(input: str) -> list[str]:
return [line.strip() for line in input.splitlines() if line]
def string_to_matrix(input: str) -> list[list[str]]:
return [list(line.strip()) for line in input.splitlines() if line]
def string_to_int_matrix(input: str, separator=" ") -> list[list[int]]:
return [
[int(l) for l in line.split(separator)]
for line in input.splitlines()
if line
]
@total_ordering
class Vector2d:
def __init__(self, y, x):
self.x = x
self.y = y
def copy(self):
return Vector2d(self.y, self.x)
def __add__(self, other):
return Vector2d(self.y + other.y, self.x + other.x)
def __sub__(self, other):
return Vector2d(self.y - other.y, self.x - other.x)
def __str__(self):
return f"({self.y}, {self.x})"
def __repr__(self):
return f"Vector2d({self.y}, {self.x})"
def __hash__(self):
return hash(f"({self.y}, {self.x})")
def __eq__(self, other):
if isinstance(other, Vector2d):
return self.x == other.x and self.y == other.y
return False
def __le__(self, other):
return self.y < other.y or (self.y == other.y and self.x < other.x)
class Maze:
def __init__(self, maze):
self.max_y = len(maze)
self.max_x = len(maze[0])
self.orig_maze = maze
self.maze = [list(line) for line in maze]
def copy(self):
return Maze(self.orig_maze)
def valid_position(self, position: Vector2d) -> bool:
return 0 <= position.y < self.max_y and 0 <= position.x < self.max_x
def __str__(self):
return "\n".join(["".join(line) for line in self.maze])
def __setitem__(self, yx, value):
self.maze[yx[0]][yx[1]] = value
def __getitem__(self, yx):
if type(yx) is Vector2d:
return self.maze[yx.y][yx.x]
return self.maze[yx[0]][yx[1]]