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
Day 16 asks us to use a set of integer range rules to examine potentially invalid tickets. Part 1 starts off easy - we need to identify values that do not satisfy any of the provided rules.
import D16input
-- rules :: [(String, (Int, Int), (Int, Int))]
-- ticket :: [Int]
-- others :: [[Int]]
type Rule = (String, (Int, Int), (Int, Int))
check :: Int -> Rule -> Bool
check n (_, (a,b), (c,d)) =
((n >= a) && (n <= b)) || ((n >= c) && (n <= d))
isValid :: [Rule] -> Int -> Bool
isValid rs n = any (check n) rs
solve :: Int
solve = sum $ filter (not . isValid rules) $ concat others
main :: IO ()
main = print $ solve
A check function implements the straightforward range check that returns whether an integer falls within one of the two ranges specified by a rule. This is used to write isValid, returns whether the integer satisifed any of the rules.
For part 1, we just need to take the sum of all of the invalid numbers irrespective of which ticket they are on, so we use concat to concatenate all of them into one list, then use our isValid function to filter out the values that are invalid.
Part 2
We are then asked to match the fields to the columns in order to reconstruct the actual ticket. This calls for a backtracking algorithm, but first we need to perform a little bit of preprocessing on our data.
-- The input has been modified so that rules are implicitly
-- keyed by Int instead of String. The six fields starting with
-- "departure" are keyed 0 to 5.
type Rule = ((Int, Int), (Int, Int))
check :: Int -> Rule -> Bool
check n ((a,b), (c,d)) =
((n >= a) && (n <= b)) || ((n >= c) && (n <= d))
isValid :: [Rule] -> Int -> Bool
isValid rs n = any (check n) rs
isTicketValid :: [Rule] -> [Int] -> Bool
isTicketValid rs ns = all (isValid rs) ns
The first step is to remove all tickets that contain any invalid values. With the help of our isValid function, we can easily write the isTicketValid function, which returns whether all values on the ticket satisfy one of the rules.
allSatisfy :: [Int] -> Rule -> Bool
allSatisfy ns r = all ((flip check) r) ns
isValidAtPosition :: [[Int]] -> Rule -> [Bool]
isValidAtPosition os@([]:_) r = []
isValidAtPosition os r =
let col = List.map head os
rest = List.map tail os
valid = allSatisfy col r
in valid : (isValidAtPosition rest r)
getValidPositions :: [[Int]] -> Rule -> [Int]
getValidPositions os r =
let flags = isValidAtPosition os r
in List.map fst $ List.filter snd $ zip [0..] flags
Next, we would like to be able to answer the question: for a given rule, what are the positions where it could be? This is based only on whether all of the values in that position satisfy the rule, and considers each ticket in isolation, without looking at any of the other tickets.
After writing a simple allSatisfy function that determines whether all values satisfy a given rule, we can write isValidAtPosition, which recursively considers each position and adds True to a result list if it could apply to the rule, and False otherwise. Note that this is not a simple map of allSatisfy over the other tickets because those tickets are represented a lists of rows, whereas we want to check against columns. Extracting columns is done by mapping head over the [[Int]], and the remainder to be processed is extracted by mapping tail.
getValidPositions then uses this to convert the collection of flags into a list of column indices. Finally, with this, we can implement our backtracking algorithm:
import D16input
-- irules :: [(Int, (Int, Int), (Int, Int))]
-- ticket :: [Int]
-- others :: [[Int]]
import Control.Monad
addAssignment :: [Int] -> [Int] -> [[Int]]
addAssignment curr validPositions =
[next:curr | next <- (validPositions List.\\ curr)]
solve :: Int
solve =
let filteredOthers = List.filter (isTicketValid irules) others
positions = List.map (getValidPositions filteredOthers) irules
assignment = reverse $ head $ foldM addAssignment [] positions
fields = List.map (ticket !!) $ take 6 assignment
in List.foldr (*) 1 fields
main :: IO ()
main = print $ solve
We represent an assignment as a permutation of the integers from 0 to 19 (since there are 20 fields in the input), arranged such that the zeroth integer gives the column corresponding to the zeroth rule, etc. Our strategy will be to build this list up by considering rules one at a time. If we ever come up to a rule where there are no positions available, we back out so that we can try other possible choices for the earlier rules.
In Haskell, this sort of algorithm is implemented very nicely by performing our computations within the list monad. Running out of positions would result in an empty list, which would effectively cut off all future steps (recall that computation in the list monad has flavors of cross-product, and a cross-product with an empty set is an empty set). While we could implement this using do notation, as we did in earlier days, we will use foldM, which performs a monadic fold to accumulate into the final assignment.
Let's start with a helper addAssignment function. This takes a "current" list (i.e., the list of valid assignments that we have built up so far), and then creates list of lists by trying each possible position for the next rule. The trick here is that we do not just try every possible valid positions of the next rule. Instead, we try all valid positions except for those we have already taken. This has the effect of "accumulating" all of the lists of valid positions into a list of valid assignments.
In other words, here is what we've accomplished. After the first iteration, we have a list of all possible assignments of the first rule. After the second iteration, we have a list of all possible assignments of the first and second rules, without repetition. After the third iteration, we have a list of all possible assignments of the first, second, and third positions, again without repetition. Once we have "folded" in all lists of valid positions in this way, we are left with all possible valid assignments of all 20 fields. It is guaranteed by the problem that we will have exactly one valid assignment, so we can take the head to extract it. However, more generally, this method will actually return all valid assignments, in those cases where the constraints imposed by the other tickets do not yield a unique assignment. For the sake of efficiency, we construct the list backwards (prepending the next element to the head is more efficient than appending the next element at the end), so we reverse the final result as well before calling it our one true assignment.
Finally, we use the assignment of positions to extract the fields on our ticket corresponding to the first six rules (which, by inspection of the input, are the rules whose names start with "departure"). Multiplying these together gives us the final answer.
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