In this final article on my experience with the Advent of Code event, I describe how I attacked grid and graph problems, and summarize how Java has worked out for me.
My humble solutions and utility code are at https://github.com/cayhorstmann/adventofcode2024. For a different perspective and commented solutions (also in Java), see this post by Arjen Wiersma. More Java solutions by Dashie, Michiel Graat, David Welguisz , and Balázs Zaicsek.
In my everyday programming experience, I don’t usually deal with two-dimensional grids filled with robots, obstacles, and the like. But these are a staple for Advent of Code problems. And why not? They are a source of all kinds of engaging behaviour. Escaping from a maze. Pushing multi-cellular objects until they hit obstacles. Displaying christmas trees. In the 2024 round, about half of the problems involved a grid.
It’s just a two-dimensional array of characters, char[][]. How hard can it be?
Actually, as it happens, I am an accidental expert in grids. Many years ago, I was a member of the AP CS development committee, which designs a course for high school students that is meant to be equivalent to an introductory computer science course at US universities. When I joined, the Marine Biology case study, designed by Alyce Brady of Kalamazoo College, reached the end of life because all plausible exam questions about fish in a grid had been asked. I thought that was a shame, because Julie Zelensky of Stanford University had produced a beautiful Swing app showing those fish in a grid. I ran with that and turned it into GridWorld, which lived on for another six years, delighting|torturing students with all sorts of actors in a grid. Rocks. Rock eaters. Robots. Whatever. And, it being Java, with Critters that have a well-defined life cycle.
What I learned from Alyce is that a grid API should not be centered around a 2D array and integer row/column coordinates. She designed classes Location and Direction to simplify grid navigation. A Location has row/column coordinates. It is valid in a grid if its coordinates are within the limits of the grid. That’s for the grid to decide. In an infinite grid, all locations are valid. In a bounded grid, they can’t step outside the bounds. The grid also controls neighbors. In a toroidal grid, neighbors wrap around the edges.
A Direction type encapsulates the eight compass directions N, NE, E, SE, S, SW, W, NW. In many grid problems, you only care about the main directions N, E, S, W, but it is not worth the trouble to have two separate types.
Having these as data types makes it easy to define useful methods: moving a location in a given direction, rotating a direction, and so on. At the time, these were both Java classes. Nowadays, Location is a record and Direction an enum.
In GridWorld, Grid<E> was a generic interface. You could have a Grid<Critter> with an implementing class for a bounded or unbounded grid. I have not yet seen an Advent of Code problem where this generality was useful. I am using a CharGrid class whose the elements are char values. That’s good enough for the AoC problems, where a typical grid looks like this:
############### #...#...#.....# #.#.#.#.#.###.# #S12..#.#.#...# ###3###.#.#.### ###4###.#.#...# ###5###.#.###.# ###6.E#...#...# ###.#######.### #...###...#...# #.#####.#.###.# #.#...#.#.#...# #.#.#.#.#.#.### #...#...#...### ###############
The CharGrid class has a bunch of useful methods. Get the valid neighbors of a location, either in the four main directions or in all directions. Find a location containing a character, or all such locations. And so on. And a static method for reading the grid from a file.
That’s what a class is for. It is natural place to add those useful methods. And a natural place to find them when one is needed. It’s basic object-oriented programming.
Does it work? It sure does. In AoC problems, I just call
CharGrid grid = CharGrid.parse(path);
and
Location start = grid.findFirst('S');
When I mouse over a grid in the debugger, I get a nicely formatted grid, thanks to the provided toString method.
One concern that I had when building out the API was when to return sets and when to return streams. I ended up using sets when they were small and streams when they could potentially be large, to prepare for sparse or unbounded grids in the future. For example,
Stream<Location> locations()
returns all valid locations in the grid, which could be large or infinite, but
Set<Location> sameNeighbors(Location p)
returns the locations of the neighbors with the same content as p, of which there can be at most four.
My day job is computationally pretty boring. Get data from here and there, transform as necessary, and put the results where they belong.
But in AoC, you have to find optimal solutions, or count feasible solutions, in intricate situations where brute force doesn’t always cut it. Each puzzle has two parts. and sometimes brute force works in the first part, but then you see the input for the second part (which is only revealed after you provided the correct answer for the first part). Often, you must find a new and more efficient plan of attack.
Standard graph algorithms can be very helpful. Finding shortest paths. Finding all paths without cycles. Or connected components. Of course, since most programmers’ day jobs don’t involve these algorithms, one can’t expect help from the core Java API.
I looked around for good graph algorithm libraries. There were not many choices. JGraphT looks promising, but also a tad complicated. Which is, of course, not uncommon for a professional library.
So I decided to reimplement the algorithms that I learned, way, way back, in graduate school. I enjoyed doing it, and after all, that’s why I participate in AoC—to learn techniques outside my comfort zone.
My first idea was to have a class UndirectedGraph and DirectedGraph and DirectedGraphWithEdgeWeights and so on. With a common Graph interface. That’s similar to what JGraphT does.
But as I wrote ad-hoc puzzle solutions, I noticed that I never needed a graph class. For most of the algorithms, I only needed to compute neighbors of a given vertex. A simple function of the type
V → Set<V>
suffices, where V is the vertex type. For example, consider breadth first search, where you find neighbors, starting from a root vertex.
public static <V> SequencedMap<V, V> bfs(V root, Function<V, Set<V>> neighbors) {
var parents = new LinkedHashMap<V, V>();
Set<V> discovered = new HashSet<V>();
discovered.add(root);
parents.put(root, null);
Queue<V> q = new LinkedList<V>();
q.add(root);
while (!q.isEmpty()) {
V p = q.remove();
for (V n : neighbors.apply(p)) {
if (discovered.add(n)) {
parents.put(n, p);
q.add(n);
}
}
}
return parents;
}
A common task is finding all locations that are reachable from a given location in a grid where . indicates an empty space and # a wall. Simply call
var parents = Graphs.bfs(start, grid::sameNeighbors) var reachable = parents.keySet();
Sometimes, the neighbor function is more involved, due to the nature of the problem, but I found it always easier to write a function than to populate a graph object. After all, how would you fill up a graph with vertices and edges? Most commonly, you add a vertex, then its neighbors, and so on. That’s in itself a breadth-first search.
I use the same approach with other graph utilities. For example,
var paths = Graphs.simplePaths(start, end, this::neighbors);
finds all hiking trails in Day 10. Here,
List<Location> neighbors(Location p)
is a function giving the neighboring locations in the arcane context of that puzzle.
In some graphs, edges have weights. In a classical graph library, there would be an Edge class with a method to get the weight. Or the edge type could be a type parameter, and a weighted graph has edge type Integer. In my code, I instead use a function
(V, V) → int
In Dikstra’s algorithm for computing the costs of the shortest paths from a given root, both a neighbor and a cost function are needed. Day 16 is a typical example. A reindeer needs to find a path through a maze, moving forward or turning 90 degrees. Turning is much more expensive than moving, though.
The standard trick for modeling such a situation is to define a suitable state space. The reindeer’s position is described by its location and direction. A move either visits the next location, or rotates the direction.
record Position(Location loc, Direction dir) {
Set<Position> next() {
var result = new HashSet<Position>();
result.add(new Position(loc, dir.turn(2)));
result.add(new Position(loc, dir.turn(6)));
Location n = loc.moved(dir);
if (grid.isValid(n) && grid.get(n) != '#') result.add(new Position(n, dir));
return result;
}
int cost(Position q) {
if (q.loc == loc) {
int t = dir.turnsTo(q.dir); // 45 degree turns
if (t == 2 || t == 6) return 1000;
} else if (q.loc.equals(loc.moved(dir)) && q.dir == dir)
return 1;
throw new IllegalArgumentException("Should not need cost from " + this + " to " + q);
}
}
Now simply call:
var costs = Graphs.dijkstraCosts(startPos, Position::next, Position::cost);
By the way, note how the Position record provides a great place for the next and cost methods. That’s why I love records.
In Day 23, I would have been better off using JGraphT, which has an implementation of a clique-finding algorithm. It turned out easy enough to do it by hand, but of course it is always better to use a previously debugged implementation.
Otherwise, I found my non-OO approach quite effective. I was, however, considering whether I should make classes for some of the algorithms. For example, the internal data structures of Dijkstra’s algorithm yield useful information about the costs of the shortest paths, as well as the paths themselves. I ended up with two methods dijkstraCosts and dijkstraPaths, but what if you want both?
In general, I was very happy with Java for solving the AoC puzzles. The tooling is great, and the resulting code is organized and readable, even though it was produced in a hurry. But there were a few nits.
long for most numerical results because int overflows too quickly. But it is a pain refactoring from int to long when it is needed in part 2 of a puzzle. I lived in fear of having to refactor to BigInteger, but fortunately that was not necessary in 2024.int to char require casts. Normally, I stay away from char, but for AoC I use them with CharGrid. And error messages can be confusing in the middle of an IntStream pipeline. Maybe a grid of code points next year?char, int, long, boolean types all the time. The Character, Integer, Long, Boolean wrapper types are a bit of a pain. I can’t wait for Valhalla.Position record from the preceding section. Its methods access a grid instance, which must be declared as
static CharGrid grid;
I am trying to use streams with taste and restraint. But sometimes, I just want a simple filtering or mapping operation, and that gets awfully verbose:
locations = locations.stream().filter(n -> grid.get(n) == grid.get(loc) + 1).collect(Collectors.toSet()); locations = locations.stream().map(l -> l.moved(d)).collect(Collectors.toSet());
I wish there were filtered and mapped methods in the Set interface. Or a toSet terminal stream operation. I would also like methods for set union, intersection, and difference that don’t mutate (unlike addAll, retainAll, removeAll)
Turning a local instance of a generic type to a field, or the other way around, is a bit awkward:
var costs = new Map<String, Integer>();⇔
Map<String, Integer> costs = new HashMap<>();
In Python, you don’t have those issues. But you also don’t have compile-time typing. I can’t count the number of times that I was saved from runtime errors because the compiler reported a type error that I fixed in an instant.
For the first few days, I was a bit envious of the brevity of Python or Scala. But as the puzzles got harder, the programming language mattered less. The most important skill was to move away from the computer, sit on a comfortable chair with pencil and paper, and think through what one is actually supposed to do, and how to do it efficiently.
Here are some of the lessons that I learned from doing Advent of Code in Java.
With a Mastodon account (or any account on the fediverse), please visit this link to add a comment.
Thanks to Carl Schwann for the code for loading the comments.
Not on the fediverse yet? Comment below with Talkyard.
