AOC 2022 – Day 5: Supply Stacks5 min read

You can read the full description for day 5 here.

In summary for part 1, we have been provided a number of stacks, each stack may contain a number of crates. And you have to apply the move operation to move crates from one stack to another, after the moving operations are complete for all stacks, we need to find out what crate ends up at the top of each stack.

To solve this, we simply need to use the Stack data structure to hold our crates, and just in case:

• Stack is a last-in-first-out (LIFO) data structure, it’s an abstract data type and is usually implemented by an array or a list.
• The push() operation adds an element to the top of the stack.
• The pop() operation removes the topmost element of the stack.

But first, we need to parse our input to get the initial crates setup as well as moving operations, here is the sample input:

[Q]         [N]             [N]    
[H]     [B] [D]             [S] [M]
[C]     [Q] [J]         [V] [Q] [D]
[T]     [S] [Z] [F]     [J] [J] [W]
[N] [G] [T] [S] [V]     [B] [C] [C]
[S] [B] [R] [W] [D] [J] [Q] [R] [Q]
[V] [D] [W] [G] [P] [W] [N] [T] [S]
[B] [W] [F] [L] [M] [F] [L] [G] [J]
 1   2   3   4   5   6   7   8   9 

move 3 from 6 to 2
move 2 from 8 to 7
move 3 from 3 to 8
move 2 from 5 to 3
move 5 from 9 to 7

To make the crates parsing process easier, here, for each stack that is not completely filled, we add to them the [-] crate:

[Q] [-] [-] [N] [-] [-] [-] [N] [-]
[H] [-] [B] [D] [-] [-] [-] [S] [M]
[C] [-] [Q] [J] [-] [-] [V] [Q] [D]
[T] [-] [S] [Z] [F] [-] [J] [J] [W]
[N] [G] [T] [S] [V] [-] [B] [C] [C]
[S] [B] [R] [W] [D] [J] [Q] [R] [Q]
[V] [D] [W] [G] [P] [W] [N] [T] [S]
[B] [W] [F] [L] [M] [F] [L] [G] [J]
 1   2   3   4   5   6   7   8   9

We are now ready to parse the crate setup, we have 9 different stacks, so ideally we want each number of its associated crates like this:

public static Map<Integer, Stack<Character>> getCrates(String input) {
	Map<Integer, Stack<Character>> stacks = new HashMap<>();
	List<List<String>> lines = input
                                .lines()
				.limit(8)
				.map(x -> Arrays.stream(x.split("\\s+")).collect(Collectors.toList()))
				.collect(Collectors.toList());
	for(int i = lines.size() - 1; i >= 0; i--) {
		List<String> crates = lines.get(i);
		for(int j = 0; j < crates.size(); j++) {
			Character label = getLabel(crates.get(j));
			if (!label.equals('\0')) {
			    if (stacks.get(j + 1) == null) {
			        Stack<Character> stack = new Stack<>();
				stack.push(label);
				stacks.put(j + 1, stack);
			    } else {
				Stack<Character> stack = stacks.get(j + 1);
				stack.push(label);
			    }
			}
		  }
	}
	return stacks;
}

Next, we parse the operations that move the crate from one stack to another, to do this, we create an object that represents exactly this information:

@AllArgsConstructor
class Operation {
      int moves;
      int from;
      int to;
}

And here we have a function that parses operations:

public static List<Operation> getOperations(String input) {
	List<String> lines = input
			.lines()
			.skip(10)
			.collect(Collectors.toList());
	List<Operation> operations = new ArrayList<>();
	List<Integer> nums = new ArrayList<>();
	for(final var line : lines) {
		String[] in = line.split("\\s+");
		for(final var i : in) {
			char ch = i.charAt(0);
			if (Character.isDigit(ch)) {
			    nums.add(Integer.parseInt(i));
			}
		}
		operations.add(new Operation(nums.get(0), nums.get(1), nums.get(2)));
		nums.clear();
	}
	return operations;
}

For part 1, we simply need to iterate through each of the operations, and for each of them, we sequentially move one crate from one stack to another before the next:

Map<Integer, Stack<Character>> crates = getCrates(input);
List<Operation> operations = getOperations(input);
for(final var op : operations) {
    for(int i = 0; i < op.moves; i++) {
        Stack<Character> fromStack = crates.get(op.from);
	Character label = fromStack.pop();
	Stack<Character> toStack = crates.get(op.to);
        toStack.push(label);
    }
}

Finally, we loop through each of the stacks to get topmost crates:

StringBuilder sb = new StringBuilder();
for(final var stack : crates.values()) {
    if (!stack.isEmpty()) {
       sb.append(stack.peek());
    }
}

For part 2, the requirement is slightly changed, instead of reversing the crates order, now we have to preserve the order of the crates before and after moving. To do that, we simply change our data structure, from a stack to a list:

Map<Integer, List<Character>> crates = getCrates(input)
				.entrySet()
				.stream()
				.collect(Collectors.toMap(Map.Entry::getKey, x -> new ArrayList<>(x.getValue())));

For each operation, we move a sublist of crates from one stack to another. Since the number of moves can be larger than the source stack size, we need to be a little cautious:

int left = from.size() - op.moves;
int right = left + op.moves;
List<Character> moves = from.subList(Math.max(0, left), Math.min(from.size(), right));

We then add the sublist from the source stack to the destination stack:

List<Character> from = crates.get(op.from);
List<Character> to = crates.get(op.to);
to.addAll(moves);

Since there are some crates that are still left in the source stack, we need to make them stay intact there:

List<Character> stay = from.subList(0, Math.min(from.size() - op.moves, from.size()));
crates.put(op.from, stay);

Finally, we can check the topmost crate for each of the stacks by looking at the last elements in the list and we’re done:

StringBuilder sb = new StringBuilder();
for(final var stack : crates.values()) {
    if (!stack.isEmpty()) {
       sb.append(stack.get(stack.size() - 1));
    }
}