You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
58 lines
1.7 KiB
Elixir
58 lines
1.7 KiB
Elixir
defmodule Day19 do
|
|
def run do
|
|
{patterns, designs} = parse_file("data.txt")
|
|
|
|
{possibles, _c} =
|
|
Enum.reduce(designs, {[], %{}}, fn d, {list, cache} ->
|
|
{total, c} = possible_designs(d, patterns, cache)
|
|
{[total | list], c}
|
|
end)
|
|
|
|
part1 = Enum.filter(possibles, fn el -> el != 0 end) |> length
|
|
dbg(part1)
|
|
|
|
part2 = Enum.sum(possibles)
|
|
dbg(part2)
|
|
end
|
|
|
|
# if the design is empty list, we got to the end successfully
|
|
defp possible_designs([], _, cache), do: {1, cache}
|
|
|
|
defp possible_designs(design, patterns, cache) do
|
|
# look in the cache for this design
|
|
if Map.has_key?(cache, design) do
|
|
# if it's there, just return it
|
|
{Map.get(cache, design), cache}
|
|
else
|
|
# find all the patterns that match the beginning of the design
|
|
matching_patterns = Enum.filter(patterns, &List.starts_with?(design, &1))
|
|
|
|
{new_total, new_cache} =
|
|
if length(matching_patterns) == 0 do
|
|
# if there are none, we've failed
|
|
{0, cache}
|
|
else
|
|
# recurse on rest of the list
|
|
Enum.reduce(matching_patterns, {0, cache}, fn pattern, {total, new_cache} ->
|
|
rest = Enum.drop(design, length(pattern))
|
|
{t, c} = possible_designs(rest, patterns, new_cache)
|
|
{t + total, c}
|
|
end)
|
|
end
|
|
|
|
# add this new total to the cache & return it
|
|
new_cache2 = Map.put(new_cache, design, new_total)
|
|
{new_total, new_cache2}
|
|
end
|
|
end
|
|
|
|
defp parse_file(file) do
|
|
[top, bottom] = File.read!(file) |> String.trim() |> String.split("\n\n")
|
|
patterns = String.split(top, ", ") |> Enum.map(&String.graphemes/1)
|
|
designs = String.split(bottom, "\n") |> Enum.map(&String.graphemes/1)
|
|
{patterns, designs}
|
|
end
|
|
end
|
|
|
|
Day19.run()
|