2y ago

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

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

11 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!
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 &<)
- 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?
  
  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 :)
Haskell
Abused ParserCombinators for the first part. For the second, I took quite a while to figure out dynamic programming in Haskell.

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);

11 comments

Day 12: Hot Springs

Megathread guidelines

FAQ

Haskell

Rust

C

Scala3

Haskell

Dart