Another push of the button leaves you in the familiar hallways of some friendly amphipods! Good thing you each somehow got your own personal mini submarine. The Historians jet away in search of the Chief, mostly by driving directly into walls.
-- [Day 9 - Advent of Code 2024[(https://adventofcode.com/2024/day/9)
Solution in Java
Full source can be found: in GitHub
Since todays challenge talks about disk usage with two potential states, one containing files (the FileSegment) the other being empty (the Spacing), I decided to model that out first.
1sealed interface DiskUsage permits Spacing, FileSegment {
2 int size();
3}
4
5final class Spacing implements DiskUsage {
6 private int size;
7 public Spacing(int size) {
8 this.size = size;
9 }
10
11 public int size() {
12 return size;
13 }
14
15 public void shrink(int size) {
16 this.size -= size;
17 }
18}
19
20record FileSegment(int size, int fileNumber) implements DiskUsage {
21 public FileSegment reduceSize(int size) {
22 return new FileSegment(this.size - size, this.fileNumber);
23 }
24}
Part 1
The first step I took was to create a small method that would compute the checksum as indicated in the assignment. This code could be re-used for both parts today.
1private long computeChecksum(List<DiskUsage> diskUsage) {
2 var checkSum = 0L;
3 var blockPointer = 0;
4 for (var file : diskUsage) {
5 if (file instanceof FileSegment fileSegment) {
6 for (var i = 0; i < fileSegment.size; i++) {
7 checkSum += (blockPointer + i) * fileSegment.fileNumber;
8 }
9 }
10
11 blockPointer += file.size();
12 }
13
14 return checkSum;
15}
After tackling this I needed a way to parse the input into the data structures created earlier.
1private List<DiskUsage> parseUsage(String input) {
2 var diskUsage = new ArrayList<DiskUsage>();
3 for (var idx = 0; idx < input.length(); idx++) {
4 if (idx % 2 == 0) {
5 diskUsage.add(new FileSegment(input.charAt(idx) - '0', idx / 2));
6 } else {
7 diskUsage.add(new Spacing(input.charAt(idx) - '0'));
8 }
9 }
10
11 return diskUsage;
12}
This method essentially loops over all the numbers in the input using the each even position as a FileSegment and each odd position as a Spacing.
Now that all that boiler plating is out of the way it was time to write the actual defrag algorithm. For part 1 this was relatively simple as you could move individual segments into any Spacing location.
1public void part1() {
2 var diskUsage = parseUsage(inputLoader.string());
3 var updatedList = new ArrayList<DiskUsage>();
4
5 // defrag algorithm
6 for (var idx = 0; idx < diskUsage.size(); idx++) {
7 var usage = diskUsage.get(idx);
8 switch (usage) {
9 case Spacing spacing -> {
10 // fill from right of list
11 var toFill = spacing.size();
12 while (toFill > 0) {
13 var fillWith = diskUsage.removeLast();
14 switch (fillWith) {
15 case FileSegment fileSegment -> {
16 var movable = Math.min(toFill, fileSegment.size);
17 updatedList.add(new FileSegment(movable, fileSegment.fileNumber));
18 if (movable < fileSegment.size) {
19 diskUsage.add(fileSegment.reduceSize(movable));
20 }
21 toFill -= movable;
22 }
23 case Spacing space -> {}
24 }
25 }
26 }
27 case FileSegment fileSegment -> {
28 log.debug("Encountered file {} of size {}, no need to move.", fileSegment.fileNumber, fileSegment.size);
29 updatedList.add(fileSegment);
30 }
31 }
32 }
33
34 validator.part1(computeChecksum(updatedList));
35}
Part 2
In part 2 all that was needed was a small little change. I loop over the FileSegment from the last element in the list to the current Spacing to find one that fits. If any fits that gets copied over and a Spacing gets put into its place. If we still have space left then we look for the next FileSegment that would fit.
1public void part2() {
2 var diskUsage = parseUsage(inputLoader.string());
3
4 // defrag algorithm
5 for (var idx = 0; idx < diskUsage.size(); idx++) {
6 var usage = diskUsage.get(idx);
7 switch (usage) {
8 case Spacing spacing -> {
9 // fill from right of list
10 for (var rtl = diskUsage.size() - 1; rtl >= idx; rtl--) {
11 var fillAttempt = diskUsage.get(rtl);
12 if (fillAttempt instanceof FileSegment fileSegment && fileSegment.size <= spacing.size) {
13 // insert at idx
14 diskUsage.set(idx, fileSegment);
15
16 // replace file with space
17 diskUsage.set(rtl, new Spacing(fileSegment.size()));
18
19 spacing.shrink(fileSegment.size);
20 if (spacing.size() > 0) {
21 diskUsage.add(idx + 1, spacing);
22 }
23
24 break;
25 }
26 }
27 }
28 case FileSegment s -> {}
29 }
30 }
31
32 validator.part2(computeChecksum(diskUsage));
33}