Day 19HEADmaster

1 files changed, 104 insertions, 0 deletions

diff --git a/src/day19.exs b/src/day19.exs
new file mode 100644
index 0000000..9c9a1e2
--- /dev/null
+++ b/src/day19.exs
@@ -0,0 +1,104 @@
+defmodule Day19 do
+  defmodule Onsen do
+    @derive Inspect
+    @enforce_keys [:patterns, :designs]
+    defstruct @enforce_keys
+
+    def from_data(data) do
+      [patterns, designs] = data
+      |> String.split("\n\n", trim: true)
+
+      patterns = patterns
+      |> String.split(", ", trim: true)
+
+      designs = designs
+      |> String.split("\n", trim: true)
+
+      %Onsen{patterns: patterns, designs: designs}
+    end
+
+    def count_feasible_designs(onsen) do
+      onsen.designs
+      |> Enum.filter(& feasible?(&1, onsen.patterns) |> elem(0))
+      |> Enum.count()
+    end
+
+    defp feasible?(design, patterns, vis \\ MapSet.new()) do
+      cond do
+        MapSet.member?(vis, design) ->
+          {false, vis}
+        design == "" ->
+          {true, vis}
+        true ->
+          for pat <- patterns, reduce: {false, MapSet.put(vis, design)} do
+            {acc, vis} ->
+              cond do
+                acc == true ->
+                  {acc, vis}
+                String.starts_with?(design, pat) ->
+                  design
+                  |> String.split_at(String.length(pat))
+                  |> elem(1)
+                  |> feasible?(patterns, vis)
+                true ->
+                  {acc, vis}
+              end
+          end
+      end
+    end
+
+    def count_feasible_ways(onsen) do
+      onsen.designs
+      |> Enum.map(& ways(&1, onsen.patterns) |> elem(0))
+      |> Enum.sum()
+    end
+
+    defp ways(design, patterns, vis \\ Map.new()) do
+      case Map.fetch(vis, design) do
+        {:ok, count} ->
+          {count, vis}
+        :error ->
+          if design == "" do
+            {1, vis}
+          else
+            for pat <- patterns, reduce: {0, vis} do
+              {acc, vis} ->
+                cond do
+                  String.starts_with?(design, pat) ->
+                    design
+                    |> String.split_at(String.length(pat))
+                    |> elem(1)
+                    |> ways(patterns, vis)
+                    |> then(fn {acc2, vis} -> {acc + acc2, vis} end)
+                  true ->
+                    {acc, vis}
+                end
+            end
+            |> then(fn {acc, vis} -> {acc, Map.put(vis, design, acc)} end)
+          end
+      end
+    end
+  end
+
+  def part1(data) do
+    data
+    |> Onsen.from_data()
+    |> Onsen.count_feasible_designs()
+  end
+
+  def part2(data) do
+    data
+    |> Onsen.from_data()
+    |> Onsen.count_feasible_ways()
+  end
+end
+
+data = IO.read(:stdio, :eof)
+
+{time1, ans1} = :timer.tc(fn -> Day19.part1(data) end)
+IO.puts("Time  : #{time1 / 1000000}")
+IO.puts("Answer: #{ans1}")
+
+{time2, ans2} = :timer.tc(fn -> Day19.part2(data) end)
+IO.puts("Time  : #{time2 / 1000000}")
+IO.puts("Answer: #{ans2}")