Done day 16

diff --git a/advent16/package.yaml b/advent16/package.yaml
new file mode 100644 (file)
index 0000000..3b53e87
--- /dev/null
+++ b/advent16/package.yaml
@@ -0,0 +1,62 @@
+# This YAML file describes your package. Stack will automatically generate a
+# Cabal file when you run `stack build`. See the hpack website for help with
+# this file: <https://github.com/sol/hpack>.
+
+name: advent16
+synopsis: Advent of Code
+version: '0.0.1'
+
+default-extensions:
+- AllowAmbiguousTypes
+- ApplicativeDo
+- BangPatterns
+- BlockArguments
+- DataKinds
+- DeriveFoldable
+- DeriveFunctor
+- DeriveGeneric
+- DeriveTraversable
+- EmptyCase
+- FlexibleContexts
+- FlexibleInstances
+- FunctionalDependencies
+- GADTs
+- GeneralizedNewtypeDeriving
+- ImplicitParams
+- KindSignatures
+- LambdaCase
+- MonadComprehensions
+- MonoLocalBinds
+- MultiParamTypeClasses
+- MultiWayIf
+- NamedFieldPuns
+- NegativeLiterals
+- NumDecimals
+# - OverloadedLists
+- OverloadedStrings
+- PartialTypeSignatures
+- PatternGuards
+- PatternSynonyms
+- PolyKinds
+- RankNTypes
+- RecordWildCards
+- ScopedTypeVariables
+- TemplateHaskell
+- TransformListComp
+- TupleSections
+- TypeApplications
+- TypeFamilies
+- TypeInType
+- TypeOperators
+- ViewPatterns
+
+executables:
+  advent16:
+    main: advent16.hs
+    source-dirs: src
+    dependencies:
+    - base >= 2 && < 6
+    - text
+    - attoparsec
+    - containers
+    - csp

diff --git a/advent16/src/advent16.hs b/advent16/src/advent16.hs
new file mode 100644 (file)
index 0000000..e636bbd
--- /dev/null
+++ b/advent16/src/advent16.hs
@@ -0,0 +1,113 @@
+-- import Debug.Trace
+
+import Data.Text (Text)
+-- import qualified Data.Text as T
+import qualified Data.Text.IO as TIO
+
+import Data.Attoparsec.Text hiding (take)
+-- import Data.Attoparsec.Combinator
+import Control.Applicative
+import qualified Data.Map.Strict as M
+import Data.List
+import Control.Monad.CSP
+
+
+type RuleSet = M.Map String Body
+
+data Body = Body Range Range -- the two ranges
+  deriving (Show, Eq)
+
+data Range = Range Int Int -- lower, upper bounds
+  deriving (Show, Eq)
+
+type Ticket = [Int]
+
+type ColCandidateSet = M.Map String [Int]
+
+
+main :: IO ()
+main = 
+  do  text <- TIO.readFile "data/advent16.txt"
+      let (rules, myTicket, nearbyTickets) = successfulParse text
+      print $ part1 rules nearbyTickets
+      print $ part2 rules myTicket nearbyTickets
+
+part1 = ticketErrorRate
+
+part2 rules myTicket nearbyTickets = product $ M.elems departureTicket
+  where 
+    columnDomains = possibleColumnsAll rules nearbyTickets
+    namedCols = knownCols columnDomains
+    filledTicket = buildTicket namedCols myTicket
+    departureTicket = M.filterWithKey (\k _ -> "departure" `isPrefixOf` k) filledTicket
+
+
+inRange (Range lower upper) value = (lower <= value) && (value <= upper)
+matchesRule (Body a b) value = (inRange a value) || (inRange b value)
+
+validForAnyField :: RuleSet -> Int -> Bool
+validForAnyField rules value = any (flip matchesRule value) $ M.elems rules
+
+ticketErrorRate :: RuleSet -> [Ticket] -> Int
+ticketErrorRate rules tickets = 
+  sum [ v 
+      | t <- tickets
+      , v <- t
+      , (not $ validForAnyField rules v) ]
+
+isValidTicket :: RuleSet -> Ticket -> Bool
+isValidTicket rules ticket = and $ map (validForAnyField rules) ticket
+
+possibleColumnsAll :: RuleSet -> [Ticket] -> ColCandidateSet
+possibleColumnsAll rules tickets = M.map (possibleColumns ticketCols) rules
+  where validTickets = filter (isValidTicket rules) tickets
+        ticketCols = transpose validTickets
+
+possibleColumns ticketCols body = map fst $ filter columnMatches $ zip [0..] ticketCols
+  where columnMatches (_, col) = all (matchesRule body) col
+
+
+knownCols :: ColCandidateSet -> M.Map String Int
+knownCols colCandidates = M.fromList $ zip names cols
+  where 
+    (names, colDomains) = unzip $ M.toList colCandidates
+    cols = solveColumns colDomains
+
+solveColumns :: [[Int]] -> [Int]
+solveColumns colDomains = oneCSPSolution $ do
+  dvs <- mapM mkDV colDomains
+  mapAllPairsM_ (constraint2 (/=)) dvs
+  return dvs
+
+mapAllPairsM_ :: Monad m => (a -> a -> m b) -> [a] -> m ()
+mapAllPairsM_ f []     = return ()
+mapAllPairsM_ f (_:[]) = return ()
+mapAllPairsM_ f (a:l) = mapM_ (f a) l >> mapAllPairsM_ f l
+
+buildTicket :: M.Map String Int -> Ticket -> M.Map String Int
+buildTicket namedCols ticketData = M.map (ticketData!!) namedCols
+
+
+-- Parse the input file
+
+inputP = (,,) <$> rulesP <* blankLines <*> myTicketP <* blankLines <*> nearbyTicketsP
+
+blankLines = skipMany1 endOfLine
+
+rulesP = M.fromList <$> (ruleP `sepBy` endOfLine)
+
+ruleP = (,) <$> nameP <* ": " <*> ruleBodyP
+nameP = many1 (letter <|> space)
+ruleBodyP = Body <$> rangeP <* " or " <*> rangeP
+rangeP = Range <$> decimal <* "-" <*> decimal
+
+myTicketP = "your ticket:" *> endOfLine *> ticketValsP
+nearbyTicketsP = "nearby tickets:" *> endOfLine *> (ticketValsP `sepBy` endOfLine)
+
+ticketValsP = decimal `sepBy1` (string ",")
+
+-- successfulParse :: Text -> (Integer, [Maybe Integer])
+successfulParse input = 
+  case parseOnly inputP input of
+    Left  _err -> (M.empty, [], []) -- TIO.putStr $ T.pack $ parseErrorPretty err
+    Right ticketInfo -> ticketInfo

diff --git a/data/advent16.txt b/data/advent16.txt
new file mode 100644 (file)
index 0000000..7e4189f
--- /dev/null
+++ b/data/advent16.txt
@@ -0,0 +1,268 @@
+departure location: 25-568 or 594-957
+departure station: 33-447 or 466-952
+departure platform: 31-700 or 725-956
+departure track: 43-124 or 141-952
+departure date: 26-290 or 306-962
+departure time: 34-754 or 763-960
+arrival location: 29-208 or 217-958
+arrival station: 48-118 or 124-973
+arrival platform: 35-368 or 389-972
+arrival track: 47-91 or 106-970
+class: 35-521 or 528-960
+duration: 27-833 or 855-965
+price: 25-870 or 895-957
+route: 31-140 or 146-965
+row: 35-736 or 743-957
+seat: 33-227 or 249-961
+train: 27-763 or 788-961
+type: 34-167 or 193-950
+wagon: 47-437 or 443-952
+zone: 48-928 or 940-955
+
+your ticket:
+113,197,59,167,151,107,79,73,109,157,199,193,83,53,89,71,149,61,67,163
+
+nearby tickets:
+659,831,365,819,499,735,227,617,597,323,200,413,863,803,5,753,925,468,632,658
+927,75,984,694,820,863,534,221,199,559,628,748,860,940,792,351,496,947,278,259
+418,710,489,833,397,567,488,620,158,218,199,857,271,566,911,790,152,489,746,421
+148,646,536,509,923,537,944,552,488,390,113,218,256,522,562,685,628,400,568,148
+470,488,669,648,802,323,801,109,926,496,207,267,68,397,565,196,648,648,815,383
+911,362,638,673,911,4,471,647,646,164,699,681,557,906,288,657,90,445,730,218
+493,679,809,398,116,544,405,692,616,736,662,410,316,201,906,403,322,314,331,703
+792,481,67,503,545,536,806,220,677,118,988,726,551,106,87,400,479,155,910,71
+863,322,355,482,550,432,157,661,113,749,308,805,77,167,75,107,645,885,529,506
+336,433,147,909,530,727,751,617,220,68,904,442,59,82,537,425,562,794,506,613
+329,908,363,321,504,419,794,521,269,417,285,189,568,940,912,902,498,57,421,558
+696,649,444,413,503,363,596,78,536,977,626,329,745,538,263,166,308,899,404,428
+613,919,354,163,278,919,865,158,614,419,620,260,128,205,567,651,792,153,820,685
+706,321,903,437,444,477,443,395,447,364,160,445,529,365,88,262,700,630,226,421
+790,236,632,411,865,60,405,266,315,64,356,107,146,118,644,699,608,503,792,447
+56,944,115,277,434,621,331,287,21,607,904,274,909,434,280,494,433,472,249,473
+888,323,672,419,447,635,678,391,788,791,331,403,274,664,270,686,194,338,403,736
+112,341,491,258,814,404,112,282,337,322,614,277,911,419,252,108,690,500,10,828
+312,392,337,669,508,557,200,694,309,226,700,909,16,343,289,333,754,262,664,789
+602,476,793,561,427,416,627,112,663,821,74,279,554,427,536,123,365,826,899,203
+54,685,193,321,866,650,417,196,680,287,79,360,117,62,495,412,272,205,438,681
+940,269,566,519,642,52,164,513,606,829,159,796,603,89,312,492,661,363,988,217
+156,826,316,525,895,902,823,619,149,310,863,536,208,495,685,533,594,813,284,355
+353,560,814,293,655,639,365,949,553,926,546,401,917,793,672,907,693,725,813,814
+604,636,124,69,259,682,602,343,863,640,154,445,531,625,509,942,292,796,624,197
+490,55,6,860,395,865,831,89,910,115,731,639,725,537,79,163,310,691,671,366
+276,196,442,221,594,644,273,660,594,418,810,808,436,108,429,609,261,281,664,863
+633,568,272,412,67,541,561,678,729,308,444,274,418,948,652,197,81,400,517,937
+155,736,402,897,595,615,55,266,109,404,280,692,625,918,735,759,633,421,903,672
+651,113,914,632,271,80,386,626,511,220,869,255,531,811,413,353,57,763,76,391
+331,546,82,266,826,326,54,945,933,948,920,118,287,903,801,106,358,163,618,676
+911,520,922,287,733,57,195,796,624,672,932,624,810,650,833,666,801,428,868,911
+108,65,79,272,818,265,544,80,426,809,671,218,152,936,353,630,664,493,445,113
+469,652,633,274,675,166,448,653,225,540,150,946,630,322,157,200,437,472,151,735
+636,275,670,680,164,285,771,312,869,628,898,653,912,492,500,520,640,655,223,196
+91,112,408,601,508,90,823,564,345,401,878,50,267,864,508,349,338,512,261,146
+397,549,803,74,394,637,150,685,922,868,870,407,330,997,903,492,833,223,308,332
+638,677,342,152,333,467,476,530,947,809,487,50,656,940,799,912,536,686,619,989
+688,605,258,668,152,50,815,642,631,107,410,946,154,124,768,819,407,85,917,856
+552,342,897,114,61,867,118,165,544,346,323,920,558,438,796,687,693,155,290,419
+155,406,331,899,499,312,796,820,747,870,699,323,83,385,365,151,744,317,665,193
+303,615,602,942,476,425,642,551,817,830,401,640,666,906,628,162,566,317,221,639
+258,0,506,513,548,537,258,405,255,679,631,659,792,365,799,532,420,556,499,159
+831,904,949,493,271,810,622,677,429,645,327,167,146,807,597,685,980,405,330,411
+683,614,403,274,743,661,367,830,625,687,361,54,918,53,618,703,948,565,611,320
+115,51,330,926,74,158,894,788,545,63,350,789,115,106,420,649,669,62,822,56
+284,898,410,517,827,613,943,310,686,161,283,904,362,492,664,203,330,142,259,927
+457,333,345,555,62,659,489,633,540,166,828,833,861,482,685,495,624,856,827,226
+355,940,224,145,864,629,147,308,437,415,913,926,662,679,273,402,156,635,156,306
+646,818,70,659,628,610,552,280,865,148,928,158,351,807,526,680,496,920,422,503
+942,208,511,151,899,489,414,912,811,497,865,613,684,480,185,351,490,689,476,567
+663,339,510,495,914,555,201,195,493,433,529,630,656,4,644,506,920,488,820,546
+656,512,568,621,731,206,283,419,391,895,306,486,593,560,631,519,434,66,697,619
+685,309,624,755,422,84,493,55,912,502,656,801,325,117,897,205,725,790,310,404
+485,446,219,726,619,725,748,400,814,217,941,668,770,227,108,735,220,788,672,150
+323,147,612,942,400,397,390,440,263,317,641,860,567,83,613,913,151,259,124,903
+619,456,503,631,193,685,601,551,909,916,433,534,819,510,476,686,817,497,763,313
+509,751,655,322,926,744,407,684,675,65,697,511,947,914,22,622,907,594,389,898
+242,907,252,823,543,686,700,788,905,867,52,901,336,155,258,202,330,902,422,469
+151,582,280,672,659,489,447,160,596,148,432,594,695,124,430,557,86,860,598,869
+791,64,353,686,641,802,792,288,256,208,928,687,819,945,307,628,426,993,473,426
+224,397,167,218,58,194,706,54,536,683,347,505,337,697,492,535,487,653,521,111
+611,634,627,645,556,501,108,314,81,310,86,354,697,351,881,328,432,310,534,416
+862,196,350,949,819,485,251,988,447,860,494,419,90,484,828,111,747,345,393,318
+307,509,731,337,252,150,204,678,499,919,327,826,59,309,439,824,749,436,813,76
+924,154,942,751,206,620,610,414,749,438,322,55,412,253,860,90,649,338,793,350
+683,185,906,915,661,829,198,831,670,943,683,434,566,415,58,529,263,78,164,201
+480,689,548,658,674,646,694,869,58,251,680,195,541,319,477,178,925,400,267,562
+251,809,901,809,162,66,87,810,159,287,543,485,802,400,72,81,217,643,531,120
+87,689,920,787,788,918,84,409,808,350,50,82,404,917,320,70,148,72,753,435
+77,269,665,632,422,205,409,626,158,553,200,406,942,207,271,531,266,370,116,159
+139,537,913,317,500,161,921,260,434,265,652,447,820,276,468,271,161,467,394,403
+405,110,412,670,336,618,113,4,745,202,254,221,420,349,166,79,336,219,434,866
+202,909,251,260,512,226,279,72,866,510,537,558,198,762,257,218,561,164,390,564
+905,253,743,107,944,431,499,148,307,728,251,320,178,288,155,659,921,68,813,261
+675,444,502,165,407,681,566,278,265,79,610,56,639,663,272,566,141,729,534,923
+636,948,91,921,526,487,604,609,636,529,947,319,915,515,112,409,830,490,696,124
+259,147,615,855,516,626,413,502,559,259,547,821,568,342,694,736,6,639,353,390
+392,346,150,669,682,310,745,510,260,925,376,789,729,665,620,497,856,505,925,916
+536,617,275,563,601,497,897,177,503,226,791,160,791,315,261,153,821,856,494,74
+154,412,54,896,616,111,226,596,492,735,603,901,603,696,933,353,856,509,653,652
+111,69,316,285,832,1,65,434,273,431,557,832,507,494,466,51,644,691,225,433
+339,158,306,120,272,493,556,84,446,910,612,506,606,655,826,629,626,474,520,684
+544,488,501,275,262,362,153,82,442,730,351,274,562,898,698,149,691,512,810,367
+913,611,830,856,641,312,437,280,436,331,162,70,891,687,113,80,404,533,225,602
+537,378,686,333,77,108,627,566,414,672,407,51,69,608,548,537,625,116,81,497
+289,727,912,820,350,538,317,327,946,276,942,428,620,447,870,483,282,862,736,525
+944,536,195,540,688,948,688,393,617,499,141,811,900,628,207,906,333,71,905,917
+149,292,857,649,321,614,227,346,467,916,637,500,753,804,348,306,561,358,161,332
+355,466,805,485,899,695,299,195,509,395,480,568,792,623,154,82,491,676,695,278
+436,405,264,745,51,76,679,324,536,665,650,208,936,699,362,415,325,624,264,75
+277,648,666,223,392,897,744,379,619,568,275,278,945,895,351,927,646,490,321,482
+210,445,315,616,360,597,551,604,696,913,665,795,164,751,606,824,162,434,558,264
+868,322,905,82,193,57,312,630,787,820,501,536,800,63,926,327,398,549,487,470
+736,827,520,551,747,815,935,390,536,730,56,601,218,553,478,745,753,312,343,683
+612,540,626,748,725,59,192,287,699,820,437,262,606,945,84,59,519,686,814,857
+869,427,548,473,749,429,16,609,365,395,62,66,480,443,155,898,68,443,352,471
+81,930,547,279,698,866,943,650,641,686,788,565,725,483,530,816,636,491,155,745
+84,637,389,870,408,478,689,314,142,55,566,283,690,61,149,504,162,667,697,686
+808,599,514,632,788,61,625,424,432,311,673,519,862,281,814,992,390,657,632,506
+898,608,483,269,62,362,274,272,747,796,149,807,89,597,919,652,604,341,858,296
+77,736,901,897,642,677,344,914,310,382,68,315,608,161,73,80,418,335,537,288
+896,410,498,673,635,797,307,111,857,390,59,321,824,288,608,87,61,943,686,755
+335,922,696,91,650,262,307,536,662,161,897,647,369,154,666,250,249,652,194,620
+50,269,699,697,807,323,517,116,621,908,663,559,224,532,200,780,807,612,594,357
+684,73,328,895,200,542,578,51,480,948,563,685,270,332,347,677,678,751,632,918
+942,858,411,288,546,418,616,489,468,546,68,289,658,446,330,572,354,87,250,69
+472,78,487,934,57,316,414,944,822,799,657,636,698,324,273,686,447,423,65,478
+409,429,696,620,472,831,808,197,413,492,944,486,316,917,545,529,420,540,618,23
+106,151,559,711,273,692,896,149,910,519,86,344,672,603,206,194,404,557,331,744
+605,108,519,255,56,282,444,793,361,167,669,261,314,733,340,797,694,916,685,787
+312,655,619,643,207,69,414,564,427,222,257,608,206,529,508,628,919,157,410,585
+759,81,642,147,814,559,726,796,260,72,390,257,423,902,669,618,272,688,86,793
+564,622,749,655,363,686,620,392,997,309,745,350,866,151,150,323,788,725,52,401
+534,599,114,855,919,347,431,801,423,523,260,367,275,685,553,687,348,478,271,116
+203,910,909,64,366,76,527,69,57,537,217,651,330,644,687,469,162,424,198,615
+897,494,499,430,322,617,67,108,595,110,515,549,394,804,979,603,747,356,357,162
+542,911,326,815,544,424,469,513,993,249,489,487,530,620,112,282,599,259,162,810
+495,259,641,659,625,866,806,655,809,549,160,901,726,320,387,747,794,315,925,286
+290,675,73,54,18,436,203,409,747,816,855,468,342,831,659,654,554,630,347,664
+434,482,362,333,612,268,330,161,156,615,226,218,494,51,416,283,524,391,392,671
+412,914,366,557,528,434,51,420,310,886,674,344,544,368,725,641,158,637,474,688
+17,815,109,646,306,288,911,822,321,159,699,904,674,476,799,201,539,201,945,401
+521,617,622,162,401,350,808,149,744,624,90,270,342,813,677,167,479,524,655,904
+251,325,161,536,635,610,745,406,257,601,517,64,947,808,797,926,801,731,595,142
+75,976,332,167,668,474,828,149,350,326,473,276,224,900,744,82,799,736,332,343
+217,423,949,919,270,923,333,620,541,275,409,553,684,74,987,54,348,650,648,354
+153,600,167,727,650,221,800,223,312,262,920,665,736,18,340,343,819,208,628,411
+439,940,220,654,84,320,598,599,616,869,622,59,605,315,349,425,896,217,534,731
+646,474,749,401,518,610,640,615,673,620,469,348,597,993,528,496,220,68,857,312
+260,655,634,443,597,79,868,268,114,282,923,763,164,632,727,928,138,124,356,117
+263,541,266,157,87,500,755,551,277,744,487,661,151,918,531,351,227,164,859,147
+825,906,526,88,733,466,331,900,866,625,471,640,669,351,682,905,158,560,594,633
+370,156,57,56,73,909,656,414,856,160,596,606,153,643,610,637,205,368,659,743
+748,628,155,477,485,80,473,812,338,857,202,662,349,445,336,490,672,56,200,998
+86,542,512,922,151,597,676,433,864,317,919,823,438,565,813,791,547,412,206,311
+606,539,541,926,289,670,204,261,81,790,905,530,818,403,306,473,501,183,750,112
+426,828,809,700,426,412,307,895,107,949,174,861,262,264,698,504,225,749,645,796
+403,411,433,270,601,390,645,537,315,166,514,829,562,478,359,667,149,831,76,211
+419,928,502,650,544,805,688,519,78,486,12,159,535,736,904,817,59,60,317,816
+620,901,915,333,415,154,629,538,643,429,285,18,681,258,261,307,806,895,494,203
+810,621,829,685,71,478,605,942,315,863,195,659,640,785,58,163,827,682,515,640
+491,430,275,249,323,484,747,73,65,312,830,260,412,319,410,792,781,428,117,831
+281,920,54,286,795,828,141,405,423,803,418,860,855,657,410,528,409,552,277,357
+856,738,736,679,365,814,644,729,520,344,635,568,520,331,515,73,830,224,411,273
+685,51,281,656,407,788,945,751,306,531,74,75,822,640,636,604,195,217,555,459
+804,821,4,792,415,53,163,656,402,497,251,562,512,676,397,405,164,423,400,516
+269,52,649,285,266,637,667,202,255,55,65,345,365,354,819,64,725,326,700,440
+803,745,926,432,482,628,745,698,306,621,441,111,650,115,445,66,855,661,443,435
+732,435,656,604,678,158,675,651,525,551,284,219,594,482,348,330,281,605,823,915
+602,832,399,683,855,467,309,488,330,817,635,154,595,428,534,629,534,342,914,999
+737,753,311,564,751,917,924,679,258,263,86,728,206,447,604,113,832,861,221,683
+824,330,289,513,536,153,664,317,157,357,344,253,525,390,903,319,664,330,310,162
+555,135,90,506,812,357,221,659,615,829,731,728,605,162,62,819,339,725,398,194
+252,941,56,928,551,532,518,523,421,672,111,820,395,549,922,529,800,501,477,816
+934,618,725,609,698,331,918,506,470,818,809,362,926,482,117,165,748,347,730,264
+645,812,393,799,754,329,255,445,483,332,664,524,925,626,347,492,685,699,948,673
+123,406,362,745,655,508,675,152,357,317,698,675,907,402,346,866,217,907,321,207
+539,783,903,342,288,339,151,667,694,567,567,198,699,816,675,490,559,197,79,631
+276,518,827,508,202,550,81,77,669,532,797,355,656,414,452,252,616,897,204,917
+745,480,563,60,904,800,488,897,507,151,154,544,630,809,59,377,657,395,532,59
+4,727,828,422,431,900,321,68,643,446,725,431,53,404,162,499,540,636,310,810
+790,84,444,330,477,252,498,686,729,52,608,824,271,445,390,512,761,258,124,323
+351,103,820,73,78,732,252,752,659,540,619,625,927,154,749,425,364,788,366,83
+900,525,443,560,941,867,728,822,167,605,356,157,611,662,869,919,109,165,107,897
+437,250,354,827,548,313,408,52,262,168,507,113,252,808,204,218,870,941,70,749
+545,901,987,657,108,399,832,596,409,748,506,285,949,365,317,336,629,482,435,907
+586,749,118,281,804,921,698,201,828,504,649,277,84,606,633,290,249,698,398,368
+261,689,942,624,432,798,623,260,507,619,902,425,908,161,410,976,398,306,807,830
+515,156,220,925,667,611,441,270,62,358,358,799,545,61,364,67,286,668,548,393
+772,825,606,731,685,165,91,920,608,654,155,833,227,510,532,274,344,595,259,396
+678,399,909,861,335,923,700,323,892,543,744,410,485,153,620,606,541,790,511,274
+419,503,108,342,675,193,825,918,602,420,260,148,164,145,517,549,279,500,639,255
+725,72,54,469,436,507,856,72,830,653,502,944,856,75,688,736,529,779,746,730
+445,503,944,752,68,319,432,164,510,72,513,331,416,359,77,72,462,489,393,413
+689,90,278,166,157,19,167,332,912,500,682,481,911,676,544,807,342,530,794,471
+596,915,664,751,621,71,748,943,414,223,483,633,295,549,677,551,317,69,529,538
+913,540,832,335,748,656,685,826,656,89,138,700,362,73,427,351,560,327,562,612
+405,690,390,731,396,78,895,249,549,626,155,311,337,404,923,298,799,693,153,254
+271,210,924,926,678,339,366,162,430,686,904,901,267,155,544,162,905,322,868,802
+81,284,261,498,919,334,621,750,600,536,865,435,203,825,312,226,473,925,277,236
+142,507,157,492,621,201,491,278,470,681,609,194,417,619,649,860,746,661,616,908
+274,920,66,355,479,10,55,435,158,338,503,446,414,500,816,406,654,508,61,257
+824,149,516,673,361,803,668,926,500,730,51,410,823,857,308,162,441,429,366,901
+147,145,158,112,595,867,332,108,925,400,797,368,542,558,323,427,77,554,337,503
+337,344,871,790,360,158,551,727,269,52,83,539,734,327,597,285,335,753,484,402
+903,697,728,532,655,944,75,143,57,445,743,273,684,109,347,506,77,864,111,491
+516,424,899,816,752,199,227,266,172,734,74,165,222,601,652,468,85,279,531,415
+56,70,159,537,354,196,610,206,833,416,605,859,975,609,645,437,675,922,655,594
+823,657,323,163,509,277,0,362,552,311,668,308,636,436,922,801,253,56,219,350
+267,331,338,680,568,678,487,947,858,412,77,818,656,290,917,665,667,269,90,887
+253,600,284,895,908,90,831,857,56,256,656,58,489,73,314,197,383,306,520,803
+396,603,638,732,18,823,54,109,796,113,858,808,796,261,401,393,420,683,391,803
+524,415,255,910,422,915,693,803,535,117,323,80,830,472,56,353,268,151,51,116
+425,669,679,827,793,58,366,856,479,219,219,689,312,218,69,460,309,730,410,82
+615,735,809,150,860,488,796,221,791,555,316,362,634,146,420,475,391,928,279,189
+915,416,86,619,314,505,163,908,277,327,12,801,152,601,797,346,557,289,398,265
+619,122,927,195,903,400,736,619,249,603,664,498,817,282,414,72,362,520,427,356
+489,889,641,154,603,629,150,622,610,492,926,485,763,320,352,273,947,444,555,747
+470,90,483,91,59,941,683,359,810,81,70,886,763,546,366,218,162,345,497,413
+664,486,485,675,223,733,814,607,644,748,523,567,662,607,157,342,752,106,730,367
+478,152,88,220,600,280,312,256,518,791,79,606,326,515,306,138,488,814,114,394
+901,197,75,381,320,65,257,857,602,193,71,339,402,153,399,282,207,322,648,320
+601,329,314,443,542,528,904,754,336,807,783,813,53,791,85,801,923,858,420,258
+65,520,752,61,351,159,810,732,928,278,286,324,490,184,277,167,813,867,198,280
+157,322,617,64,442,53,225,350,659,422,813,268,665,610,942,266,487,419,415,158
+474,318,79,440,223,327,289,89,226,506,147,647,109,698,472,402,634,485,911,810
+808,642,824,418,74,490,695,310,150,868,758,485,862,218,275,475,436,322,202,789
+170,632,287,632,548,536,283,221,670,792,503,943,896,251,547,625,324,604,657,663
+343,519,359,754,74,494,127,601,949,315,538,437,811,752,407,922,319,149,362,203
+435,642,253,830,336,258,414,157,794,355,521,598,307,801,553,540,977,347,343,322
+270,416,513,237,901,360,426,327,124,345,868,484,651,645,763,205,60,821,746,154
+332,157,480,828,554,903,361,277,261,640,515,316,275,505,128,601,609,859,643,557
+541,700,203,495,267,422,426,999,789,644,62,269,617,636,217,551,633,474,726,109
+606,940,155,580,311,796,77,467,415,53,166,727,521,947,632,308,200,746,410,76
+496,943,609,858,91,599,124,53,393,730,208,308,800,148,621,440,618,529,437,165
+430,752,605,340,920,400,109,502,407,315,699,483,75,255,654,14,813,566,546,800
+725,270,404,393,545,124,160,389,402,926,222,333,143,830,166,321,552,71,436,258
+924,748,601,918,310,553,500,693,162,904,602,700,448,153,560,692,333,490,86,500
+519,598,161,471,276,612,604,561,823,509,485,735,406,350,518,432,115,441,804,529
+343,263,84,606,751,928,647,67,162,691,416,677,90,729,512,815,507,816,995,634
+165,670,469,282,342,533,858,290,547,194,162,482,833,888,156,310,557,475,807,744
+665,634,806,614,466,594,164,889,262,217,557,405,682,745,321,627,444,413,67,601
+326,758,657,488,310,394,318,278,205,691,148,446,916,534,923,403,206,63,195,51
+810,344,594,217,272,368,611,830,387,342,866,82,616,60,322,693,663,519,261,805
+252,152,412,894,315,542,268,496,327,638,497,673,362,437,469,77,282,552,205,614
+858,280,630,320,671,512,895,401,510,479,329,558,115,310,145,91,75,333,88,117
+147,798,77,648,689,801,904,796,253,623,865,618,316,410,761,275,310,62,502,630
+539,84,311,926,194,639,356,446,821,445,253,679,757,53,633,749,902,490,543,193
+354,359,432,916,547,940,349,820,692,424,734,944,403,519,118,141,732,664,596,160
+342,346,50,616,146,919,472,281,469,700,225,364,83,948,668,411,873,403,286,400
+553,162,633,346,497,489,117,258,280,823,693,919,279,404,193,933,203,827,808,623
+341,509,751,132,486,645,898,425,899,794,699,609,636,807,906,514,63,748,568,535
+547,607,860,459,285,166,693,78,67,830,802,355,743,691,901,349,538,695,60,391
+481,501,477,195,429,647,63,561,610,320,336,663,534,799,330,994,748,910,789,351
+535,746,501,553,831,107,515,149,482,79,563,795,617,645,734,483,391,729,650,125
+276,792,492,536,733,285,552,432,208,981,350,818,347,71,735,322,225,435,788,651
+813,820,436,431,596,944,330,518,256,354,277,647,870,264,284,527,530,505,54,152
+115,420,204,619,509,351,699,352,402,634,361,425,925,808,333,886,415,364,160,659
+111,749,731,187,67,790,89,437,491,610,677,61,225,550,791,341,945,864,537,389
+690,632,89,763,538,389,831,333,366,864,157,253,64,732,652,763,181,791,333,556
+313,194,489,272,153,520,274,124,700,676,506,565,518,624,816,390,929,227,362,555
+788,439,948,678,596,411,539,57,596,77,323,614,204,323,71,333,540,635,348,476

diff --git a/data/advent16a.txt b/data/advent16a.txt
new file mode 100644 (file)
index 0000000..ba62efb
--- /dev/null
+++ b/data/advent16a.txt
@@ -0,0 +1,12 @@
+class: 1-3 or 5-7
+row: 6-11 or 33-44
+seat: 13-40 or 45-50
+
+your ticket:
+7,1,14
+
+nearby tickets:
+7,3,47
+40,4,50
+55,2,20
+38,6,12
\ No newline at end of file

diff --git a/data/advent16b.txt b/data/advent16b.txt
new file mode 100644 (file)
index 0000000..c629bd3
--- /dev/null
+++ b/data/advent16b.txt
@@ -0,0 +1,11 @@
+class: 0-1 or 4-19
+row: 0-5 or 8-19
+seat: 0-13 or 16-19
+
+your ticket:
+11,12,13
+
+nearby tickets:
+3,9,18
+15,1,5
+5,14,9
\ No newline at end of file

diff --git a/problems/day16.html b/problems/day16.html
new file mode 100644 (file)
index 0000000..1160226
--- /dev/null
+++ b/problems/day16.html
@@ -0,0 +1,168 @@
+<!DOCTYPE html>
+<html lang="en-us">
+<head>
+<meta charset="utf-8"/>
+<title>Day 16 - Advent of Code 2020</title>
+<!--[if lt IE 9]><script src="/static/html5.js"></script><![endif]-->
+<link href='//fonts.googleapis.com/css?family=Source+Code+Pro:300&subset=latin,latin-ext' rel='stylesheet' type='text/css'/>
+<link rel="stylesheet" type="text/css" href="/static/style.css?25"/>
+<link rel="stylesheet alternate" type="text/css" href="/static/highcontrast.css?0" title="High Contrast"/>
+<link rel="shortcut icon" href="/favicon.png"/>
+</head><!--
+
+
+
+
+Oh, hello!  Funny seeing you here.
+
+I appreciate your enthusiasm, but you aren't going to find much down here.
+There certainly aren't clues to any of the puzzles.  The best surprises don't
+even appear in the source until you unlock them for real.
+
+Please be careful with automated requests; I'm not a massive company, and I can
+only take so much traffic.  Please be considerate so that everyone gets to play.
+
+If you're curious about how Advent of Code works, it's running on some custom
+Perl code. Other than a few integrations (auth, analytics, social media), I
+built the whole thing myself, including the design, animations, prose, and all
+of the puzzles.
+
+The puzzles are most of the work; preparing a new calendar and a new set of
+puzzles each year takes all of my free time for 4-5 months. A lot of effort
+went into building this thing - I hope you're enjoying playing it as much as I
+enjoyed making it for you!
+
+If you'd like to hang out, I'm @ericwastl on Twitter.
+
+- Eric Wastl
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+-->
+<body>
+<header><div><h1 class="title-global"><a href="/">Advent of Code</a></h1><nav><ul><li><a href="/2020/about">[About]</a></li><li><a href="/2020/events">[Events]</a></li><li><a href="https://teespring.com/stores/advent-of-code" target="_blank">[Shop]</a></li><li><a href="/2020/settings">[Settings]</a></li><li><a href="/2020/auth/logout">[Log Out]</a></li></ul></nav><div class="user">Neil Smith <a href="/2020/support" class="supporter-badge" title="Advent of Code Supporter">(AoC++)</a> <span class="star-count">32*</span></div></div><div><h1 class="title-event">&nbsp;&nbsp;&nbsp;<span class="title-event-wrap">0x0000|</span><a href="/2020">2020</a><span class="title-event-wrap"></span></h1><nav><ul><li><a href="/2020">[Calendar]</a></li><li><a href="/2020/support">[AoC++]</a></li><li><a href="/2020/sponsors">[Sponsors]</a></li><li><a href="/2020/leaderboard">[Leaderboard]</a></li><li><a href="/2020/stats">[Stats]</a></li></ul></nav></div></header>
+
+<div id="sidebar">
+<div id="sponsor"><div class="quiet">Our <a href="/2020/sponsors">sponsors</a> help make Advent of Code possible:</div><div class="sponsor"><a href="https://github.com/" target="_blank" onclick="if(ga)ga('send','event','sponsor','sidebar',this.href);" rel="noopener">GitHub</a> - We&apos;re hiring engineers to make GitHub fast. Interested? Email fast@github.com with details of exceptional performance work you&apos;ve done in the past.</div></div>
+</div><!--/sidebar-->
+
+<main>
+<script>window.addEventListener('click', function(e,s,r){if(e.target.nodeName==='CODE'&&e.detail===3){s=window.getSelection();s.removeAllRanges();r=document.createRange();r.selectNodeContents(e.target);s.addRange(r);}});</script>
+<article class="day-desc"><h2>--- Day 16: Ticket Translation ---</h2><p>As you're walking to yet another connecting flight, you realize that one of the legs of your re-routed trip coming up is on a high-speed train. However, the train ticket you were given is in a language you don't understand. You should probably figure out what it says before you get to the train station after the next flight.</p>
+<p>Unfortunately, you <span title="This actually happened to me once, but I solved it by just asking someone.">can't actually <em>read</em> the words on the ticket</span>. You can, however, read the numbers, and so you figure out <em>the fields these tickets must have</em> and <em>the valid ranges</em> for values in those fields.</p>
+<p>You collect the <em>rules for ticket fields</em>, the <em>numbers on your ticket</em>, and the <em>numbers on other nearby tickets</em> for the same train service (via the airport security cameras) together into a single document you can reference (your puzzle input).</p>
+<p>The <em>rules for ticket fields</em> specify a list of fields that exist <em>somewhere</em> on the ticket and the <em>valid ranges of values</em> for each field. For example, a rule like <code>class: 1-3 or 5-7</code> means that one of the fields in every ticket is named <code>class</code> and can be any value in the ranges <code>1-3</code> or <code>5-7</code> (inclusive, such that <code>3</code> and <code>5</code> are both valid in this field, but <code>4</code> is not).</p>
+<p>Each ticket is represented by a single line of comma-separated values. The values are the numbers on the ticket in the order they appear; every ticket has the same format. For example, consider this ticket:</p>
+<pre><code>.--------------------------------------------------------.
+| ????: 101    ?????: 102   ??????????: 103     ???: 104 |
+|                                                        |
+| ??: 301  ??: 302             ???????: 303      ??????? |
+| ??: 401  ??: 402           ???? ????: 403    ????????? |
+'--------------------------------------------------------'
+</code></pre>
+<p>Here, <code>?</code> represents text in a language you don't understand. This ticket might be represented as <code>101,102,103,104,301,302,303,401,402,403</code>; of course, the actual train tickets you're looking at are <em>much</em> more complicated. In any case, you've extracted just the numbers in such a way that the first number is always the same specific field, the second number is always a different specific field, and so on - you just don't know what each position actually means!</p>
+<p>Start by determining which tickets are <em>completely invalid</em>; these are tickets that contain values which <em>aren't valid for any field</em>. Ignore <em>your ticket</em> for now.</p>
+<p>For example, suppose you have the following notes:</p>
+<pre><code>class: 1-3 or 5-7
+row: 6-11 or 33-44
+seat: 13-40 or 45-50
+
+your ticket:
+7,1,14
+
+nearby tickets:
+7,3,47
+40,<em>4</em>,50
+<em>55</em>,2,20
+38,6,<em>12</em>
+</code></pre>
+<p>It doesn't matter which position corresponds to which field; you can identify invalid <em>nearby tickets</em> by considering only whether tickets contain <em>values that are not valid for any field</em>. In this example, the values on the first <em>nearby ticket</em> are all valid for at least one field. This is not true of the other three <em>nearby tickets</em>: the values <code>4</code>, <code>55</code>, and <code>12</code> are are not valid for any field. Adding together all of the invalid values produces your <em>ticket scanning error rate</em>: <code>4 + 55 + 12</code> = <em><code>71</code></em>.</p>
+<p>Consider the validity of the <em>nearby tickets</em> you scanned. <em>What is your ticket scanning error rate?</em></p>
+</article>
+<p>Your puzzle answer was <code>25984</code>.</p><article class="day-desc"><h2 id="part2">--- Part Two ---</h2><p>Now that you've identified which tickets contain invalid values, <em>discard those tickets entirely</em>. Use the remaining valid tickets to determine which field is which.</p>
+<p>Using the valid ranges for each field, determine what order the fields appear on the tickets. The order is consistent between all tickets: if <code>seat</code> is the third field, it is the third field on every ticket, including <em>your ticket</em>.</p>
+<p>For example, suppose you have the following notes:</p>
+<pre><code>class: 0-1 or 4-19
+row: 0-5 or 8-19
+seat: 0-13 or 16-19
+
+your ticket:
+11,12,13
+
+nearby tickets:
+3,9,18
+15,1,5
+5,14,9
+</code></pre>
+<p>Based on the <em>nearby tickets</em> in the above example, the first position must be <code>row</code>, the second position must be <code>class</code>, and the third position must be <code>seat</code>; you can conclude that in <em>your ticket</em>, <code>class</code> is <code>12</code>, <code>row</code> is <code>11</code>, and <code>seat</code> is <code>13</code>.</p>
+<p>Once you work out which field is which, look for the six fields on <em>your ticket</em> that start with the word <code>departure</code>. <em>What do you get if you multiply those six values together?</em></p>
+</article>
+<p>Your puzzle answer was <code>1265347500049</code>.</p><p class="day-success">Both parts of this puzzle are complete! They provide two gold stars: **</p>
+<p>At this point, you should <a href="/2020">return to your Advent calendar</a> and try another puzzle.</p>
+<p>If you still want to see it, you can <a href="16/input" target="_blank">get your puzzle input</a>.</p>
+<p>You can also <span class="share">[Share<span class="share-content">on
+  <a href="https://twitter.com/intent/tweet?text=I%27ve+completed+%22Ticket+Translation%22+%2D+Day+16+%2D+Advent+of+Code+2020&amp;url=https%3A%2F%2Fadventofcode%2Ecom%2F2020%2Fday%2F16&amp;related=ericwastl&amp;hashtags=AdventOfCode" target="_blank">Twitter</a>
+  <a href="javascript:void(0);" onclick="var mastodon_instance=prompt('Mastodon Instance / Server Name?'); if(typeof mastodon_instance==='string' && mastodon_instance.length){this.href='https://'+mastodon_instance+'/share?text=I%27ve+completed+%22Ticket+Translation%22+%2D+Day+16+%2D+Advent+of+Code+2020+%23AdventOfCode+https%3A%2F%2Fadventofcode%2Ecom%2F2020%2Fday%2F16'}else{return false;}" target="_blank">Mastodon</a
+></span>]</span> this puzzle.</p>
+</main>
+
+<!-- ga -->
+<script>
+(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
+(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
+m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
+})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
+ga('create', 'UA-69522494-1', 'auto');
+ga('set', 'anonymizeIp', true);
+ga('send', 'pageview');
+</script>
+<!-- /ga -->
+</body>
+</html>
\ No newline at end of file

diff --git a/stack.yaml b/stack.yaml
index 007b43813ca09e0c3942a10b7770f58847d0af8b..9e7091de47f13b245257843ba90c4292eee3c8c4 100644 (file)
--- a/stack.yaml
+++ b/stack.yaml
@@ -50,6 +50,7 @@ packages:
 - advent13
 - advent14
 - advent15
+- advent16
 
 # Dependency packages to be pulled from upstream that are not in the resolver.
 # These entries can reference officially published versions as well as