Dec 06, 2022

Advent Of Code 2022 - Day 5 - Supply Stacks

When I start a new problem, a lot of times I will look at the sample test data first to try and understand what I might need to do with the data. This test data for Day 5 had me perplexed for a bit.

    [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 premise is that you are in the supply docks and have a crane moving around containers. You must move them in a prescribed order and report their final state.

Part I

After a while, I realized it was the combination of a stack/queue problem and a regular expression problem. I HATE doing regexes. Further, in the first section of the input, the last line had the ids of the stacks and I could use that index position to find all the crates in that stack. The lines were varying lengths so I needed to make sure to not throw an index error but that was easy to manage.

val stacks = mutableListOf()
while(scan.hasNextLine()) {
    val line = scan.nextLine()
    if (line.isEmpty()) {
        break
    } else {
        stacks.add(line)
    }
}

val lastLine = stacks[stacks.size - 1]
val stackIds = stacks[stacks.size - 1].split(" ").filter{ it.isNotEmpty()}

val indices = stackIds.map { lastLine.indexOf(""+it) }

queues = Array>(stackIds.size) {i -> ArrayDeque()}
for (i in 0..stacks.size-2) {
    stackIds.forEachIndexed { j, value ->
            val index = indices[j]
            if (stacks[i].length > index) {
                val c = stacks[i][index]
                println("value  c:" + c)
            }
            if (stacks[i].length > index && stacks[i][index] != null && stacks[i][index] != ' ') {
                queues[value.toInt()-1].add(stacks[i][index])
            }
        }
}
 

The sneaky bit was the regex. My first version worked perfectly on the sample data but wasn't even close with the real data set. It turns out I made a subtle error that only became apparent when I switched datasets. My original regex only worked on single digits.

Regex("""move(\d)+ from (\d)+ to (\d)+""")

should have been

Regex("""move (\d+) from (\d+) to (\d+)""")

The parentheses define the digits as a matchable group, so putting the plus (indicating one or more items) causes the part of the input to be matched and affecting the results. With that sorted I could move the proper quantity of crates from the right source to the right destination.

fun moveObjects(queues:Array>, quantity:Int, source:Int, destination:Int) {
    repeat(quantity) {
        // remove from old
        val valueToPop = queues[source-1].pollFirst()
        // push to new
        if (valueToPop != null)
            queues[destination-1].addFirst(valueToPop)
    }
}
 

Part II

In Part II, you were still moving crates but instead of one by one, you needed to move them as a set and preserve initial ordering. To do this, I opted for a double ended queue as temporary storage and added items into it using addLast. When adding to the destination, I added each item to the front of the destination with addFirst but with the source items being repeated calls to removeLast on the temporary storage location. you could have done it with another data structure like a simple array but I'll take readability over terseness and having to track multiple indices.

fun moveCrates(q:Array>, quantity: Int, source: Int, destination: Int) {
    if (quantity == 1) {
        moveObjects(q, 1, source, destination)
    } else {
        val tempQueue = ArrayDeque()
        repeat(quantity) {
            val valueToPop = q[source-1].pollFirst()
            if (valueToPop != null)
            tempQueue.addLast(valueToPop)
        }
        while(tempQueue.isNotEmpty()) {
            q[destination-1].addFirst(tempQueue.removeLast())
        }
    }
}

override fun part02(): Any? {
    queuesClone.forEach{println(it)}
    instructions.forEach {
        moveCrates(queuesClone, it.first, it.second, it.third)
    }

    var topCrates = ""
    queuesClone.forEach {
        val peek = it.peekFirst()
        if (peek != null) topCrates += peek
        else topCrates += " "
    }
    return topCrates
}