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 &<)
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 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 :)
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.