After a rusty start of day 1, we have to fix a broken password database today Our input exists of a list of passwords and for each password a policy. This is our example input:

1-3 a: abcde
1-3 b: cdefg
2-9 c: ccccccccc

Looking the first part of each line is the policy, it means that there should be between 1 and 3 a's in the password. So the first one is a match. The second is not. There are no b's. The third is a match, there are 9 c's. The final answer is the number of matching passwords, for this example that would be 2.

To solve our problem today we are going to break it into smaller parts. A functional language like Haskell kind of forces you (or maybe it is better to say lends itself) to break things into basic parts. This is of course a good thing for a developer to do because it makes code more understandable and maintainable. Breaking a problem into small pieces gives us the ability to make easy changes when our requirements change.

The first part is parsing the input into structured information. I'm going to use the splitOn function which breaks a string into parts on a separator.

splitInput line = (low, high, letter, password) where
  parts = splitOn " " line
  parts2 = splitOn "-" (head parts)
  low = read (head parts2) :: Int
  high = read (parts2 !! 1) :: Int
  letter = head (parts !! 1)
  password = parts !! 2

We first split with space as a separator, the first part is split again with - as a separator, the numbers are converted to Int with the read function. The four values are put together in a tuple. This is what I came up with, and it does the trick. A more experienced Haskell developer would have used a parser library like Megaparsec and the parsing function would look like this.

format = (,,,) <$> number <* "-" <*> number <* " " <*> anySingle <* ": " <*> many anySingle

This function does exactly the same thing, and really shows the power of Haskell. But until I properly learn how to do this, you will have to stick with the clunky function above.

Our next part is a function to match the password with the policy. We will filter our password on each character to match it against the character from the policy. And check to see if the length of the filtered string is between the low and high bounds.

isValid (low, high, letter, password) = low <= cnt && cnt <= high where
  cnt = count (==letter) password

And finally, we need one ring to rule them all, sorry I meant one function to put it all together.

solve = length . (filter isValid) . (map splitInput) 

we combine the map function with our splitInput function which runs splitInput on each line of our input and leaves us with an array of input tuples. The filter function loops over the array and only leaves the elements that return true for isValid, and finally we return the length of the filtered array. Running this on our example input gives us 2 as we expect. We run our program on the actual input and get the correct answer of 378 (This is probably different for your data set.) I always really love the feeling of having the answer the first time right.

Part 2

In part 2 we learn that the policy check is actually a little different. The information we get as input should be treated a little differently. The first to numbers are not bound, but indexes to the characters in the password (the index is one-based), and exactly one of the characters at the index should match the character of the policy. So from our example, the first line will match because the character at index 1 is an 'a' just like the policy, the character at index 3 is a 'c'. Since we build things in a flexible way, we are going to write a new validation function.

isValid2 (low, high, letter, password) = match1 || match2 where
  match1 = password !! (low - 1) == letter
  match2 = password !! (high - 1) == letter

We will change our function to combine everything a little so it can take a validation function as a parameter. Functions are first-class in Haskell, so we can easily pass them as a parameter. So our new function will look like this

solve f = length . (filter f) . (map splitInput)

solve1 = solve isValid
solve2 = solve isValid2

We see that we added the parameter f, and in the function body, we replace isValid with f. We can also see that we can call our solve function with the two validation functions. Running this on our input gives us 384, which unfortunately is not the correct answer. Bummer. Running this on our example input gives us 2, but in the explanation, it says that only the first would be valid. The second doesn't contain 'b' at all. And the third password matches 'c' on index 2 and on index 9. Oh wait a minute it should only match exactly once, so this one should not match. Let's change our isValid2 function, so either index 1 should match or index 2, but not both.

isValid2 (low, high, letter, password) = (match1 || match2) && (not (match1 && match2)) where
  match1 = password !! (low - 1) == letter
  match2 = password !! (high - 1) == letter

Probably this boolean logic could be done better, but since I want to finish as fast, I'm going to run this on the input. Now we get the correct answer 280.

Day 2 completed in a much better time than yesterday, and today we keep our scores, so that leaves me in third place within the ING leaderboard, much better.

Having a look at the code after finishing give a few improvements. First, the boolean evaluation could have been written much simpler.

isValid2 (low, high, letter, password) = match1 low /= match2 where

So a simple match1 is not match2 would have worked. The second thing that could have been simplified is that match1 and match2 both have the same implementation but differ in low or high. So we can replace that with one function

isValid2 (low, high, letter, password) = match low /= match high where
  match n = password !! (n - 1) == letter

Much cleaner, no duplication anymore. We did good today, and we learned that not bigger but smaller is better. See you tomorrow.

Day 1 Revisited

Yesterday I started out with a recursive implementation which I could not get to work. This was the function that I came up with

solve (x:xs) = if ((check x xs) > 0) then check x xs else solve (tail xs)

check n (y:ys) = if n+y == 2020 then n*y else check n ys

After finishing the assignment I got back to my original implementation to see where I went wrong. Did somebody already spot the error? Please let me know in the comments if you did. The idea of a recursive function is that you check one element and recursively call the function for the remainder of the array. So I did call solve with tail (which is the array minus the first element) on xs, the problem is that xs is already the tail of our input array, since we use (x:xs) pattern matching, which splits the array into the first element x and the tail xs. So I did a double tail and that caused my function to fail. Removing tail and adding the extra guards for empty arrays would have made a working implementation.