Advent of Code 2022 – Object-oriented Solutions in Java

Impatient? Then go straight to my solutions for Advent of Code 2022 :-)

What is Advent of Code?

Advent of Code is an annual, pre-Christmas series of programming tasks packaged as an Advent calendar. Behind its doors, daily challenges are hidden, each more difficult than the previous.

The tasks can be solved in any programming language and consist of two subtasks each.

Is Advent of Code Hard?

The first subtask can usually be solved relatively quickly.

In the second task, the scale of the problem is drastically increased. This usually leads to the need to revise the solution since the intuitively implemented algorithm often has too high a complexity class and would take hours, days, or even months to solve the task.

Shortly after the release of a new Advent of Code puzzle, you can find the first solutions on the corresponding Reddit. Those solutions primarily consist of procedural spaghetti code that is not very readable, let alone maintainable.

My Advent of Code Answers 2022

I, therefore, took the trouble to implement each task in Java in a genuinely object-oriented and test-driven way, resulting in a solution of small, understandable objects interacting with each other.

This approach also usually results in the optimizations required for subtask two being limited to a small section of the code – often a single class.

You can find my solutions in this GitHub repository: Advent of Code 2022 - Object-oriented Solutions in Java.

static IntStream getCaloriesSums(String input) {
  String[] blocks = input.split("\\n\\n");
  return Arrays.stream(blocks)
      .mapToInt(block -> block.lines().mapToInt(Integer::parseInt).sum());
}Code language: Java (java)

static int calculateMaxCalories(String input) {
  IntStream caloriesSums = getCaloriesSums(input);
  return caloriesSums.max().orElse(0);
}Code language: Java (java)

static int calculateSumOfTopThreeCalories(String input) {
  IntStream caloriesSums = getCaloriesSums(input);
  return caloriesSums
      .boxed()
      .sorted(Comparator.reverseOrder())
      .mapToInt(Integer::valueOf)
      .limit(3)
      .sum();
}Code language: Java (java)

record SectionAssignment(int start, int end) {
  boolean fullyContains(SectionAssignment other) {
    return start <= other.start && end >= other.end;
  }

  boolean overlaps(SectionAssignment other) {
    return start >= other.start && start <= other.end
        || end >= other.start && end <= other.end
        || other.start >= start && other.start <= end
        || other.end >= start && other.end <= end;
  }
}Code language: Java (java)

Advent of Code 2022 – Day 5 Solution

On day 5, I applied the Strategy Pattern to implement the two types of cranes and make them interchangeable:

The move() methods are implemented as follows. The CrateMover 9000 takes – one by one – the desired number of crates from one stack and places them on the other:

class CrateMover9000 implements CrateMover {

  @Override
  public void move(CrateStacks crateStacks, Move move) {
    CrateStack fromStack = CrateMover.getSourceStack(crateStacks, move);
    CrateStack toStack = CrateMover.getTargetStack(crateStacks, move);

    for (int i = 0; i < move.number(); i++) {
      toStack.push(fromStack.pop());
    }
  }
}Code language: Java (java)

CrateMover 9001 uses an auxiliary stack to flip the order of the crates in between:

class CrateMover9001 implements CrateMover {

  @Override
  public void move(CrateStacks crateStacks, Move move) {
    CrateStack fromStack = CrateMover.getSourceStack(crateStacks, move);
    CrateStack toStack = CrateMover.getTargetStack(crateStacks, move);

    Deque<Crate> helperStack = new LinkedList<>();
    for (int i = 0; i < move.number(); i++) {
      helperStack.push(fromStack.pop());
    }

    while (!helperStack.isEmpty()) {
      toStack.push(helperStack.pop());
    }
  }
}Code language: Java (java)

GitHub: Advent of Code 2022 day 5 solution

Advent of Code 2022 – Day 7 Solution

For day 7, I wrote a parser that builds a directory tree from the given commands using the following classes (conforming to the composite pattern):

For the solution of part one, we then only need to recursively go through all subdirectories and filter out those that match the size criterion. We can solve this very elegantly with Java’s Stream API:

long sumOfSizes =
    root.listWithAllSubDirectories().stream()
        .mapToLong(Directory::totalSize)
        .filter(totalSize -> totalSize <= maxTotalSize)
        .sum();Code language: Java (java)

For part two, we also need to filter by size and then determine the smallest directory:

long freeSpace = 70_000_000 - root.totalSize();
long moreSpaceNeeded = 30_000_000 - freeSpace;

long smallestDirectoryToDeleteTotalSize =
    root.listWithAllSubDirectories().stream()
        .filter(directory -> directory.totalSize() >= moreSpaceNeeded)
        .min(Comparator.comparing(Directory::totalSize))
        .orElseThrow()
        .totalSize();Code language: Java (java)

GitHub: Advent of Code 2022 day 7 solution

enum Direction {
  TOP,
  RIGHT,
  BOTTOM,
  LEFT;
}

record Position(int column, int row) {
  Position moveTo(Direction direction) {
    return switch (direction) {
      case TOP -> new Position(column, row - 1);
      case RIGHT -> new Position(column + 1, row);
      case BOTTOM -> new Position(column, row + 1);
      case LEFT -> new Position(column - 1, row);
    };
  }
}Code language: Java (java)

Advent of Code 2022 – Day 11 Solution

The problem with part two of day 11 is that the "worry level" quickly takes on gigantic proportions due to squaring. The trick to keep the worry level low without changing the game logic is to replace the relief formula

worryLevel = worryLevel / 3;Code language: Java (java)

by

worryLevel = worryLevel % reliefDivisorCode language: Java (java)

where reliefDivisor is the product of all the different denominators of the "test" operations.

In the example, we have the following four tests:

Test: divisible by 23
Test: divisible by 19
Test: divisible by 13
Test: divisible by 17Code language: plaintext (plaintext)

For this example, the reliefDivisor is calculated as 23 × 19 × 13 × 17 = 96,577

If we now, for the relief operation, set the worry level to the remainder when dividing by this value, it is ensured that a) the worry level remains small and b) the result of the "test" operations do not change, no matter which monkey has a specific item.

GitHub: Advent of Code 2022 day 11 solution

Advent of Code 2022 – Day 12 Solution

For day 12, I implemented a breadth-first algorithm that goes from the start position to all reachable fields and then from each reachable field further to all fields reachable from there, and so on. Fields already reached in a previous step are ignored since a shorter path has already been found there.

For part two, I simply applied the algorithm from part one to all possible starting squares and determined the shortest of all shortest paths.

The relatively small size of the problem made this trivial solution possible. If the map had been much larger, it would have been possible to go back from the finish to the start and return the squares traversed up to that point when reaching a potential start square for the first time.

GitHub: Advent of Code 2022 day 12 solution

Advent of Code 2022 – Day 13 Solution

For day 13, I wrote a Comparator that I use both in part one to count how many packet pairs are in the correct order and in part two to sort the packets using List.sort().

GitHub: Advent of Code 2022 day 13 solution

Advent of Code 2022 – Day 14 Solution

The task of day 14 can be solved quickly with a grid of tiles. Part two does not require any special tricks today.

GitHub: Advent of Code 2022 day 14 solution

Advent of Code 2022 – Day 15 Solution

The trivial solution for day 15 also works with a grid. For part two, however, a grid proves to be too costly.

The trick is to store the areas covered by the sensors not in a grid but with start and end positions, combining adjacent or overlapping regions and ultimately determining the uncovered position from these regions.

GitHub: Advent of Code 2022 day 15 solution

Advent of Code 2022 – Day 16 Solution

The task of day 16 can be solved with a depth-first search. There is not one optimization but several, each of which makes the algorithm faster by a significant factor. I applied the following four optimizations:

1. In each situation, the algorithm checks whether the same situation (i.e., the combination of valve positions, actuator positions, and elapsed minutes) has occurred before. If so, and if that situation resulted in the same or more pressure being discharged, the current path does not need to be explored further.
2. In each situation, the maximum amount of pressure that can be released during the remaining time if the valves are opened according to descending flow rate is calculated. If this results in a worse result than the current best, the path is not pursued further.
3. When comparing the situation with all previous situations, two situations are considered the same even if the positions of you and the elephant are reversed.
4. If it is detected that an actor has run in a circle without having opened a valve on it, the current path is also not followed further.

With the help of these optimizations, sub-task two can be solved in about two seconds.

GitHub: Advent of Code 2022 day 16 solution

Advent of Code 2022 – Day 17 Solution

The simulation for day 17 is implemented relatively quickly with binary operations: "shift left" and "shift right" to move the rock, "bitwise and" for collision checking, and "bitwise or" for manifesting a rock.

However, simulating 1,000,000,000 rocks would have taken close to 20 hours with my initial implementation.

The trick for subtask two is to find repetitions in the fall and displacement patterns. To do this, my algorithm stores a combination of the current rock, the current position in the input, and the height profile of the upper rock rows as a key in a map with the current highest rock and the number of rocks that have fallen so far as the value.

As soon as the same combination occurs again (which happens surprisingly quickly), we can skip a few billion steps in a few milliseconds with the help of the number of rocks that have fallen in the meantime and the intermediate growth of the rock mountain. Thus, subtask two can also be solved in a few hundred milliseconds.

GitHub: Advent of Code 2022 day 17 solution

Advent of Code 2022 – Day 18 Solution

Subtask one of day 18 is quickly solved. We store all cubes in a set and then iterate over it and count – using Set.contains() – those sides on which there is no cube.

I solved part two with iterative floodfill. The area outside the droplet is filled cube by cube with "steam." Each time a cube cannot be filled because there is lava, a counter is incremented. In the end, this counter contains the searched outer area.

GitHub: Advent of Code 2022 day 18 solution

Advent of Code 2022 – Day 19 Solution

Day 19 reminds us of the valve task from day 16. This task is also solved with a depth-first search and various optimizations:

• Assuming that we produce a geode robot every turn, we can calculate the maximum number of geodes that could still be produced in a given situation. If this number is smaller than the current best value, the path does not need further exploration.
• If a certain robot could have been bought in the previous round – but no robot was bought in that round, then we don't need to buy it now. Saving only makes sense for another robot.
• At the last minute, we do not need to produce a robot.
• In the penultimate minute, we only need to produce geode robots.
• In the pre-penultimate minute, we only need to produce geode, ore, or obsidian robots (i.e., no clay robots).

My implementation solves part one in 4 seconds and part two in 52 seconds.

GitHub: Advent of Code 2022 day 19 solution

Advent of Code 2022 – Day 20 Solution

The solution for day 20 can be implemented easily with a doubly linked circular list. Part one does not require any optimizations.

In part two, we would have to move the nodes several trillion times. We can reduce that to a few thousand with a simple formula:

long distance = node.value() % (size - 1);Code language: Java (java)

The trick is not to divide by size (the number of elements) but by size - 1. You can see this in the example: In the list of length 7, you would have to move an element six times to the right to get it back to its starting point.

GitHub: Advent of Code 2022 day 20 solution

Advent of Code 2022 – Day 21 Solution

For the solution of day 21, I built a directed acyclic graph of the mathematical operations. Since the results of some operations are used multiple times, they are stored once they have been calculated.

For part two, I first tried to implement a depth-first search, i.e., using different values for the "humn" node and then checking whether both operands of the "root" node are the same. I optimized this variant by not deleting all stored results between two attempts but only those on the path from "root" to "humn." But even so, the calculation would have taken too long to accept this solution.

Based on the optimization just mentioned, I was able to implement a much faster solution. We can simply execute the mathematical operations on the path from "root" to "humn" backwards and get the result in a few milliseconds.

GitHub: Advent of Code 2022 day 21 solution

Advent of Code 2022 – Day 22 Solution

Day 22 started off easy once again. With a two-dimensional grid and a few special treatments for the areas outside the map, part one is quickly solved.

Part two is much trickier. I wrote logic for this that maps the coordinates on the map to coordinates on a cube face, then moves and rotates the cube face using an additional list of edge connections ("wormholes"), and finally maps the coordinates on the moved and rotated cube face back to the coordinates on the global map.

I manually generated the list of edge connections from my puzzle input. So my solution will not work without manually adjusting the edge connections on all of them (unless your input has the same cutting pattern). You can also determine the edge connections algorithmically, but I haven't had time to do that. I may do that later.

GitHub: Advent of Code 2022 day 22 Solution

Advent of Code 2022 – Day 23 Solution

On day 23, when solving the first sub-task, we can already be prepared that we will probably have to simulate more than ten rounds in sub-task two. Since the field will keep growing this way, we should not store the elves in a two-dimensional array.

My algorithm stores the elves as a list and additionally their positions in a Set<Position>. So the collision check can be easily solved via Set.contains(). Solving subtask two takes less than one second.

GitHub: Advent of Code 2022 day 23 Solution

Advent of Code 2022 – Day 24 Solution

On day 24, we once more have to implement a pathfinding algorithm. For today's task, a depth-first search is not suitable because the map changes with each move. With my puzzle input, it takes 95,400 steps to reach the target the first time and just over a minute to solve subtask one.

A breadth-first search solves part one in just 95 ms and part two in 130 ms.

I optimized the calculation of free positions. Instead of simulating the complete valley map for each step, I use a modulo operation to calculate whether a field is free at a certain time or not:

boolean isBlizzardAtMinute(Position pos, int minute) {
  return tiles[modulo(pos.row() + minute, height)][pos.column()] == Tile.UP
      || tiles[modulo(pos.row() - minute, height)][pos.column()] == Tile.DOWN
      || tiles[pos.row()][modulo(pos.column() + minute, width)] == Tile.LEFT
      || tiles[pos.row()][modulo(pos.column() - minute, width)] == Tile.UP;
}Code language: Java (java)

GitHub: Advent of Code 2022 day 24 solution

Advent of Code 2022 – Day 25 Solution

The solution for day 25 consists of only a few lines of code. The trickier part is converting a decimal number to a SNAFU string. This is the corresponding method:

static String toSnafuString(long decimal) {
  StringBuilder result = new StringBuilder();

  do {
    long fives = (decimal + 2) / 5;
    int digit = (int) (decimal - 5 * fives);
    result.insert(0, convertDecimalToSnafuDigit(digit));
    decimal = fives;
  } while (decimal != 0);

  return result.toString();
}Code language: Java (java)

GitHub: Advent of Code 2022 day 25 solution

If you liked the article, please share it using one of the share buttons at the end. Want to be notified by email when I publish a new article? Then click here to join the HappyCoders newsletter.