1 files changed, 156 insertions, 0 deletions
diff --git a/aoc2023/build/packages/gap/src/gap@myers.erl b/aoc2023/build/packages/gap/src/gap@myers.erl
new file mode 100644
index 0000000..6a8ad35
--- /dev/null
+++ b/aoc2023/build/packages/gap/src/gap@myers.erl
@@ -0,0 +1,156 @@
+-module(gap@myers).
+-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function]).
+
+-export([difference/2]).
+-export_type([edit/1, path/1, status/1]).
+
+-type edit(FUV) :: {eq, list(FUV)} | {del, list(FUV)} | {ins, list(FUV)}.
+
+-type path(FUW) :: {path,
+        integer(),
+        integer(),
+        list(FUW),
+        list(FUW),
+        list(edit(FUW))}.
+
+-type status(FUX) :: {done, list(edit(FUX))} |
+    {next, list(path(FUX))} |
+    {cont, path(FUX)}.
+
+-spec compact_reverse(list(edit(FVH)), list(edit(FVH))) -> list(edit(FVH)).
+compact_reverse(Edits, Acc) ->
+    case {Edits, Acc} of
+        {[], Acc@1} ->
+            Acc@1;
+
+        {[{eq, Elem} | Rest], [{eq, Result} | Acc_rest]} ->
+            compact_reverse(
+                Rest,
+                [{eq, gleam@list:flatten([Elem, Result])} | Acc_rest]
+            );
+
+        {[{del, Elem@1} | Rest@1], [{del, Result@1} | Acc_rest@1]} ->
+            compact_reverse(
+                Rest@1,
+                [{del, gleam@list:flatten([Elem@1, Result@1])} | Acc_rest@1]
+            );
+
+        {[{ins, Elem@2} | Rest@2], [{ins, Result@2} | Acc_rest@2]} ->
+            compact_reverse(
+                Rest@2,
+                [{ins, gleam@list:flatten([Elem@2, Result@2])} | Acc_rest@2]
+            );
+
+        {[{eq, Elem@3} | Rest@3], Acc@2} ->
+            compact_reverse(Rest@3, [{eq, Elem@3} | Acc@2]);
+
+        {[{del, Elem@4} | Rest@4], Acc@3} ->
+            compact_reverse(Rest@4, [{del, Elem@4} | Acc@3]);
+
+        {[{ins, Elem@5} | Rest@5], Acc@4} ->
+            compact_reverse(Rest@5, [{ins, Elem@5} | Acc@4])
+    end.
+
+-spec move_right(path(FWA)) -> path(FWA).
+move_right(Path) ->
+    case Path of
+        {path, X, Y, List1, [Elem | Rest], Edits} ->
+            {path, X + 1, Y, List1, Rest, [{ins, [Elem]} | Edits]};
+
+        {path, X@1, Y@1, List1@1, [], Edits@1} ->
+            {path, X@1 + 1, Y@1, List1@1, [], Edits@1}
+    end.
+
+-spec move_down(path(FWD)) -> path(FWD).
+move_down(Path) ->
+    case Path of
+        {path, X, Y, [Elem | Rest], List2, Edits} ->
+            {path, X, Y + 1, Rest, List2, [{del, [Elem]} | Edits]};
+
+        {path, X@1, Y@1, [], List2@1, Edits@1} ->
+            {path, X@1, Y@1 + 1, [], List2@1, Edits@1}
+    end.
+
+-spec proceed_path(integer(), integer(), list(path(FVU))) -> {path(FVU),
+    list(path(FVU))}.
+proceed_path(Diag, Limit, Paths) ->
+    Neg_limit = - Limit,
+    case {Diag, Limit, Paths} of
+        {0, 0, [Path]} ->
+            {Path, []};
+
+        {Diag@1, _, [Path@1 | _] = Paths@1} when Diag@1 =:= Neg_limit ->
+            {move_down(Path@1), Paths@1};
+
+        {Diag@2, Limit@1, [Path@2 | _] = Paths@2} when Diag@2 =:= Limit@1 ->
+            {move_right(Path@2), Paths@2};
+
+        {_, _, [Path1, Path2 | Rest]} ->
+            case erlang:element(3, Path1) > erlang:element(3, Path2) of
+                true ->
+                    {move_right(Path1), [Path2 | Rest]};
+
+                false ->
+                    {move_down(Path2), [Path2 | Rest]}
+            end
+    end.
+
+-spec follow_snake(path(FWG)) -> status(FWG).
+follow_snake(Path) ->
+    case Path of
+        {path, X, Y, [Elem1 | Rest1], [Elem2 | Rest2], Edits} when Elem1 =:= Elem2 ->
+            follow_snake(
+                {path, X + 1, Y + 1, Rest1, Rest2, [{eq, [Elem1]} | Edits]}
+            );
+
+        {path, _, _, [], [], Edits@1} ->
+            {done, Edits@1};
+
+        _ ->
+            {cont, Path}
+    end.
+
+-spec each_diagonal(integer(), integer(), list(path(FVO)), list(path(FVO))) -> status(FVO).
+each_diagonal(Diag, Limit, Paths, Next_paths) ->
+    case Diag > Limit of
+        true ->
+            {next, gleam@list:reverse(Next_paths)};
+
+        false ->
+            {Path, Rest} = proceed_path(Diag, Limit, Paths),
+            case follow_snake(Path) of
+                {cont, Path@1} ->
+                    each_diagonal(Diag + 2, Limit, Rest, [Path@1 | Next_paths]);
+
+                Other ->
+                    Other
+            end
+    end.
+
+-spec find_script(integer(), integer(), list(path(FVD))) -> list(edit(FVD)).
+find_script(Envelope, Max, Paths) ->
+    case Envelope > Max of
+        true ->
+            [];
+
+        false ->
+            case each_diagonal(- Envelope, Envelope, Paths, []) of
+                {done, Edits} ->
+                    compact_reverse(Edits, []);
+
+                {next, Paths@1} ->
+                    find_script(Envelope + 1, Max, Paths@1);
+
+                _ ->
+                    erlang:error(#{gleam_error => panic,
+                            message => <<"Didn't expect a Cont here"/utf8>>,
+                            module => <<"gap/myers"/utf8>>,
+                            function => <<"find_script"/utf8>>,
+                            line => 35})
+            end
+    end.
+
+-spec difference(list(FUY), list(FUY)) -> list(edit(FUY)).
+difference(List1, List2) ->
+    Path = {path, 0, 0, List1, List2, []},
+    find_script(0, gleam@list:length(List1) + gleam@list:length(List2), [Path]).