Day 3 is a cute one. Again, simple lazy list processing parser taking advantage of the standard library, or writing lazy recursive functions.

One of those rare cases when using length is not frowned upon.

The Problem

We are given a dataset of unknown length. Lines have different even lengths, and look like a jumble of letters

    vJrwpWtwJgWrhcsFMMfFFhFp\n
    jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL\n
    ...

We are told to look at each line separately, considering its first and second half, to see if there's a shared element. For instance

    vJrwpWtwJgWrhcsFMMfFFhFp
      { split in half }
    vJrwpWtwJgWr hcsFMMfFFhFp
      { notice `p` is the single element in common }

There's a «priority» system with lowercase letters having values between 1 and 26, and uppercase letters having values between 27 and 52, respectively.

Main Program

The main program is pretty much the same as Day 1.

Parse and compute, all over again.

Part A asks to find the common element among both halves of each line, compute its priority, and total them up. So we're looking at this signature again

    partA :: String -> Int

and can break its implementation in three parts:

1. Parse the input String into a list of lines, using lines.

2. Have a way to find the sharedElement among two halves of a line, and compute its priority

    sharedElement :: String -> Char
    priority      :: Char -> Int
   

3. Add the list with sum.

This leads to a high level implemenation like so

    partA = sum . map (priority . sharedElement) . lines

You'll notice I'm using Int instead of Integer, because I'm going to take advantage of Enum typeclass for computing the priority.

Haskell's Data.List library, part of GHC's «base», provides a lot of handy functions for dealing with lists beyond those in the standard Prelude. There's a group of functions that allow you to treat lists as if they were sets, so you can compute union, difference, and interesection, the latter being exactly what we need to find out the common element. We write

    sharedElement :: String -> Char
    sharedElement r = head $ intersect f s
                        where
                          (f,s) = splitAt (length r `div` 2) r

As promised, one of those rare cases where you actually need to use length because there's no other cheap and clever way to split the list in half preserving positions.

Computing the priority takes advantage of Char being an instance of Enum. The instance follows the reasonable mapping for ASCII (and Unicode) from character entities to positive integers. This means 'a' is actually mapped to 97, its ASCII value, so we need to offset accordingly.

    priority :: Char -> Int
    priority c | isLower c = fromEnum c - fromEnum 'a' + 1
    priority c | isUpper c = fromEnum c - fromEnum 'A' + 27

And that's all it takes to solve Part A.

Just change a tiny bit, again

Part B just changes things a bit. Firstly, we need to consider lines in groups of three at a time. Secondly, we need to find out the single character common to all three lines. We see that it's similar to Part A, so we can reuse what we have:

1. Parse the input String into a list of lines, using lines.

2. Have a way to grab chunksOf a particular size. This function actually exists in a non-base Haskell library, so I chose to implement it myself and in a generic way, as one should.

    chunksOf :: Int -> [a] -> [[a]]
   

3. We need to find the commonElement for every group, and compute its priority

    commonElement :: [String] -> Char
   

4. Add the list with sum.

This leads to a high level implemenation like so

    partB = sum . map (priority . commonElement) . chunkOf 3 . lines

In order to have an efficient solution, it becomes important that the «chunking» happens in a lazy fashion. That way, map can start finding out commonElement and computing priorities immediately, without having all the list in memory at once.

This means writing chunkOf in an explicit recursive way

    chunksOf :: Int -> [a] -> [[a]]
    chunksOf _ [] = []
    chunksOf n xs = take n xs : chunksOf n (drop n xs)

It doesn't matter for this exercise, but it's important that you realize this implementation can actually handle infinite lists.

In order to find the commonElement of a chunk of any size, we make the following observation: a chunk is nothing more than a list of lists, and the problem specification ensures there will be a single common element, therefore said element must be present in all lists of the chunk.

So, for any non-empty chunk of arbitrary length

    [ l1, l2, l3, ..., lN ]

it follows that

    l1 `intersect` l2 `intersect` l3 ... `intersect` lN

will find the common element among all the lists, the result being a single element list. This pattern of recursion is the familiar fold over non-empty lists, so we write

    commonElement :: [String] -> Char
    commonElement = head . foldr1 intersect

And that's all it takes to solve Part B.

Conclusion

List processing is the core of functional programming, but with a twist that sometimes escapes the beginner: instead of worrying about how long the list is (computing the length) and then using loops with counters, we worry about a way to process groups of elements at a time.

That's why we favor using map and the fold family of functions, as well as writing additional function in a lazy recursive way. That is, we think of lists as control structures rather than mere data types. That is one of the «aha!» moments that will mark the transition from imperative thinking, to declarative thinking. In fact, we think about any recursive data structure as a control structure, but more on that on future AOC problems.

More often than not length is a terrible code smell in functional programming, specially in a lazy evaluation setting. If you find yourself writing Haskell and thinking «let's get the length and then count/move», you're not there yet: think harder and find a recursive solution.

This problem is cute in that the single use of length is entirely warranted.