Dazbo's Advent of Code solutions, written in Python

Day 12: Hill Climbing Algorithm

BFS and Path AlgorithmsComprehensionClassesMatplotlib

About this time every year, we find AoC starts to itensify. And sometimes you get a problem where you either:

*just know*how to do it, and it’s easy.*have no idea*, and it’s a nightmare.

For me, yesterday was a bit of a nightmare. But today was a relief because I do like a BFS problem!! A couple of years ago, I didn’t know my way around path-solving algorithms, and a problem like this one would have taken me forever. So it’s quite satisfying to be able to deploy knowledge acquired as a result of previous time and effort.

If you don’t know anything about algorithms like BFS, Dijkstra’s, and A*, then YOU NEED TO LOOK AT MY GUIDE. Honestly, it will totally change AoC experience!

Okay, so today’s problem…

Our input is a grid of elevation data. Elevation is represented by `a-z`

,
where `a`

is the lowest possible elevation, and `z`

is the higest possible elevation.

The input data looks like this:

```
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
```

`S`

is our *start* position and `E`

is our goal.

From `S`

, we can move to any adjacent position by moving left, right, up, or down; but only if the adjacent position’s elevation is less than or equal to: our current elevation, plus 1.

**What is the fewest steps required to move from your current position to the location that should get the best signal?**

This is a pretty simple BFS!! Check my guide for how BFS works.

First, a bit of importing, and a `Point`

class:

```
from __future__ import annotations
from collections import deque
from copy import deepcopy
from dataclasses import dataclass
from pathlib import Path
import time
SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
@dataclass(frozen=True)
class Point():
""" Point class, which knows how to return a list of all adjacent coordinates """
x: int
y: int
def neighbours(self) -> list[Point]:
""" Return all adjacent orthogonal (not diagonal) Points """
return [Point(self.x+dx, self.y+dy) for dx in range(-1, 2)
for dy in range(-1, 2)
if abs(dy) != abs(dx)]
```

Note that this `Point`

class is able to return a list of all its neighbours. It does this with a *list comprehension*.

Next, our `Grid`

class:

```
class Grid():
""" 2D grid of point values. """
def __init__(self, grid_array: list[str]) -> None:
""" Generate Grid instance from 2D array.
This works on a deep copy of the input data, so as not to mutate the input. """
self.array = deepcopy(grid_array) # Store a deep copy of input data
self.x_size = len(self.array[0])
self.y_size = len(self.array)
self.start = self._get_point_for_elevation("S")
self.goal = self._get_point_for_elevation("E")
def _all_points(self) -> list[Point]:
points = [Point(x, y) for x in range(self.x_size) for y in range(self.y_size)]
return points
def _get_point_for_elevation(self, x: str) -> Point:
""" Use this to find the point where "S" or "E" are located. """
assert x in ("S", "E"), "Specified point must be Start or End!"
for row_num, row in enumerate(self.array):
if x in row:
return Point(row.index(x), row_num)
def elevation_at_point(self, point: Point) -> int:
""" Elevation value at this point """
if point not in (self.start, self.goal):
return ord(self.array[point.y][point.x])
if point == self.start:
return ord("a") # we're told start location is elevation a
if point == self.goal:
return ord("z") # we're told start location is elevation z
def _point_in_grid(self, point: Point) -> bool:
""" Check if a location is within the grid """
if (0 <= point.x < self.x_size and 0 <= point.y < self.y_size):
return True
return False
def _valid_neighbours(self, location:Point):
""" Yield adjacent neighbour points.
We can move L, R, U, D by one unit. But we can only move to locations that
are no more than one higher than current elevation. """
current_elevation = self.elevation_at_point(location)
for neighbour in location.neighbours():
if self._point_in_grid(neighbour):
if self.elevation_at_point(neighbour) <= current_elevation + 1:
yield neighbour
def get_path(self, start: Point):
""" Given a start point, determine best path to reach the goal specified by 'E'.
Returns: list of points that make up the path
or: None, if no valid path from this start point.
"""
points_to_assess: deque[Point] = deque() # Points we want to get value of, and get neighbours for
points_to_assess.append(start) # where we start
came_from = {}
came_from[start] = None
while points_to_assess: # They should only ever be valid points
current = points_to_assess.popleft()
if current == self.goal: # We've reached the end
break
for neighbour in self._valid_neighbours(current):
if neighbour not in came_from: # We will need to assess this point
points_to_assess.append(neighbour)
came_from[neighbour] = current
# build the breadcrumb path
current = self.goal
path = []
while current != start:
path.append(current)
current = came_from[current]
return path
def __repr__(self) -> str:
return "\n".join("".join(map(str, row)) for row in self.array)
```

A few points about the above code:

`_point_in_grid()`

is used to check if a point is within the grid.`_valid_neighbours()`

iterates through the*neighbours*of our point, and checks whether this neighbour is*valid*, given the rules about elevation.`get_path()`

works by:- Performing a BFS from
`S`

to`E`

. - Uses a
`dictionary`

to explore the explored points, and to build the breadcrumb trail.

- Performing a BFS from

Now we solve as follows:

```
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
grid = Grid(data)
# Part 1
path = grid.get_path(grid.start)
p1_length = len(path)
print(f"Part 1: {p1_length}")
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
```

Easy when you know how!

**What is the fewest steps required to move starting from any square with elevation a to the location that should get the best signal?**

*“Oh awesome!”*, I thought to myself. All I need to do is:

- Get a list of all the points with elevation
`a`

. - Perform exactly the same BFS, but using each new start location, rather than
`S`

.

So, that’s what I did. It worked straight away with the sample code. And then throw an exception with the real data. Doh!!

It turns out there’s a small gotcha, which took me quite a few minutes to debug. It turns out that many of the `a`

start locations in the real data *DO NOT HAVE SOLUTIONS*. So we need to handle that situation.

Here are my changes to solve this part…

First, we add this method to our `Grid`

class:

```
def all_lowest_elevation_points(self) -> set[Point]:
low_points = {point for point in self._all_points()
if self.array[point.y][point.x] == "a"
or self.array[point.y][point.x] == "S"}
return low_points
```

Then we need to handle the “no solution” scenario. We just add this code in the `get_path()`

method,
before building our breadcrumbs.

```
if current != self.goal:
return None # No valid path from this point
```

Then we just add this to our `main()`

method:

```
# Part 2
start_points = grid.all_lowest_elevation_points()
p2_length = p1_length
for start in start_points:
path = grid.get_path(start)
if path:
p2_length = min(p2_length, len(path))
print(f"Part 2: {p2_length}")
```

The final code:

```
from __future__ import annotations
from collections import deque
from copy import deepcopy
from dataclasses import dataclass
from pathlib import Path
import time
SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
@dataclass(frozen=True)
class Point():
""" Point class, which knows how to return a list of all adjacent coordinates """
x: int
y: int
def neighbours(self) -> list[Point]:
""" Return all adjacent orthogonal (not diagonal) Points """
return [Point(self.x+dx, self.y+dy) for dx in range(-1, 2)
for dy in range(-1, 2)
if abs(dy) != abs(dx)]
class Grid():
""" 2D grid of point values. """
def __init__(self, grid_array: list[str]) -> None:
""" Generate Grid instance from 2D array.
This works on a deep copy of the input data, so as not to mutate the input. """
self.array = deepcopy(grid_array) # Store a deep copy of input data
self.x_size = len(self.array[0])
self.y_size = len(self.array)
self.start = self._get_point_for_elevation("S")
self.goal = self._get_point_for_elevation("E")
def _all_points(self) -> list[Point]:
points = [Point(x, y) for x in range(self.x_size) for y in range(self.y_size)]
return points
def all_lowest_elevation_points(self) -> set[Point]:
low_points = {point for point in self._all_points()
if self.array[point.y][point.x] == "a"
or self.array[point.y][point.x] == "S"}
return low_points
def _get_point_for_elevation(self, x: str) -> Point:
""" Use this to find the point where "S" or "E" are located. """
assert x in ("S", "E"), "Specified point must be Start or End!"
for row_num, row in enumerate(self.array):
if x in row:
return Point(row.index(x), row_num)
def elevation_at_point(self, point: Point) -> int:
""" Elevation value at this point """
if point not in (self.start, self.goal):
return ord(self.array[point.y][point.x])
if point == self.start:
return ord("a") # we're told start location is elevation a
if point == self.goal:
return ord("z") # we're told start location is elevation z
def _point_in_grid(self, point: Point) -> bool:
""" Check if a location is within the grid """
if (0 <= point.x < self.x_size and 0 <= point.y < self.y_size):
return True
return False
def _valid_neighbours(self, location:Point):
""" Yield adjacent neighbour points.
We can move L, R, U, D by one unit. But we can only move to locations that
are no more than one higher than current elevation. """
current_elevation = self.elevation_at_point(location)
for neighbour in location.neighbours():
if self._point_in_grid(neighbour):
if self.elevation_at_point(neighbour) <= current_elevation + 1:
yield neighbour
def get_path(self, start: Point):
""" Given a start point, determine best path to reach the goal specified by 'E'.
Returns: list of points that make up the path
or: None, if no valid path from this start point.
"""
points_to_assess: deque[Point] = deque() # Points we want to get value of, and get neighbours for
points_to_assess.append(start) # where we start
came_from = {}
came_from[start] = None
while points_to_assess: # They should only ever be valid points
current = points_to_assess.popleft()
if current == self.goal: # We've reached the end
break
for neighbour in self._valid_neighbours(current):
if neighbour not in came_from: # We will need to assess this point
points_to_assess.append(neighbour)
came_from[neighbour] = current
if current != self.goal:
return None # No valid path from this point
# build the breadcrumb path
current = self.goal
path = []
while current != start:
path.append(current)
current = came_from[current]
return path
def __repr__(self) -> str:
return "\n".join("".join(map(str, row)) for row in self.array)
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
grid = Grid(data)
# Part 1
path = grid.get_path(grid.start)
p1_length = len(path)
print(f"Part 1: {p1_length}")
# Part 2
start_points = grid.all_lowest_elevation_points()
p2_length = p1_length
for start in start_points:
path = grid.get_path(start)
if path:
p2_length = min(p2_length, len(path))
print(f"Part 2: {p2_length}")
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
```

And the output looks like this:

```
Part 1: 472
Part 2: 465
Execution time: 4.0638 seconds
```

In retrospect, it was really dumb for me to solve Part 2 but running a BFS for EVERY `a`

location. It would be much faster to run the BFS *once*, storing the path from the `E`

to every `a`

. Then we can simply print the lengths of the valid paths to each `a`

.

So here’s the amended code:

```
SCRIPT_DIR = Path(__file__).parent
# INPUT_FILE = Path(SCRIPT_DIR, "input/sample_input.txt")
INPUT_FILE = Path(SCRIPT_DIR, "input/input.txt")
@dataclass(frozen=True)
class Point():
""" Point class, which knows how to return a list of all adjacent coordinates """
x: int
y: int
def neighbours(self) -> list[Point]:
""" Return all adjacent orthogonal (not diagonal) Points """
return [Point(self.x+dx, self.y+dy) for dx in range(-1, 2)
for dy in range(-1, 2)
if abs(dy) != abs(dx)]
class Grid():
""" 2D grid of point values. """
def __init__(self, grid_array: list[str]) -> None:
""" Generate Grid instance from 2D array.
This works on a deep copy of the input data, so as not to mutate the input. """
self.array = grid_array # Store a deep copy of input data
self.x_size = len(self.array[0])
self.y_size = len(self.array)
self.start = self._get_point_for_elevation("S")
self.goal = self._get_point_for_elevation("E")
def _all_points(self) -> list[Point]:
points = [Point(x, y) for x in range(self.x_size) for y in range(self.y_size)]
return points
def all_lowest_elevation_points(self) -> set[Point]:
low_points = {point for point in self._all_points()
if self.array[point.y][point.x] == "a"
or self.array[point.y][point.x] == "S"}
return low_points
def _get_point_for_elevation(self, x: str) -> Point:
""" Use this to find the point where "S" or "E" are located. """
assert x in ("S", "E"), "Specified point must be Start or End!"
for row_num, row in enumerate(self.array):
if x in row:
return Point(row.index(x), row_num)
def elevation_at_point(self, point: Point) -> int:
""" Elevation value at this point """
if point not in (self.start, self.goal):
return ord(self.array[point.y][point.x])
if point == self.start:
return ord("a") # we're told start location is elevation a
if point == self.goal:
return ord("z") # we're told start location is elevation z
def _point_in_grid(self, point: Point) -> bool:
""" Check if a location is within the grid """
if (0 <= point.x < self.x_size and 0 <= point.y < self.y_size):
return True
return False
def _valid_neighbours(self, location:Point):
""" Yield adjacent neighbour points.
We can move L, R, U, D by one unit. But we can only move to locations that
are no more than one higher than current elevation. """
current_elevation = self.elevation_at_point(location)
for neighbour in location.neighbours():
if self._point_in_grid(neighbour):
if self.elevation_at_point(neighbour) <= current_elevation + 1:
yield neighbour
def get_breadcrumbs(self, end: Point) -> dict[Point, Point]:
""" Given the start point, find all paths to destination. """
points_to_assess: deque[Point] = deque() # Points we want to get value of, and get neighbours for
points_to_assess.append(end) # where we start
came_from = {}
came_from[end] = None
# BFS with no goal
while points_to_assess: # They should only ever be valid points
current = points_to_assess.popleft()
for neighbour in self._valid_neighbours(current):
if neighbour not in came_from: # We will need to assess this point
points_to_assess.append(neighbour)
came_from[neighbour] = current
return came_from
@staticmethod
def create_path(breadcrumbs: dict[Point, Point], start: Point, goal: Point):
""" Calculate the path from goal to start, as list of Points.
Return None if no valid path. """
path = []
current = goal # we need to walk backwards from destination to start
while current != start:
path.append(current)
if current in breadcrumbs:
current = breadcrumbs[current]
else:
return None
return path
def __repr__(self) -> str:
return "\n".join("".join(map(str, row)) for row in self.array)
def main():
with open(INPUT_FILE, mode="rt") as f:
data = f.read().splitlines()
grid = Grid(data)
breadcrumbs = grid.get_breadcrumbs(grid.start) # every path to every point
# Part 1
path = grid.create_path(breadcrumbs, grid.start, grid.goal) # from 'S' to 'E'
print(f"Part 1: {len(path)}")
# Part 2
best_path = path
for goal in grid.all_lowest_elevation_points(): # Going to all 'a'
if goal in breadcrumbs:
path = grid.create_path(breadcrumbs, goal, grid.goal) # from 'a' to 'E'
if path:
if len(path) < len(best_path):
best_path = path
print(f"Part 2: {len(best_path)}")
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"Execution time: {t2 - t1:0.4f} seconds")
```

It is indeed much faster!

```
Part 1: 472
Part 2: 465
Execution time: 0.3467 seconds
```

Let’s add a quick visualisation. It’s very easy. I just added this:

```
def render_as_plt(grid, path):
""" Render the display as a scatter plot """
x_vals = [point.x for point in grid.all_points()]
y_vals = [point.y for point in grid.all_points()]
path_x = [point.x for point in path]
path_y = [point.y for point in path]
axes = plt.gca()
axes.set_aspect('equal')
axes.set_xlim(min(x_vals)-1, max(x_vals)+1)
axes.set_ylim(min(y_vals)-1, max(y_vals)+1)
axes.invert_yaxis()
axes.scatter(x_vals, y_vals, marker="o", s=5, color="black")
axes.scatter(path_x, path_y, marker="o", s=5, color="red")
plt.show()
```

Here’s what it looks like: