Description: advent of code 2020 solutions in haskell :)
Compute Environment: Ubuntu 18.04 (Stable)
Advent of Code 2020 in Haskell
Day 1: Report Repair
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:
In [ ]:
solve_d1p1::[Int]->Intsolve_d1p1list=head[x*y|x<-list,y<-list,x+y==2020]-- we take the first element since there could be multiple matches
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 mapped read to convert to [Int]. To actually solve the problem:
In [ ]:
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 gives us a password policy, and asks us the find how many passwords are valid given their policy. Each line is in the form:
m-n c: p
requiring that the given password p must contain c at least m times and at most n times. For example given the list:
1-3 a: abcde
1-3 b: cdefg
2-9 c: ccccccccc
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 [a,b], 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)".
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:
stack install parsec
Let's import it:
In [ ]:
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:
passwordParser :: P.Parsec String () Password
to parse from a String to our very own Password type.
Notice that the string we want to parse is in the form:
N-N C: S
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 returning the type we want from the results. This will hopefully make sense then:
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:
In [ ]:
Pr.parsepasswordParser"""1-3 a: abcde"
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.
In [ ]:
importData.Either(fromRight)-- note that this was relatively recently introduced in 8.2.1 (Jul 2017).
byr (Birth Year) - four digits; at least 1920 and at most 2002.iyr (Issue Year) - four digits; at least 2010 and at most 2020.eyr (Expiration Year) - four digits; at least 2020 and at most 2030.hgt (Height) - a number followed by either cm or in: If cm, the number must be at least 150 and at most 193. If in, the number must be at least 59 and at most 76.hcl (Hair Color) - a # followed by exactly six characters 0-9 or a-f.ecl (Eye Color) - exactly one of: amb blu brn gry grn hzl oth.pid (Passport ID) - a nine-digit number, including leading zeroes.cid (Country ID) - ignored, missing or not.