A look back on the event
The hardest part of day 4 turned out to be reading the input file!
The problem is that I've been using the Megaparsec library to parse the input. This is a powerful parsing library, but it's been developed to assist the parsing of the languages that humans write. One of the key ideas is that tokens in the parsed filed are separated by spaces, and humans aren't very good at being precise when it comes to what they mean by "space". People can put different amounts of space in places, mix spaces and tabs, throw random line-breaks in the middle of expressions, and so on. That means that Megaparsec is very good at consuming all this white space and allowing you to focus on the actual text in the file.
But the input for today had fields separated by spaces (whether space characters, newlines, or both) and records separated by blank lines.
ecl:gry pid:860033327 eyr:2020 hcl:#fffffd byr:1937 iyr:2017 cid:147 hgt:183cm iyr:2013 ecl:amb cid:350 eyr:2023 pid:028048884 hcl:#cfa07d byr:1929 hcl:#ae17e1 iyr:2013 eyr:2024 ecl:brn pid:760753108 byr:1931 hgt:179cm hcl:#cfa07d eyr:2025 pid:166559648 iyr:2011 ecl:brn hgt:59in
The standard Megaparsec approach would be to treat all of that as "whitespace" and consume the lot, collapsing all the records into one.
I ended up with a complicated whitespace consumer that only consumed one newline character at a time (using
notFollowedBy to make sure there's only one newline). This combined with a
blankLines parser that accepts only blank lines.
sc :: Parser () sc = L.space (skipSome ( char ' ' <|> char '\t' <|> (try (newline <* notFollowedBy newline)) ) ) CA.empty CA.empty blankLines = skipSome newline kvP = (,) <$> stringP <* colonP <*> stringP passportsP = passportP `sepBy` blankLines passportP = M.fromList <$> many kvP
This does the job, but it's pretty fragile in not handling "blank" lines that contain some space characters. But it's enough to do the job for this task.
Now I could read the data, time to validate it. Not knowing what I'd be using the data for, I decided to store each passport as a
Map of key-value pairs.
The validation rules were a bit unclear (what if there are fields outside the specified ones? what if there are duplicates of a field?), but I decided to take the most obvious approach. I defined a
Set of required fields. To validate a passport, find the set of fields defined in it, subtracted that from the set of required fields. If the result is emtpy, all the required fields are present and the passport passes that stage of validation.
The code is much shorter than the explanation.
requiredFields = S.fromList ["byr", "iyr", "eyr", "hgt", "hcl", "ecl", "pid"] part1 = length . filter hasRequiredFields hasRequiredFields passport = S.null $ requiredFields `S.difference` (M.keysSet passport)
This was a bit fiddly. A passport validates if it has all the required fields, and each field passes validation. (As all I'm doing is validating key-value pairs, there was no need to convert the set of key-value pairs from the parser into a
Map only to convert it back. Oh well.)
part2 = length . filter validPassport validPassport :: Passport -> Bool validPassport passport = (hasRequiredFields passport) && (all validField $ M.assocs passport)
validField is just a big
case statement. Note that
cid always validates, and unknown fields always fail.
validField :: (String, String) -> Bool validField (key, value) = case key of "byr" -> validRanged 1920 2002 value "iyr" -> validRanged 2010 2020 value "eyr" -> validRanged 2020 2030 value "hgt" -> validHeight value "hcl" -> validHex value "ecl" -> validEye value "pid" -> validPid value "cid" -> True _ -> False
The rest of the validations are pretty much implementing the rules. Nothing much to see here.
validRanged lower upper value = if all isDigit value then v >= lower && v <= upper else False where v = read @Int value validHeight value = if u == "cm" then validRanged 150 193 v else if u == "in" then validRanged 59 76 v else False where (v, u) = span isDigit value validHex value = (length value == 7) && (head value == '#') && (all isHexDigit $ tail value) validEye value = value `S.member` eyeColours eyeColours = S.fromList ["amb", "blu", "brn", "gry", "grn", "hzl", "oth"] validPid value = (length value == 9) && (all isDigit value)