Advent of Code 2020 in Haskell
Day 1: Report Repair
Part 1
In the first part of the first day of AoC, we are asked to find from a list, the two elements which sum to 2020, and report their product. In mathematical notation, this would be:
Assuming we have somehow managed to parse the input as a list of integers [Int]
, we can translate the notation directly to Haskell using a list comprehension:
To parse the input as [Int]
:
We used readFile :: FilePath -> IO String
to read the contents of the file, applied lines :: String -> [String]
to split it line by line, and finally map
ped read
to convert to [Int]
. To actually solve the problem:
Part 2
Part 2 does a simple twist, it wants us to find THREE elements satisfying the same condition. We just change the list comprehension to include a third element z
and the condition to x + y + z == 2020
Day 2: Password Philosophy
Part 1
Day 2 gives us a password policy, and asks us the find how many passwords are valid given their policy. Each line is in the form:
requiring that the given password p
must contain c
at least m
times and at most n
times. For example given the list:
We see that 2 passwords are valid. The middle password, cdefg
, is not; it contains no instances of b
, but needs at least 1. The first and third passwords are valid: they contain one a
or nine c
, both within the limits of their respective policies.
Let's start by defining a data class Password
to contain the policy and the password for each line:
We will worry about parsing the string later, and focus on the algorithm. To determine if a password is valid, we have to check the number of occurrences of c
in password p
(using countChar
)and check if it is in the range [m, n]
(using isIn
).
isIn
is simple, for x to be in the range , it has to be "bigger than or equal to a" AND "smaller than or equal to b". The reason I put the limits a
and b
into their own tuple is because I want to be able to use it in infix form like "x isIn (a,b)
".
Counting the occurrences is a bit trickier: basically we want to filter
the elements of a list checking their equality to a given element. For example:
Then to calculate the number of occurrences, we simply determine how many elements we are left with:
Thus:
Re-defining the isValid
now that we wrote the others:
Let's check if it works:
I have told you that we would worry about the parsing later: now let's worry! While we could use regex
or even multiple split
operations to extract the data we want from the given string, I have taken this challenge as an opportunity to learn parsing in Haskell. I used the famous library parsec
*. Note that using a parser for this specific task is probably an overkill, but hey, aren't we here for learning new things?
To install parsec
using stack
:
Let's import it:
Notice how we used a qualified
and aliased
import. This is mainly because we don't want to pollute our name space with pesty 3rd party libraries ! 😃
Now parsec
is a full-fledged parser library, which you can use to parse very complicated languages: we will be using it to parse a simple string without any nested complicated structures or anything, so we will mainly limit ourselves to the mini parsers in Text.Parsec.Char
*, which parse characters one at a time.
The main type of a parser in Parsec
is Parsec s () a
, which parses a type s
into a type a
(it actually parses it into an Either
, but we will deal with that later). So our function passwordParser
will have the type:
to parse from a String
to our very own Password
type.
Notice that the string we want to parse is in the form:
where N
is an integer, C
is a character and S
is a string. Then corresponding to these types, we will use the the mini parsers digit, letter, anyChar
and the modifier many
. As the names imply, digit
and letter
parse digits and letters, whereas anyChar
matches any character. many
applies the given mini-parser zero or more times, and returns the resulting [Char]
.
Finally, Parsec
lets us define the password in a do
block, binding the results using <-
and then return
ing the type we want from the results. This will hopefully make sense then:
To test our parser, Parsec
helpfully gives us parseTest
:
YAY! There is only one slight problem remaining, the parseTest
function is intended for tests only, and the real parse
function is an Either
type, containing a ParseError (Left)
if there is an error, or the value we want (Right)
. Being good coders, we care about error handling, so we won't use parseTest
to actually parse.
If there is no error, parse
returns:
To extract the real value, we can use fromRight
or a case
analysis. fromRight
is more concise, we simply give a default
value to be outputted in the case on an error (Left), and it automatically extracts the value for us.
Thus the main function to convert the given string to Password
is simply:
Phew! As last steps: let's read all the lines from the file and convert them into Passwords
:
It appears to be working ! Now let's filter them using isValid
and find how many of them satisfy their password policies.
Part 2
Part 2 gives us another password policy: it now requires "exactly one of these positions must contain the given letter". Then, given
the policy requires either p[m]
or p[n]
to be c, but not both! The operation "a
or b
but not both" is known as the exclusive-or (XOR) function. We can simply define it as:
and use it infix:
Now all we have to do is check both locations to see if they are the character c
, and xor
the results. We are warned however:
(Be careful; Toboggan Corporate Policies have no concept of "index zero"!)
Thus here are the relevant isValid
and solve
functions:
Day 4
Part 1
Part 2
Day 5
Part 1
Part 2
Day 6
Part 1
Part 2
Day 7
Part 1
.
.
.
.
.
.
.
.
.
.
.