Today’s problem turned out to be more of a parsing problem than a logic problem for me. Last year when doing AoC in OCaml, I wrote my own parser combinator library and I’m heavily considering doing the same in swift just to learn how to better, but even then a parser combinator wouldn’t have helped me nearly as much as I would have liked.
Parsing
Our input consists of three bits of information:
- the crates and which stack they are in
- the stacks number
- the operations to move crates from one stack to another
The first two are separated from the moves via a double line break and thankfully the moves are fairly easy to break away. The stacks, however, are going to take a bit more work:
[D]
[N] [C]
[Z] [M] [P]
1 2 3
One thing to note is that each stack’s columns are 4 characters wide (with the exception of the last which is 3) so we could reuse our Array#chunked() extension from day 04 to get our stacks broken apart.
| 0 | 1 | 2 | 3 |
|---|---|---|---|
| [ | D | ] |
Note that we’ll want to use the safer version that slices to the chunk size OR the string length if it’s smaller to account for the last stack being of length 3 and not 4. Per chunk we can extract the second element to figure out if it’s a stack or empty space, something like this:
let rawStacks = lines.split(separator: "\n")
let stackDefinitions = rawStacks.dropLast()
.map { line in
Array(line).chunked(into: 4).map { $0[1] }
}
.reversed()
There’s a lot going on here, first we don’t care about the last line as it’s just the stack numbers so we call Array#dropLast() which will give us a collection that, when iterated over, will not include the final line. It’s a cleaner way of doing:
rawStacks[0..<rawStacks.count - 1]
Next, for each line we convert it to an array of String.Elements aka Characters and use our chunking function to get each stack broken apart. Finally we map over the array of chunks to give us back an array where each index corresponds to a stack and each element with either be an empty space or a crate letter. Finally, we reverse it which will make the next step of transposing these rows into our initial stacks array a lot easier. After running over our lines, we end up with a 2-d array looking something like this:
[
["Z", "M", "P"],
["N", "C", " "],
[" ", "D", " "]
]
Lastly, before we move onto parsing the moves and solving part one, we need to transpose our stack data such that we end up with an array where each index is a column or stack, as opposed to the current situation that we have, where each index is a row. Our final array that we’ll use for the solutions will look like this:
[
["Z", "N"],
["M", "C", "D"],
["P"]
]
First, we’ll need to make the array representing our stacks that we’re going to transpose into. It’ll be easier if we pre-fill it with empty arrays so that we can just append to the correct stack when we come across a crate, so we can use the Array(repeating:, count:) initializer and we’ll use the length of our first row as a quick a dirty count for the number of stacks that we have:
let numberOfStacks = stackDefinitions.first!.count
var stacks: [[Character]] = Array(repeating: [], count: numberOfStacks)
If number of crates is 3 for example, this is equivalent to:
var stacks: [[Character]] = [ [], [], [] ]
But it avoids hardcoding the length in, which is helpful when we want this code to run against both the example input and our own input file. Another approach would be to simply map over the first row, returning an empty array:
var stacks: [[Character]] = stackDefinitions.first!.map { _ in [] }
However, I wanted to show off the use of the Array initializer, and I think it’s a littler clearer than the map.
Finally we can transpose our data. For each row we’ll iterate over the elements and use the elements index to look up which stack array we need. We’ll also filter out spaces using swift’s for ... where syntax:
for stackRow in stackDefinitions {
for (idx, crate) in stackRow.enumerated() where crate != " " {
stacks[idx].append(crate)
}
}
Finally we’ve gotten our stack data parsed out and we’re onto the moves instructions before we solve this. Thankfully parsing the move is easier than the stack definitions.
First we’ll define a little container to make our code a little easier to read:
struct Move {
let numberOfCrates: Int
let fromStackIndex: Int
let toStackIndex: Int
}
Since the move instructions are all in the same fixed format, we can do a little trick rather than reach for something like regex (what I did when I initially solved this):
1> "move 3 from 5 to 2".split(separator: " ").map { String($0) }
$R0: [String] = 6 values {
[0] = "move"
[1] = "3"
[2] = "from"
[3] = "5"
[4] = "to"
[5] = "2"
}
For each line we can split on the spaces and take:
- the second element as our number of crates
- the fourth element as the stack to move the crates from
- the sixth element as the stack to move the creates to
func parseMoveLine(_ line: Substring) -> Move {
let parts = line.split(separator: " ")
return .init(
numberOfCrates: Int(parts[1])!,
fromStackIndex: Int(parts[3])! - 1,
toStackIndex: Int(parts[5])! - 1
)
}
The key part here is to subtract one from the stack numbers as the puzzle uses 1-indexing but our code operates in swift’s 0-indexing system.
Part One
After the rearrangement procedure completes, what crate ends up on top of each stack?
At this point we’ve got our stacks, modeled as an [[Character]] and our move instructions in an [Move]. For each move, we’ve got an amount of crates to transfer from one stack to another stack and this happens sequentially. For example, the line move 3 from 1 to 3 requires us to pop a crate off of stack number 1 and append it to stack number 3, and we’ll do that three times.
Using the example, we start with the following stacks:
[
["Z", "N"],
["M", "C", "D"],
["P"]
]
After the first instruction move 1 from 2 to 1 We’ll have:
[
["Z", "N", "D"],
["M", "C"],
["P"]
]
The next instruction brings us to this process of popping and appending in a much more noticeable way, though: move 3 from 1 to 3. After the first pop, we end up with:
[
["Z", "N"],
["M", "C"],
["P", "D"]
]
Notice we didn’t move 3 all at once, this means that our crates that are getting moved around will be getting reversed in order each time multiples are moved per instruction, as see in the second and third crates getting moved by this instruction:
[
[],
["M", "C"],
["P", "D", "N", "Z"]
]
We’ll do this process with the following:
for move in moves {
for _ in 0..<numberOfCrates {
let movingCrate = stacks[move.fromStackIndex].popLast()!
stacks[move.toStackIndex].append(movingCrate)
}
}
Notice that our logic looks pretty much as we described it, the actual solution is fairly simple while the difficulty laid in the parsing for this problem!
Part Two
After the rearrangement procedure completes, what crate ends up on top of each stack?
Next up we’ve got a twist: we’re going to move all of the crates all at once. Now our second instruction in our example results in this:
[
[],
["M", "C"],
["P", "Z", "N", "D"]
]
Notice how the group of three crates from stack one, Z, N, D remains in the same order as they’re moved rather than being reversed due to the pop/append process? Instead of popping a single crate off at a time, we’ll just slice off the top using suffix(from:) to get the crates and removeLast(_: Int) to remove them from the stack we are moving them from, and append(contentsOf:) to add them all at once, in the same order that we removed them in, to our stack we are moving to. Writing some pseudo-code would give us something like:
let length = stacks[move.fromStackIndex].count
let slicePoint = length - move.numberOfCrates
let fromStack = stacks[move.fromStackIndex]
stacks[move.toStackIndex] = stacks[move.toStackIndex] + fromStack[slicePoint..<length]
stacks[move.fromStackIndex] = fromStack[0..<slicePoint]
We can make this a little more expressive using the suffix(from:), removeLast(_: Int) and append(contentsOf:) functions:
for move in input.moves {
let length = stacks[move.fromStackIndex].count
let slicePoint = length - move.numberOfCrates
let movingCrates = stacks[move.fromStackIndex].suffix(from: slicePoint)
stacks[move.fromStackIndex].removeLast(move.numberOfCrates)
stacks[move.toStackIndex].append(contentsOf: movingCrates)
}
Some languages have a “removeAndReturn” method which might reduce the lines here by one, but this isn’t the worst considering half of it is calculating an index to start the suffix from!