Day 12: Hot Spring

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
  answer = 0
  # Try adding a '.' to the candidate
  answer += COUNT_SOLUTIONS(string_candidate+'.', array_position)
  # 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 '.'
  answer += COUNT_SOLUTIONS(
       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.

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

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

Did you notice an optimization for our COUNT_SOLUTIONSsearch 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_SOLUTIONSis 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.

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';
}

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.

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,
      read_concurrency: true,
      write_concurrency: true,
      decentralized_counters: true
    ])

    lines
    |> Stream.map(&parse_line/1)
    |> Task.async_stream(
      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

module Main (main) where

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

main :: IO ()
main = do
    input <- readFile "./input.txt"
    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)

// @ts-check
import * as fs from 'fs'

let input = fs.readFileSync(process.argv[2]).toString().trimEnd()
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)

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

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.

#[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)
}

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