2022 Day 5

Posted on Dec 5, 2022

Part 1

Problem

The file input includes a number of stacks, their contents (crates), and a series of instructions for moving crates betwene stacks. Process all the instructions and then find the identifier of each crate at the top of each stack. Some stacks may be empty at the beginning or end of the process.

General solution

This is more difficult than previous days, as our input file now has three different line types:

Crates for this level. As stacks are different sizes, each level will not necessarily have a crate for each stack. There may be zero or more levels, but in practice there will be at least one, otherwise there would be no crates to move. Crates are labelled with a single letter but labels are not guaranteed to be unique.
Stack numbers. There will only be one line containing this data, however the stack count can be one or more.
Move instructions. There may be zero or more instructions, but in practice there will be at least one.

The move instructions are possibly the easiest to manage, as they are always in a fixed format:

move N from S to T

where N is the stack number, S is the source stack, and T is the target stack.

As we are working with stacks, it probably makes sense to read the file backwards, i.e. from the bottom up. This isn’t easy in most languages, so the simplest solution is to read the file forwards into an array of lines, then reverse that array and iterate over it.

Solution: Go

First of all, we need to define data structures for each of the three types in our input:

Crates: ID
Stacks: List of crates, lowest to highest.
Instructions: How many crates to move, the source stack, and the target stack.

As usual, these can be implemented as structs.

Initially a regular expression was used for extracting the move instructions, as this seemed like a good opportunity to learn how to use regexs in Go, and resulted in the following code:

instuctionRegex := regexp.MustCompile(`^move\s+(\d+)\s+from\s+(\d+)\s+to\s+(\d+)$`)

if instuctionRegex.MatchString(line) {
    matches := instuctionRegex.FindStringSubmatch(line)
    instruction := StackInstruction{}
    instruction.count, _ = strconv.Atoi(matches[1])
    instruction.source, _ = strconv.Atoi(matches[2])
    instruction.target, _ = strconv.Atoi(matches[3])
    instructions = append(instructions, instruction)
}

However, a regular expression is overkill in this case as we can simply use string.Fields, which splits on whitespace. All we need to do is to check whether the line starts with ‘move’.

Lines containing crates are also easy to identify as they will contain opening and closing square brackets ([ and ]). A crate definition is always four characters - either [X]\s (where X is the label of the crate) or four spaces.

The stack labels can be identified by the first non-whitespace character of the line being 1. This does assume that the stacks start from 1 and are labelled sequentially.

As mentioned in the general solution, we have to read the file into a slice of lines first, and then reverse it, because we need to process the stacks in reverse order (by definition a stack can only grow by appending elements, it is not possible to insert an element anywhere other than at the end).

Once we have the stacks we can process the instructions. Before doing so, we need to reverse the instructions as they need to be processed in the order in which they appear in the file, but we have already reversed the file. Reversing the instructions again puts them in their original order.

Processing the instructions is straightforward - we iterate over them and then move one crate from the source stack to the target stack c times, where c is the count. Unfortunately Go does not have a pop operation for slices, so we have to get the last element in the stack and then re-assign the stack to be the same contents minus the last element (other languages have a function which does both of these, without needing to calculate indexes and offsets). Moving the element to another stack is trivial, as we can use append.

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	type Crate struct {
		id string
	}

	type Stack struct {
		crates []Crate
	}

	type Instruction struct {
		count  int
		source int
		target int
	}

	instructions := []Instruction{}
	stacks := []Stack{}
	lines := []string{}

	// Add an empty zero-indexed stack so we start from 1 when adding
	// real stacks
	emptyStack := Stack{}
	stacks = append(stacks, emptyStack)

	scanner := bufio.NewScanner(os.Stdin)

	// Read the file into a slice
	for scanner.Scan() {
		lines = append(lines, scanner.Text())
	}

	// Reverse the slice of lines so we can iterate over it backwards
	for x, y := 0, len(lines)-1; x < y; x, y = x+1, y-1 {
		lines[x], lines[y] = lines[y], lines[x]
	}

	for lineIndex := range lines {
		line := lines[lineIndex]

		if strings.Index(line, "move") == 0 {
			// Instruction
			parts := strings.Fields(line)
			instruction := Instruction{}
			instruction.count, _ = strconv.Atoi(parts[1])
			instruction.source, _ = strconv.Atoi(parts[3])
			instruction.target, _ = strconv.Atoi(parts[5])
			instructions = append(instructions, instruction)
		} else if strings.Contains(line, "[") {
			// Crates
			// Each crate definition is 4 characters
			// ASSUMPTION: By the time we process the crate definitions,
			// we have built all the stacks
			for start, end, stackNumber := 0, 3, 1; start < len(line); start, end, stackNumber = start+4, end+4, stackNumber+1 {
				crateDefinition := line[start:end]

				if strings.Contains(crateDefinition, "[") {
					crate := Crate{}
					crate.id = crateDefinition[1:2]
					stacks[stackNumber].crates = append(stacks[stackNumber].crates, crate)
				}
			}
		} else if strings.Index(strings.TrimSpace(line), "1") == 0 {
			// Stacks
			// ASSUMPTION: Stack numbers will be sequential and start from 1
			stackNumbers := strings.Fields(line)

			for s := 0; s < len(stackNumbers); s++ {
				stack := Stack{}
				stacks = append(stacks, stack)
			}
		}
	}

	// We now have all the stacks, so process the instructions
	// Reverse the slice of instructions as they will be in the wrong order
	for x, y := 0, len(instructions)-1; x < y; x, y = x+1, y-1 {
		instructions[x], instructions[y] = instructions[y], instructions[x]
	}

	for i := range instructions {
		for c := 1; c <= instructions[i].count; c++ {
			// Pop top crate from source stack - this requires
			// two assignments in Go because there is no slice.pop
			topCrate := stacks[instructions[i].source].crates[len(stacks[instructions[i].source].crates)-1]
			stacks[instructions[i].source].crates = stacks[instructions[i].source].crates[:len(stacks[instructions[i].source].crates)-1]

			// Move the top crate to the target stack
			stacks[instructions[i].target].crates = append(stacks[instructions[i].target].crates, topCrate)
		}
	}

	// Print the top crate from each stack (if there is one)
	for s := range stacks {
		if len(stacks[s].crates) >= 1 {
			fmt.Print(stacks[s].crates[len(stacks[s].crates)-1].id)
		}
	}

	fmt.Println("")
}

Part 2

Problem

The same as Part 1, except multiple crates can be picked up at once and retain their order when moved.

General solution

The solution remains the same, except when moving crates we need to pick up several at once. We then add them to the target stack in reverse order because that will maintain the stack order. For example, if the source stack has:

ABCD

and we move 3 crates to the target stack, we will create a temporary stack with:

DCB (as each one is popped individually from the source)

reverse them to:

BCD

and then add them one at a time to the target stack.

Solution: Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	type Crate struct {
		id string
	}

	type Stack struct {
		crates []Crate
	}

	type Instruction struct {
		count  int
		source int
		target int
	}

	instructions := []Instruction{}
	stacks := []Stack{}
	lines := []string{}

	// Add an empty zero-indexed stack so we start from 1 when adding
	// real stacks
	emptyStack := Stack{}
	stacks = append(stacks, emptyStack)

	scanner := bufio.NewScanner(os.Stdin)

	// Read the file into a slice
	for scanner.Scan() {
		lines = append(lines, scanner.Text())
	}

	// Reverse the slice of lines so we can iterate over it backwards
	for x, y := 0, len(lines)-1; x < y; x, y = x+1, y-1 {
		lines[x], lines[y] = lines[y], lines[x]
	}

	for lineIndex := range lines {
		line := lines[lineIndex]

		if strings.Index(line, "move") == 0 {
			// Instruction
			parts := strings.Fields(line)
			instruction := Instruction{}
			instruction.count, _ = strconv.Atoi(parts[1])
			instruction.source, _ = strconv.Atoi(parts[3])
			instruction.target, _ = strconv.Atoi(parts[5])
			instructions = append(instructions, instruction)
		} else if strings.Contains(line, "[") {
			// Crates
			// Each crate definition is 4 characters
			// ASSUMPTION: By the time we process the crate definitions,
			// we have built all the stacks
			for start, end, stackNumber := 0, 3, 1; start < len(line); start, end, stackNumber = start+4, end+4, stackNumber+1 {
				crateDefinition := line[start:end]

				if strings.Contains(crateDefinition, "[") {
					crate := Crate{}
					crate.id = crateDefinition[1:2]
					stacks[stackNumber].crates = append(stacks[stackNumber].crates, crate)
				}
			}
		} else if strings.Index(strings.TrimSpace(line), "1") == 0 {
			// Stacks
			// ASSUMPTION: Stack numbers will be sequential and start from 1
			stackNumbers := strings.Fields(line)

			for s := 0; s < len(stackNumbers); s++ {
				stack := Stack{}
				stacks = append(stacks, stack)
			}
		}
	}

	// We now have all the stacks, so process the instructions
	// Reverse the slice of instructions as they will be in the wrong order
	for x, y := 0, len(instructions)-1; x < y; x, y = x+1, y-1 {
		instructions[x], instructions[y] = instructions[y], instructions[x]
	}

	for i := range instructions {
		moveCrates := []Crate{}

		for c := 1; c <= instructions[i].count; c++ {
			// Pop top crate from source stack - this requires
			// two assignments in Go because there is no slice.pop
			topCrate := stacks[instructions[i].source].crates[len(stacks[instructions[i].source].crates)-1]
			stacks[instructions[i].source].crates = stacks[instructions[i].source].crates[:len(stacks[instructions[i].source].crates)-1]

			moveCrates = append(moveCrates, topCrate)
		}

		// Reverse the crates to be moved so we add them in the correct order
		for x, y := 0, len(moveCrates)-1; x < y; x, y = x+1, y-1 {
			moveCrates[x], moveCrates[y] = moveCrates[y], moveCrates[x]
		}

		// Add each crate one at a time
		for mc := range moveCrates {
			// Move the top crate to the target stack
			stacks[instructions[i].target].crates = append(stacks[instructions[i].target].crates, moveCrates[mc])
		}
	}

	// Print the top crate from each stack (if there is one)
	for s := range stacks {
		if len(stacks[s].crates) >= 1 {
			fmt.Print(stacks[s].crates[len(stacks[s].crates)-1].id)
		}
	}

	fmt.Println("")
}

Post-solution thoughts

Adding an empty stack to the list to allow for 1-indexing feels like a bit of a hack, and this was pointed out to me on Mastodon.

There is probably a better way to pick up multiple crates using slice indexing, but I couldn’t get this to work. Picking them up one a time (in the code) was easier to implement.

We could have split the file into two parts - stacks and instructions - and processed stacks in reverse order and instructions in the order of the file. This would have negated the need to reverse the instructions after they have been loaded into a slice.

Given that we have 3 reversal operations, it might be a good idea to write a generic function that reverses a slice (for some reason Go does not include this in the standard library).

A better member name for Crate.id might be Crate.label, as id can imply a unique identifier but multiple crates can have the same label.