# Day 12: Hot Spring

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace `python` with any of the "short names" listed in this page of supported languages):

``````<details>
<summary>Part 1</summary>

```python
```

</details>
``````

1. Hvv
This problem isn't really quality-checking your initial implementation so much as it is daring you to do the straightforward solution so it can pull the rug out from under you. Part 1 Solution...

This problem isn't really quality-checking your initial implementation so much as it is daring you to do the straightforward solution so it can pull the rug out from under you.

Part 1 Solution

Like yesterday if we go with the future-proof solution here we won't have anything to discuss for Part 2, so we'll spend a bit of time checking out the most obvious solution.

Namely, just try all the combinations and see what works!

I imagine you could have a hideous for loop do the manual checking since the array size is limited, but we can at least spare ourselves the dignity here of using recursion to deal with that instead. I would imagine such a solution could pass to itself the context of which part of the string you're building and where in the list you are, like something like:

``````COUNT_SOLUTIONS(string_candidate, array_position):
if array_position is at the end of the array:
if string_candidate matches against the reference string:
return 1
else:
return 0
# Try adding a '.' to the candidate
# Try adding a block of '#' corresponding to the current array position.
# Note that if we're not at the end of the array, we need to add another '.'
string_candidate+(array[array_position]*'#'+'.' if we're not at the end of the array,
array_position+1)
``````

This solution is pretty crude and elides some detail, but the general idea should work for a real solution.

If you program it well (and you don't need to program it well to get this part), then your code will only make a few calls per valid assignment, assuming there aren't many assignments, it should be pretty fast.

My answer was on the order of thousands, so it really doesn't take that long.

Part 2 Solution

Now it's time for the rug pull, because this expanded version absolutely takes that long (my answer was on the order of 1012).

Let's go back to the original problem and our original solution.

Did you notice an optimization for our `COUNT_SOLUTIONS`search routine? Namely, if the `string_candidate` is known to not match the reference string prefix, then we can cut it off early. This sounds simple, but it means that we can actually have `COUNT_SOLUTIONS` be in terms of

`string_index` and `array_position` (i.e. we know that the string is correct up to `string_index` and we're trying to build the rest of the string afterwards).

But now we realize something even more interesting: If we call `COUNT_SOLUTIONS` with the same `string_index` and `array_position` every time, it will always return the same answer, but our current search algorithm calls itself billions of times to count every solution one by one. Why process all those calls for `COUNT_SOLUTIONS` when we can just call each `string_index` and `array_position` once and cache the answer to return any time it gets called again?

This insight represents a ridiculous speedup (and a complete rethinking of the solution's complexity which we'll get back to later), because it saves not only the immediate call to `COUNT_SOLUTIONS` but also every recursive call that it would have made, and every call that that call makes, etc.

So, after rewriting the `COUNT_SOLUTIONS` to be based off of `string_index` and `array_position` we can stick an map/dict/2d array somewhere that, if we encounter a call where we've already calculated the answer, just returns it immediately.

Now back to the complexity. It's much faster, but how much faster?

Well we can answer that with how our function is called and what it does.

There are at most (string length) values of `string_index` and at most (array length) values of `array_position`, and most importantly every corresponding calculation with `COUNT_SOLUTIONS`is done at most once (because every call after that is just a map/dict/array lookup).

Then, for each call, `COUNT_SOLUTIONS` does some string building/checking and makes 2 other calls to `COUNT_SOLUTIONS`.

This gives means that we do at most `(string length)*(array length)*(string comparison cost)` operations, which is much faster than the `(weird, could be really bad)` complexity that it was before and definitely enough to solve the expanded version of the problem they're throwing at us now.

Just to note, the strategy we used here is has the wonderfully undescriptive computer science name of Dynamic Programming, which can be used to find solutions to some very weird and hard problems, though with the distinct downside of the solutions themselves being strange looking and difficult to describe.

C++ Part 1/2 Code

I have to preface this with the fact that my solution doesn't actually do `COUNT_SOLUTIONS` in the same way as above, but it uses the same dynamic programming idea of re-using existing counts.

``````#include <bits/stdc++.h>
using namespace std;
vector<int> string_to_array(const string& s) {
vector<int> ans;
long long val = 0;
for(int i=0;i<s.size();i++) {
if(s[i] == ',') {
ans.push_back(val);
val = 0;
} else {
val *= 10;
val += s[i]-'0';
}
}
ans.push_back(val);
return ans;
}
long long solve(const string& s, const vector<int>& gear_list) {
vector<vector<long long>> dp(s.size()+1,vector<long long>(gear_list.size()+1,0));
// prefix_good[i] = # of gears before index i in s that are known to be good
// In the solution I described "cost of string comparison" but
// here we can reduce that to a 2 array lookups to answer the question of
// "Is ######. valid?"
// With "does the string from [x,x+5) contain no '.' values and
// one non-'#' at the end?"
vector<int> prefix_good(1);
for(int i=0;i<s.size();i++) {
prefix_good.push_back(prefix_good.back());
if(s[i] == '.') {
prefix_good.back()++;
}
}
// dp[string_index][array_index] counts:
// the number of string prefixes up to string_index (exclusive)
// that are valid and account for the gear list up to
// array_index (exclusive)

// Our full answer is then dp[string size][array size]
dp[0][0] = 1;
int n = s.size();
for(int i=0;i<s.size();i++) {
for(int j=0;j<=gear_list.size();j++) {
if(s[i] != '#') {
dp[i+1][j] += dp[i][j];
}
if(j < gear_list.size()) {
if(i+gear_list[j] <= n) {
if(prefix_good[i+gear_list[j]]-prefix_good[i] == 0) {
if(j+1 == gear_list.size()) {
dp[i+gear_list[j]][j+1] += dp[i][j];
} else {
if(i+gear_list[j] < n && s[i+gear_list[j]] != '#') {
dp[i+gear_list[j]+1][j+1] += dp[i][j];
}
}
}
}
}
}
}
return dp[n][gear_list.size()];
}
int main() {
string input_line;
long long ans1 = 0;
long long ans2 = 0;
while(getline(cin,input_line)) {
if(input_line.size() == 0) {break;}
stringstream ss(input_line);

string gears;
ss >> gears;

string gear_list_string;
ss >> gear_list_string;

vector<int> gear_list = string_to_array(gear_list_string);

ans1 += solve(gears,gear_list);

string extended_gears;
vector<int> extended_gear_list;
for(int i=0;i<5;i++) {
if(i > 0) {
extended_gears.push_back('?');
}
extended_gears = extended_gears+gears;
extended_gear_list.insert(extended_gear_list.end(),gear_list.begin(),gear_list.end());
}

ans2 += solve(extended_gears,extended_gear_list);

}
cout << ans1 << '\n';
cout << ans2 << '\n';
}
``````
2. first-must-burn
Ugh, this one kicked my ass. Ran out of steam last night and didn't have much time today, but I was barking up the completely wrong tree for a while. I was very tired when I started the problem,...

Ugh, this one kicked my ass. Ran out of steam last night and didn't have much time today, but I was barking up the completely wrong tree for a while. I was very tired when I started the problem, so that meant I got pretty far up the blind alley and had a hard time abandoning the whole strategy.

Golang solution

Discussion

I was treating it like a DFS problem (walking through trying each value for each bit), which worked okay Part 1, but didn't scale well. So I was hammering on pruning optimizations for a good while before I had to go looking for hints. In the end, I don't think I was ever going to get there because I was incrementally setting the unknowns, measuring the groups (up to the first unknown that hadn't been set), then seeing if the measured group was compatible. This meant I was also always working with the whole string, and the approach didn't make it easy to tell which parts of the input were related to which groups.

When I started the problem last night, the scalable solution (recursively peeling groups off the front of the row) seemed like it would require too much backtracking to get right. I was missing the insight that any good spring must separate a group. That greatly simplifies the peeling logic and the number of cases to consider. In the end I'm pretty happy with my solution. It has a simple flow and not too many edge cases in the logic.

One other good outcome, I learned what memoization is.

3. [2]
lily
Wondering if anyone could point me in the right direction for this day's part 2? I tried for hours to get it working but hadn't ever done dynamic programming before and so wasn't able to figure...

Wondering if anyone could point me in the right direction for this day's part 2? I tried for hours to get it working but hadn't ever done dynamic programming before and so wasn't able to figure out what to memoize to make my program fast enough.

1. whs
(edited )
My code is probably dynamic programming. If I have the input .###..# 3,1 the algorithm works by Look at the leftmost character. It should be #, . or ? If it is ., then it is not relevant. The...

My code is probably dynamic programming. If I have the input `.###..# 3,1` the algorithm works by

1. Look at the leftmost character. It should be `#`, `.` or `?`
2. If it is `.`, then it is not relevant. The result of `.###..# 3,1` is the same as `###..# 3,1`. So, we recurse with new input `###..# 3,1`
3. If it is `#`, then count all continuous `#` or `?` next to it.
4. If it is less than 3 (the first number) then this is not a valid solution (eg. `#.` `#?.` or premature end of string)
5. Now we're sure that the first 3 characters must be `###`. The fourth must be either end of string, `.` or `?` (which can only be resolved as `.`). Check that it is so.
6. Now that we know the first four characters, and used the first block we can strip them from the input. We now know that the result is the same as input `.# 1`.
7. Recurse with the new input until end of string
8. At the end there should be zero map left and zero blocks. This is one valid solution.

So with that you can now validate whether a solution is valid or not, but that is only a single solution. Now the `?` comes into play. Let's say the input is `?##?.? 3,1`

1. The first character is `?`. It can be either `#` or `.`
2. Assume that it is `#`, then, similar to step 3-5 previously we check that the first 3 characters are `###`. And the 4th character is either end of string, `.` or `?` (which can only be`.`).
• If the check holds, then similar to step 6 we strip the known part `?##?` = `###.`. The input is now `.? 1`. Recurse and count the number of solutions
3. Assume that it is `.`, then as mentioned in step 2 `.` can be removed. The input is now `##?.? 3,1`. Recurse and count the number of solutions.
4. Sum the number of solution from step 2+3

As for the caching part, if you have the same inputs (map & blocks) then there's only one correct answer. So you can use both of them as cache key and lookup the cache first before actually recursing.

I found that for part 1, actually building out the solutions help in debugging. It is not scalable enough for part 2, however. Bugs may cause your algorithm to run wild (like I added an extra `?` at the end of part 2 input), so good luck.

4. jzimbel
(edited )
Welp, my updated solution for part 2 is passing unit tests (including checking the count for each line individually) but giving too high an answer for the real input. It seems like I'm missing...

Welp, my updated solution for part 2 is passing unit tests (including checking the count for each line individually) but giving too high an answer for the real input. It seems like I'm missing some edge case that exists only in the real input, but I couldn't begin to guess what that is.

Could someone who has a working solution share their puzzle input, with each individual line tagged with its individual arrangement count? Only if you have time to help a stranger on the internet, ofc.
Maybe via pastebin / GH gist, considering how big the input is...

edit: I figured it out! I wasn't checking that the arrangement contains no '#'s after the last contiguous segment.

Parts 1 and 2, now working

After changing it to run on all lines concurrently, and tuning the cache table appropriately, it solves part 2 in about 1.8 sec on my machine. :)

``````defmodule AdventOfCode.Solution.Year2023.Day12 do
@table __MODULE__.MemoTable

def part1(input) do
input
|> String.split("\n", trim: true)
|> solve()
end

def part2(input) do
input
|> String.split("\n", trim: true)
|> Stream.map(&quintuple/1)
|> solve()
end

defp solve(lines) do
:ets.new(@table, [
:named_table,
:public,
write_concurrency: true,
decentralized_counters: true
])

lines
|> Stream.map(&parse_line/1)
fn {pattern, contig_counts} ->
memo_count_arrangements(pattern, contig_counts, 0)
end,
ordered: false
)
|> Stream.map(fn {:ok, count} -> count end)
|> Enum.sum()
after
:ets.delete(@table)
end

defp quintuple(line) do
[springs_str, sizes_str] = String.split(line)

[{springs_str, "?"}, {sizes_str, ","}]
|> Enum.map(fn {s, j} -> List.duplicate(s, 5) |> Enum.join(j) end)
|> Enum.join(" ")
end

defp memo_count_arrangements(pattern, contig_counts, offset) do
memo({pattern, contig_counts, offset}, fn ->
count_arrangements(pattern, contig_counts, offset)
end)
end

defp count_arrangements(pattern, [contig_count | _], offset)
when byte_size(pattern) - offset < contig_count,
do: 0

defp count_arrangements(pattern, [], offset) do
# If there are any '#'s in the remainder of the string, this arrangement is not valid.
case :binary.match(pattern, "#", scope: {byte_size(pattern), offset - byte_size(pattern)}) do
:nomatch -> 1
_ -> 0
end
end

defp count_arrangements(pattern, [contig_count | rest_contig], offset) do
trailing_dot? = match?([_ | _], rest_contig)
segment_size = contig_count + if(trailing_dot?, do: 1, else: 0)

# The first '#' we find limits how far we can go. The last possible fit for this contig_count starts at that '#'.
stop_after =
case :binary.match(pattern, "#", scope: {byte_size(pattern), offset - byte_size(pattern)}) do
{pos, _len} -> pos
:nomatch -> :infinity
end

dot = if trailing_dot?, do: "[?.]", else: ""

~r"""
[?\#]   # This is the character that we'll get the index of. The first character of this valid contiguous section.
(?=     # Positive lookahead. Check that the correct characters follow the start of this contiguous section, without consuming them.
[?\#]{#{contig_count - 1}}   # Remaining characters of the contiguous section.
#{dot}                       # Optional trailing '.', if this is not the final contiguous section.
)
"""x
|> Regex.scan(pattern, offset: offset, return: :index)
|> Stream.flat_map(fn [{pos, _len}] -> if pos <= stop_after, do: [pos], else: [] end)
|> Stream.map(&memo_count_arrangements(pattern, rest_contig, &1 + segment_size))
|> Enum.sum()
end

defp memo(key, fun) do
case :ets.match(@table, {key, :"\$1"}) do
[[value]] -> value
[] -> tap(fun.(), &:ets.insert(@table, {key, &1}))
end
end

defp parse_line(line) do
[springs_str, sizes_str] = String.split(line)

{springs_str, Enum.map(String.split(sizes_str, ","), &String.to_integer/1)}
end
end
``````
5. scarecrw
Fun day, and continuing to step up the difficulty! Overall I'm not especially thrilled with my solution; after the manipulation to make it memoized it's no longer very readable (and I'm too tired...

Fun day, and continuing to step up the difficulty!

Overall I'm not especially thrilled with my solution; after the manipulation to make it memoized it's no longer very readable (and I'm too tired to bother cleaning it up).

I am, however, happy to have learned how Haskell can implement memoization with just a list. It took some mangling to convert my solution into taking a single `Int` parameter, but after that the conversion to the memoized form was neat.

``````module Main (main) where

import Data.List (intercalate)
import AOCTools (splitBy)

main :: IO ()
main = do
putStrLn \$ "Part 1: " ++ show (solve1 \$ lines input)
putStrLn \$ "Part 2: " ++ show (solve2 \$ lines input)

parseRow :: String -> (String, [Int])
parseRow s = (springs ++ ".", nums) where -- add extra '.' to simplify end state
springs = takeWhile (/=' ') s
numStr = tail (dropWhile (/=' ') s)
nums = map read \$ splitBy "," numStr

solve1 :: [String] -> Integer
solve1 input = sum \$ map (uncurry solve . parseRow) input

solve2 :: [String] -> Integer
solve2 input = solve1 \$ map unfold input where
unfold s = springs ++ " " ++ nums where
[origSprings, origNums] = splitBy " " s
springs = intercalate "?" (replicate 5 origSprings)
nums = intercalate "," (replicate 5 origNums)

solve :: String -> [Int] -> Integer
solve s n = memo_solve 0 where
sLen = length s
nLen = length n
memo_solve = (map hsolve [0..] !!)
hsolve v
| j == nLen = if '#' `notElem` drop i s then 1 else 0
| i == sLen = 0
| s !! i == '.' = op1
| sLen - i < n !! j + 1 = 0
| s !! i == '?' = if couldFit then op1 + op2 else op1
| couldFit = op2
| otherwise = 0
where
(i, j) = divMod v sLen
couldFit = s !! (i + (n !! j)) /= '#' && notElem '.' (take (n !! j) (drop i s))
op1 = memo_solve \$ (i+1)*sLen + j
op2 = memo_solve \$ (i + (n !! j) + 1)*sLen + (j+1)
``````
1 vote
6. RheingoldRiver
As a huge paint-by-numbers fan, I appreciate the setup of this problem quite a bit. Part 2 notes After an easy part 1, I tried to ~~ math ~~ this with a partially-recursive,...

As a huge paint-by-numbers fan, I appreciate the setup of this problem quite a bit.

Part 2 notes After an easy part 1, I tried to ~~ math ~~ this with a partially-recursive, partially-combinatorial method. Then I gave up after an hour or more and did it straightforward. Had a couple dumb mistakes (what a surprise) but eventually got there.

Python solutions

1 vote
7. whs
Today's language is JavaScript. I wanted to use TypeScript, but I'm lazy to setup the compiler. A trailing separator in my join implementation make me rewrote part 2 into recursiveless, before...

Today's language is JavaScript. I wanted to use TypeScript, but I'm lazy to setup the compiler. A trailing separator in my join implementation make me rewrote part 2 into recursiveless, before realizing it would be very complicated. I spotted the error during the rewrite.

Part 1 My actual part 1 implementation use exception to signify "invalid solution". Later on the the catch block catches the recursion depth limit error and make it return the wrong results. So during part 2 rewrite I had to change it to returning empty list.
``````// @ts-check
import * as fs from 'fs'

let problems = input.split("\n").map((line) => {
let [map, unknowns] = line.split(" ")
return {
map,
unknowns: unknowns.split(",").map((i) => parseInt(i, 10))
}
})

function getBlock(map) {
let out = 0
for(let i = 0; i < map.length; i++){
if(map[i] === '#' || map[i] === '?') {
out++
}else{
break
}
}
return out
}

/**
* @param {string} map
* @param {number[]} unknowns
* @returns string[]
*/
function solve1(map, unknowns){
if(map.length === 0){
if(unknowns.length > 0){
// throw new Error(`invalid solution - empty map but \${unknowns.length} unknowns items left`)
return []
}
console.log(`End of the line - empty map`)
return [""]
}

if (map[0] === "?") {
let solns = []

// Try to fill right side
let continuousUnknownOrDamaged = getBlock(map)
let wantedSize = unknowns[0]
if(continuousUnknownOrDamaged >= wantedSize){
// we can fill, but only if the right side is EOL or . or ?
if(wantedSize === map.length || map[wantedSize] !== '#'){
console.log(`We can fill left side \${map} with length \${wantedSize}`)
let subsoln = cachedSolve1(map.slice(wantedSize + 1), unknowns.slice(1))
solns.push(...subsoln.map(v => "#".repeat(wantedSize) + "." + v))
}
}

// Or fill the current tile with . and go on
let subsoln = cachedSolve1(map.slice(1), unknowns)
solns.push(...subsoln.map(v => `.\${v}`))

return solns
}else if(map[0] === "#") {
let block = getBlock(map)
if(block < unknowns[0]) {
// throw new Error(`invalid solution - # block of \${block} but we want at least \${unknowns[0]}`)
return []
}
// fill the block with broken ones
let prefix = "#".repeat(unknowns[0])
let newMap = map.slice(unknowns[0])
let newUnknown = unknowns.slice(1)
if (newMap.length === 0){
if(newUnknown.length > 0){
// throw new Error(`invalid solution - end of line but \${newUnknown.length} unknowns items left`)
return []
}
// we reach the end, hooray!
console.log("End of line after block fill")
return [prefix]
}else if (newMap[0] === "?") {
// make that operational
newMap = newMap.slice(1)
prefix += "."
}else if (newMap[0] === "#") {
// throw new Error(`invalid solution - block filled but the next item is #`)
return []
}
console.log(`In \${map} we got block of \${block}. After we filled \${unknowns[0]} we got \${newMap} and unknown \${JSON.stringify(newUnknown)}`)
return cachedSolve1(newMap, newUnknown).map(v => prefix + v)
}else if(map[0] === ".") {
return cachedSolve1(map.slice(1), unknowns).map(v => `.\${v}`)
}else{
throw new Error("unknown char")
}
}

const cache = {}
function cachedSolve1(map, unknowns) {
let key = map + JSON.stringify(unknowns)
if(cache[key] !== undefined){
return cache[key]
}
let out = solve1(map, unknowns)
cache[key] = out
return out
}

let out1 = problems.map((p) => {
let out = cachedSolve1(p.map, p.unknowns)
console.log("Problem:")
console.log(p)
console.log(`Solutions \${out.length}`)
console.log(out)
return out.length
}).reduce((a, b) => a+b, 0)
console.log(out1)
``````
Part 2 The part 2 version do not visually build the output (it was useful in part 1 to debug any mistakes). Otherwise it is mostly the same as part 1. Adding cache also help improve large running time.
``````34c34
< 			return []
---
> 			return 0
37c37
< 		return [""]
---
> 		return 1
41c41
< 		let solns = []
---
> 		let solns = 0
51c51
< 				solns.push(...subsoln.map(v => "#".repeat(wantedSize) + "." + v))
---
> 				solns += subsoln
57c57
< 		solns.push(...subsoln.map(v => `.\${v}`))
---
> 		solns += subsoln
64c64
< 			return []
---
> 			return 0
73c73
< 				return []
---
> 				return 0
77c77
< 			return [prefix]
---
> 			return 1
84c84
< 			return []
---
> 			return 0
87c87
< 		return cachedSolve1(newMap, newUnknown).map(v => prefix + v)
---
> 		return cachedSolve1(newMap, newUnknown)
89c89
< 		return cachedSolve1(map.slice(1), unknowns).map(v => `.\${v}`)
---
> 		return cachedSolve1(map.slice(1), unknowns)
107,112c107,116
< 	let out = cachedSolve1(p.map, p.unknowns)
< 	console.log("Problem:")
< 	console.log(p)
< 	console.log(`Solutions \${out.length}`)
< 	console.log(out)
< 	return out.length
---
> 	let map = ""
> 	let unknowns = []
> 	for(let i = 0; i < 5; i++){
> 		map += p.map + "?"
> 		unknowns.push(...p.unknowns)
> 	}
> 	map = map.slice(0, map.length-1)
> 	let out = cachedSolve1(map, unknowns)
> 	console.log(`\${p.map}: \${out}`)
> 	return out
``````
1 vote
8. DataWraith
God, this one was hard. I didn't complete it within 24h. The algorithm I came up with was sound, but once again, I lost hours upon hours in implementation bugs. At one point I was exhausted enough...

God, this one was hard. I didn't complete it within 24h. The algorithm I came up with was sound, but once again, I lost hours upon hours in implementation bugs. At one point I was exhausted enough to screw up my unit tests, which made further progress extremely difficult... but I'm proud that I finally got through it after two days, and without any spoilers, too.

Algorithm

For part 1 I wrote a RegEx template that validated the strings, it looks like this: `^(\.|\?)*(\#|\?){4}(\.|\?)+(\#|\?){1}(\.|\?)+(\#|\?){1}(\.|\?)*\$` for a row with `4,1,1` as the consecutive broken spring numbers. I knew this was highly sub-optimal, but I just threw that in a Breadth-First Search that successively replaced the question marks and it worked fairly quickly, because the RegEx pruned away the invalid states. Had I not spent quite a bit of time on a more elegant solution by that time (because I was fairly certain this was another one of those 'make the naive solution exponentially slower' part 2's), it would have been a quick win...

Since the RegEx worked so well, I decided to try and use them for Part 2 as well. The idea was to generate a simple finite state automaton (a simplified version of what is used for regular expressions) for each row, that would `accept` if the row was 'proper' and then count the number of times we end up in the `accept` state, similar to Day 5. Yes, this is technically dynamic programming.

Rust
``````#[derive(Eq, PartialEq, Clone, Hash, Copy)]
enum State {
ColumnStart(usize),
ConsecutiveBroken((usize, usize)),
Final,
}

impl std::fmt::Debug for State {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
State::ColumnStart(col) => write!(f, "S({})", col),
State::ConsecutiveBroken((col, i)) => write!(f, "B({}, {})", col, i),
State::Final => write!(f, "F"),
}
}
}

#[derive(Debug)]
pub struct Automaton {
pub states: HashSet<State>,
}

impl Automaton {
pub fn new(consecutives: Vec<usize>) -> Self {
let mut states = vec![];

// Ignore this, I had originally interspersed usize::MAX between the spring counts as a sentinel value.
let consecutives = consecutives
.into_iter()
.filter(|x| *x != usize::MAX)
.collect::<Vec<_>>();

for (col, c) in consecutives.iter().enumerate() {
states.push(State::ColumnStart(col));

for i in 0..*c {
states.push(State::ConsecutiveBroken((col, i)));
}
}

states.push(State::ColumnStart(consecutives.len()));
states.push(State::Final);

let mut s = HashSet::default();
states.into_iter().for_each(|st| {
s.insert(st);
});

Self { states: s }
}

pub fn transitions(&self, state: State, input: char) -> Vec<State> {
assert!(input == '.' || input == '#' || input == '?' || input == 'x');

match (state, input) {
(State::ColumnStart(col), '.') => vec![State::ColumnStart(col)],
(State::ColumnStart(col), '?') => {
vec![State::ColumnStart(col), State::ConsecutiveBroken((col, 0))]
}
(State::ColumnStart(col), '#') => {
vec![State::ConsecutiveBroken((col, 0))]
}

(State::ColumnStart(col), 'x') => {
if !self.states.contains(&State::ColumnStart(col + 1))
&& !self.states.contains(&State::ConsecutiveBroken((col, 0)))
{
vec![State::Final]
} else {
vec![]
}
}

(State::ConsecutiveBroken((col, i)), '#') => {
vec![State::ConsecutiveBroken((col, i + 1))]
}

(State::ConsecutiveBroken((col, i)), '?') => {
let mut result = vec![];

result.push(State::ConsecutiveBroken((col, i + 1)));

if !self
.states
.contains(&State::ConsecutiveBroken((col, i + 1)))
{
result.push(State::ColumnStart(col + 1));
}

result
}

(State::ConsecutiveBroken((col, i)), '.') => {
if !self
.states
.contains(&State::ConsecutiveBroken((col, i + 1)))
{
vec![State::ColumnStart(col + 1)]
} else {
vec![]
}
}

_ => vec![],
}
.into_iter()
.filter(|x| self.states.contains(x))
.collect()
}
}

pub fn count_possible_arrangements(record: &str, consecutives: Vec<usize>) -> usize {
let mut chars = record.chars().collect::<Vec<_>>();
chars.push('.');
chars.push('x');

let automaton = Automaton::new(consecutives);

let mut states = HashMap::default();
states.insert(State::ColumnStart(0), 1);

let states = chars.iter().fold(states, |states, c| {
let mut new_states = HashMap::default();

for (state, count) in states {
let transitions = automaton.transitions(state, *c);

for new_state in transitions.into_iter() {
new_states
.entry(new_state)
.and_modify(|x| *x += count)
.or_insert(count);
}
}

new_states
});

*states.get(&State::Final).unwrap_or(&0)
}
``````
Performance
``````day_12_bench  fastest       │ slowest       │ median        │ mean          │ samples │ iters
├─ parse      151 µs        │ 302.2 µs      │ 201.7 µs      │ 191.6 µs      │ 100     │ 100
├─ part1      5.726 ms      │ 6.205 ms      │ 5.79 ms       │ 5.812 ms      │ 100     │ 100
╰─ part2      66.02 ms      │ 104.7 ms      │ 66.66 ms      │ 67.3 ms       │ 100     │ 1
``````
1 vote