Day 23 part 2
[advent-of-code-23.git] / advent12 / MainBruteForce.hs
1 -- Writeup at https://work.njae.me.uk/2023/12/15/advent-of-code-2023-day-12/
2
3 import AoC
4 import Data.Text (Text)
5 import qualified Data.Text.IO as TIO
6 import Data.Attoparsec.Text -- hiding (take)
7 import Control.Applicative
8 import Data.List
9
10 data Spring = Unknown | Damaged | Operational deriving (Show, Eq)
11 data Record = Record [Spring] [Int] deriving (Show)
12
13 main :: IO ()
14 main =
15 do dataFileName <- getDataFileName
16 text <- TIO.readFile dataFileName
17 let records = successfulParse text
18 -- print records
19 -- print $ fmap numDamagedToPlace records
20 -- print $ fmap candidates records
21 -- print $ possibleAssignments (records !! 1)
22 -- print $ fmap countViableAssignments records
23 print $ part1 records
24 -- print $ unfoldRecord $ head records
25 -- print $ part2 records
26
27 part1, part2 :: [Record] -> Int
28 part1 = sum . fmap countViableAssignments
29 part2 = sum . fmap (countViableAssignments . unfoldRecord)
30
31 unfoldRecord :: Record -> Record
32 unfoldRecord (Record springs signature) = Record uSprings uSignature
33 where uSprings = intercalate [Unknown] $ replicate 5 springs
34 uSignature = concat $ replicate 5 signature
35
36
37 countViableAssignments :: Record -> Int
38 countViableAssignments = length . filter matchesSignature . possibleAssignments
39
40 matchesSignature :: Record -> Bool
41 matchesSignature (Record springs signature) = signSprings springs == signature
42
43 signSprings :: [Spring] -> [Int]
44 signSprings = fmap (length) . filter ((== Damaged) . head) . group
45
46 choose :: Int -> [a] -> [[a]]
47 choose 0 _ = [[]]
48 choose n (x:xs)
49 | length xs == n - 1 = [(x:xs)]
50 | otherwise = (fmap (x:) (choose (n-1) xs)) ++ (choose n xs)
51
52 numDamagedToPlace :: Record -> Int
53 numDamagedToPlace (Record springs signature) = totalDamaged - knownDamaged
54 where knownDamaged = length $ filter (== Damaged) springs
55 totalDamaged = sum signature
56
57 candidates :: Record -> [[Int]]
58 candidates r@(Record springs _) =
59 choose (numDamagedToPlace r) (elemIndices Unknown springs)
60
61 replaceUnknowns :: [Spring] -> [Int] -> [Spring]
62 replaceUnknowns springs indices = foldr go [] indexedSprings
63 where indexedSprings = zip [0..] springs
64 go (i, Unknown) acc = if (i `elem` indices) then Damaged:acc
65 else Operational:acc
66 go (_, s) acc = s:acc
67
68 possibleAssignments :: Record -> [Record]
69 possibleAssignments r@(Record springs signature) =
70 fmap (\p -> Record p signature) possibles
71 where cands = candidates r
72 possibles = fmap (replaceUnknowns springs) cands
73
74 -- Parse the input file
75
76 recordsP :: Parser [Record]
77 recordP :: Parser Record
78 springP :: Parser Spring
79
80 recordsP = recordP `sepBy` endOfLine
81 recordP = Record <$> (many1 springP <* " ") <*> (decimal `sepBy` ",")
82 springP = (Unknown <$ "?") <|> (Damaged <$ "#") <|> (Operational <$ ".")
83
84 successfulParse :: Text -> [Record]
85 successfulParse input =
86 case parseOnly recordsP input of
87 Left _err -> [] -- TIO.putStr $ T.pack $ parseErrorPretty err
88 Right matches -> matches