Advent of Code 2024 - Day 10 of 25
Table of Contents
The tenth day of Advent of Code was yesterday 12/10/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 and Day 9.
I classified the tenth problem as easy (part 1) and easy (part 2). The problem is very similar to day 4.
Tips#
-
You can start looking for paths when you find ‘0’ in the maze.
-
The problem defines that the path can be made in 4 directions: up, down, left, and right. Diagonals are not allowed.
-
As we did in other problems, you can use vectors to represent path directions.
-
For each possible direction, you must check if the coordinate is valid and if the value corresponds to the next step in the path. This search repeats until you find ‘9’.
-
The problem provides several test vectors. Use them to validate your functions.
-
For part 1, you only need to count how many unique ‘9’s you can reach from the starting ‘0’. To know if the found ‘9’ is unique, you can use a dictionary or set with the ‘9’ coordinate as the key/element.
-
You should consider that each path can reach the same destination more than once, as it can change direction in the next step but arrive at the same place. For part 2, you’ll need to know how many paths from 0 to 9 were made.
How much Python do you need to know?#
The chapters refer to my book Introduction to Programming with Python.
- Lists, tuples - Chapter 6
- Strings - Chapter 7
- Recursive functions - Chapter 8
Answer#
from aux import (
Maze,
string_to_matrix,
Vector2d,
read_file_without_blank_lines,
)
class Island(Maze):
DIRECTIONS = (
Vector2d(1, 0),
Vector2d(0, 1),
Vector2d(0, -1),
Vector2d(-1, 0),
)
def trail_starts(self):
trail_head = []
for y, line in enumerate(self.maze):
for x, c in enumerate(line):
if c == "0":
trail_head.append(Vector2d(y, x))
return trail_head
def search_trail(self, start, current="0"):
heads = {}
if (current_pos := self.maze[start.y][start.x]) != current:
return None
elif current_pos == "9":
return {start: 1}
for direction in self.DIRECTIONS:
next_pos = start + direction
if self.valid_position(next_pos):
found = self.search_trail(next_pos, str(int(current) + 1))
if found:
for head in found:
heads[head] = (
heads.setdefault(head, 0) + found[head]
)
return heads
def find_trails(input_data):
island = Island(string_to_matrix(input_data))
part1, part2 = 0, 0
for start in island.trail_starts():
heads = island.search_trail(start)
part1 += len(heads)
part2 += sum(heads.values())
return part1, part2
INPUT = """
0123
1234
8765
9876
"""
INPUT2 = """
...0...
...1...
...2...
6543456
7.....7
8.....8
9.....9
"""
INPUT3 = """
..90..9
...1.98
...2..7
6543456
765.987
876....
987....
"""
INPUT4 = """
10..9..
2...8..
3...7..
4567654
...8..3
...9..2
.....01
"""
INPUT5 = """
89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732
"""
found, _ = find_trails(INPUT)
print("Test 1 - part 1:", found)
assert found == 1
found, _ = find_trails(INPUT2)
print("Test 2 - part 1:", found)
assert found == 2
found, _ = find_trails(INPUT3)
print("Test 3 - part 1:", found)
assert found == 4
found, _ = find_trails(INPUT4)
print("Test 4 - part 1:", found)
assert found == 3
found, _ = find_trails(INPUT5)
print("Test 5 - part 1:", found)
assert found == 36
INPUT_PART_1 = read_file_without_blank_lines("10/input.txt")
found, _ = find_trails(INPUT_PART_1)
print("Input - part 1:", found)
assert found == 667
# Part 2
INPUT_PART_2_1 = """
.....0.
..4321.
..5..2.
..6543.
..7..4.
..8765.
..9....
"""
INPUT_PART_2_2 = """
..90..9
...1.98
...2..7
6543456
765.987
876....
987....
"""
INPUT_PART_2_3 = """
012345
123456
234567
345678
4.6789
56789.
"""
INPUT_PART_2_4 = """
89010123
78121874
87430965
96549874
45678903
32019012
01329801
10456732
"""
_, found = find_trails(INPUT_PART_2_1)
print("Test 1 - part 2:", found)
assert found == 3
_, found = find_trails(INPUT_PART_2_2)
print("Test 2 - part 2:", found)
assert found == 13
_, found = find_trails(INPUT_PART_2_3)
print("Test 3 - part 2:", found)
assert found == 227
_, found = find_trails(INPUT_PART_2_4)
print("Test 4 - part 2:", found)
assert found == 81
_, found = find_trails(INPUT_PART_1)
print("Input - Part 2:", found)
assert found == 1344
# Output
# Test 1 - part 1: 1
# Test 2 - part 1: 2
# Test 3 - part 1: 4
# Test 4 - part 1: 3
# Test 5 - part 1: 36
# Input - part 1: 667
# Test 1 - part 2: 3
# Test 2 - part 2: 13
# Test 3 - part 2: 227
# Test 4 - part 2: 81
# Input - Part 2: 1344
Aux module#
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
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):
return self.maze[yx[0]][yx[1]]
def read_file_without_blank_lines(filename: str) -> str:
return "\n".join(
zz
for line in read_file(filename).splitlines()
if len(zz := line.strip()) > 0
)