advent of code 2015 solutionsadvent of code 2015 solutions
HappyCoders Glasses

Advent of Code 2015 Object-oriented Solutions in Java

Sven Woltmann
Sven Woltmann
December 1, 2018

In this article, you will find short explanations about my solutions for Advent of Code 2015.

You can find my solutions in this GitHub project: Advent of Code 2015 – Object-oriented Solutions in Java.

Advent of Code 2015 – Day 1 Solution

Day 1 is quickly solved: Increment a counter for each ‘(‘ and decrement it for each ’)’ – either until the end (part one) or until the counter reaches the value -1 (part two).

GitHub: Advent of Code 2015 day 1 solution

Advent of Code 2015 – Day 2 Solution

Day 2 is also pretty simple – parse each row into length, width, and height, and do some basic arithmetic to calculate areas, perimeter, and volume.

GitHub: Advent of Code 2015 day 2 solution

Advent of Code 2015 – Day 3 Solution

I implemented the solution for day 3 using a Set that stores all the places Santa has visited. The size of the Set is the answer for part one.

For part two, I used one Set for Santa and one for Robo-Santa. In the end, I merge both Sets; the size of the merged Set is the solution.

GitHub: Advent of Code 2015 day 3 solution

Advent of Code 2015 – Day 4 Solution

To solve day 4, we must iterate over all positive numbers until we find a hash with the required amount of leading zeros. We can speed this up by factor two if we count the leading zeros directly in the byte array and don’t convert it to a hex string first.

GitHub: Advent of Code 2015 day 4 solution

Advent of Code 2015 – Day 5 Solution

For day 5, I wrote two “nice string” detectors that implement the Predicate<String> interface. This way, we can easily replace the detector for part two.

GitHub: Advent of Code 2015 day 5 solution

Advent of Code 2015 – Day 6 Solution

I solved day 6 with a two-dimensional array of ints. I implemented the two rule sets for parts one and two, each with a Map mapping the command (“turn on,” “toggle,” “turn off”) to an IntUnaryOperator that calculates the new brightness based on the previous one.

This is the interesting part of the code:

EnumMap<Command, IntUnaryOperator> commandToOperatorPart1 = new EnumMap<>(Command.class); commandToOperatorPart1.put(TURN_ON, brightness -> 1); commandToOperatorPart1.put(TOGGLE, brightness -> 1 - brightness); commandToOperatorPart1.put(TURN_OFF, brightness -> 0); EnumMap<Command, IntUnaryOperator> commandToOperatorPart2 = new EnumMap<>(Command.class); commandToOperatorPart2.put(TURN_ON, brightness -> brightness + 1); commandToOperatorPart2.put(TOGGLE, brightness -> brightness + 2); commandToOperatorPart2.put(TURN_OFF, brightness -> Math.max(brightness - 1, 0));
Code language: Java (java)

And this is how to apply such an operation to a field in the array:

IntUnaryOperator operator = commandToOperator.get(command); brightness[y][x] = operator.applyAsInt(brightness[y][x]);
Code language: Java (java)

GitHub: Advent of Code 2015 day 6 solution

Advent of Code 2015 – Day 7 Solution

The domain model for day 7 was a bit difficult to design. This is what it looked like in the end:

Advent of Code 2015 - Day 7 - Domain model class diagram

Once this model is wired up, all left to do is find the Instruction for the given destinationWireId and call the getSignal() method for the WireSource of that Instruction.

GitHub: Advent of Code 2015 day 7 solution

Advent of Code 2015 – Day 8 Solution

On day 8, we can sit back and relax a bit. The escape and unescape methods are quickly implemented.

GitHub: Advent of Code 2015 day 8 solution

Advent of Code 2015 – Day 9 Solution

On day 9, we have to solve the classic "Travelling salesman problem". Since we only have a few cities, we can do a simple depth-first search to find all possible routes and determine their minimum and maximum lengths.

GitHub: Advent of Code 2015 day 9 solution

Advent of Code 2015 – Day 10 Solution

A look at the Wikipedia article linked from day 10 suggests that the sequence length after 40 rounds is in the order of a million. Any modern computer should be able to simulate that in a few milliseconds.

The algorithm is implemented quickly and solves part one in 5 milliseconds. My result is 492,982 – so it is within the targeted range. For part two – 50 rounds – the algorithm needs 70 ms.

GitHub: Advent of Code 2015 day 10 solution

Advent of Code 2015 – Day 11 Solution

My algorithm for day 11 manages the task in under 100 ms without any optimization. With some optimizations, we can greatly reduce this time:

  • Convert the String to a character array at the beginning; perform all operations on the character array; convert the character array back to a String at the end.
  • Check at the beginning whether the password contains one of the letters i, l, o. If so, increment the corresponding digit and set all subsequent digits to ‘a’.
  • When counting up, skip the letters i, l, o.

With these optimizations, the algorithm finds the next password in only 0.016 ms.

GitHub: Advent of Code 2015 day 11 solution

Advent of Code 2015 – Day 12 Solution

We can solve part one of day 12 with a simple regular expression: "-?\d+" (the quotation marks are not part of it). We just have to add up all the matches.

Part two can be solved with a JSON parser (e.g., Gson) and recursion.

GitHub: Advent of Code 2015 day 12 solution

Advent of Code 2015 – Day 13 Solution

We can solve day 13's puzzle with a depth-first search across all possible seating arrangements.

GitHub: Advent of Code 2015 day 13 solution

Advent of Code 2015 – Day 14 Solution

Part one of day 14, the distance a reindeer has traveled after a certain time, is easy to calculate.

We can use the same formula for part two; it solves the task in less than one millisecond. However, the time complexity is O(n² - m), where n is the simulated time and m is the number of reindeer. Thus, the required time grows in square with the simulated time.

We can do faster by simulating the progress of the reindeer second by second (this is how I implemented part two in the end). Thus we achieve a better time complexity of O(n - m).

GitHub: Advent of Code 2015 day 14 solution

Advent of Code 2015 – Day 15 Solution

We can solve the task of day 15 again with a depth-first search, via which we calculate the score for all possible combinations of ingredients. For part two, I adjusted the score calculation: As soon as a cookie does not have 500 calories, its score is set to 0.

GitHub: Advent of Code 2015 day 15 solution

Advent of Code 2015 – Day 16 Solution

The solution for day 16 can be implemented elegantly with a Predicate<Sue> as an abstract base class for a strategy pattern. This way, we can easily implement two different strategies for part one and part two.

Since all requested properties are known in advance, they could be stored in appropriately named variables, with an unknown property stored as null or -1. More elegant and flexible is a list of tuples of property names and values. An unknown property is then identified by its absence from the list.

GitHub: Advent of Code 2015 day 16 solution

Advent of Code 2015 – Day 17 Solution

The task of day 17 can be solved by depth-first search. With 20 containers, there are precisely 220 – just over a million – different combinations. It takes about 3.2 milliseconds to try them all.

But there is a lot of potential for optimization:

  1. If the target volume is reached without using all containers, we have found a combination and do not need to follow the path any further – the remaining containers are not needed.
  2. If the target volume is exceeded, we can abort the current path.
  3. If the current sum plus the smallest of the remaining container volumes exceeds the target sum, we can also abort the path. We can determine the smallest element of the last x elements in advance for each position within the container sequence.
  4. If the sum of the volumes of the remaining containers is not enough to reach the remaining sum needed, we can also abort the path. We can also calculate the remaining sums of the last x elements in advance.

With these optimizations, it takes only 0.15 ms to find all matching combinations. The optimizations have thus accelerated the algorithm by more than a factor of 20.

GitHub: Advent of Code 2015 day 17 solution

Advent of Code 2015 – Day 18 Solution

On day 18, we have to implement Conway's Game of Life. Since our grid is limited and contains many living cells, a two-dimensional boolean array is suitable. (If we have unlimited fields or few living cells, we can store only the living cells in a collection).

The adjustments for part two – leaving the four corners always on – are quickly done.

GitHub: Advent of Code 2015 day 18 solution

Advent of Code 2015 – Day 19 Solution

Task one of day 19 is quickly solved by going through the molecule atom by atom, replacing each of the atoms with all their substitutions, and storing the resulting molecules in a Set. The size of this Set is the puzzle's solution.

Part two is significantly more complex. I tried several brute-force approaches:

  • Breadth-first search forward.
  • Depth-first search forward.
  • Breadth-first search backward.
  • Depth-first search backward.

The only way that led to a solution at all in adequate time was a depth-first search backward (i.e., trying to get from the target molecule to the electron by applying the substitution rules in reverse) – with prioritization of the substitution rules descending by the length of the target molecule. This way, at least one result was found after a few seconds. But it would have taken days to run the search to the end.

I found a better solution only by looking at the related Reddit topic:

If we take a closer look at the substitution rules, we notice that they belong to one of the following patterns, where X stands for any atom:

  • e => XX
  • X => XX
  • X => XRnXAr
  • X => XRnXYXAr
  • X => XRnXYXYXAr

Rn, Y, and Ar are only on the right side of the rules. If we replace them with ‘(‘, ‘,‘, and ‘)‘, the rules look like this:

  • e => XX
  • X => XX
  • X => X(X)
  • X => X(X,X)
  • X => X(X,X,X)

There is always exactly one atom on the left side. And each target pattern has a specific length. So the application of a particular pattern increases the size of the molecule by a certain number of atoms:

  • e => XX – von 1 auf 2, also +1
  • X => XX – von 1 auf 2, also +1
  • X => X(X) – von 1 auf 4, also +3
  • X => X(X,X) – von 1 auf 6, also +5
  • X => X(X,X,X) – von 1 auf 8, also +7

If we didn’t have parentheses and commas, the number of steps to get from one atom ("e") to n atoms would be exactly n-1 since we lengthen the molecule by one atom at each step.

Example: To get from "e" to "XXXX" (n = 4), we would need 4-1 = 3 steps:

  1. e → XX
  2. XX → XXX
  3. XXX → XXXX

If we additionally observe the rule X => X(X), the molecule lengthens further by the “parenthesis atoms.” To calculate the number of steps out of the target molecule, we can subtract these “parenthesis atoms” again. So we need n-1-(number of parentheses) steps.

Example: To get from "e" to "X(X)X(X)" (n = 8), we would need 8-1-4 = 3 steps:

  1. e → XX
  2. XX → X(X)X (erstes X ersetzt)
  3. X(X)X → X(X)X(X) (letztes X ersetzt)

If we now also observe the rules X => X(X,X) and X => X(X,X,X), the molecule lengthens with each comma by two atoms: the comma atom itself and the atom following the comma. So for each comma, we have to subtract two atoms. Our final formula becomes:

Number of steps = number of target atoms - 1 - number of parentheses - 2 × number of commas

Example: to get from "e" to "X(X,X(X,X))X" (n = 14), we would need 14-1-4-2×4 = 3 steps:

  1. e → XX
  2. XX → X(X,X)X (first X replaced)
  3. X(X,X)X → X(X,X(X,X,X))X (second X inside the parentheses replaced)

Using this formula, part two of the task is also quickly solved.

GitHub: Advent of Code 2015 day 19 solution

Advent of Code 2015 – Day 20 Solution

Subtask one of day 20 can also be phrased as follows:

We are looking for the smallest n for which the divisor function σ1(n) >= p (with p = puzzle input / 10).

This function is quickly implemented and adapted for subtask two with a few additional parameters.

GitHub: Advent of Code 2015 day 20 solution

Advent of Code 2015 – Day 21 Solution

For day 21, I wrote a simulator that plays the game with the given parameters (“hit points,” “damage,” and “armor” per player) and returns the winner. Using the simulator, we can play all allowed combinations of weapon, defense, and rings (there are only 1,080 such combinations).

Suppose we sort the possible combinations in advance by total cost (ascending for subtask one and descending for subtask two). Then we can stop the simulations as soon as we find the first combination where the player (for subtask one) or the boss (for subtask two) wins.

GitHub: Advent of Code 2015 day 21 solution

Advent of Code 2015 – Day 22 Solution

The puzzle of day 22 can be solved well with a breadth-first search since there are only so many options per turn (the affordable and currently inactive spells).

I implemented the breadth-first search using a PriorityQueue that sorts the reached game states by total cost in ascending order.

If a solution was found and we had to skip a spell (because it was not affordable or already active), we could still find a better solution – from a game state further down the queue with the same or higher cost combined with a cheaper spell.

However, we only need to continue the search until the cost of the next game state in the queue plus the cost of the cheapest spell is equal to or higher than the cost of the best solution so far. All further game states in the queue would lead to a more expensive solution.

The adjustments for part two are minimal.

GitHub: Advent of Code 2015 day 22 solution

Advent of Code 2015 – Day 23 Solution

On day 23, we have to emulate a CPU with two registers and six instructions. That is relatively easy, and the changes for part two are trivial.

GitHub: Advent of Code 2015 day 23 solution

Advent of Code 2015 – Day 24 Solution

To solve the puzzle of day 24, a depth-first search over the possible package combinations is suitable again. We only have to find an optimal solution for the first compartment. Whenever we have found a solution for the first compartment better than the previous best solution, we only have to check whether there is at least one solution for the remaining compartments.

As soon as the depth-first search for the first compartment leads to more packets than the previous best solution, the corresponding path can be aborted.

My implementation solves part one in 1.5 s and part two in 40 ms.

GitHub: Advent of Code 2015 day 24 solution

Advent of Code 2015 – Day 25 Solution

On day 25 of Advent of Code 2015, we have to implement a code generator. The description of the task is long, but the solution requires only a few lines of code:

static int solve(int row, int col) { int elementIndex = calculateElementIndex(row - 1, col - 1); return getCode(elementIndex); } static int calculateElementIndex(int row, int col) { int diagonalNumber = row + col; int diagonalStart = diagonalNumber * (diagonalNumber + 1) / 2; return diagonalStart + col; } static int getCode(int iterations) { int code = 20_151_125; for (int i = 0; i < iterations; i++) { code = (int) (code * 252_533L % 33_554_393); } return code; }
Code language: Java (java)

GitHub: Advent of Code 2015 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.