Day 19 part 2

1 files changed, 67 insertions, 18 deletions

diff --git a/2015/day19.exs b/2015/day19.exs
index cb3ddf5..f68ab9b 100644
--- a/2015/day19.exs
+++ b/2015/day19.exs
@@ -20,6 +20,7 @@ defmodule Tokenizer do
         token
       end
     end)
+    |> Enum.into(<<>>, fn token -> <<token>> end)
   end
 end
 
@@ -32,40 +33,86 @@ end
   |> Stream.map(fn line ->
     case Regex.run(~r/(\w+) => (\w+)/, line) do
       [_, from, to] ->
-        [from] = Tokenizer.tokenize(from)
-        {:replacement, from, Tokenizer.tokenize(to)}
+        {:replacement, Tokenizer.tokenize(from), Tokenizer.tokenize(to)}
 
       _ ->
         {:start, Tokenizer.tokenize(line)}
     end
   end)
   |> Enum.reduce({[], nil}, fn
-    {:replacement, from, to}, {replacements, start} -> {[{from, to} | replacements], start}
-    {:start, start}, {replacements, _start} -> {replacements, start}
+    {:replacement, from, to}, {replacements, start} ->
+      {Enum.sort_by([{from, to} | replacements], fn {_, to} -> byte_size(to) end, :desc), start}
+
+    {:start, start}, {replacements, _start} ->
+      {replacements, start}
   end)
 
 defmodule MedicineSearcher do
+  use Agent
+
+  def start do
+    Agent.start_link(fn -> %{} end, name: __MODULE__)
+  end
+
   def nextGen(start, replacements) do
-    Enum.flat_map(0..(length(start) - 1), fn offset ->
-      {beforeReplace, [replaceStart | afterReplace]} = Enum.split(start, offset)
+    Enum.flat_map(0..(byte_size(start) - 1), fn offset ->
+      beforeReplace = binary_part(start, 0, offset)
+      replaceStart = binary_part(start, offset, byte_size(start) - offset)
+      <<replaceStart, afterReplace::binary>> = replaceStart
 
-      Enum.filter(replacements, fn {from, _} -> replaceStart == from end)
+      Enum.filter(replacements, fn {from, _} -> <<replaceStart>> == from end)
       |> Enum.map(fn {_, to} ->
-        beforeReplace ++ to ++ afterReplace
+        <<beforeReplace <> to <> afterReplace>>
+      end)
+    end)
+    |> Enum.uniq()
+  end
+
+  def previousGen(start, replacements) do
+    Enum.flat_map(replacements, fn {from, to} ->
+      Enum.map(0..(byte_size(start) - 1), fn offset ->
+        beforeReplace = binary_part(start, 0, offset)
+        replaceStart = binary_part(start, offset, byte_size(start) - offset)
+        {beforeReplace, replaceStart}
+      end)
+      |> Enum.filter(fn {_, replaceStart} -> String.starts_with?(replaceStart, to) end)
+      |> Enum.map(fn {beforeReplace, replaceStart} ->
+        afterReplace =
+          binary_part(replaceStart, byte_size(to), byte_size(replaceStart) - byte_size(to))
+
+        <<beforeReplace <> from <> afterReplace>>
       end)
     end)
     |> Enum.uniq()
   end
 
-  def occursInNGenerations?(start, _replacements, medicine, 0) do
-    start == medicine
+  def findPathDistance(start, _replacements, medicine) when start == medicine do
+    0
   end
 
-  def occursInNGenerations?(start, replacements, medicine, n) do
-    Enum.any?(
-      nextGen(start, replacements),
-      &occursInNGenerations?(&1, replacements, medicine, n - 1)
-    )
+  def findPathDistance(start, replacements, medicine) do
+    cached = Agent.get(__MODULE__, &Map.get(&1, medicine))
+
+    if cached do
+      cached
+    else
+      previous = previousGen(medicine, replacements)
+
+      shortestPaths =
+        Stream.map(previous, &findPathDistance(start, replacements, &1))
+        |> Stream.filter(&(&1 != :no_route))
+        |> Stream.map(&(&1 + 1))
+        |> Enum.take(1)
+
+      shortest =
+        case shortestPaths do
+          [shortest] -> shortest
+          [] -> :no_route
+        end
+
+      Agent.update(__MODULE__, &Map.put(&1, medicine, shortest))
+      shortest
+    end
   end
 end
 
@@ -75,8 +122,10 @@ IO.puts("Calibration size: #{length(calibration)}")
 
 start = Tokenizer.tokenize("e")
 
-medicineGeneration =
-  Stream.each(0..100, &IO.puts("Generation: #{&1}"))
-  |> Enum.find_index(&MedicineSearcher.occursInNGenerations?(start, replacements, medicine, &1))
+IO.puts("Max generations: #{byte_size(medicine)}")
+
+{:ok, _} = MedicineSearcher.start()
+
+medicineGeneration = MedicineSearcher.findPathDistance(start, replacements, medicine)
 
 IO.puts("The Medicine generation: #{medicineGeneration}")