It is December again and that means it is time for the Advent of Code. Due to my workload and family obligations I will probably not be able to get very far this year, but still I wanted to write a post about it.

This year I am using Java, together with my students. My goal is to write as modern as possible Java, which means using streams and new language constructs where possible.

Day 1

In day 1 we are parsing 2 lists of numbers, with the lists printed vertically. This means each line has 2 numbers, one for list one and the other for list two. To parse these data structures I used a very nice stream where I map each line onto a String[] using split.

To be sure that the input is valid, the peek method allows you to check if the result is what you intended, and otherwise an exception will terminate everything. From here I map the String[] into a Pair record which holds the 2 numbers. Streaming over the resulting pairs the left and right lists can be extracted quite easily.

I loved this approach, it is very straightforward and does not have a lot of control flow.

@Override
public List<List<Integer>> parseInput(List<String> input) {
    var pairs = input.stream()
        .map(s -> s.split("\\s+"))
        .peek(parts -> {
                if (parts.length != 2)
                    throw new IllegalArgumentException("Invalid input format");
            })
        .map(parts -> new Pair<>(Integer.parseInt(parts[0]), Integer.parseInt(parts[1])))
        .collect(Collectors.toList());

    var left = pairs.stream()
        .map(Pair::left)
        .collect(Collectors.toList());

    var right = pairs.stream()
        .map(Pair::right)
        .collect(Collectors.toList());

    return List.of(left, right);
}

Solving the problem with these lists was quite easy. In part 2 there was a need for a frequency table of a list. I also found a very nice solution to that problem using the groupingBy method from Collectors.

input.get(1).stream()
    .collect(Collectors.groupingBy(n -> n, Collectors.counting()));

Day 2

I really liked day 2, the first part was quite straightforward. You have to identify increment or decrement only lists and apply some conditions to them.

Part 2 was much more interesting, here you have to account for fault tolerance. In the Python implementations that were posted the common solution is to concatenate 2 parts of the array and then rerun the validation logic.

Using streams we can something very similar. First we use an IntStream to iterate over every int[] (report). Then for every int in that report, we construct a new array by filtering out the index of the current item. After that it is a simple case of determining increment or decrement and applying the conditional logic.

Suppose you have a list of [1,2,4,7], while iterating it will first hit index 0, the filter will prevent that entry from continuing. Next 1 through 3 will continue and as a result of toArray() a new array will be constructed with only those items.

x == 0
     |    map ------.
     v  -------     v
    [1, 2, 4, 7]    [2,4,7]

input.stream()
    // Loop over the list
    .filter(in -> IntStream.range(0, in.length) // take a report
            // for every entry in that int[]
            .anyMatch(x -> {
                    // create a new list, excluding the one we are on now
                    int[] c = IntStream.range(0, in.length)
                        .filter(i -> i != x)
                        .map(i -> in[i])
                        .toArray();

                    boolean allInc = IntStream.range(0, c.length - 1)
                        .allMatch(i -> c[i] <= c[i + 1]);

                    boolean allDec = IntStream.range(0, c.length - 1)
                        .allMatch(i -> c[i] >= c[i + 1]);

                    boolean good = IntStream.range(0, c.length - 1)
                        .allMatch(i -> Math.abs(c[i] - c[i + 1]) >= 1 &&
                                  Math.abs(c[i] - c[i + 1]) <= 3);

                    // matching the condition
                    return (allInc || allDec) && good;
                })
            )
    .count();

My first solution was nothing like this, but after refining it I am very happy with how clean it came out.

Day 3

This was the traditional easy puzzle after a more complicated one. Basically simple parsing for which I used regular expressions. Nothing special, on to day 4.

Day 4

For day 4 I solved the first part with an over engineered path finding solution, which turned out to be quite the overkill, but extremely fun to program.

I really like the pattern in use, below is some of the code of it. First you create a Deque that holds the work, then you load it up with the initial starting points. In the case of the puzzle these are the location of the X characters.

From there you just loop over the work, taking a partial solution and seeing if any cells around it will lead to another partial solution, so from XM to XMA and on the next iteration to XMAS. The dx is a collection of Coord that indicate valid movements across the board.

Deque<Path> work = new ArrayDeque<>();

// Load initial points
for (int y = 0; y < input.length; y++) {
    for (int x = 0; x < input[y].length; x++) {
        if (input[y][x] == 'X') {
            work.add( new Path(List.of(new Coord(x,y)), "X", null) );
        }
    }
}

// Process each outstanding point..
while (!work.isEmpty()) {
    var path = work.pop();
    for (Coord d : dx) {
        if (path.dir() != null && path.dir != d) {
            continue;
        }
        var newCoord = lastStep.add(d);
        // Ensure this is a valid point on the grid
        if (newCoord.x() >= 0 && newCoord.x() < input[0].length &&
            newCoord.y() >= 0 && newCoord.y() < input.length) {
            // ... create new paths and string based on location
            // Check if we have an end case, else add it to the work
            if (target.equals(xmas)) {
                matches.add(newPath);
            } else if (target.startsWith(xmas)) {
                work.add(newPath);
            }

        }
    }
}

A more straightforward approach, which was actually needed for part 2, is to just try to solve it in one step. First you iterate over both y and x coordinates looking for an X, just as above. When you find one, iterate over [-1, 0, 1] on both the x and y axis-es, using dy and dx for the direction. If both direction are 0, we continue as it would give the current position. The beauty of this approach is that you can move outward in steps, x + 3 * dx will give you a value 3 cells in the give direction. From there it is a simple matter of checking if we are in bounds and if the letters spell MAS.

for (int y = 0; y < input.length; y++) {
    for (int x = 0; x < input[y].length; x++) {
        if (input[y][x] != 'X') continue;
        for (int dy = -1; dy <= 1; dy++) {
            for (int dx = -1; dx <= 1; dx++) {
                if (dy == dx && dx == 0) continue;
                if (!(0 <= y + 3 * dy && y + 3 * dy < input.length &&
                      0 <= x + 3 * dx && x + 3 * dx < input[y].length)) continue;

                if (input[y+1*dy][x+1*dx] == 'M' &&
                    input[y+2*dy][x+2*dx] == 'A' &&
                    input[y+3*dy][x+3*dx] == 'S') {
                    matches++;
                }
            }
        }
    }
}

For part 2 a similar approach can be used, however the order is not important. So I chose to create a List and then check against a target list with the containsAll method, it does not care about order.

var x1 = List.of(input[y-1][x-1], input[y][x], input[y+1][x+1]);
var x2 = List.of(input[y-1][x+1], input[y][x], input[y+1][x-1]);
if (x1.containsAll( target ) && x2.containsAll( target )){
    matches++;
}

Another reminder to not over engineer at the start.

[This article will be update with more days]