Day 5: Print Queue
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
You are viewing a single thread.
View all comments 2 points
Haskell
I should probably have used sortBy instead of this ad-hoc selection sort.
import Control.Arrow
import Control.Monad
import Data.Char
import Data.List qualified as L
import Data.Map
import Data.Set
import Data.Set qualified as S
import Text.ParserCombinators.ReadP
parse = (,) <$> (fromListWith S.union <$> parseOrder) <*> (eol *> parseUpdate)
parseOrder = endBy (flip (,) <$> (S.singleton <$> parseInt <* char '|') <*> parseInt) eol
parseUpdate = endBy (sepBy parseInt (char ',')) eol
parseInt = read <$> munch1 isDigit
eol = char '\n'
verify :: Map Int (Set Int) -> [Int] -> Bool
verify m = and . (zipWith fn <*> scanl (flip S.insert) S.empty)
where
fn a = flip S.isSubsetOf (findWithDefault S.empty a m)
getMiddle = ap (!!) ((`div` 2) . length)
part1 m = sum . fmap getMiddle
getOrigin :: Map Int (Set Int) -> Set Int -> Int
getOrigin m l = head $ L.filter (S.disjoint l . preds) (S.toList l)
where
preds = flip (findWithDefault S.empty) m
order :: Map Int (Set Int) -> Set Int -> [Int]
order m s
| S.null s = []
| otherwise = h : order m (S.delete h s)
where
h = getOrigin m s
part2 m = sum . fmap (getMiddle . order m . S.fromList)
main = getContents >>= print . uncurry runParts . fst . last . readP_to_S parse
runParts m = L.partition (verify m) >>> (part1 m *** part2 m)
