Day 19: Aplenty

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

  • Amy
    2·
    2 年前

    Haskell

    Echoes of Day 5… Not particularly difficult, but lots of typing. I’d like to golf this one a bit more.

    Solution 
    import Control.Monad
import Data.Either
import Data.Maybe
import Text.Parsec

type Rule = (Maybe (Char, Ordering, Int), String)

type Flow = (String, [Rule])

type Part = [(Char, Int)]

readInput :: String -> ([Flow], [Part])
readInput s =
  let (flows, _ : parts) = break (== "") $ lines s
   in (map readFlow flows, map readPart parts)
  where
    readFlow = fromRight (error "bad flow") . parse flow ""
    readPart = fromRight (error "bad part") . parse part ""
    flow = do
      name <- many1 letter
      rules <- between (char '{') (char '}') (rule `sepBy` char ',')
      return (name, rules)
    rule = do
      c <- optionMaybe $ try condition
      n <- many1 letter
      return (c, n)
    condition = do
      p <- anyChar
      o <- choice [LT <$ char '<', GT <$ char '>']
      n <- read <$> many1 digit
      char ':' >> return (p, o, n)
    part = between (char '{') (char '}') (param `sepBy` char ',')
    param = do
      p <- anyChar
      n <- char '=' >> (read <$> many1 digit)
      return (p, n)

runPart :: [Flow] -> Part -> Bool
runPart flows part = runFlow "in"
  where
    runFlow "A" = True
    runFlow "R" = False
    runFlow f = runRules $ fromJust $ lookup f flows
    runRules ((Nothing, next) : _) = runFlow next
    runRules ((Just (p, o, n), next) : rest)
      | compare (fromJust $ lookup p part) n == o = runFlow next
      | otherwise = runRules rest

mapRanges :: [Flow] -> [(Char, (Int, Int))] -> [[(Char, (Int, Int))]]
mapRanges flows = runFlow "in"
  where
    runFlow "A" = return
    runFlow "R" = const mzero
    runFlow f = runRules (fromJust $ lookup f flows)
    runRules ((Nothing, next) : _) = runFlow next
    runRules ((Just test, next) : rest) =
      (\(a, b) -> join [a >>= runFlow next, b >>= runRules rest]) . splitRange test
    splitRange (p, op, n) range =
      let (v1, v2) = fromJust $ lookup p range
          others = filter ((/= p) . fst) range
       in case op of
            LT
              | v1 >= n -> ([], [range])
              | v2 < n -> ([range], [])
              | otherwise -> ([(p, (v1, n - 1)) : others], [(p, (n, v2)) : others])
            GT
              | v2 <= n -> ([], [range])
              | v1 > n -> ([range], [])
              | otherwise -> ([(p, (n + 1, v2)) : others], [(p, (v1, n)) : others])

main = do
  (flows, parts) <- readInput <$> readFile "input19"
  print . sum . concatMap (map snd) $ filter (runPart flows) parts
  print $
    sum . map (product . map (\(_, (v1, v2)) -> v2 - v1 + 1)) $
      mapRanges flows [(p, (1, 4000)) | p <- "xmas"]
    • sjmulder
      2·
      2 年前

      That’s a nice parser and I like the use of pattern matching here.

      What I wonder is if you couldn’t make a cool monadic representation of the ranges, where you could do the equivalent of

      if (foo.x > 12)
    return bar(x);
else
    return baz(x);

      but ‘x’ wouldn’t be an integer, it’d be a collection of integer ranges. The > operator would return a collection of pairs of (newly split) integer ranges and booleans. The if would yield map the pairs to a new bunch of pairs and so on.

      • Amy
        2·
        2 年前

        Mmm, I was thinking something similar. I’ve been meaning to go back and have another go, but the last few problems have eaten up all my time (and energy!)

        I realized with the parser you can write eg

            rule = (,) <$> optionMaybe (try condition) <*> many1 letter

        which avoids even more of those pesky variable names! (I still haven’t quite internalized how to use Applicative)