We have to crack some cipher today, to do that we have to find a weakness in the encryption. I shall go into the solution a little bit deeper to explain how list comprehension works as it is such a powerful feature of the language..

Our input is a list of numbers, the numbers follow a rule and the first number that breaks the rule is our weakness. The first number that is checked is the 26th number, for this number to be valid it has to be a sum of two numbers in the first 25 numbers (called the preamble). For the next number (27th) it has to be the sum of two numbers in the range of the 2nd number until the 26th. And so on. The first number that doesn't follow this rule is the weakness and also the answer to our puzzle. My cleaned implementation looks like this.

solve1 = go 25 where
  go n xs | x `elem` sums = go n (tail xs)
          | otherwise     = x where
    (preamble, (x:_)) = splitAt n xs
    sums = [x + y | (x:ys) <- tails preamble, y <- ys]

n is 25, the length of the preamble. For testing the example a length of 5 was used, so that's why it is an argument. xs is our input and we are using the splitAt function and pattern matching to split it into preamble(1st until 25th) and x(6th) number.

We are going to use list comprehension and tails to find all the sums of two numbers in the preamble. The tails function takes a list and outputs a list of lists. The first list in the output is the same as the input. The second is the tail of the first element. The third is the tail of the second and so on until there are no more elements. It will be more clear in an example

Haskell> tails [1,2,3,4,5]
[[1,2,3,4,5],[2,3,4,5],[3,4,5],[4,5],[5],[]]

List comprehension is a powerful tool to create lists. Let's start with a very simple example which gives the first 5 squared numbers

Haskell> [ x * x | x <- [1..5] ] 
[1,4,9,16,25]

It consists of two parts, the part before the | which is the output where the number x is actually squared (x * x). The part after the | is a generator, for each element in [1..5] it is assigned to x and creates an output element. You can already do some powerful things with this, but it becomes even better with more generators.

Haskell> [ x * y | x <- [1..5], y <- [x..5] ] 
[1,2,3,4,5,4,6,8,10,9,12,15,16,20,25]

When there is more than 1 generator they are used left to right. So in this case first x is 1, and then we have a look at the second generator, which goes from x to 5, so 1 to 5. This gives us the numbers 1,2,3,4,5 in the output. Then x becomes 2 and y goes from 2 till five giving number 4,6,8,10, and so on. The x from the first generator can be used in the second, but not the other way around. If there was a third generator, x and y could have been used there.

After the generators, we can add guards, which will add something to the output or not based on the predicate.

Haskell> [ x * y | x <- [1..5], y <- [x..5], even (x * y) ] 
[2,4,4,6,8,10,12,16,20]

This is the same as the previous list but only the even numbers. Just like generators, multiple guards can be added, but they have to be after the generators.

Let us see what happens in our sum function. As an example, we shall take a very small list for the preamble: [5,7,8]. First, the tails function is called on the list which will give [[5,7,8],[7,8],[8],[]]. In the first iteration, the generated element is [5,7,8], which is assigned via a list pattern, x becomes 5 and ys becomes [7,8]. y get assigned 7. Sum is 5 + 7 = 12. Next, y becomes 8. Sum is 5 + 8 = 13. Next first generator gives [7,8] which gives x is 7 and ys is [8]. y becomes 8. Sum is 7 + 8 = 15. Next [8] comes from the generator. x = 8 and ys = []. The second generator will not yield a value. Next, the generator gives [] which gives an error while assigning it to the (x:ys) pattern and it will be skipped. The result is [12,13,15]. All in a small table for clarity.

step | (x:ys). | x | ys    | y | x + y
     | [5,7,8] | 5 | [7,8] | 7 | 5 + 7 = 12
     | [5,7,8] | 5 | [7,8] | 8 | 5 + 8 = 13
     | [7,8]   | 7 | [8]   | 8 | 7 + 7 = 15
     | [8]     | 8 | done  |   |
     | error   |   | []    |   |
     

For a preamble of 25 numbers, there will be 25 * 24 = 600 sums. The list comprehension is lazy, so not everything will be generated. If the correct value is found before the end of the list, the end of the list will not be generated. The next step in our code is the go function, which has two guarded implementations. The first will check to see if x is an element in sums, in that case, it is a valid number and the function will call itself recursively with the tail of the list, so effectively doing the same thing again, but without the first element. If the guard fails it will go to the otherwise branch, which will then always pass, it will return the invalid number x.

For the second part of the day, we will use the answer from part 1 and have to find a contiguous set of numbers that sum up to the answer from day 1. If such a sum is found, adding the highest and lowest number within the set is the final answer. The code ended looking like this.

solve2 xs = go (solve1 xs) xs where
  go n xs | r == n    = s
          | otherwise = go n (tail xs) where
    initsSums = [ (sum ys, minimum ys + maximum ys) | ys <- inits xs ]
    Just (r,s) = find ((>= n) . fst) initsSums

Again list comprehension is used to generate a list of tuples from the sums of the first elements of the list. The first element is the first element. The second is the sum of the first and second. The third is the sum of the first until the third and so on. The second part of the tuple is the sum of the minimum and maximum of the set. We use find to find the first sum that is larger than the number we are looking for. In the go function, we check to see if is an exact match and in that case return the second part of the tuple which is our answer. Otherwise, we call our function recursively with the tail of the list. So starting to generate sums starting from the second element, this will keep repeating.

It took me quite a while to get this implementation to work because I used tails instead of inits in the list comprehension. Two functions that do something similar, but give a completely different outcome.

Haskell> tails [1,2,3,4,5]
[[1,2,3,4,5],[2,3,4,5],[3,4,5],[4,5],[5],[]]
Haskell> inits [1,2,3,4,5]
[[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]]

Let me know if you liked learning about list comprehensions. If you do, have a look at what your own language can bring you. There are multiple languages with similar features. See you again tomorrow or go back to the beginning of the series.