Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25
Part 1
Ugh... let me just preface this by saying I'm not a huge fan of my solutions for this Day. Given the nature of the problem, I think this is definitely a problem where I would reach for an imperative style if I had the choice (seems like a good fit for Python). Anyways, here's Day 4, in which we need to parse sets of key-value pairs and perform validation, with part 1 focusing on making sure that each set contains every tag (or key). Each set is split across multiple lines, however, so we need to put some thought into how to parse them.
import D4input
--input :: [String]
--codes :: [String]
import Data.List
containsAll :: [String] -> [String] -> Bool
containsAll tags (c:[]) = elem c tags
containsAll tags (c:cs)
| elem c tags = containsAll tags cs
| otherwise = False
isValid :: [String] -> Bool
isValid lines =
let tokens = concat $ map words lines
tags = map (take 3) tokens
in tags `containsAll` codes
countValid :: [String] -> Int
countValid [] = 0
countValid lines =
let next = takeWhile (/="") lines
remainder = tail $ dropWhile (/="") lines
valid = if (isValid next) then 1 else 0
in valid + countValid remainder
solve :: Int
solve = countValid input
main :: IO ()
main = print $ solve
We start with a containsAll function, which returns True iff all elements of one list are found in another. It's implemented as a quick little recursive function: return False if we ever reach a string that is not contained in the list; otherwise, check the rest of the strings. This is an O(mn) algorithm that could be improved if we used a different data structure, but the lists in question here are small.
The isValid function takes a chunk of the input, intended to represent a single passport, and performs the validation. We use concat as well as map words to handle the multi-line nature of each chunk and give us a clean list of tokens moving forward. We also make the assumption that each tag or key is exactly three characters, and use map (take 3) to get a list of tags.
Finally, the countValid function handles the division of the input into chunks based on separation by blank line (each chunk being stored in next), and calculates the total valid count recursively.
Part 2
Part 2 adds additional validation. A valid passport not only contains all needed fields, but each field must now also satisfy various criteria.
import D4input
--input :: [String]
--codes :: [String]
import Data.Char
import Data.List
containsAll :: [String] -> [String] -> Bool
containsAll tags (c:[]) = elem c tags
containsAll tags (c:cs)
| elem c tags = containsAll tags cs
| otherwise = False
allTagsValid :: [String] -> [String] -> Bool
allTagsValid (t:[]) (v:[]) = isTagValid t v
allTagsValid (t:ts) (v:vs)
| isTagValid t v = allTagsValid ts vs
| otherwise = False
isHeightValid :: String -> Bool
isHeightValid s = let h = read (takeWhile isDigit s) :: Int
u = dropWhile isDigit s
in if u == "cm"
then h >= 150 && h <= 193
else h >= 59 && h <= 76
isHairColorValid :: String -> Bool
isHairColorValid (c:cs) =
let isHexDigit d = isDigit d || (d >= 'a') || (d <= 'f')
allHexDigits = foldr (&&) True (map isHexDigit cs)
in (c == '#') && allHexDigits
isEyeColorValid :: String -> Bool
isEyeColorValid = (flip elem) ["amb", "blu", "brn", "gry", "grn", "hzl", "oth"]
isPidValid :: String -> Bool
isPidValid pid = (length pid == 9) && foldr (&&) True (map isDigit pid)
isTagValid :: String -> String -> Bool
isTagValid t v
| t == "byr" = let y = read v in y >= 1920 && y <= 2002
| t == "iyr" = let y = read v in y >= 2010 && y <= 2020
| t == "eyr" = let y = read v in y >= 2020 && y <= 2030
| t == "hgt" = isHeightValid v
| t == "hcl" = isHairColorValid v
| t == "ecl" = isEyeColorValid v
| t == "pid" = isPidValid v
| t == "cid" = True
isValid :: [String] -> Bool
isValid lines =
let tokens = concat $ map words lines
tags = map (take 3) tokens
values = map (drop 4) tokens
in (tags `containsAll` codes) && (allTagsValid tags values)
countValid :: [String] -> Int
countValid [] = 0
countValid lines =
let next = takeWhile (/="") lines
remainder = tail $ dropWhile (/="") lines
valid = if (isValid next) then 1 else 0
in valid + countValid remainder
solve :: Int
solve = countValid input
main :: IO ()
main = print $ solve
This solution uses the same countValid and isValid functions, except that all tags must be valid for a passport to be valid, which leads to the extra call to the new function allTagsValid. This offloads checking of an individual tag to isTagValid, which is a giant switch statement that performs the field-specific validation.
Most of these validation functions are fairly straightforward. I'm not a huge fan of the isHeightValid function presented here; it's quite brittle, and only works on inputs of the form [0-9]+(cm|in). Even isTagValid feels a little brittle, since multiple cases read the value from String to Int assuming it will just work. Technically, some of these guarantees are not provided by the question, but this solution does happen to work with the provided input.
I think the only other feature of the above solution that might be interesting is the use of flip in isEyeColorValid to concisely express the simple membership check. elem is a function that takes a value and a list (note the order) and returns whether value is an element of the list. (flip elem) therefore is a function that takes a list and a value (again, note the order) and returns whether the value is an element of the list. We can then partially apply the list of valid eye colors to get a function that determines whether a string is a valid eye color.
Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25