This one was scary at first.
I loved how part one directs you into an obvious optimization, and then part 2 kicks your butt by asking to not do that very specific optimization 
My solution for part 2 runs in between 150ms and 380ms. I guess it’s because of the async streams, but it’s always fast (around 150, rarely even 120) when I run it once, but then with benchee for 10 seconds it averages between 170 and 380 depending on the runs …) Anyways, is fast enough.
defmodule AdventOfCode.Solutions.Y24.Day19 do
alias AoC.Input
def parse(input, _part) do
[towels, targets] = input |> Input.read!() |> String.trim() |> String.split("\n\n")
towels = towels |> String.split([",", " "], trim: true) |> Enum.map(&{&1, byte_size(&1)})
targets = String.split(targets, "\n", trim: true)
{towels, targets}
end
def part_one({towels, targets}) do
primitives = reduce_towels(towels)
targets = filter_possible_targets(targets, primitives)
length(targets)
end
# remove towels that can be constructed with other towels
defp reduce_towels(towels) do
case Enum.split_with(towels, fn {text, _} = t -> possible_target?(text, towels -- [t]) end) do
{[], all_primitives} -> all_primitives
{_composable, primitives} -> reduce_towels(primitives)
end
end
defp filter_possible_targets(targets, towels) do
targets
|> Task.async_stream(&{possible_target?(&1, towels), &1}, ordered: false, timeout: :infinity)
|> Enum.flat_map(fn
{:ok, {true, t}} -> [t]
{:ok, {false, _}} -> []
end)
end
defp possible_target?(target, towels) do
possible_target?(target, towels, towels)
end
defp possible_target?("", _, _), do: true
defp possible_target?(_, [], _), do: false
defp possible_target?(target, [{h, b} | t], towels) do
sub_match? =
case target do
<<^h::binary-size(b), rest::binary>> -> possible_target?(rest, towels, towels)
_ -> false
end
sub_match? || possible_target?(target, t, towels)
end
def part_two({towels, targets}) do
primitives = reduce_towels(towels)
targets
|> filter_possible_targets(primitives)
|> Task.async_stream(&count_combinations(&1, towels), ordered: false, timeout: :infinity)
|> Enum.reduce(0, fn {:ok, n}, acc -> acc + n end)
end
defp count_combinations(target, towels) do
possible_towels = Enum.filter(towels, fn {text, _} -> String.contains?(target, text) end)
do_count(%{target => 1}, possible_towels, 0)
end
defp do_count(target_suffixes, _towels, count) when map_size(target_suffixes) == 0 do
count
end
defp do_count(target_suffixes, towels, count) do
new_suffixes =
for {t, count} <- target_suffixes, {h, b} <- towels, reduce: [] do
sufxs ->
case t do
<<^h::binary-size(b), rest::binary>> -> [{rest, count} | sufxs]
_ -> sufxs
end
end
{target_suffixes, finished_count} =
Enum.reduce(new_suffixes, {%{}, 0}, fn
{"", cpt}, {map, finished_count} -> {map, finished_count + cpt}
{sufx, cpt}, {map, finished_count} -> {Map.update(map, sufx, cpt, &(&1 + cpt)), finished_count}
end)
do_count(target_suffixes, towels, count + finished_count)
end
end
