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!

{-# 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 < 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)