Dec 06, 2022

Advent Of Code 2022 - Day 3 - Ruck Reorganization

For day 3, you had to identify objects that were in one or more compartments of a single rucksack or occur across multiple rucksack. A rucksack is a rugged backpack. Its typical usage is in military settings or hiking/backpacking and are usually packed to the brim with items.

Day 3's problem at the core was a string search problem. For Part I, each line of the input was treated as a rucksack with 2 equally sized compartments that you had identify yourself.

vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw
 

In each compartment, you needed to find the character that appears in both and based on that characters id, determine a priority and sum up the priorities. The priorities are:

• Lowercase item types a through z have priority values 1 to 26, and,
• Uppercase item types A through Z have priority values 27 to 52.

Part I

I began by substringing the lines into two halves, incurring some off by one errors along the way and then did what amounted to a full random search (n^2 worst case) because the two halves weren't guaranteed to be in any sort of order beforehand.

After getting the matches, I ran through them and subtracted the appropriate constant per the ASCII chart to convert the character to the 1 - 52 range.

fun part1(): Any {
    val common = mutableListOf()

    while (scan.hasNextLine()) {
        val localMatches = mutableSetOf()
        val line = scan.nextLine()
        val len = line.length
        val part1 = line.substring(0, len / 2).toCharArray()
        val part2 = line.substring(len / 2).toCharArray()
        part1.forEach { if (part2.contains(it)) localMatches.add(it) }
        common.addAll(localMatches)
    }
    return common.sumOf {
        if (it.isLowerCase())
            it.toInt() - 96
        else (it.toInt() - 38)
    }
}
 

Part II

For Part II, the goal was now to identify the common item between groups of three rucksacks. That new requirement made the solution for Part I unsuitable for Part II. It already had a slow runtime but the n was small so it was manageable. n^3 time is hard to justify in any circumstance.

To speed things up, I altered the order of my transformations. First, the code to convert the item types into priority ids was spun out into its own function.

fun charToScaledInt(c: Char): Int {
    return if (c.isLowerCase())
        c.toInt() - 96
    else (c.toInt() - 38)
}
 

The next problem to solve was the variable ruck size. This would wreak havoc on the search code as you could easily throw ArrayIndexOutOfBoundsExceptions. The solution was to normalize the ruck strings into IntArrays. The code in processString is essentially the first part of Counting Sort

fun processString(input: String): IntArray {
    val array = IntArray(53)
    input.forEach {
        val index = charToScaledInt(it)
        array[index] += 1
    }
    return array
}
 

The sorted rucks can be searched in linear time with one pass versus n^3. Here's the full part II code:

override fun part02(): Any? {
    var sum = 0
    while (lines.isNotEmpty()) {
        val elf1 = processString(lines.removeFirst())
        val elf2 = processString(lines.removeFirst())
        val elf3 = processString(lines.removeFirst())

        for (i in 0..53) {
            if (elf1[i] > 0 && elf2[i] > 0 && elf3[i] > 0) {
                sum += i
                break
            }
        }
    }
    return sum
}