Advent of Code 2020 in Haskell - Day 6



Jump to:

D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25


Part 1

Day 6 was a lot of fun! I feel like I'm finally starting to write "Haskellic" code. Part 1 is a classic deduplication problem: given a list of strings, how many unique characters are there?

    
import D6input
-- input :: [String]
import qualified Data.Set as Set
import qualified Data.List as List

blankLineSplit :: [String] -> [[String]]
blankLineSplit lines = 
    let matchingBlankLineStatus s1 s2 = (s1 == "") == (s2 == "")
        grouped = List.groupBy matchingBlankLineStatus lines
        isNotBlankLineGroup g = (head g) /= ""
        in filter isNotBlankLineGroup grouped

countUniqueLetters :: [String] -> Int
countUniqueLetters = 
    Set.size . (foldr Set.union Set.empty) . (List.map Set.fromList)

solve :: Int
solve = sum $ map countUniqueLetters $ blankLineSplit input

main :: IO ()
main = print $ solve
    

Since the input is once again provided as groups of lines separated by a blank line, I decided to implement a cleaner way of dividing such input up into individual cases. This input format was seen in Day 4, where I didn't really like how it was handled there. The blankLineSplit function exploits the groupBy function to group the lines of the input. Our equality condition is "whether the line is blank", which will group the input into alternating groups of non-blank lines and blank lines. Finally, if we filter out to blank groups, we are left with the grouping we want. That's a bit of a mouthful, so here's an illustrative example:

["a","b","","c","d","","e"]
    groupBy results in
[["a","b"],[""],["c","d"],[""],["e"]]
    and filter results in
[["a","b"],["c","d"],["e"]]

I'll probably stick this in a library soon, as I bet this will come up again.

With that out of the way, we can focus on the problem of counting the number of unique letters that occur in a [String]. This is implemented by countUniqueLetters, with the help of the Set data structure. I really like how this function turned out - it's very naturally expressed in pointfree form. Essentially, we are saying that counting unique letters is equivalent to "first, turn all Strings into Sets of Chars; then, take the set union of all such Sets; finally, return the size of the union."

The final answer is obtained by simply applying countUniqueLetters to all of our groups obtained by blankLineSplit, and then summing the results together.

Part 2

Sometimes, part 2 is merely a small variation on part 1, and this is one of those times. Those familiar with set theory will immediately recognize that part 2 is the same question as part 1, but with set intersection instead of set union.

    
import D6input
-- input :: [String]
import qualified Data.Set as Set
import qualified Data.List as List

blankLineSplit :: [String] -> [[String]]
blankLineSplit lines = 
    let matchingBlankLineStatus s1 s2 = (s1 == "") == (s2 == "")
        grouped = List.groupBy matchingBlankLineStatus lines
        isNotBlankLineGroup g = (head g) /= ""
        in filter isNotBlankLineGroup grouped

countCommonLetters :: [String] -> Int
countCommonLetters ss = 
    let init = Set.fromList ['a'..'z']
        sets = List.map Set.fromList ss
        commonSet = foldr Set.intersection init sets
        in Set.size commonSet

solve :: Int
solve = sum $ map countCommonLetters $ blankLineSplit input

main :: IO ()
main = print $ solve
    

Instead of countUniqueLetters, we implement countCommonLetters instead. It's the same algorithm as above, but using Set.intersection instead of Set.union. I could have written it in pointfree form as well, but the statement ends up being a little long, so I broke it up with a let statement instead.

Note that our reduction starts with the set of all letters instead of the empty set, as we did for the union. The problem states that all characters will be in lowercase, so we specify that with ['a'..'z'].


Jump to:

D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25