Advent of Code 2022 — Day 3

This is the third article in the series where I share my solutions to the puzzles from the Advent of Code 2022. This year I am using PHP and I created a platform for comfortable development. You can find more details about the platform here and feel free to use it as well.

<Day 2 | Day 4>

Photo by Larry George II on Unsplash

Before you start reading, I encourage you to try to solve the puzzle by yourself.

Rucksack Reorganization

Unfortunately, the Elf that was loading all the rucksacks with supplies for the jungle journey didn’t quite follow the instructions. That’s the reason why some of the items need to be rearranged.

Each rucksack has two large compartments. All items of a given type are meant to go into exactly one of the two compartments. The Elf that did the packing failed to follow this rule for exactly one item type per rucksack.

Today's input is a list of all the items in each rucksack. We have to find the errors. Item types are represented by lowercase or uppercase letters where each letter has priority.

• Lowercase a-z has priorities 1–26
• Uppercase A-Zhas priorities 27–52

To calculate the priority we can use mb_ord functions which give us the ASCII value of the letter and then subtract the corresponding offset to align with the range of priorities. Since lowercase a has an ASCII value of 97 we have to subtract 96 from all lowercase letters. Uppercase A has a value of 65 since uppercase priorities start at 27 we need to subtract 38.

protected function getPriority(string $char): int
{
    $char = mb_ord($char);
    if (($char > 64 && $char < 91)) {
        return $char - 38;
    } elseif ($char > 96 && $char < 123) {
        return $char - 96;
    }

    return 0;
}

A given rucksack always has the same number of items in each of its two compartments in view of we have to split each input line in half.

function getCompartments(array $rucksack): array
{
    return array_chunk($rucksack, count($rucksack) / 2);
}

Towards the real fun, the goal of the main part is to find the priority of the intersection of those compartments and then sum the priorities for every rucksack. The scaffolding part is quite similar to the previous day.

public function run(array $input): int|string
{
    return array_reduce(
              $this->preprocessInput($input), 
              $this->sumPriorities(),
              0
           );
}

The preprocessInput function converts each line of the input to the array of individual letters.

protected function preprocessInput(array $input): array
{
    return array_map(function ($rucksack) {
        return mb_str_split($rucksack);
    }, $input);
}

The algorithm for finding the intersection of two sets (or n sets in general) looks like this. We said that the intersection is the first set. Then for the rest of the sets, we check whether the items in the intersection are present in the processed set. If not we drop the item from the intersection. In case we use the hash table (associative array in PHP) to represent the intersection the algorithm has quite good time complexity. In the worst case, it’s O(nk) where n represents the size of the first set and k represents a number of sets. In our case, we need to convert the input array of items in the compartment to the array of priorities.

protected function toPriorityArray($arr): array
{
    return array_reduce($arr, function ($arr, $ch) {
        $priority = $this->getPriority($ch);
        $arr[$priority] = $priority;
        return $arr;
    }, []);
}

Now we are ready to combine all the functions into the final algorithm.

protected function sumPriorities(): \Closure
{
    return function ($total, $rucksack) {
        $compartments = $this->getCompartments($rucksack);

        $intersection = $this->toPriorityArray(array_shift($compartments));
        foreach ($compartments as $compartment) {
            $priorityArray = $this->toPriorityArray($compartment);

            foreach ($intersection as $item) {
                if (!isset($priorityArray[$item])) {
                    unset($intersection[$item]);
                }
            }

        }

        $priority = array_sum($intersection);
        return $total + $priority;
    };
}

The second part

For safety, the Elves are divided into groups of three. Every Elf carries a badge that identifies their group. For efficiency, within each group of three Elves, the badge is the only item type carried by all three Elves.

The problem is that someone forgot to put this year’s updated authenticity sticker on the badges. All of the badges need to be pulled out of the rucksacks so the new authenticity stickers can be attached.

Additionally, nobody wrote down which item type corresponds to each group’s badges. The only way to tell which item type is the right one is by finding the one item type that is common between all three Elves in each group.

In other words, we have to find the intersection between the group of three rucksacks. Luckily we have already implemented the algorithm which can do that. The only thing we have to do is to modify the input in a corresponding way. The preprocessed input has to be grouped into groups of three.

protected function preprocessInput(array $input): array
{
    return array_chunk(parent::preprocessInput($input), 3);
}

And the compartments are now whole rucksacks.

public function getCompartments(array $rucksack): array
{
    return $rucksack;
}

Conclusion

Apart from the transformation of the input to a usable form, the task was only about the algorithm finding the intersection of the sets. Great generalization in the first part pays off and in the second part, we did just minor changes.

The complete source code of today’s solution can be found on my GitHub.

Do you want to know how I solve the other days? Please follow me here on Medium and don’t miss the following articles.

<Day 2 | Day 4>