Skip Navigation

🎁 - 2023 DAY 12 SOLUTIONS -🎁

Day 12: Hot Springs

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)
  • Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ


πŸ”’ Thread is locked until there's at least 100 2 star entries on the global leaderboard

πŸ”“ Unlocked after 25 mins

12
12 comments
  • Haskell

    Phew! I struggled with this one. A lot of the code here is from my original approach, which cuts down the search space to plausible positions for each group. Unfortunately, that was still way too slow...

    It took an embarrassingly long time to try memoizing the search (which made precomputing valid points far less important). Anyway, here it is!

    Solution
    {-# LANGUAGE LambdaCase #-}
    
    import Control.Monad
    import Control.Monad.State
    import Data.List
    import Data.List.Split
    import Data.Map (Map)
    import qualified Data.Map as Map
    import Data.Maybe
    
    readInput :: String -> ([Maybe Bool], [Int])
    readInput s =
      let [a, b] = words s
       in ( map (\case '#' -> Just True; '.' -> Just False; '?' -> Nothing) a,
            map read $ splitOn "," b
          )
    
    arrangements :: ([Maybe Bool], [Int]) -> Int
    arrangements (pat, gs) = evalState (searchMemo 0 groups) Map.empty
      where
        len = length pat
        groups = zipWith startPoints gs $ zip minStarts maxStarts
          where
            minStarts = scanl (\a g -> a + g + 1) 0 $ init gs
            maxStarts = map (len -) $ scanr1 (\g a -> a + g + 1) gs
            startPoints g (a, b) =
              let ps = do
                    (i, pat') <- zip [a .. b] $ tails $ drop a pat
                    guard $
                      all (\(p, x) -> maybe True (== x) p) $
                        zip pat' $
                          replicate g True ++ [False]
                    return i
               in (g, ps)
        clearableFrom i =
          fmap snd $
            listToMaybe $
              takeWhile ((<= i) . fst) $
                dropWhile ((< i) . snd) clearableRegions
          where
            clearableRegions =
              let go i [] = []
                  go i pat =
                    let (a, a') = span (/= Just True) pat
                        (b, c) = span (== Just True) a'
                     in (i, i + length a - 1) : go (i + length a + length b) c
               in go 0 pat
        searchMemo :: Int -> [(Int, [Int])] -> State (Map (Int, Int) Int) Int
        searchMemo i gs = do
          let k = (i, length gs)
          cached <- gets (Map.!? k)
          case cached of
            Just x -> return x
            Nothing -> do
              x <- search i gs
              modify (Map.insert k x)
              return x
        search i gs | i >= len = return $ if null gs then 1 else 0
        search i [] = return $
          case clearableFrom i of
            Just b | b == len - 1 -> 1
            _ -> 0
        search i ((g, ps) : gs) = do
          let maxP = maybe i (1 +) $ clearableFrom i
              ps' = takeWhile (<= maxP) $ dropWhile (< i) ps
          sum <$> mapM (\p -> let i' = p + g + 1 in searchMemo i' gs) ps'
    
    expand (pat, gs) =
      (intercalate [Nothing] $ replicate 5 pat, concat $ replicate 5 gs)
    
    main = do
      input <- map readInput . lines <$> readFile "input12"
      print $ sum $ map arrangements input
      print $ sum $ map (arrangements . expand) input
    
  • Rust

    Took me way too long, but I'm happy with my solution now. I spent probably half an hour looking at my naive backtracking program churning away unsuccessfully before I thought of dynamic programming, meaning caching all intermediate results in a hashtable under their current state. The state is just the index into the spring array and the index into the range array, meaning there really can't be too many different entries. Doing so worked very well, solving part 2 in 4ms.

    Adding the caching required me to switch from a loop to a recursive function, which turned out way easier. Why did no one tell me to just go recursive from the start?

  • C

    That was something! I quickly settled on the main approach for part 1 but it took some unit testing to get it all right. Then part 2 had me stumped for a bit. It was clear some kind of pruning was necessary, possibly with memoization.

    Hashmaps are possible but annoying with C so I was happy to realise that, for my implementation, (num chars, num runs) is a suitable key within the context of a single recursive search. That space is small enough to index with an array 😁

    https://github.com/sjmulder/aoc/tree/master/2023/c/day12.c

  • Scala3

    def countDyn(a: List[Char], b: List[Int]): Long =
        // Simple dynamic programming approach
        // We fill a table T, where
        //  T[ ai, bi ] -> number of ways to place b[bi..] in a[ai..]
        //  T[ ai, bi ] = 0 if an-ai >= b[bi..].sum + bn-bi
        //  T[ ai, bi ] = 1 if bi == b.size - 1 && ai == a.size - b[bi] - 1
        //  T[ ai, bi ] = 
        //   (place) T [ ai + b[bi], bi + 1]   if ? or # 
        //   (skip)  T [ ai + 1, bi ]          if ? or .
        // 
        def t(ai: Int, bi: Int, tbl: Map[(Int, Int), Long]): Long =
            if ai >= a.size then
                if bi >= b.size then 1L else 0L 
            else
                val place = Option.when(
                    bi < b.size && // need to have piece left
                    ai + b(bi) <= a.size && // piece needs to fit
                    a.slice(ai, ai + b(bi)).forall(_ != '.') && // must be able to put piece there
                    (ai + b(bi) == a.size || a(ai + b(bi)) != '#') // piece needs to actually end
                )((ai + b(bi) + 1, bi + 1)).flatMap(tbl.get).getOrElse(0L)
                val skip = Option.when(a(ai) != '#')((ai + 1, bi)).flatMap(tbl.get).getOrElse(0L)
                place + skip
    
        @tailrec def go(ai: Int, tbl: Map[(Int, Int), Long]): Long =
            if ai == 0 then t(ai, 0, tbl) else go(ai - 1, tbl ++ b.indices.inclusive.map(bi => (ai, bi) -> t(ai, bi, tbl)).toMap)
    
        go(a.indices.inclusive.last + 1, Map())
    
    def countLinePossibilities(repeat: Int)(a: String): Long =
        a match
            case s"$pattern $counts" => 
                val p2 = List.fill(repeat)(pattern).mkString("?")
                val c2 = List.fill(repeat)(counts).mkString(",")
                countDyn(p2.toList, c2.split(",").map(_.toInt).toList)
            case _ => 0L
    
    
    def task1(a: List[String]): Long = a.map(countLinePossibilities(1)).sum
    def task2(a: List[String]): Long = a.map(countLinePossibilities(5)).sum
    

    (Edit: fixed mangling of &<)

  • Python

    Let me know if you have any questions or feedback!

    import dataclasses
    import functools
    
    from .solver import Solver
    
    
    class MatchState:
      pass
    
    @dataclasses.dataclass
    class NotMatching(MatchState):
      pass
    
    @dataclasses.dataclass
    class Matching(MatchState):
      current_length: int
      desired_length: int
    
    @functools.cache
    def _match_one_template(template: str, groups: tuple[int, ...]) -> int:
      if not groups:
        if '#' in template:
          return 0
        else:
          return 1
      state: MatchState = NotMatching()
      remaining_groups: list[int] = list(groups)
      options_in_other_branches: int = 0
      for i in range(len(template)):
        match (state, template[i]):
          case (NotMatching(), '.'):
            pass
          case (NotMatching(), '?'):
            options_in_other_branches += _match_one_template(template[i+1:], tuple(remaining_groups))
            if not remaining_groups:
              return options_in_other_branches
            group, *remaining_groups = remaining_groups
            state = Matching(1, group)
          case (NotMatching(), '#'):
            if not remaining_groups:
              return options_in_other_branches
            group, *remaining_groups = remaining_groups
            state = Matching(1, group)
          case (Matching(current_length, desired_length), '.') if current_length == desired_length:
            state = NotMatching()
          case (Matching(current_length, desired_length), '.') if current_length &lt; desired_length:
            return options_in_other_branches
          case (Matching(current_length, desired_length), '?') if current_length == desired_length:
            state = NotMatching()
          case (Matching(current_length, desired_length), '?') if current_length &lt; desired_length:
            state = Matching(current_length + 1, desired_length)
          case (Matching(current_length, desired_length), '#') if current_length &lt; desired_length:
            state = Matching(current_length + 1, desired_length)
          case (Matching(current_length, desired_length), '#') if current_length == desired_length:
            return options_in_other_branches
          case _:
            raise RuntimeError(f'unexpected {state=} with {template=} position {i} and {remaining_groups=}')
      match state, remaining_groups:
        case NotMatching(), []:
          return options_in_other_branches + 1
        case Matching(current, desired), [] if current == desired:
          return options_in_other_branches + 1
        case (NotMatching(), _) | (Matching(_, _), _):
          return options_in_other_branches
      raise RuntimeError(f'unexpected {state=} with {template=} at end of template and {remaining_groups=}')
    
    
    def _unfold(template: str, groups: tuple[int, ...]) -> tuple[str, tuple[int, ...]]:
      return '?'.join([template] * 5), groups * 5
    
    
    class Day12(Solver):
    
      def __init__(self):
        super().__init__(12)
        self.input: list[tuple[str, tuple[int]]] = []
    
      def presolve(self, input: str):
        lines = input.rstrip().split('\n')
        for line in lines:
          template, groups = line.split(' ')
          self.input.append((template, tuple(int(group) for group in groups.split(','))))
    
      def solve_first_star(self) -> int:
        return sum(_match_one_template(template, groups) for template, groups in self.input)
    
      def solve_second_star(self) -> int:
        return sum(_match_one_template(*_unfold(template, groups)) for template, groups in self.input)
    
  • Haskell

    Abused ParserCombinators for the first part. For the second, I took quite a while to figure out dynamic programming in Haskell.

    Solution
    module Day12 where
    
    import Data.Array
    import Data.Char (isDigit)
    import Data.List ((!!))
    import Relude hiding (get, many)
    import Relude.Unsafe (read)
    import Text.ParserCombinators.ReadP
    
    type Spring = (String, [Int])
    
    type Problem = [Spring]
    
    parseStatus :: ReadP Char
    parseStatus = choice $ char &lt;$> ".#?"
    
    parseSpring :: ReadP Spring
    parseSpring = do
      status &lt;- many1 parseStatus &lt;* char ' '
      listFailed &lt;- (read &lt;$> munch1 isDigit) `sepBy` char ','
      return (status, listFailed)
    
    parseProblem :: ReadP Problem
    parseProblem = parseSpring `sepBy` char '\n'
    
    parse :: ByteString -> Maybe Problem
    parse = fmap fst . viaNonEmpty last . readP_to_S parseProblem . decodeUtf8
    
    good :: ReadP ()
    good = choice [char '.', char '?'] $> ()
    
    bad :: ReadP ()
    bad = choice [char '#', char '?'] $> ()
    
    buildParser :: [Int] -> ReadP ()
    buildParser l = do
      _ &lt;- many good
      sequenceA_ $ intersperse (many1 good) [count x bad | x &lt;- l]
      _ &lt;- many good &lt;* eof
    
      return ()
    
    combinations :: Spring -> Int
    combinations (s, l) = length $ readP_to_S (buildParser l) s
    
    part1, part2 :: Problem -> Int
    part1 = sum . fmap combinations
    part2 = sum . fmap (combinations' . toSpring' . bimap (join . intersperse "?" . replicate 5) (join . replicate 5))
    
    run1, run2 :: FilePath -> IO Int
    run1 f = readFileBS f >>= maybe (fail "parse error") (return . part1) . parse
    run2 f = readFileBS f >>= maybe (fail "parse error") (return . part2) . parse
    
    data Status = Good | Bad | Unknown deriving (Eq, Show)
    
    type Spring' = ([Status], [Int])
    
    type Problem' = [Spring']
    
    toSpring' :: Spring -> Spring'
    toSpring' (s, l) = (fmap toStatus s, l)
      where
        toStatus :: Char -> Status
        toStatus '.' = Good
        toStatus '#' = Bad
        toStatus '?' = Unknown
        toStatus _ = error "impossible"
    
    isGood, isBad :: Status -> Bool
    isGood Bad = False
    isGood _ = True
    isBad Good = False
    isBad _ = True
    
    combinations' :: Spring' -> Int
    combinations' (s, l) = t ! (0, 0)
      where
        n = length s
        m = length l
    
        t = listArray ((0, 0), (n, m)) [f i j | i &lt;- [0 .. n], j &lt;- [0 .. m]]
    
        f :: Int -> Int -> Int
        f n' m'
          | n' >= n = if m' >= m then 1 else 0
          | v == Unknown = tGood + tBad
          | v == Good = tGood
          | v == Bad = tBad
          | otherwise = error "impossible"
          where
            v = s !! n'
            x = l !! m'
    
            ss = drop n' s
    
            (bads, rest) = splitAt x ss
            badsDelimited = maybe True isGood (viaNonEmpty head rest)
            off = if null rest then 0 else 1
    
            tGood = t ! (n' + 1, m')
    
            tBad =
              if m' + 1 &lt;= m &amp;&amp; length bads == x &amp;&amp; all isBad bads &amp;&amp; badsDelimited
                then t ! (n' + x + off, m' + 1)
                else 0
    
  • Dart

    Terrible monkey-coding approach of banging strings together and counting the resulting shards. Just kept to a reasonable 300ms runtime by a bit of memoisation of results. I'm sure this can all be replaced by a single line of clever combinatorial wizardry.

    var __countMatches = {};
    int _countMatches(String pattern, List counts) =>
        __countMatches.putIfAbsent(
            pattern + counts.toString(), () => countMatches(pattern, counts));
    
    int countMatches(String pattern, List counts) {
      if (!pattern.contains('#') &amp;&amp; counts.isEmpty) return 1;
      if (pattern.startsWith('..')) return _countMatches(pattern.skip(1), counts);
      if (pattern == '.' || counts.isEmpty) return 0;
    
      var thisShape = counts.first;
      var minSpaceForRest =
          counts.length == 1 ? 0 : counts.skip(1).sum + counts.skip(1).length + 1;
      var lastStart = pattern.length - minSpaceForRest - thisShape;
      if (lastStart &lt; 1) return 0;
    
      var total = 0;
      for (var start in 1.to(lastStart + 1)) {
        // Skipped a required spring. Bad, and will be for all successors.
        if (pattern.take(start).contains('#')) break;
        // Includes a required separator. Also bad.
        if (pattern.skip(start).take(thisShape).contains('.')) continue;
        var rest = pattern.skip(start + thisShape);
        if (rest.startsWith('#')) continue;
        // force '.' or '?' to be '.' and count matches.
        total += _countMatches('.${rest.skip(1)}', counts.skip(1).toList());
      }
      return total;
    }
    
    solve(List lines, {stretch = 1}) {
      var ret = [];
      for (var line in lines) {
        var ps = line.split(' ');
        var pattern = List.filled(stretch, ps.first).join('?');
        var counts = List.filled(stretch, ps.last)
            .join(',')
            .split(',')
            .map(int.parse)
            .toList();
         ret.add(countMatches('.$pattern.', counts)); // top and tail.
      }
      return ret.sum;
    }
    
    part1(List lines) => solve(lines);
    
    part2(List lines) => solve(lines, stretch: 5);
    
    
You've viewed 12 comments.