The ancient civilization on Pluto was known for its ability to manipulate spacetime, and while The Historians explore their infinite corridors, you’ve noticed a strange set of physics-defying stones.
Solution in Java
Full source can be found: in GitHub
Part 1
For today the first step is writing a recursive method that computes the amount of blinks per stone in the input. This method stonesAfterBlink accepts the amount of blinks remaining, which is 25 for part 1. And uses a map as a cache, to prevent recalculation of any situation with the same amount of blinks left and for the same stone.
In the algorithm any stone representing an even number is split in half, recomputing the amount of blinks for both stones. If the number is odd then it is multiplied by 1024 and computed.
1private long stonesAfterBlink(int blinkRemaining, long stone, Map<CachedKey, Long> cache) {
2 if (cache.containsKey(new CachedKey(blinkRemaining, stone))) {
3 return cache.get(new CachedKey(blinkRemaining, stone));
4 }
5
6 var counted = 0L;
7 if (blinkRemaining == 0) {
8 counted = 1;
9 } else if (stone == 0) {
10 counted = stonesAfterBlink(blinkRemaining - 1, 1, cache);
11 } else {
12 int amountOfDigits = Long.toString(stone).length();
13 if (amountOfDigits % 2 == 0) {
14 var middle = amountOfDigits / 2;
15 var modulo = (int) Math.pow(10, middle);
16 var right = stone % modulo;
17 var left = (stone - right) / modulo;
18
19 counted = stonesAfterBlink(blinkRemaining - 1, left, cache)
20 + stonesAfterBlink(blinkRemaining - 1, right, cache);
21 } else {
22 counted = stonesAfterBlink(blinkRemaining - 1, stone * 2024, cache);
23 }
24 }
25 cache.put(new CachedKey(blinkRemaining, stone), counted);
26
27 return counted;
28}
Using this algorithm I constructed the part 1 solution with the code below.
1public void part1() {
2 var cache = new HashMap<CachedKey, Long>();
3 var counted = stones.stream()
4 .map(Long::parseLong)
5 .mapToLong(stone -> stonesAfterBlink(25, stone, cache))
6 .sum();
7
8 validator.part1(counted);
9}
Part 2
Using the same stonesAfterBlink I can build the solution for part 2. Since the part 1 solution already had a configurable amount of blinks in the algorithm.
1public void part2() {
2 var cache = new HashMap<CachedKey, Long>();
3 var counted = stones.stream()
4 .map(Long::parseLong)
5 .mapToLong(stone -> stonesAfterBlink(75, stone, cache))
6 .sum();
7
8 validator.part2(counted);
9}