🎄 Christmas Coding with Elixir, Day 2

Advent Of Code 2018

Santa: Big Elixir fan

Following on from yesterday, here’s the second puzzle of Advent of Code.

The Puzzle: Part 1

— — Day 2: Inventory Management System — -

You stop falling through time, catch your breath, and check the screen on the device. “Destination reached. Current Year: 1518. Current Location: North Pole Utility Closet 83N10.” You made it! Now, to find those anomalies.

Outside the utility closet, you hear footsteps and a voice. “…I’m not sure either. But now that so many people have chimneys, maybe he could sneak in that way?” Another voice responds, “Actually, we’ve been working on a new kind of suit that would let him fit through tight spaces like that. But, I heard that a few days ago, they lost the prototype fabric, the design plans, everything! Nobody on the team can even seem to remember important details of the project!”

“Wouldn’t they have had enough fabric to fill several boxes in the warehouse? They’d be stored together, so the box IDs should be similar. Too bad it would take forever to search the warehouse for two similar box IDs…” They walk too far away to hear any more.

Late at night, you sneak to the warehouse — who knows what kinds of paradoxes you could cause if you were discovered — and use your fancy wrist device to quickly scan every box and produce a list of the likely candidates (your puzzle input).

To make sure you didn’t miss any, you scan the likely candidate boxes again, counting the number that have an ID containing exactly two of any letter and then separately counting those with exactly three of any letter. You can multiply those two counts together to get a rudimentary checksumand compare it to what your device predicts.

For example, if you see the following box IDs:

abcdef contains no letters that appear exactly two or three times.

bababc contains two a and three b, so it counts for both.

abbcde contains two b, but no letter appears exactly three times.

abcccd contains three c, but no letter appears exactly two times.

aabcdd contains two a and two d, but it only counts once.

abcdee contains two e.

ababab contains three a and three b, but it only counts once.

Of these box IDs, four of them contain a letter which appears exactly twice, and three of them contain a letter which appears exactly three times. Multiplying these together produces a checksum of 4 * 3 = 12.

What is the checksum for your list of box IDs?

Solving It

Here’s our input:

And here’s some code to get our answer. Let’s break it down.

There’s quite a lot going on here. Boxes.group_by_letters/1 takes the list of box IDs and uses Enum.group_by/2 to move them into groups (once we’ve turned each string into an array of individual characters with String.codepoints/1). The second argument is the tiny anonymous function, &(&1), which simply returns the current element. As a result, the function groups each letter with other letters that match it i.e.

> ["a", "a", "a", "b", "b", "c"] |> Enum.group_by(&(&1))
%{"a" => ["a", "a", "a"], "b" => ["b", "b"], "c" => ["c"]}

Next, we use a nested map to convert this into an array of tuples.

> ["aaabbc", "def"] |> Boxes.group_by_letters
[[{"a", 3}, {"b", 2}, {"c", 1}], [{"d", 1}, {"e", 1}, {"f", 1}]]

Now we have a decent structure to work with!

The Boxes.ids_with_repeated_letters/2 function takes the above input (along with an integer) and returns all the tuples where the count value matches the given integer. We achieve this with Enum.filter/2 and then use Enum.reject/2 to get rid of empty arrays.

Once we have the filtered arrays for strings that occur twice and three times, we can use Enum.count/1 to tell us how many of each there are, then multiply them to get our checksum.

$ cat input.txt | ./advent2.1.exs
9633

Quite a lot of steps there, but nothing too groundbreaking.

The Puzzle: Part 2

— — Part Two — -

Confident that your list of box IDs is complete, you’re ready to find the boxes full of prototype fabric.

The boxes will have IDs which differ by exactly one character at the same position in both strings. For example, given the following box IDs:

abcde
fghij
klmno
pqrst
fguij
axcye
wvxyz

The IDs abcde and axcye are close, but they differ by two characters (the second and fourth). However, the IDs fghij and fguij differ by exactly one character, the third (h and u). Those must be the correct boxes.

What letters are common between the two correct box IDs? (In the example above, this is found by removing the differing character from either ID, producing fgij.)

Solving It

Here things get a little trickier.

We need to find two strings in a list of 250 that are identical except for a single different character. Here’s the code in full, and I’ll break it down afterwards.

Let’s start with Boxes.differences/2 on line 25. This takes two strings, then uses Enum.zip/1 to interleave the characters of each as an array of tuples e.g.

> [["a", "a", "a"], ["b", "b", "b"]] |> Enum.zip()
[{"a", "b"}, {"a", "b"}, {"a", "b"}]

Now we can use Enum.filter/2 to find pairs of characters that don’t match and Enum.count/1 to count them. If there’s only 1 character different, this function returns 1 (which we’ll use in the next function).

The Boxes.differences_of_one/1 function on line 18 takes a list of parcel ID numbers and then uses an Elixir comprehension to generate all possible combinations. In order to find the two parcels that have IDs differing by one, it makes sense to have a list of all possible pairs so the comprehension is an easy approach to build it.

Here it is in action:

> for a <- 1..3, b <- 1..3, do: [a, b]
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]

As you can see, it generates duplicates ([1, 2] is the same pair as [2, 1])! To work around this, we use Enum.sort/1 in the comprehension do-block and then Enum.uniq/1 to filter out the unique combinations.

Now it’s a simple case of Enum.filter/2, using our Boxes.differences/2 function to find pairs of IDs that differ only by one.

So that’s most of the work done! The Boxes.common_letters/1 function on line 4 takes the unique pair of IDs we discovered and then tells us the common letters between them. To do this, we use Enum.zip/1 again to interleave them, Enum.reject/2 to remove any tuple with differing characters, then Enum.map/2 and Enum.join/1 to re-assemble the common characters into a single string again.

Tada! 🎉

$ cat input.txt | ./advent2.2.exs
lujnogabetpmsydyfcovzixaw

Summary

The list comprehensions in Elixir are very powerful for generating data. I strongly recommend checking out the documentation and then experimenting with them.

I’ll be adding my Ruby and Elixir solutions to Github if you’d like to read further: https://github.com/seanhandley/adventofcode2018

EDIT: My December turned out to be way busier than I’d expected and I bailed on this. Sorry folks ☹️