Skip to content
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Go to file
Cannot retrieve contributors at this time

Day 16

all / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13 / 14 / 15 / 16 / 17 / 18 / 19 / 20 / 21 / 22 / 23 / 24 / 25

Available as an RSS Feed

Prompt / Code / Rendered

Today was a nice little self-contained constraint satisfaction problem! Well, it didn't have to be (apparently), but it was fun as one :)

First, our data type:

type Passport = [Int]

data Info = Info
      { iFields :: IntervalMap Int (Set Text)
      , iYours  :: Passport
      , iTheirs :: [Passport]

Here we're using IntervalMap from the data-interval package, which makes it easy to store data at different intervals with easy lookups. For example, if we have ["class"] at interval (1,5), and we had ["row"] at interval (3,7), IntervalMap will merge them together (with <>, if we choose) to get ["class"] at (1,3), ["class","row"] at (3,5), and ["row"] at (5,7).

If we have this IntervalMap, part 1 becomes straightforward enough with the efficient IM.notMember:

import qualified Data.IntervalMap.Lazy as IM

part1 :: Info -> Int
part1 info = sum
    [ n
    | ns <- iTheirs info
    , n  <- ns
    , n `IM.notMember` iFields info

So now let's move on to the search for part 2!

Our goal is to get a list [(Int, Set Text)] of a column number (in the passport) with the set of all valid field names for that position. And because we are going to be doing a search, we want this list in order of smallest to largest valid-name sets.

First, we can replace the Ints in each passport instead with the set of fields they are valid for

validate :: IntervalMap Int (Set Text) -> [Int] -> Maybe [Set Text]
validate flds = traverse (`IM.lookup` flds)

validateAll :: IntervalMap Int (Set Text) -> [Passport] -> [[Set Text]]
validateAll flds = mapMaybe (validate flds)

Here (`IM.lookup` flds) is Int -> Set Text: it'll look up the Set Text corresponding to the interval that the Int falls under in the IntervalMap. It'll return Nothing if any of the Ints are invalid, and Just if all of the Ints are valid.

Next we want to build our [(Int, Set Text)]. The Set Text is a set of what is valid for that column number, so to get the Set Text for 0, for instance, we need to S.intersection all of the first Set Texts in our list,; to get the Set Text for 1, we need to S.intersection all of the second Set Texts in our lists, etc. This can be done succinctly with a transpose (transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]). Then we can use sortOn to sort by the size of the valids set.

columnSets :: [[Set Text]] -> [(Int, Set Text)]
columnSets = sortOn (S.size . snd)
           . zip [0..]
           . map (foldl1' S.intersection)
           . transpose

Now we're ready for our search! We'll be using StateT over list, to get a backtracking search with backtracking state (I described this technique in a constraint solving blog post). Our state will be the Set Text of all the "committed" fields so far.

search :: [(Int, Set Text)] -> Maybe [(Int, Text)]
search candidateMap = listToMaybe . flip evalStateT S.empty $ do
    for candidates $ \(i, cands) -> do              -- for each (Int, Set Text):
      soFar <- get                                  -- get the seen candidates
      pick  <- lift . toList $ cands S.\\ soFar     -- pick from the Set Text not including seens
      (i, pick) <$ modify (S.insert pick)           -- propose this index/pick, inserting into seens

And that should be it for our search! In the end this gets the first [(Int, Text)] that is valid, matching a column ID to the field at that column. Our search supports backtracking through the list monad, but it should be noted that we actually don't end up needing it for the way the puzzle input is structured. But, because we sort our lists first from smallest to largest valid-sets, our solution ends up being equivalent to the non-backtracking method and backtracking is never actually triggered.

And we can wrap it all up:

part2 :: Info -> Int
part2 = product
    [ iYours info !! i
    | (i, fld) <- res
    , "departure" `isPrefixOf` fld
    cSets    = columnSets $ validateAll (iFields info) (iTheirs info)
    Just res = search cSets

Back to all reflections for 2020

Day 16 Benchmarks

>> Day 16a
time                 819.9 μs   (816.9 μs .. 823.7 μs)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 811.0 μs   (807.4 μs .. 819.9 μs)
std dev              16.97 μs   (9.577 μs .. 31.05 μs)
variance introduced by outliers: 11% (moderately inflated)

* parsing and formatting times excluded

>> Day 16b
time                 3.517 ms   (3.485 ms .. 3.580 ms)
                     0.998 R²   (0.994 R² .. 1.000 R²)
mean                 3.508 ms   (3.493 ms .. 3.554 ms)
std dev              79.20 μs   (23.71 μs .. 158.8 μs)

* parsing and formatting times excluded