🎁 - 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 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

cacheson,
cacheson avatar

Nim

I don't want to talk about it. -_-

cacheson,
cacheson avatar

And finally:

LeixB,

Haskell

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

Solutionmodule 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 <$> “.#?” parseSpring :: ReadP Spring parseSpring = do status <- many1 parseStatus <* char ’ ’ listFailed <- (read <$> munch1 isDigit) sepBychar ‘,’ return (status, listFailed) parseProblem :: ReadP Problem parseProblem = parseSpringsepBy 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 _ <- many good sequenceA_ $ intersperse (many1 good) [count x bad | x <- l] _ <- many good <* 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 <- [0 … n], j <- [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 <= m && length bads == x && all isBad bads && badsDelimited then t ! (n’ + x + off, m’ + 1) else 0

Gobbel2000,
@Gobbel2000@feddit.de avatar

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?

lwhjp,
@lwhjp@lemmy.sdf.org avatar

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

cvttsd2si, (edited )

Scala3


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

(Edit: fixed mangling of &<)

mykoza,

I’m struggling to fully understand your solution. Could you tell me, why do you return 1 when at the end of a and b ? And why do you start from size + 1?

cvttsd2si,

T counts the number of ways to place the blocks with lengths specified in b in the remaining a.size - ai slots. If there are no more slots left, there are two cases: Either there are also no more blocks left, then everything is fine, and the current situation is 1 way to place the blocks in the slots. Otherwise, there are still blocks left, and no more space to place them in. This means the current sitution is incorrect, so we contribute 0 ways to place the blocks. This is what the if bi >= b.size then 1L else 0L{.scala} does.

The start at size + 1 is necessary, as we need to compute every table entry before it may get looked up. When placing the last block, we may check the entry (ai + b(bi) + 1, bi + 1), where ai + b(bi) may already equal a.size (in the case where the block ends exactly at the end of a). The + 1 in the entry is necessary, as we need to skip a slot after every block: If we looked at (ai + b(bi), bi + 1), we could start at a.size, but then, for e.g. b = [2, 3], we would consider …#####. a valid placement.

Let me know if there are still things unclear :)

mykoza,

Thanks for the detailed explanation. It helped a lot, especially what the tbl actually holds.

I’ve read your code again and I get how it works, but it still feels kinda strange that we are considering values outside of range of a and b, and that we are marking them as correct. Like in first row of the example ???.### 1,1,3, there is no spring at 8 and no group at 3 but we are marking (8,3) and (7,3) as correct. In my mind, first position that should be marked as correct is 4,2, because that’s where group of 3 can fit.

cvttsd2si,

If you make the recurrent case a little more complicated, you can sidestep the weird base cases, but I like reducing the endpoints down to things like this that are easily implementable, even if they sound a little weird at first.

mykoza,

You are probably right. Just my rumblings. Thanks for the help.

sjmulder,

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 😁

github.com/sjmulder/aoc/tree/master/…/day12.c

hades,

Python

Also on Github.

Let me know if you have any questions or feedback!


<span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">dataclasses
</span><span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">functools
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">from .</span><span style="color:#323232;">solver </span><span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">Solver
</span><span style="color:#323232;">
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">class </span><span style="color:#0086b3;">MatchState</span><span style="color:#323232;">:
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">pass
</span><span style="color:#323232;">
</span><span style="color:#323232;">@dataclasses.dataclass
</span><span style="font-weight:bold;color:#a71d5d;">class </span><span style="color:#0086b3;">NotMatching</span><span style="color:#323232;">(</span><span style="color:#0086b3;">MatchState</span><span style="color:#323232;">):
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">pass
</span><span style="color:#323232;">
</span><span style="color:#323232;">@dataclasses.dataclass
</span><span style="font-weight:bold;color:#a71d5d;">class </span><span style="color:#0086b3;">Matching</span><span style="color:#323232;">(</span><span style="color:#0086b3;">MatchState</span><span style="color:#323232;">):
</span><span style="color:#323232;">  current_length: </span><span style="color:#0086b3;">int
</span><span style="color:#323232;">  desired_length: </span><span style="color:#0086b3;">int
</span><span style="color:#323232;">
</span><span style="color:#323232;">@functools.cache
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">_match_one_template</span><span style="color:#323232;">(template: </span><span style="color:#0086b3;">str</span><span style="color:#323232;">, groups: </span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">...</span><span style="color:#323232;">]) -> </span><span style="color:#0086b3;">int</span><span style="color:#323232;">:
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">if not </span><span style="color:#323232;">groups:
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#183691;">'#' </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">template:
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#0086b3;">0
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">else</span><span style="color:#323232;">:
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#0086b3;">1
</span><span style="color:#323232;">  state: MatchState </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">NotMatching()
</span><span style="color:#323232;">  remaining_groups: </span><span style="color:#0086b3;">list</span><span style="color:#323232;">[</span><span style="color:#0086b3;">int</span><span style="color:#323232;">] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">list</span><span style="color:#323232;">(groups)
</span><span style="color:#323232;">  options_in_other_branches: </span><span style="color:#0086b3;">int </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">0
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">i </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#62a35c;">range</span><span style="color:#323232;">(</span><span style="color:#62a35c;">len</span><span style="color:#323232;">(template)):
</span><span style="color:#323232;">    match (state, template[i]):
</span><span style="color:#323232;">      case (NotMatching(), </span><span style="color:#183691;">'.'</span><span style="color:#323232;">):
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">pass
</span><span style="color:#323232;">      case (NotMatching(), </span><span style="color:#183691;">'?'</span><span style="color:#323232;">):
</span><span style="color:#323232;">        options_in_other_branches </span><span style="font-weight:bold;color:#a71d5d;">+= </span><span style="color:#323232;">_match_one_template(template[i</span><span style="font-weight:bold;color:#a71d5d;">+</span><span style="color:#0086b3;">1</span><span style="color:#323232;">:], </span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">(remaining_groups))
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if not </span><span style="color:#323232;">remaining_groups:
</span><span style="color:#323232;">          </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">options_in_other_branches
</span><span style="color:#323232;">        group, </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;">remaining_groups </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">remaining_groups
</span><span style="color:#323232;">        state </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">Matching(</span><span style="color:#0086b3;">1</span><span style="color:#323232;">, group)
</span><span style="color:#323232;">      case (NotMatching(), </span><span style="color:#183691;">'#'</span><span style="color:#323232;">):
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if not </span><span style="color:#323232;">remaining_groups:
</span><span style="color:#323232;">          </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">options_in_other_branches
</span><span style="color:#323232;">        group, </span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;">remaining_groups </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">remaining_groups
</span><span style="color:#323232;">        state </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">Matching(</span><span style="color:#0086b3;">1</span><span style="color:#323232;">, group)
</span><span style="color:#323232;">      case (Matching(current_length, desired_length), </span><span style="color:#183691;">'.'</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">current_length </span><span style="font-weight:bold;color:#a71d5d;">== </span><span style="color:#323232;">desired_length:
</span><span style="color:#323232;">        state </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">NotMatching()
</span><span style="color:#323232;">      case (Matching(current_length, desired_length), </span><span style="color:#183691;">'.'</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">current_length </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; desired_length:
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">options_in_other_branches
</span><span style="color:#323232;">      case (Matching(current_length, desired_length), </span><span style="color:#183691;">'?'</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">current_length </span><span style="font-weight:bold;color:#a71d5d;">== </span><span style="color:#323232;">desired_length:
</span><span style="color:#323232;">        state </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">NotMatching()
</span><span style="color:#323232;">      case (Matching(current_length, desired_length), </span><span style="color:#183691;">'?'</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">current_length </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; desired_length:
</span><span style="color:#323232;">        state </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">Matching(current_length </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#0086b3;">1</span><span style="color:#323232;">, desired_length)
</span><span style="color:#323232;">      case (Matching(current_length, desired_length), </span><span style="color:#183691;">'#'</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">current_length </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; desired_length:
</span><span style="color:#323232;">        state </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">Matching(current_length </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#0086b3;">1</span><span style="color:#323232;">, desired_length)
</span><span style="color:#323232;">      case (Matching(current_length, desired_length), </span><span style="color:#183691;">'#'</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">current_length </span><span style="font-weight:bold;color:#a71d5d;">== </span><span style="color:#323232;">desired_length:
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">options_in_other_branches
</span><span style="color:#323232;">      case _:
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">raise </span><span style="color:#0086b3;">RuntimeError</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">f</span><span style="color:#183691;">'unexpected </span><span style="color:#323232;">{state=}</span><span style="color:#183691;"> with </span><span style="color:#323232;">{template=}</span><span style="color:#183691;"> position </span><span style="color:#323232;">{i}</span><span style="color:#183691;"> and </span><span style="color:#323232;">{remaining_groups=}</span><span style="color:#183691;">'</span><span style="color:#323232;">)
</span><span style="color:#323232;">  match state, remaining_groups:
</span><span style="color:#323232;">    case NotMatching(), []:
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">options_in_other_branches </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#0086b3;">1
</span><span style="color:#323232;">    case Matching(current, desired), [] </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">current </span><span style="font-weight:bold;color:#a71d5d;">== </span><span style="color:#323232;">desired:
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">options_in_other_branches </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#0086b3;">1
</span><span style="color:#323232;">    case (NotMatching(), _) </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">(Matching(_, _), _):
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">options_in_other_branches
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">raise </span><span style="color:#0086b3;">RuntimeError</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">f</span><span style="color:#183691;">'unexpected </span><span style="color:#323232;">{state=}</span><span style="color:#183691;"> with </span><span style="color:#323232;">{template=}</span><span style="color:#183691;"> at end of template and </span><span style="color:#323232;">{remaining_groups=}</span><span style="color:#183691;">'</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">_unfold</span><span style="color:#323232;">(template: </span><span style="color:#0086b3;">str</span><span style="color:#323232;">, groups: </span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">...</span><span style="color:#323232;">]) -> </span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">str</span><span style="color:#323232;">, </span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">int</span><span style="color:#323232;">, </span><span style="color:#0086b3;">...</span><span style="color:#323232;">]]:
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#183691;">'?'</span><span style="color:#323232;">.join([template] </span><span style="font-weight:bold;color:#a71d5d;">* </span><span style="color:#0086b3;">5</span><span style="color:#323232;">), groups </span><span style="font-weight:bold;color:#a71d5d;">* </span><span style="color:#0086b3;">5
</span><span style="color:#323232;">
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">class </span><span style="color:#0086b3;">Day12</span><span style="color:#323232;">(</span><span style="color:#0086b3;">Solver</span><span style="color:#323232;">):
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#62a35c;">__init__</span><span style="color:#323232;">(self):
</span><span style="color:#323232;">    </span><span style="color:#62a35c;">super</span><span style="color:#323232;">().</span><span style="color:#62a35c;">__init__</span><span style="color:#323232;">(</span><span style="color:#0086b3;">12</span><span style="color:#323232;">)
</span><span style="color:#323232;">    self.input: </span><span style="color:#0086b3;">list</span><span style="color:#323232;">[</span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">str</span><span style="color:#323232;">, </span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">[</span><span style="color:#0086b3;">int</span><span style="color:#323232;">]]] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">[]
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">presolve</span><span style="color:#323232;">(self, input: </span><span style="color:#0086b3;">str</span><span style="color:#323232;">):
</span><span style="color:#323232;">    lines </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#62a35c;">input</span><span style="color:#323232;">.rstrip().split(</span><span style="color:#183691;">'</span><span style="color:#0086b3;">n</span><span style="color:#183691;">'</span><span style="color:#323232;">)
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">line </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">lines:
</span><span style="color:#323232;">      template, groups </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">line.split(</span><span style="color:#183691;">' '</span><span style="color:#323232;">)
</span><span style="color:#323232;">      self.input.append((template, </span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">(</span><span style="color:#0086b3;">int</span><span style="color:#323232;">(group) </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">group </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">groups.split(</span><span style="color:#183691;">','</span><span style="color:#323232;">))))
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">solve_first_star</span><span style="color:#323232;">(self) -> </span><span style="color:#0086b3;">int</span><span style="color:#323232;">:
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#62a35c;">sum</span><span style="color:#323232;">(_match_one_template(template, groups) </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">template, groups </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">self.input)
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">solve_second_star</span><span style="color:#323232;">(self) -> </span><span style="color:#0086b3;">int</span><span style="color:#323232;">:
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#62a35c;">sum</span><span style="color:#323232;">(_match_one_template(</span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;">_unfold(template, groups)) </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">template, groups </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">self.input)
</span>
  • All
  • Subscribed
  • Moderated
  • Favorites
  • •
  • advent_of_code@programming.dev
  • tacticalgear
  • DreamBathrooms
  • cisconetworking
  • magazineikmin
  • InstantRegret
  • Durango
  • thenastyranch
  • Youngstown
  • rosin
  • slotface
  • mdbf
  • khanakhh
  • kavyap
  • everett
  • provamag3
  • modclub
  • Leos
  • cubers
  • ngwrru68w68
  • ethstaker
  • osvaldo12
  • GTA5RPClips
  • anitta
  • megavids
  • normalnudes
  • tester
  • JUstTest
  • lostlight
  • All magazines
    •