sample_input =
"""
???.### 1,1,3
.??..??...?##. 1,1,3
?#?#?#?#?#?#?#? 1,3,1,6
????.#...#... 4,1,1
????.######..#####. 1,6,5
?###???????? 3,2,1
"""
defmodule Combinations do
def create({_a, _b} = elements, total_count, a_count) when total_count >= a_count do
create_rec([], elements, total_count, a_count)
|> Enum.uniq()
end
defp create_rec(combination_builder, {a, _b} = _elements, total_count, a_count)
when length(combination_builder) == total_count do
case Enum.count(combination_builder, &(&1 == a)) do
^a_count -> [combination_builder]
current_a_count when current_a_count < a_count -> []
end
end
defp create_rec(combination_builder, {a, b} = elements, total_count, a_count)
when length(combination_builder) < total_count do
case Enum.count(combination_builder, &(&1 == a)) do
^a_count ->
[List.duplicate(b, total_count - length(combination_builder)) ++ combination_builder]
current_a_count when current_a_count < a_count ->
elements
|> Tuple.to_list()
|> Enum.flat_map(&create_rec([&1 | combination_builder], elements, total_count, a_count))
end
end
end
defmodule HotSprings do
def sum_count_arrangements(input) do
input
|> String.split("\n", trim: true)
|> Enum.map(&count_arrangements/1)
|> Enum.sum()
end
defp count_arrangements(line) do
[damaged_spring_list, groups] = String.split(line, " ", trim: true)
groups = groups |> String.split(",") |> Enum.map(&String.to_integer/1)
unknown_count = damaged_spring_list |> String.to_charlist() |> Enum.count(&(&1 == ??))
known_damaged_count = damaged_spring_list |> String.to_charlist() |> Enum.count(&(&1 == ?#))
missing_damaged_count = Enum.sum(groups) - known_damaged_count
Combinations.create({"#", "."}, unknown_count, missing_damaged_count)
|> Enum.count(fn combination ->
damaged_spring_list
|> merge_into(combination)
|> complies?(groups)
end)
end
defp merge_into(damaged_spring_spec, combination) do
Enum.reduce(combination, damaged_spring_spec, fn replacement, acc ->
String.replace(acc, "?", replacement, global: false)
end)
end
defp complies?(damaged_spring_spec, groups),
do: to_damaged_groups(damaged_spring_spec) == groups
defp to_damaged_groups(damaged_spring_spec) do
damaged_spring_spec
|> String.split("", trim: true)
|> Enum.chunk_by(& &1)
|> Enum.filter(fn [first | _] -> first == "#" end)
|> Enum.map(&length/1)
end
end
HotSprings.sum_count_arrangements(sample_input)
# expected 21
Path.join(__DIR__, "day-12.input")
|> File.read!()
|> HotSprings.sum_count_arrangements()
# 6827
# dammit, this is still slow (with less combinations) (10 seconds)