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
- 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
🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard
🔓 Unlocked after 25 mins
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
Also on Github.
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 < 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 < desired_length: state = Matching(current_length + 1, desired_length) case (Matching(current_length, desired_length), '#') if current_length < 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)
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
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