Supply Stacks
Welcome to day 5 of AoC, aka, annoying AF parsing day.
We are crane operators!
What do we want?! More stacks and crates!
Anyhow, we are charged to execute a series of delicate manuvers using our insane crane skills
Our input is given to us as follows
[D]
[N] [C]
[Z] [M] [P]
1 2 3
move 1 from 2 to 1
move 3 from 1 to 3
move 2 from 2 to 1
move 1 from 1 to 2
The first half represents the current state of stacks and crates.
The second one is a series of moves we need to perform.
Crates can only be moved one at a time!
Parsing
How can we parse that input into something meaningful?
Well first let's seprate both halves using
parts := strings.Split(raw, "\n\n")
rawStacks := parts[0]
rawMoves := parts[1]
Now let's tackle parsing the crates!
One way we can go about it is simply copy-pasting our input into an object by hand but where is the fun in that?!
If we look closely at our input we might notice that the letters fit in chunks of four chars, for example
0 | 1 | 2 | // positions in chunks array
xxxxxxxxxxxx
[D]
[N] [C]
[Z] [M] [P]
1 2 3
// row 1 col 1,2,3
chunks -> [ [" ","[D] "," "] ...]
Armed with that information we can write the following code to prase crates and classify them into the right stack
func parseStacks(crates []string) [][]string {
stacks := make([][]string, 9)
for _, row := range crates {
rowOfCrates := chunkBy(strings.Split(row, ""), 4)
for crateNo, crateCandidate := range rowOfCrates {
for _, char := range crateCandidate {
if char >= "A" && char <= "Z" {
//pre-appending an element to array
stacks[crateNo] = append([]string{char}, stacks[crateNo]...)
}
}
}
}
return stacks
}
Let us look at the list of instructions, each line represents one command move x from y to z, lets's create a struct to populate exactly that and turn our list into a list of those structs
type Instruction struct {
amount int
from int
to int
}
func toInts(fromStrings []string) (result []int) {
for _, n := range fromStrings {
num, _ := strconv.Atoi(n)
result = append(result, num)
}
return result
}
func parseInstructions(rawInstructions []string) (instructions []Instruction) {
matcher := regexp.MustCompile(`move (\d+) from (\d+) to (\d+)`)
for _, line := range rawInstructions {
match := toInts(matcher.FindStringSubmatch(line)[1:])
instructions = append(instructions, Instruction{
amount: match[0],
from: match[1] - 1,
to: match[2] - 1,
})
}
return instructions
}
Combining parseInstructions and parseStacks to get our parse function
func parse(raw string) ([][]string, []Instruction) {
chunks := strings.Split(string(raw), "\n\n")
rawCrates := strings.Split(chunks[0], "\n")
rawInstructions := strings.Split(chunks[1], "\n")
return parseStacks(rawCrates), parseInstructions(rawInstructions)
}
In go you can have more than one return value.
Part 1
Perform the list of instructions then construct a string built from the top crate of each stack, for example in our current example its NDP but after the instructions are applied its CMZ
Using our parsed instructions and stacks, the solution becomes quite trivial
func Part1(raw string) string {
stacks, instructions := parse(string(raw))
// applying instructions
for _, instruction := range instructions {
from := instruction.from
to := instruction.to
// another approach is to create a slice of size amount from `moveFrom`
// reverse that slice and push it to `moveTo` but the approach here is much simpler to reason about
for i := 0; i < instruction.amount; i++ {
stacks[to] = append(stacks[to], stacks[from][len(stacks[from])-1])
stacks[from] = stacks[from][:len(stacks[from])-1]
}
}
answer := ""
for _, stack := range stacks {
if len(stack) > 0 {
answer += stack[len(stack)-1]
}
}
return answer
}
And that's it for part one, besides the parsing it was quite simple.
Part 2
Something was off with our stacks, we went to make sure that our crane is CrateMover 9000 but it was the 9001 model! this means we can move multiple crates at once.
The meaning of this in the context of the code we wrote is that we don't need to preserve a stack-like order when moving crates, the top element from our source crane will stay on top instead of being at the bottom of the crates we are moving
func Part2(raw string) string {
stacks, instructions := parse(string(raw))
// mutating the stacks
for _, instruction := range instructions {
from := instruction.from
to := instruction.to
amount := instruction.amount
takeRange := len(stacks[from]) - amount
// take items from `takeRange` until the end of the slice and append them to the target stack
stacks[to] = append(stacks[to], stacks[from][takeRange:]...)
// remove items that come after the `takeRange` from our source crate
stacks[from] = stacks[from][:takeRange]
}
answer := ""
for _, stack := range stacks {
if len(stack) > 0 {
answer += stack[len(stack)-1]
}
}
return answer
}
That's it for day 5 of AoC, hoped you enjoyed reading it, and feel free to suggest improvements to my poor Go or solution
You can find the complete code here
Thanks for reading!
Top comments (0)