Day 7, more efficient solution

1 files changed, 34 insertions, 36 deletions

diff --git a/src/day07.exs b/src/day07.exs
index 1adeb54..0ec37b6 100644
--- a/src/day07.exs
+++ b/src/day07.exs
@@ -6,52 +6,50 @@ defmodule Utils do
   end
 end
 
-defmodule Equation do
-  @derive Inspect
-  defstruct [:result, :terms]
-
-  def from_string(string) do
-    string
-    |> Utils.parse_integer_list([":", " "])
-    |> then(& %Equation{result: hd(&1), terms: tl(&1)})
-  end
+defmodule Day07 do
+  defmodule Equation do
+    @derive Inspect
+    defstruct [:result, :terms]
 
-  def has_lr_solution(equation, ops) do
-    has_lr_solution(hd(equation.terms), tl(equation.terms), equation.result, ops)
-  end
+    def from_string(string) do
+      string
+      |> Utils.parse_integer_list([":", " "])
+      |> then(& %Equation{result: hd(&1), terms: tl(&1)})
+    end
 
-  defp has_lr_solution(acc, terms, result, ops) do
-    cond do
-      acc > result ->
-        false
-      terms == [] and acc == result ->
-        true
-      terms == [] ->
-        false
-      true ->
-        ops
-        |> Enum.any?(& has_lr_solution(apply_op(acc, hd(terms), &1), tl(terms), result, ops))
+    def lr_solution?(equation, ops) do
+      lr_solution_rev?(equation.result, Enum.reverse(equation.terms), ops)
     end
-  end
 
-  defp apply_op(l, r, op) do
-    case op do
-      :add ->
-        l + r
-      :mul ->
-        l * r
-      :concat ->
-        String.to_integer("#{l}#{r}")
+    defp lr_solution_rev?(result, terms, ops) do
+      cond do
+        terms == [] and result == 0 ->
+          true
+        terms == [] or result == 0 ->
+          false
+        true ->
+          ops
+          |> Enum.map(& apply_op_rev(result, hd(terms), &1))
+          |> Enum.filter(&Kernel.is_integer/1)
+          |> Enum.any?(& lr_solution_rev?(&1, tl(terms), ops))
+      end
     end
+
+    defp apply_op_rev(l, r, :add), do: l >= r and l-r
+    defp apply_op_rev(l, r, :mul), do: rem(l, r) == 0 and div(l, r)
+    defp apply_op_rev(l, r, :concat), do: uncat(l, r)
+
+    defp uncat(l, 0), do: l
+    defp uncat(0, _), do: false
+    defp uncat(l, r) when rem(l, 10) == rem(r, 10), do: uncat(div(l, 10), div(r, 10))
+    defp uncat(_, _), do: false
   end
-end
 
-defmodule Day07 do
   def part1(data) do
     data
     |> String.split("\n", trim: true)
     |> Enum.map(& Equation.from_string(&1))
-    |> Enum.filter(& Equation.has_lr_solution(&1, [:mul, :add]))
+    |> Enum.filter(& Equation.lr_solution?(&1, [:mul, :add]))
     |> Enum.map(& &1.result)
     |> Enum.sum()
   end
@@ -60,7 +58,7 @@ defmodule Day07 do
     data
     |> String.split("\n", trim: true)
     |> Enum.map(& Equation.from_string(&1))
-    |> Enum.filter(& Equation.has_lr_solution(&1, [:mul, :concat, :add]))
+    |> Enum.filter(& Equation.lr_solution?(&1, [:mul, :concat, :add]))
     |> Enum.map(& &1.result)
     |> Enum.sum()
   end