Attention!

• Check Advent of Code for the full challenge details. They created everything we need to know about the challenge - give them your support.

• My solutions are not ‘the’ solutions - I target one of the possible solutions. They might not be the most efficient, but they are a way to solve the problem. I do not plan to spend too much time the challenges.

• Every challenge = different language - just for fun and learning.

• I do not include the input data, but you can find it on the Advent of Code website or in the repository of the code.

---

For today’s Advent of Code challenge, I faced a problem involving topographic maps and hiking trails, where the goal was to identify trails on a map based on height values. The map’s values ranged from 0 to 9, with each trail requiring an increase of exactly 1 in height as we move in one of four directions: up, down, left, or right.

Part One: Trailhead Scores

The first part asks us to find all “trailheads,” or starting points with a height of 0, and calculate the score of each trailhead. The score of a trailhead is the number of reachable height 9 locations via valid hiking trails, where the trail always increases by exactly 1 at each step.

Part Two: Trailhead Ratings

In the second part, the focus shifts from scoring to calculating ratings. The rating of a trailhead is determined by counting the number of distinct hiking trails that begin at that trailhead, i.e., all paths that start at height 0 and end at height 9.

Approach

I implemented the solution in Java, and the problem required several key steps to be tackled:

1. Input Parsing: The topographic map is given as a grid of numbers, which I read in from a file. This grid would serve as the representation of the area, with each value indicating the height at that position.

2. Trail Search: For each trailhead (cells with a height of 0), I needed to search for all possible hiking trails starting from that point. A trail continues to the next cell if the height increases by exactly 1.

3. Breadth-First Search (BFS): I used BFS to explore each trail to be sure that I only traverse valid paths where the height increment is exactly 1. BFS is ideal here because it naturally handles the exploration of all possible trails from a given point.

4. Trailhead Scoring: For Part One, I calculated how many height 9 positions were reachable from each trailhead and summed these values to get the total score for all trailheads.

5. Trailhead Rating: For Part Two, I counted the distinct trails for each trailhead by looking at all reachable height 9 positions and counting the number of unique trails leading to them.

---

Solution Overview

1. Grid Representation: The grid is read from an input file and stored as a 2D array of integers. Each cell represents a height, with values between 0 (lowest) and 9 (highest). Each cell in the grid is represented by a pair of coordinates (x, y), for which I created a custom class IntPair to handle the coordinates and operations on them (I used it also for the result of the trail search but it’s not important).

// main.java
// method in the Main class
public static int[][] readGrid() {
    Path path = Paths.get(filename);
    try {
        List<String> lines = Files.readAllLines(path);
        return lines.stream()
                    .map(line -> line.chars().map(Character::getNumericValue).toArray())
                    .toArray(int[][]::new);
    } catch (IOException e) {
        e.printStackTrace();
        return null;
    }
}

// main.java
class IntPair {
    int x;
    int y;
    IntPair(int x, int y) {
        this.x = x; this.y = y;
    }

    IntPair add(IntPair other) {
        return new IntPair(this.x + other.x, this.y + other.y);
    }

    void addTo(IntPair other) {
        this.x += other.x;
        this.y += other.y;
    }

    // Override equals and hashCode for use in sets...
}

2. Trail Search with BFS: For each trailhead (a cell with height 0), I used a queue to explore all reachable positions using BFS. I only added adjacent cells where the height increased by exactly 1.

// main.java
// method in the Main class
public static IntPair lookForTrails(IntPair start, int gridX, int gridY) {
    Set<IntPair> trails = new HashSet<>();
    Queue<IntPair> queue = new ArrayDeque<>();

    queue.add(start);
    int trailsCount = 0;

    while (!queue.isEmpty()) {
        IntPair current = queue.poll();
        int currentValue = grid[current.x][current.y];
        if (currentValue == 9) {
            trails.add(current);
            trailsCount++;
            continue;
        }
        for (IntPair direction : directions) {
            IntPair next = current.add(direction);
            if (!inBounds(gridX, gridY, next)) continue;
            if (grid[next.x][next.y] != currentValue + 1) continue;
            queue.add(next);
        }
    }
    return new IntPair(trails.size(), trailsCount);
}

3. Trailhead Scoring and Rating:
   • In Part One, I computed the total number of reachable height 9 cells for each trailhead and summed them up to get the total score.
   • In Part Two, I counted how many distinct hiking trails could reach each trailhead’s reachable height 9 cells, and summed the counts to get the total trailhead rating.

// main.java
// method in the Main class
public static void main(String[] args) {
    grid = readGrid();
    if (grid == null) return;
    int gridX = grid.length;
    int gridY = grid[0].length;

    IntPair trails = new IntPair(0, 0);

    for (int row = 0; row < gridX; row++)
    for (int col = 0; col < gridY; col++) {
        if (grid[row][col] != 0) continue;
        IntPair start = new IntPair(row, col);
        trails.addTo(lookForTrails(start, gridX, gridY));
    }
    System.out.println("Total number of trails: " + trails.x);
    System.out.println("Total ratings of trails: " + trails.y);
}

---

Final Solution Code

The final solution code can be found on my GitHub repository.

If you like the content, don’t forget to give it a star ⭐.

---

Conclusion

This was a fun and not so challenging problem, where I combined breadth-first search (BFS) and set operations to track hiking trails and calculate trailhead scores and ratings. The problem’s structure helped reinforce key algorithmic concepts like BFS and pathfinding in grids.

I enjoyed solving this one using Java. I need to practice more with it. I think I like Kotlin more, but Java is still a good language to know.

Tomorrow, I plan to try solving the next puzzle with Ruby.