aboutsummaryrefslogtreecommitdiff
path: root/aoc2023/build/packages/gap/src
diff options
context:
space:
mode:
Diffstat (limited to 'aoc2023/build/packages/gap/src')
-rw-r--r--aoc2023/build/packages/gap/src/gap.app.src13
-rw-r--r--aoc2023/build/packages/gap/src/gap.erl538
-rw-r--r--aoc2023/build/packages/gap/src/gap.gleam438
-rw-r--r--aoc2023/build/packages/gap/src/gap/comparison.gleam22
-rw-r--r--aoc2023/build/packages/gap/src/gap/myers.gleam122
-rw-r--r--aoc2023/build/packages/gap/src/gap/styled_comparison.gleam4
-rw-r--r--aoc2023/build/packages/gap/src/gap/styling.gleam233
-rw-r--r--aoc2023/build/packages/gap/src/gap@comparison.erl15
-rw-r--r--aoc2023/build/packages/gap/src/gap@myers.erl156
-rw-r--r--aoc2023/build/packages/gap/src/gap@styled_comparison.erl8
-rw-r--r--aoc2023/build/packages/gap/src/gap@styling.erl202
-rw-r--r--aoc2023/build/packages/gap/src/gap_ffi.mjs431
12 files changed, 2182 insertions, 0 deletions
diff --git a/aoc2023/build/packages/gap/src/gap.app.src b/aoc2023/build/packages/gap/src/gap.app.src
new file mode 100644
index 0000000..1abc7df
--- /dev/null
+++ b/aoc2023/build/packages/gap/src/gap.app.src
@@ -0,0 +1,13 @@
+{application, gap, [
+ {vsn, "1.0.1"},
+ {applications, [gleam_community_ansi,
+ gleam_stdlib,
+ gleeunit]},
+ {description, "A Gleam library for comparing strings/lists and producing a textual (styled) representation of the differences."},
+ {modules, [gap,
+ gap@comparison,
+ gap@myers,
+ gap@styled_comparison,
+ gap@styling]},
+ {registered, []}
+]}.
diff --git a/aoc2023/build/packages/gap/src/gap.erl b/aoc2023/build/packages/gap/src/gap.erl
new file mode 100644
index 0000000..827e5ce
--- /dev/null
+++ b/aoc2023/build/packages/gap/src/gap.erl
@@ -0,0 +1,538 @@
+-module(gap).
+-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function]).
+
+-export([to_styled/1, compare_strings_with_algorithm/3, compare_lists_with_algorithm/3, myers/2, compare_lists/2, compare_strings/2, lcs/2]).
+-export_type([score/1]).
+
+-type score(GAM) :: {score, integer(), gleam@option:option(GAM)}.
+
+-spec to_styled(gap@comparison:comparison(any())) -> gap@styled_comparison:styled_comparison().
+to_styled(Comparison) ->
+ _pipe = Comparison,
+ _pipe@1 = gap@styling:from_comparison(_pipe),
+ _pipe@2 = gap@styling:highlight(
+ _pipe@1,
+ fun gap@styling:first_highlight_default/1,
+ fun gap@styling:second_highlight_default/1,
+ fun gap@styling:no_highlight/1
+ ),
+ gap@styling:to_styled_comparison(_pipe@2).
+
+-spec compare_strings_with_algorithm(
+ binary(),
+ binary(),
+ fun((list(binary()), list(binary())) -> gap@comparison:comparison(binary()))
+) -> gap@comparison:comparison(binary()).
+compare_strings_with_algorithm(First, Second, Algorithm) ->
+ Comparison = Algorithm(
+ gleam@string:to_graphemes(First),
+ gleam@string:to_graphemes(Second)
+ ),
+ case Comparison of
+ {list_comparison, First@1, Second@1} ->
+ {string_comparison, First@1, Second@1};
+
+ {string_comparison, First@2, Second@2} ->
+ {string_comparison, First@2, Second@2}
+ end.
+
+-spec compare_lists_with_algorithm(
+ list(GBB),
+ list(GBB),
+ fun((list(GBB), list(GBB)) -> gap@comparison:comparison(GBB))
+) -> gap@comparison:comparison(GBB).
+compare_lists_with_algorithm(First_sequence, Second_sequence, Algorithm) ->
+ Algorithm(First_sequence, Second_sequence).
+
+-spec myers(list(GBG), list(GBG)) -> gap@comparison:comparison(GBG).
+myers(First_sequence, Second_sequence) ->
+ Edits = gap@myers:difference(First_sequence, Second_sequence),
+ _pipe = Edits,
+ _pipe@1 = gleam@list:reverse(_pipe),
+ gleam@list:fold(
+ _pipe@1,
+ {list_comparison, [], []},
+ fun(Comparison, Edit) -> case Comparison of
+ {list_comparison, First, Second} ->
+ case Edit of
+ {eq, Segment} ->
+ {list_comparison,
+ [{match, Segment} | First],
+ [{match, Segment} | Second]};
+
+ {ins, Segment@1} ->
+ {list_comparison,
+ First,
+ [{no_match, Segment@1} | Second]};
+
+ {del, Segment@2} ->
+ {list_comparison,
+ [{no_match, Segment@2} | First],
+ Second}
+ end;
+
+ {string_comparison, _, _} ->
+ Comparison
+ end end
+ ).
+
+-spec compare_lists(list(GAX), list(GAX)) -> gap@comparison:comparison(GAX).
+compare_lists(First_sequence, Second_sequence) ->
+ myers(First_sequence, Second_sequence).
+
+-spec compare_strings(binary(), binary()) -> gap@comparison:comparison(binary()).
+compare_strings(First, Second) ->
+ Comparison = compare_lists(
+ gleam@string:to_graphemes(First),
+ gleam@string:to_graphemes(Second)
+ ),
+ case Comparison of
+ {list_comparison, First@1, Second@1} ->
+ {string_comparison, First@1, Second@1};
+
+ {string_comparison, First@2, Second@2} ->
+ {string_comparison, First@2, Second@2}
+ end.
+
+-spec prepend_and_merge(
+ list(gap@comparison:match(list(GBO))),
+ gap@comparison:match(list(GBO))
+) -> list(gap@comparison:match(list(GBO))).
+prepend_and_merge(Matches, Match) ->
+ case {Matches, Match} of
+ {[], _} ->
+ [Match];
+
+ {[{match, First_match} | Rest], {match, _}} ->
+ [{match,
+ begin
+ _pipe = erlang:element(2, Match),
+ gleam@list:append(_pipe, First_match)
+ end} |
+ Rest];
+
+ {[{no_match, First_match@1} | Rest@1], {no_match, _}} ->
+ [{no_match,
+ begin
+ _pipe@1 = erlang:element(2, Match),
+ gleam@list:append(_pipe@1, First_match@1)
+ end} |
+ Rest@1];
+
+ {Matches@1, Match@1} ->
+ [Match@1 | Matches@1]
+ end.
+
+-spec append_and_merge(
+ list(gap@comparison:match(list(GBX))),
+ gap@comparison:match(list(GBX))
+) -> list(gap@comparison:match(list(GBX))).
+append_and_merge(Matches, Match) ->
+ _pipe@3 = case {begin
+ _pipe = Matches,
+ gleam@list:reverse(_pipe)
+ end,
+ Match} of
+ {[], _} ->
+ [Match];
+
+ {[{match, First_match} | Rest], {match, _}} ->
+ [{match,
+ begin
+ _pipe@1 = First_match,
+ gleam@list:append(_pipe@1, erlang:element(2, Match))
+ end} |
+ Rest];
+
+ {[{no_match, First_match@1} | Rest@1], {no_match, _}} ->
+ [{no_match,
+ begin
+ _pipe@2 = First_match@1,
+ gleam@list:append(_pipe@2, erlang:element(2, Match))
+ end} |
+ Rest@1];
+
+ {Matches@1, Match@1} ->
+ [Match@1 | Matches@1]
+ end,
+ gleam@list:reverse(_pipe@3).
+
+-spec collect_matches(
+ gleam@map:map_(GFY, any()),
+ list(GCH),
+ fun((GFY) -> integer())
+) -> list(gap@comparison:match(list(GCH))).
+collect_matches(Tracking, Str, Extract_fun) ->
+ Matching_indexes = begin
+ _pipe = gleam@map:keys(Tracking),
+ _pipe@1 = gleam@list:map(_pipe, Extract_fun),
+ gleam@set:from_list(_pipe@1)
+ end,
+ Matches = begin
+ _pipe@2 = Str,
+ gleam@list:index_map(
+ _pipe@2,
+ fun(Index, Item) ->
+ case gleam@set:contains(Matching_indexes, Index) of
+ true ->
+ {match, Item};
+
+ false ->
+ {no_match, Item}
+ end
+ end
+ )
+ end,
+ _pipe@3 = Matches,
+ _pipe@4 = gleam@list:chunk(_pipe@3, fun(Match) -> case Match of
+ {match, _} ->
+ true;
+
+ {no_match, _} ->
+ false
+ end end),
+ gleam@list:map(_pipe@4, fun(Match_list) -> case Match_list of
+ [{match, _} | _] ->
+ {match,
+ gleam@list:filter_map(
+ Match_list,
+ fun(Match@1) -> case Match@1 of
+ {match, Item@1} ->
+ {ok, Item@1};
+
+ {no_match, _} ->
+ {error, nil}
+ end end
+ )};
+
+ [{no_match, _} | _] ->
+ {no_match,
+ gleam@list:filter_map(
+ Match_list,
+ fun(Match@2) -> case Match@2 of
+ {no_match, Item@2} ->
+ {ok, Item@2};
+
+ {match, _} ->
+ {error, nil}
+ end end
+ )}
+ end end).
+
+-spec back_track(
+ gleam@map:map_({integer(), integer()}, score(GCL)),
+ integer(),
+ integer(),
+ list({{integer(), integer()}, GCL})
+) -> list({{integer(), integer()}, GCL}).
+back_track(Diff_map, First_index, Second_index, Stack) ->
+ case (First_index =:= 0) orelse (Second_index =:= 0) of
+ true ->
+ This_score = begin
+ _pipe = gleam@map:get(Diff_map, {First_index, Second_index}),
+ gleam@result:unwrap(_pipe, {score, 0, none})
+ end,
+ case This_score of
+ {score, _, {some, Item}} ->
+ [{{First_index, Second_index}, Item} | Stack];
+
+ _ ->
+ case {First_index, Second_index} of
+ {0, A} when A > 0 ->
+ back_track(
+ Diff_map,
+ First_index,
+ Second_index - 1,
+ Stack
+ );
+
+ {A@1, 0} when A@1 > 0 ->
+ back_track(
+ Diff_map,
+ First_index - 1,
+ Second_index,
+ Stack
+ );
+
+ {0, 0} ->
+ Stack;
+
+ {_, _} ->
+ back_track(
+ Diff_map,
+ First_index - 1,
+ Second_index,
+ Stack
+ )
+ end
+ end;
+
+ false ->
+ This_score@1 = begin
+ _pipe@1 = gleam@map:get(Diff_map, {First_index, Second_index}),
+ gleam@result:unwrap(_pipe@1, {score, 0, none})
+ end,
+ case This_score@1 of
+ {score, _, {some, Item@1}} ->
+ back_track(
+ Diff_map,
+ First_index - 1,
+ Second_index - 1,
+ [{{First_index, Second_index}, Item@1} | Stack]
+ );
+
+ {score, _, none} ->
+ Up = begin
+ _pipe@2 = gleam@map:get(
+ Diff_map,
+ {First_index, Second_index - 1}
+ ),
+ gleam@result:unwrap(_pipe@2, {score, 0, none})
+ end,
+ Back = begin
+ _pipe@3 = gleam@map:get(
+ Diff_map,
+ {First_index - 1, Second_index}
+ ),
+ gleam@result:unwrap(_pipe@3, {score, 0, none})
+ end,
+ case gleam@int:compare(
+ erlang:element(2, Up),
+ erlang:element(2, Back)
+ ) of
+ gt ->
+ back_track(
+ Diff_map,
+ First_index,
+ Second_index - 1,
+ Stack
+ );
+
+ lt ->
+ back_track(
+ Diff_map,
+ First_index - 1,
+ Second_index,
+ Stack
+ );
+
+ eq ->
+ case {First_index, Second_index} of
+ {0, A@2} when A@2 > 0 ->
+ back_track(
+ Diff_map,
+ First_index,
+ Second_index - 1,
+ Stack
+ );
+
+ {A@3, 0} when A@3 > 0 ->
+ back_track(
+ Diff_map,
+ First_index - 1,
+ Second_index,
+ Stack
+ );
+
+ {0, 0} ->
+ Stack;
+
+ {_, _} ->
+ back_track(
+ Diff_map,
+ First_index - 1,
+ Second_index,
+ Stack
+ )
+ end
+ end
+ end
+ end.
+
+-spec build_diff_map(
+ GCR,
+ integer(),
+ GCR,
+ integer(),
+ gleam@map:map_({integer(), integer()}, score(GCR))
+) -> gleam@map:map_({integer(), integer()}, score(GCR)).
+build_diff_map(First_item, First_index, Second_item, Second_index, Diff_map) ->
+ Prev_score = begin
+ _pipe = gleam@map:get(Diff_map, {First_index - 1, Second_index - 1}),
+ gleam@result:unwrap(_pipe, {score, 0, none})
+ end,
+ Derived_score_up = begin
+ _pipe@1 = Diff_map,
+ _pipe@2 = gleam@map:get(_pipe@1, {First_index, Second_index - 1}),
+ gleam@result:unwrap(_pipe@2, {score, 0, none})
+ end,
+ Derived_score_back = begin
+ _pipe@3 = Diff_map,
+ _pipe@4 = gleam@map:get(_pipe@3, {First_index - 1, Second_index}),
+ gleam@result:unwrap(_pipe@4, {score, 0, none})
+ end,
+ Derived_score = gleam@int:max(
+ erlang:element(2, Derived_score_up),
+ erlang:element(2, Derived_score_back)
+ ),
+ This_score = case First_item =:= Second_item of
+ true ->
+ {score, erlang:element(2, Prev_score) + 1, {some, First_item}};
+
+ false ->
+ {score, Derived_score, none}
+ end,
+ _pipe@5 = Diff_map,
+ gleam@map:insert(_pipe@5, {First_index, Second_index}, This_score).
+
+-spec lcs(list(GBK), list(GBK)) -> gap@comparison:comparison(GBK).
+lcs(First_sequence, Second_sequence) ->
+ Leading_matches = begin
+ _pipe = gleam@list:zip(First_sequence, Second_sequence),
+ _pipe@1 = gleam@list:take_while(
+ _pipe,
+ fun(Pair) -> erlang:element(1, Pair) =:= erlang:element(2, Pair) end
+ ),
+ gleam@list:map(_pipe@1, fun gleam@pair:first/1)
+ end,
+ Num_leading_matches = gleam@list:length(Leading_matches),
+ Trailing_matches = begin
+ _pipe@2 = gleam@list:zip(
+ gleam@list:reverse(First_sequence),
+ gleam@list:reverse(Second_sequence)
+ ),
+ _pipe@3 = gleam@list:take_while(
+ _pipe@2,
+ fun(Pair@1) ->
+ erlang:element(1, Pair@1) =:= erlang:element(2, Pair@1)
+ end
+ ),
+ _pipe@4 = gleam@list:map(_pipe@3, fun gleam@pair:first/1),
+ gleam@list:reverse(_pipe@4)
+ end,
+ Num_trailing_matches = gleam@list:length(Trailing_matches),
+ First_sequence_to_diff = begin
+ _pipe@5 = First_sequence,
+ _pipe@6 = gleam@list:drop(_pipe@5, Num_leading_matches),
+ gleam@list:take(
+ _pipe@6,
+ (gleam@list:length(First_sequence) - Num_leading_matches) - Num_trailing_matches
+ )
+ end,
+ Second_sequence_to_diff = begin
+ _pipe@7 = Second_sequence,
+ _pipe@8 = gleam@list:drop(_pipe@7, Num_leading_matches),
+ gleam@list:take(
+ _pipe@8,
+ (gleam@list:length(Second_sequence) - Num_leading_matches) - Num_trailing_matches
+ )
+ end,
+ Diff_map@2 = begin
+ _pipe@9 = Second_sequence_to_diff,
+ gleam@list:index_fold(
+ _pipe@9,
+ gleam@map:new(),
+ fun(Diff_map, Item_second, Index_second) ->
+ _pipe@10 = First_sequence_to_diff,
+ gleam@list:index_fold(
+ _pipe@10,
+ Diff_map,
+ fun(Diff_map@1, Item_first, Index_first) ->
+ build_diff_map(
+ Item_first,
+ Index_first,
+ Item_second,
+ Index_second,
+ Diff_map@1
+ )
+ end
+ )
+ end
+ )
+ end,
+ {First_segments@1, Second_segments@1} = case {First_sequence_to_diff,
+ Second_sequence_to_diff} of
+ {[], []} ->
+ {[], []};
+
+ {First_matching, []} ->
+ {[{no_match, First_matching}], []};
+
+ {[], Second_matching} ->
+ {[], [{no_match, Second_matching}]};
+
+ {First_sequence_to_diff@1, Second_sequence_to_diff@1} ->
+ Tracking = begin
+ _pipe@11 = back_track(
+ Diff_map@2,
+ gleam@list:length(First_sequence_to_diff@1) - 1,
+ gleam@list:length(Second_sequence_to_diff@1) - 1,
+ []
+ ),
+ gleam@map:from_list(_pipe@11)
+ end,
+ First_segments = collect_matches(
+ Tracking,
+ First_sequence_to_diff@1,
+ fun(Key) ->
+ {First, _} = Key,
+ First
+ end
+ ),
+ Second_segments = collect_matches(
+ Tracking,
+ Second_sequence_to_diff@1,
+ fun(Key@1) ->
+ {_, Second} = Key@1,
+ Second
+ end
+ ),
+ {First_segments, Second_segments}
+ end,
+ {First_segments_with_leading_trailing,
+ Second_segments_with_leading_trailing} = case {Leading_matches,
+ Trailing_matches} of
+ {[], []} ->
+ {First_segments@1, Second_segments@1};
+
+ {[], Trailing_matches@1} ->
+ {begin
+ _pipe@12 = First_segments@1,
+ append_and_merge(_pipe@12, {match, Trailing_matches@1})
+ end,
+ begin
+ _pipe@13 = Second_segments@1,
+ append_and_merge(_pipe@13, {match, Trailing_matches@1})
+ end};
+
+ {Leading_matches@1, []} ->
+ {begin
+ _pipe@14 = First_segments@1,
+ prepend_and_merge(_pipe@14, {match, Leading_matches@1})
+ end,
+ begin
+ _pipe@15 = Second_segments@1,
+ prepend_and_merge(_pipe@15, {match, Leading_matches@1})
+ end};
+
+ {Leading_matches@2, Trailing_matches@2} ->
+ {begin
+ _pipe@16 = First_segments@1,
+ _pipe@17 = prepend_and_merge(
+ _pipe@16,
+ {match, Leading_matches@2}
+ ),
+ append_and_merge(_pipe@17, {match, Trailing_matches@2})
+ end,
+ begin
+ _pipe@18 = Second_segments@1,
+ _pipe@19 = prepend_and_merge(
+ _pipe@18,
+ {match, Leading_matches@2}
+ ),
+ append_and_merge(_pipe@19, {match, Trailing_matches@2})
+ end}
+ end,
+ {list_comparison,
+ First_segments_with_leading_trailing,
+ Second_segments_with_leading_trailing}.
diff --git a/aoc2023/build/packages/gap/src/gap.gleam b/aoc2023/build/packages/gap/src/gap.gleam
new file mode 100644
index 0000000..7eb0e7f
--- /dev/null
+++ b/aoc2023/build/packages/gap/src/gap.gleam
@@ -0,0 +1,438 @@
+import gleam/string
+import gleam/list
+import gleam/pair
+import gleam/map.{type Map}
+import gleam/result
+import gleam/option.{type Option, None, Some}
+import gleam/int
+import gleam/order.{Eq, Gt, Lt}
+import gleam/set
+import gap/comparison.{
+ type Comparison, type Match, type Segments, ListComparison, Match, NoMatch,
+ StringComparison,
+}
+import gap/styled_comparison.{type StyledComparison}
+import gap/styling.{
+ first_highlight_default, from_comparison, highlight, no_highlight,
+ second_highlight_default, to_styled_comparison,
+}
+import gap/myers.{type Edit, Del, Eq as MyerEq, Ins}
+
+type MatchedItem(a) =
+ #(#(Int, Int), a)
+
+type Score(a) {
+ Score(value: Int, item: Option(a))
+}
+
+type DiffMap(a) =
+ Map(#(Int, Int), Score(a))
+
+/// Creates a `StyledComparison` from `Comparison` using default values for
+/// highting and serialization.
+///
+/// ## Example
+///
+/// ```gleam
+/// > compare_strings("abc", "abe") |> to_styled()
+/// ```
+/// This will return a `StyledComparison(first, second)` where "c" in `first` is green
+/// and "e" in `second` is red.
+pub fn to_styled(comparison: Comparison(a)) -> StyledComparison {
+ comparison
+ |> from_comparison()
+ |> highlight(first_highlight_default, second_highlight_default, no_highlight)
+ |> to_styled_comparison()
+}
+
+/// Compare two string and return a `StringComparison` which will be styled as string
+/// when passed to `to_styled`
+///
+/// Will use the default `myers` algorithm
+pub fn compare_strings(first: String, second: String) -> Comparison(String) {
+ let comparison =
+ compare_lists(string.to_graphemes(first), string.to_graphemes(second))
+ case comparison {
+ ListComparison(first, second) -> StringComparison(first, second)
+ StringComparison(first, second) -> StringComparison(first, second)
+ }
+}
+
+/// Compare two string and return a `StringComparison` which will be styled as string
+/// when passed to `to_styled`
+///
+/// Algorithm can be used to select either `myers` or the legacy `lcs` algorithm
+pub fn compare_strings_with_algorithm(
+ first: String,
+ second: String,
+ algorithm,
+) -> Comparison(String) {
+ let comparison =
+ algorithm(string.to_graphemes(first), string.to_graphemes(second))
+ case comparison {
+ ListComparison(first, second) -> StringComparison(first, second)
+ StringComparison(first, second) -> StringComparison(first, second)
+ }
+}
+
+/// Compare two lists and return a `ListComparison` which will be styled as list
+/// when passed to `to_styled`
+///
+/// Will use the default `myers` algorithm
+pub fn compare_lists(
+ first_sequence: List(a),
+ second_sequence: List(a),
+) -> Comparison(a) {
+ myers(first_sequence, second_sequence)
+}
+
+/// Compare two lists and return a `ListComparison` which will be styled as list
+/// when passed to `to_styled`
+///
+/// Algorithm can be used to select either `myers` or the legacy `lcs` algorithm
+pub fn compare_lists_with_algorithm(
+ first_sequence: List(a),
+ second_sequence: List(a),
+ algorithm,
+) -> Comparison(a) {
+ algorithm(first_sequence, second_sequence)
+}
+
+/// An adapter for the the `myers` algorithm.
+/// Intended to be use as an argument to `compare_strings_with_algorithm` or
+/// `compare_lists_with_algorithm`
+pub fn myers(first_sequence: List(a), second_sequence: List(a)) -> Comparison(a) {
+ let edits = myers.difference(first_sequence, second_sequence)
+ edits
+ |> list.reverse()
+ |> list.fold(
+ ListComparison([], []),
+ fn(comparison: Comparison(a), edit: Edit(a)) {
+ case comparison {
+ ListComparison(first, second) -> {
+ case edit {
+ MyerEq(segment) ->
+ ListComparison(
+ [Match(segment), ..first],
+ [Match(segment), ..second],
+ )
+ Ins(segment) -> ListComparison(first, [NoMatch(segment), ..second])
+ Del(segment) -> ListComparison([NoMatch(segment), ..first], second)
+ }
+ }
+ StringComparison(..) -> comparison
+ }
+ },
+ )
+}
+
+/// An adapter for the the `lcs` (longest common subsequence) algorithm.
+/// Intended to be use as an argument to `compare_strings_with_algorithm` or
+/// `compare_lists_with_algorithm`
+pub fn lcs(first_sequence: List(a), second_sequence: List(a)) -> Comparison(a) {
+ let leading_matches =
+ list.zip(first_sequence, second_sequence)
+ |> list.take_while(fn(pair) { pair.0 == pair.1 })
+ |> list.map(pair.first)
+ let num_leading_matches = list.length(leading_matches)
+ let trailing_matches =
+ list.zip(list.reverse(first_sequence), list.reverse(second_sequence))
+ |> list.take_while(fn(pair) { pair.0 == pair.1 })
+ |> list.map(pair.first)
+ |> list.reverse()
+ let num_trailing_matches = list.length(trailing_matches)
+ let first_sequence_to_diff =
+ first_sequence
+ |> list.drop(num_leading_matches)
+ |> list.take(
+ list.length(first_sequence) - num_leading_matches - num_trailing_matches,
+ )
+ let second_sequence_to_diff =
+ second_sequence
+ |> list.drop(num_leading_matches)
+ |> list.take(
+ list.length(second_sequence) - num_leading_matches - num_trailing_matches,
+ )
+
+ let diff_map =
+ second_sequence_to_diff
+ |> list.index_fold(
+ map.new(),
+ fn(diff_map, item_second, index_second) {
+ first_sequence_to_diff
+ |> list.index_fold(
+ diff_map,
+ fn(diff_map, item_first, index_first) {
+ build_diff_map(
+ item_first,
+ index_first,
+ item_second,
+ index_second,
+ diff_map,
+ )
+ },
+ )
+ },
+ )
+ let #(first_segments, second_segments) = case
+ first_sequence_to_diff,
+ second_sequence_to_diff
+ {
+ [], [] -> #([], [])
+ first_matching, [] -> #([NoMatch(first_matching)], [])
+ [], second_matching -> #([], [NoMatch(second_matching)])
+ first_sequence_to_diff, second_sequence_to_diff -> {
+ let tracking =
+ back_track(
+ diff_map,
+ list.length(first_sequence_to_diff) - 1,
+ list.length(second_sequence_to_diff) - 1,
+ [],
+ )
+ |> map.from_list()
+
+ let first_segments =
+ collect_matches(
+ tracking,
+ first_sequence_to_diff,
+ fn(key) {
+ let #(first, _) = key
+ first
+ },
+ )
+ let second_segments =
+ collect_matches(
+ tracking,
+ second_sequence_to_diff,
+ fn(key) {
+ let #(_, second) = key
+ second
+ },
+ )
+ #(first_segments, second_segments)
+ }
+ }
+
+ let #(
+ first_segments_with_leading_trailing,
+ second_segments_with_leading_trailing,
+ ) = case leading_matches, trailing_matches {
+ [], [] -> #(first_segments, second_segments)
+ [], trailing_matches -> #(
+ first_segments
+ |> append_and_merge(Match(trailing_matches)),
+ second_segments
+ |> append_and_merge(Match(trailing_matches)),
+ )
+ leading_matches, [] -> #(
+ first_segments
+ |> prepend_and_merge(Match(leading_matches)),
+ second_segments
+ |> prepend_and_merge(Match(leading_matches)),
+ )
+ leading_matches, trailing_matches -> #(
+ first_segments
+ |> prepend_and_merge(Match(leading_matches))
+ |> append_and_merge(Match(trailing_matches)),
+ second_segments
+ |> prepend_and_merge(Match(leading_matches))
+ |> append_and_merge(Match(trailing_matches)),
+ )
+ }
+
+ ListComparison(
+ first_segments_with_leading_trailing,
+ second_segments_with_leading_trailing,
+ )
+}
+
+fn prepend_and_merge(
+ matches: List(Match(List(a))),
+ match: Match(List(a)),
+) -> List(Match(List(a))) {
+ case matches, match {
+ [], _ -> [match]
+ [Match(first_match), ..rest], Match(_) -> [
+ Match(
+ match.item
+ |> list.append(first_match),
+ ),
+ ..rest
+ ]
+ [NoMatch(first_match), ..rest], NoMatch(_) -> [
+ NoMatch(
+ match.item
+ |> list.append(first_match),
+ ),
+ ..rest
+ ]
+ matches, match -> [match, ..matches]
+ }
+}
+
+fn append_and_merge(
+ matches: List(Match(List(a))),
+ match: Match(List(a)),
+) -> List(Match(List(a))) {
+ case
+ matches
+ |> list.reverse(),
+ match
+ {
+ [], _ -> [match]
+ [Match(first_match), ..rest], Match(_) -> [
+ Match(
+ first_match
+ |> list.append(match.item),
+ ),
+ ..rest
+ ]
+ [NoMatch(first_match), ..rest], NoMatch(_) -> [
+ NoMatch(
+ first_match
+ |> list.append(match.item),
+ ),
+ ..rest
+ ]
+ matches, match -> [match, ..matches]
+ }
+ |> list.reverse()
+}
+
+fn collect_matches(tracking, str: List(a), extract_fun) -> Segments(a) {
+ let matching_indexes =
+ map.keys(tracking)
+ |> list.map(extract_fun)
+ |> set.from_list()
+
+ let matches =
+ str
+ |> list.index_map(fn(index, item) {
+ case set.contains(matching_indexes, index) {
+ True -> Match(item)
+ False -> NoMatch(item)
+ }
+ })
+
+ matches
+ |> list.chunk(fn(match) {
+ case match {
+ Match(_) -> True
+ NoMatch(_) -> False
+ }
+ })
+ |> list.map(fn(match_list) {
+ case match_list {
+ [Match(_), ..] ->
+ Match(list.filter_map(
+ match_list,
+ fn(match) {
+ case match {
+ Match(item) -> Ok(item)
+ NoMatch(_) -> Error(Nil)
+ }
+ },
+ ))
+ [NoMatch(_), ..] ->
+ NoMatch(list.filter_map(
+ match_list,
+ fn(match) {
+ case match {
+ NoMatch(item) -> Ok(item)
+ Match(_) -> Error(Nil)
+ }
+ },
+ ))
+ }
+ })
+}
+
+fn back_track(
+ diff_map: DiffMap(a),
+ first_index: Int,
+ second_index: Int,
+ stack: List(MatchedItem(a)),
+) -> List(MatchedItem(a)) {
+ case first_index == 0 || second_index == 0 {
+ True -> {
+ let this_score =
+ map.get(diff_map, #(first_index, second_index))
+ |> result.unwrap(Score(0, None))
+ case this_score {
+ Score(_, Some(item)) -> [#(#(first_index, second_index), item), ..stack]
+ _ ->
+ case first_index, second_index {
+ 0, a if a > 0 ->
+ back_track(diff_map, first_index, second_index - 1, stack)
+ a, 0 if a > 0 ->
+ back_track(diff_map, first_index - 1, second_index, stack)
+ 0, 0 -> stack
+ _, _ -> back_track(diff_map, first_index - 1, second_index, stack)
+ }
+ }
+ }
+ False -> {
+ let this_score =
+ map.get(diff_map, #(first_index, second_index))
+ |> result.unwrap(Score(0, None))
+ case this_score {
+ Score(_, Some(item)) ->
+ back_track(
+ diff_map,
+ first_index - 1,
+ second_index - 1,
+ [#(#(first_index, second_index), item), ..stack],
+ )
+ Score(_, None) -> {
+ let up =
+ map.get(diff_map, #(first_index, second_index - 1))
+ |> result.unwrap(Score(0, None))
+ let back =
+ map.get(diff_map, #(first_index - 1, second_index))
+ |> result.unwrap(Score(0, None))
+ case int.compare(up.value, back.value) {
+ Gt -> back_track(diff_map, first_index, second_index - 1, stack)
+ Lt -> back_track(diff_map, first_index - 1, second_index, stack)
+ Eq ->
+ case first_index, second_index {
+ 0, a if a > 0 ->
+ back_track(diff_map, first_index, second_index - 1, stack)
+ a, 0 if a > 0 ->
+ back_track(diff_map, first_index - 1, second_index, stack)
+ 0, 0 -> stack
+ _, _ ->
+ back_track(diff_map, first_index - 1, second_index, stack)
+ }
+ }
+ }
+ }
+ }
+ }
+}
+
+fn build_diff_map(
+ first_item: a,
+ first_index: Int,
+ second_item: a,
+ second_index: Int,
+ diff_map: DiffMap(a),
+) -> DiffMap(a) {
+ let prev_score =
+ map.get(diff_map, #(first_index - 1, second_index - 1))
+ |> result.unwrap(Score(0, None))
+ let derived_score_up =
+ diff_map
+ |> map.get(#(first_index, second_index - 1))
+ |> result.unwrap(Score(0, None))
+ let derived_score_back =
+ diff_map
+ |> map.get(#(first_index - 1, second_index))
+ |> result.unwrap(Score(0, None))
+ let derived_score = int.max(derived_score_up.value, derived_score_back.value)
+ let this_score = case first_item == second_item {
+ True -> Score(prev_score.value + 1, Some(first_item))
+ False -> Score(derived_score, None)
+ }
+ diff_map
+ |> map.insert(#(first_index, second_index), this_score)
+}
diff --git a/aoc2023/build/packages/gap/src/gap/comparison.gleam b/aoc2023/build/packages/gap/src/gap/comparison.gleam
new file mode 100644
index 0000000..da30c29
--- /dev/null
+++ b/aoc2023/build/packages/gap/src/gap/comparison.gleam
@@ -0,0 +1,22 @@
+/// Comparison of two strings or lists
+///
+/// The comparison consists of two lists of matched segments. The segments represent
+/// a sequence of succeeding matches or non-matches (up until the next match/non-match)
+///
+/// For lists the elements in the segment will be same as the elements in the list, and
+/// for strings the elements will be the graphemes of the string
+pub type Comparison(a) {
+ ListComparison(first: Segments(a), second: Segments(a))
+ StringComparison(first: Segments(String), second: Segments(String))
+}
+
+/// Indicating that the item has a matching (`Match`) or no matching (`NoMatch`) item in the
+/// other string/list
+pub type Match(a) {
+ Match(item: a)
+ NoMatch(item: a)
+}
+
+/// List of segments of succeeding matches / non-matches
+pub type Segments(a) =
+ List(Match(List(a)))
diff --git a/aoc2023/build/packages/gap/src/gap/myers.gleam b/aoc2023/build/packages/gap/src/gap/myers.gleam
new file mode 100644
index 0000000..f0b8ddc
--- /dev/null
+++ b/aoc2023/build/packages/gap/src/gap/myers.gleam
@@ -0,0 +1,122 @@
+import gleam/list
+
+pub type Edit(a) {
+ Eq(List(a))
+ Del(List(a))
+ Ins(List(a))
+}
+
+type Path(a) {
+ Path(x: Int, y: Int, list1: List(a), list2: List(a), edits: List(Edit(a)))
+}
+
+type Status(a) {
+ Done(edits: List(Edit(a)))
+ Next(paths: List(Path(a)))
+ Cont(path: Path(a))
+}
+
+/// The algorithm is outlined in the
+/// "An O(ND) Difference Algorithm and Its Variations" paper by E. Myers.
+///
+/// Adapted from the implementation of "myers_difference" in Elixirs List module
+pub fn difference(list1: List(a), list2: List(a)) -> List(Edit(a)) {
+ let path = Path(0, 0, list1, list2, [])
+ find_script(0, list.length(list1) + list.length(list2), [path])
+}
+
+fn find_script(envelope: Int, max: Int, paths: List(Path(a))) {
+ case envelope > max {
+ True -> []
+ False -> {
+ case each_diagonal(-envelope, envelope, paths, []) {
+ Done(edits) -> compact_reverse(edits, [])
+ Next(paths) -> find_script(envelope + 1, max, paths)
+ _ -> panic as "Didn't expect a Cont here"
+ }
+ }
+ }
+}
+
+fn compact_reverse(edits: List(Edit(a)), acc: List(Edit(a))) -> List(Edit(a)) {
+ case edits, acc {
+ [], acc -> acc
+ [Eq(elem), ..rest], [Eq(result), ..acc_rest] ->
+ compact_reverse(rest, [Eq(list.flatten([elem, result])), ..acc_rest])
+ [Del(elem), ..rest], [Del(result), ..acc_rest] ->
+ compact_reverse(rest, [Del(list.flatten([elem, result])), ..acc_rest])
+ [Ins(elem), ..rest], [Ins(result), ..acc_rest] ->
+ compact_reverse(rest, [Ins(list.flatten([elem, result])), ..acc_rest])
+ [Eq(elem), ..rest], acc -> compact_reverse(rest, [Eq(elem), ..acc])
+ [Del(elem), ..rest], acc -> compact_reverse(rest, [Del(elem), ..acc])
+ [Ins(elem), ..rest], acc -> compact_reverse(rest, [Ins(elem), ..acc])
+ }
+}
+
+fn each_diagonal(
+ diag: Int,
+ limit: Int,
+ paths: List(Path(a)),
+ next_paths: List(Path(a)),
+) -> Status(a) {
+ case diag > limit {
+ True -> Next(list.reverse(next_paths))
+ False -> {
+ let #(path, rest) = proceed_path(diag, limit, paths)
+ case follow_snake(path) {
+ Cont(path) -> each_diagonal(diag + 2, limit, rest, [path, ..next_paths])
+ other -> other
+ }
+ }
+ }
+}
+
+fn proceed_path(
+ diag: Int,
+ limit: Int,
+ paths: List(Path(a)),
+) -> #(Path(a), List(Path(a))) {
+ let neg_limit = -limit
+ case diag, limit, paths {
+ 0, 0, [path] -> #(path, [])
+ diag, _limit, [path, ..] as paths if diag == neg_limit -> #(
+ move_down(path),
+ paths,
+ )
+ diag, limit, [path, ..] as paths if diag == limit -> #(
+ move_right(path),
+ paths,
+ )
+ _diag, _limit, [path1, path2, ..rest] -> {
+ case path1.y > path2.y {
+ True -> #(move_right(path1), [path2, ..rest])
+ False -> #(move_down(path2), [path2, ..rest])
+ }
+ }
+ }
+}
+
+fn move_right(path: Path(a)) -> Path(a) {
+ case path {
+ Path(x, y, list1, [elem, ..rest], edits) ->
+ Path(x + 1, y, list1, rest, [Ins([elem]), ..edits])
+ Path(x, y, list1, [], edits) -> Path(x + 1, y, list1, [], edits)
+ }
+}
+
+fn move_down(path: Path(a)) -> Path(a) {
+ case path {
+ Path(x, y, [elem, ..rest], list2, edits) ->
+ Path(x, y + 1, rest, list2, [Del([elem]), ..edits])
+ Path(x, y, [], list2, edits) -> Path(x, y + 1, [], list2, edits)
+ }
+}
+
+fn follow_snake(path: Path(a)) -> Status(a) {
+ case path {
+ Path(x, y, [elem1, ..rest1], [elem2, ..rest2], edits) if elem1 == elem2 ->
+ follow_snake(Path(x + 1, y + 1, rest1, rest2, [Eq([elem1]), ..edits]))
+ Path(_x, _y, [], [], edits) -> Done(edits)
+ _ -> Cont(path)
+ }
+}
diff --git a/aoc2023/build/packages/gap/src/gap/styled_comparison.gleam b/aoc2023/build/packages/gap/src/gap/styled_comparison.gleam
new file mode 100644
index 0000000..7103c2e
--- /dev/null
+++ b/aoc2023/build/packages/gap/src/gap/styled_comparison.gleam
@@ -0,0 +1,4 @@
+/// A comparison where the parts have been styled (serialized and highlighted)
+pub type StyledComparison {
+ StyledComparison(first: String, second: String)
+}
diff --git a/aoc2023/build/packages/gap/src/gap/styling.gleam b/aoc2023/build/packages/gap/src/gap/styling.gleam
new file mode 100644
index 0000000..623ae8a
--- /dev/null
+++ b/aoc2023/build/packages/gap/src/gap/styling.gleam
@@ -0,0 +1,233 @@
+import gleam/option.{type Option, None, Some}
+import gleam/list
+import gleam/string
+import gleam_community/ansi
+import gap/comparison.{
+ type Comparison, type Segments, ListComparison, Match, NoMatch,
+ StringComparison,
+}
+import gap/styled_comparison.{type StyledComparison, StyledComparison}
+
+/// The `Highlighter`takes a string representation of the item that was not matching
+/// and should return a string representation that can be used to visually indicate that
+/// it is a non-matching item.
+///
+/// The default implementation of the highlighters uses the
+/// [gleam_community/ansi](https://hexdocs.pm/gleam_community_ansi/index.html) library
+/// to set a different color for the item, but any type if indication can be used as long
+/// as it returns a valid string
+pub type Highlighter =
+ fn(String) -> String
+
+/// `Part` is used to indicate to a custom serializer if it should produce a serialization
+/// based on a segment with items or the final string that contains already serialized segments
+pub type Part(a) {
+ /// `acc` the already serialized part of the result, `part` is the current segment that should be serialized and appended and `highlighter` is the `Highlighter` that can be used to indicate non-matching items
+ Part(acc: String, part: List(a), highlight: Highlighter)
+ /// `all` is a string representing all serialized segments. This can be useful if some string should be prepended/appended to the final result
+ All(all: String)
+}
+
+/// A `Serializer`can be used to create string representation of the comparison results
+///
+/// See [serialize](#serialize) for adding custom serializers and [mk_generic_serializer](#mk_generic_serializer)
+pub type Serializer(a) =
+ fn(Part(a)) -> String
+
+/// Highlighters to use for indicating matches / non-matches
+///
+/// `first` is used to highlight non-matches in the first string/list
+/// `second` is used to highlight non-matches in the second string/list
+/// `matching` is used to highlight matches in the both strings/lists
+pub type Highlighters {
+ Highlighters(first: Highlighter, second: Highlighter, matching: Highlighter)
+}
+
+/// Styling of a `Comparison`
+///
+/// See [from_comparison](#from_comparison)
+pub opaque type Styling(a) {
+ Styling(
+ comparison: Comparison(a),
+ serializer: Option(Serializer(a)),
+ highlight: Option(Highlighters),
+ )
+}
+
+/// Create a new `Styling` from a `Comparison`
+///
+/// The `Styling` can be customized by adding highlighters and a serializer
+/// See [highlight](#highlight) and [serialize](#serialize)
+pub fn from_comparison(comparison: Comparison(a)) -> Styling(a) {
+ Styling(comparison, None, None)
+}
+
+/// Add highlighters to the `Styling`
+///
+/// The highlighters are used to mark the matching/non-matching items in the
+/// first/second list/string
+pub fn highlight(
+ styling: Styling(a),
+ first: Highlighter,
+ second: Highlighter,
+ matching: Highlighter,
+) -> Styling(a) {
+ Styling(..styling, highlight: Some(Highlighters(first, second, matching)))
+}
+
+/// Add a serializer to the `Styling`
+///
+/// The serializer is used to create string representation of the items in the segments of the `Comparison`
+/// See [Part](#part) for details
+///
+/// > **NOTE:** `StringComparison` will always use the default string serializer (concatenating the graphemes).
+/// > If there is a need for custom serialization of `StringComparison` convert the string to a list of
+/// > graphemes and treat it as a `ListComparison`
+pub fn serialize(styling: Styling(a), serializer: Serializer(a)) -> Styling(a) {
+ Styling(..styling, serializer: Some(serializer))
+}
+
+/// Creates a styled comparison using either custom highlighters/serializer if they where added or default
+/// highlighters and/or serializer
+pub fn to_styled_comparison(styling: Styling(a)) -> StyledComparison {
+ let highlight =
+ styling.highlight
+ |> option.unwrap(Highlighters(
+ first_highlight_default,
+ second_highlight_default,
+ no_highlight,
+ ))
+ case styling.comparison {
+ StringComparison(first, second) ->
+ to_strings(
+ first,
+ second,
+ // NOTE: Using string serializer here because otherwise we need to have a specific string serializer on the styling
+ string_serializer,
+ highlight.first,
+ highlight.second,
+ highlight.matching,
+ )
+ ListComparison(first, second) ->
+ to_strings(
+ first,
+ second,
+ option.unwrap(styling.serializer, generic_serializer),
+ highlight.first,
+ highlight.second,
+ highlight.matching,
+ )
+ }
+}
+
+/// Default highlighter for the first string/list in the comparison
+pub fn first_highlight_default(string: String) -> String {
+ case string {
+ " " ->
+ string
+ |> ansi.underline()
+ |> ansi.bold()
+ |> ansi.green()
+
+ _ ->
+ string
+ |> ansi.green()
+ |> ansi.bold()
+ }
+}
+
+/// Default highlighter for the second string/list in the comparison
+pub fn second_highlight_default(string: String) -> String {
+ case string {
+ " " ->
+ string
+ |> ansi.underline()
+ |> ansi.bold()
+ |> ansi.red()
+
+ _ ->
+ string
+ |> ansi.red()
+ |> ansi.bold()
+ }
+}
+
+/// Default highlighter used for matching items
+pub fn no_highlight(string: String) -> String {
+ string
+}
+
+fn string_serializer(part: Part(String)) -> String {
+ case part {
+ Part(acc, sequence, highlight) ->
+ acc <> {
+ sequence
+ |> list.map(highlight)
+ |> string.join("")
+ }
+ All(string) -> string
+ }
+}
+
+fn generic_serializer(part: Part(a)) -> String {
+ mk_generic_serializer(", ", fn(all) { "[" <> all <> "]" })(part)
+}
+
+/// Creates a generic serializer that uses `separator` between all items and calls
+/// `around` for possibility to prepend/append strings to the final result
+pub fn mk_generic_serializer(separator: String, around: fn(String) -> String) {
+ fn(part) {
+ case part {
+ Part(acc, sequence, highlight) -> {
+ let segment_separator = case acc {
+ "" -> ""
+ _ -> separator
+ }
+ acc <> segment_separator <> {
+ sequence
+ |> list.map(string.inspect)
+ |> list.map(highlight)
+ |> string.join(separator)
+ }
+ }
+ All(string) -> around(string)
+ }
+ }
+}
+
+fn to_strings(
+ first: Segments(a),
+ second: Segments(a),
+ serializer: Serializer(a),
+ first_highlight: Highlighter,
+ second_highlight: Highlighter,
+ no_highlight: Highlighter,
+) -> StyledComparison {
+ let first_styled =
+ first
+ |> list.fold(
+ "",
+ fn(str, match) {
+ case match {
+ Match(item) -> serializer(Part(str, item, no_highlight))
+ NoMatch(item) -> serializer(Part(str, item, first_highlight))
+ }
+ },
+ )
+ let second_styled =
+ second
+ |> list.fold(
+ "",
+ fn(str, match) {
+ case match {
+ Match(item) -> serializer(Part(str, item, no_highlight))
+ NoMatch(item) -> serializer(Part(str, item, second_highlight))
+ }
+ },
+ )
+
+ StyledComparison(
+ serializer(All(first_styled)),
+ serializer(All(second_styled)),
+ )
+}
diff --git a/aoc2023/build/packages/gap/src/gap@comparison.erl b/aoc2023/build/packages/gap/src/gap@comparison.erl
new file mode 100644
index 0000000..36bd1c3
--- /dev/null
+++ b/aoc2023/build/packages/gap/src/gap@comparison.erl
@@ -0,0 +1,15 @@
+-module(gap@comparison).
+-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function]).
+
+-export_type([comparison/1, match/1]).
+
+-type comparison(FQT) :: {list_comparison,
+ list(match(list(FQT))),
+ list(match(list(FQT)))} |
+ {string_comparison,
+ list(match(list(binary()))),
+ list(match(list(binary())))}.
+
+-type match(FQU) :: {match, FQU} | {no_match, FQU}.
+
+
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]).
diff --git a/aoc2023/build/packages/gap/src/gap@styled_comparison.erl b/aoc2023/build/packages/gap/src/gap@styled_comparison.erl
new file mode 100644
index 0000000..14cc390
--- /dev/null
+++ b/aoc2023/build/packages/gap/src/gap@styled_comparison.erl
@@ -0,0 +1,8 @@
+-module(gap@styled_comparison).
+-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function]).
+
+-export_type([styled_comparison/0]).
+
+-type styled_comparison() :: {styled_comparison, binary(), binary()}.
+
+
diff --git a/aoc2023/build/packages/gap/src/gap@styling.erl b/aoc2023/build/packages/gap/src/gap@styling.erl
new file mode 100644
index 0000000..ba226c3
--- /dev/null
+++ b/aoc2023/build/packages/gap/src/gap@styling.erl
@@ -0,0 +1,202 @@
+-module(gap@styling).
+-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function]).
+
+-export([from_comparison/1, highlight/4, serialize/2, first_highlight_default/1, second_highlight_default/1, no_highlight/1, mk_generic_serializer/2, to_styled_comparison/1]).
+-export_type([part/1, highlighters/0, styling/1]).
+
+-type part(FRE) :: {part, binary(), list(FRE), fun((binary()) -> binary())} |
+ {all, binary()}.
+
+-type highlighters() :: {highlighters,
+ fun((binary()) -> binary()),
+ fun((binary()) -> binary()),
+ fun((binary()) -> binary())}.
+
+-opaque styling(FRF) :: {styling,
+ gap@comparison:comparison(FRF),
+ gleam@option:option(fun((part(FRF)) -> binary())),
+ gleam@option:option(highlighters())}.
+
+-spec from_comparison(gap@comparison:comparison(FRI)) -> styling(FRI).
+from_comparison(Comparison) ->
+ {styling, Comparison, none, none}.
+
+-spec highlight(
+ styling(FRL),
+ fun((binary()) -> binary()),
+ fun((binary()) -> binary()),
+ fun((binary()) -> binary())
+) -> styling(FRL).
+highlight(Styling, First, Second, Matching) ->
+ erlang:setelement(
+ 4,
+ Styling,
+ {some, {highlighters, First, Second, Matching}}
+ ).
+
+-spec serialize(styling(FRO), fun((part(FRO)) -> binary())) -> styling(FRO).
+serialize(Styling, Serializer) ->
+ erlang:setelement(3, Styling, {some, Serializer}).
+
+-spec first_highlight_default(binary()) -> binary().
+first_highlight_default(String) ->
+ case String of
+ <<" "/utf8>> ->
+ _pipe = String,
+ _pipe@1 = gleam_community@ansi:underline(_pipe),
+ _pipe@2 = gleam_community@ansi:bold(_pipe@1),
+ gleam_community@ansi:green(_pipe@2);
+
+ _ ->
+ _pipe@3 = String,
+ _pipe@4 = gleam_community@ansi:green(_pipe@3),
+ gleam_community@ansi:bold(_pipe@4)
+ end.
+
+-spec second_highlight_default(binary()) -> binary().
+second_highlight_default(String) ->
+ case String of
+ <<" "/utf8>> ->
+ _pipe = String,
+ _pipe@1 = gleam_community@ansi:underline(_pipe),
+ _pipe@2 = gleam_community@ansi:bold(_pipe@1),
+ gleam_community@ansi:red(_pipe@2);
+
+ _ ->
+ _pipe@3 = String,
+ _pipe@4 = gleam_community@ansi:red(_pipe@3),
+ gleam_community@ansi:bold(_pipe@4)
+ end.
+
+-spec no_highlight(binary()) -> binary().
+no_highlight(String) ->
+ String.
+
+-spec string_serializer(part(binary())) -> binary().
+string_serializer(Part) ->
+ case Part of
+ {part, Acc, Sequence, Highlight} ->
+ <<Acc/binary,
+ (begin
+ _pipe = Sequence,
+ _pipe@1 = gleam@list:map(_pipe, Highlight),
+ gleam@string:join(_pipe@1, <<""/utf8>>)
+ end)/binary>>;
+
+ {all, String} ->
+ String
+ end.
+
+-spec mk_generic_serializer(binary(), fun((binary()) -> binary())) -> fun((part(any())) -> binary()).
+mk_generic_serializer(Separator, Around) ->
+ fun(Part) -> case Part of
+ {part, Acc, Sequence, Highlight} ->
+ Segment_separator = case Acc of
+ <<""/utf8>> ->
+ <<""/utf8>>;
+
+ _ ->
+ Separator
+ end,
+ <<<<Acc/binary, Segment_separator/binary>>/binary,
+ (begin
+ _pipe = Sequence,
+ _pipe@1 = gleam@list:map(
+ _pipe,
+ fun gleam@string:inspect/1
+ ),
+ _pipe@2 = gleam@list:map(_pipe@1, Highlight),
+ gleam@string:join(_pipe@2, Separator)
+ end)/binary>>;
+
+ {all, String} ->
+ Around(String)
+ end end.
+
+-spec generic_serializer(part(any())) -> binary().
+generic_serializer(Part) ->
+ (mk_generic_serializer(
+ <<", "/utf8>>,
+ fun(All) -> <<<<"["/utf8, All/binary>>/binary, "]"/utf8>> end
+ ))(Part).
+
+-spec to_strings(
+ list(gap@comparison:match(list(FRY))),
+ list(gap@comparison:match(list(FRY))),
+ fun((part(FRY)) -> binary()),
+ fun((binary()) -> binary()),
+ fun((binary()) -> binary()),
+ fun((binary()) -> binary())
+) -> gap@styled_comparison:styled_comparison().
+to_strings(
+ First,
+ Second,
+ Serializer,
+ First_highlight,
+ Second_highlight,
+ No_highlight
+) ->
+ First_styled = begin
+ _pipe = First,
+ gleam@list:fold(_pipe, <<""/utf8>>, fun(Str, Match) -> case Match of
+ {match, Item} ->
+ Serializer({part, Str, Item, No_highlight});
+
+ {no_match, Item@1} ->
+ Serializer({part, Str, Item@1, First_highlight})
+ end end)
+ end,
+ Second_styled = begin
+ _pipe@1 = Second,
+ gleam@list:fold(
+ _pipe@1,
+ <<""/utf8>>,
+ fun(Str@1, Match@1) -> case Match@1 of
+ {match, Item@2} ->
+ Serializer({part, Str@1, Item@2, No_highlight});
+
+ {no_match, Item@3} ->
+ Serializer({part, Str@1, Item@3, Second_highlight})
+ end end
+ )
+ end,
+ {styled_comparison,
+ Serializer({all, First_styled}),
+ Serializer({all, Second_styled})}.
+
+-spec to_styled_comparison(styling(any())) -> gap@styled_comparison:styled_comparison().
+to_styled_comparison(Styling) ->
+ Highlight = begin
+ _pipe = erlang:element(4, Styling),
+ gleam@option:unwrap(
+ _pipe,
+ {highlighters,
+ fun first_highlight_default/1,
+ fun second_highlight_default/1,
+ fun no_highlight/1}
+ )
+ end,
+ case erlang:element(2, Styling) of
+ {string_comparison, First, Second} ->
+ to_strings(
+ First,
+ Second,
+ fun string_serializer/1,
+ erlang:element(2, Highlight),
+ erlang:element(3, Highlight),
+ erlang:element(4, Highlight)
+ );
+
+ {list_comparison, First@1, Second@1} ->
+ to_strings(
+ First@1,
+ Second@1,
+ gleam@option:unwrap(
+ erlang:element(3, Styling),
+ fun generic_serializer/1
+ ),
+ erlang:element(2, Highlight),
+ erlang:element(3, Highlight),
+ erlang:element(4, Highlight)
+ )
+ end.
diff --git a/aoc2023/build/packages/gap/src/gap_ffi.mjs b/aoc2023/build/packages/gap/src/gap_ffi.mjs
new file mode 100644
index 0000000..235c80b
--- /dev/null
+++ b/aoc2023/build/packages/gap/src/gap_ffi.mjs
@@ -0,0 +1,431 @@
+import {
+ Error,
+ List,
+ Ok,
+ inspect,
+ toList,
+ makeError,
+ isEqual,
+} from "./gleam.mjs";
+import * as $option from "../gleam_stdlib/gleam/option.mjs";
+
+const HASHCODE_CACHE = new WeakMap();
+const Nil = undefined;
+
+class MutableMap {
+ static #hashcode_cache = new WeakMap();
+
+ static hash(value) {
+ let existing = this.#hashcode_cache.get(value);
+ if (existing) {
+ return existing;
+ } else if (value instanceof Object) {
+ let hashcode = inspect(value);
+ HASHCODE_CACHE.set(value, hashcode);
+ return hashcode;
+ } else {
+ return value.toString();
+ }
+ }
+
+ constructor() {
+ this.entries = new globalThis.Map();
+ }
+
+ get size() {
+ return this.entries.size;
+ }
+
+ inspect() {
+ let entries = [...this.entries.values()]
+ .map((pair) => inspect(pair))
+ .join(", ");
+ return `map.from_list([${entries}])`;
+ }
+
+ toList() {
+ return List.fromArray([...this.entries.values()]);
+ }
+
+ insert(k, v) {
+ this.entries.set(MutableMap.hash(k), [k, v]);
+ return this;
+ }
+
+ delete(k) {
+ this.entries.delete(MutableMap.hash(k));
+ return this;
+ }
+
+ get(key) {
+ let code = MutableMap.hash(key);
+ if (this.entries.has(code)) {
+ return new Ok(this.entries.get(code)[1]);
+ } else {
+ return new Error(Nil);
+ }
+ }
+}
+
+export function new_mutable_map() {
+ return new MutableMap();
+}
+
+export function mutable_map_size(map) {
+ return map.size;
+}
+
+export function mutable_map_to_list(map) {
+ return map.toList();
+}
+
+export function mutable_map_remove(k, map) {
+ return map.delete(k);
+}
+
+export function mutable_map_get(map, key) {
+ return map.get(key);
+}
+
+export function mutable_map_insert(key, value, map) {
+ return map.insert(key, value);
+}
+
+// From map.mjs
+
+export function size(map) {
+ return mutable_map_size(map);
+}
+
+export function to_list(map) {
+ return mutable_map_to_list(map);
+}
+
+export function new$() {
+ return new_mutable_map();
+}
+
+export function get(from, get) {
+ return mutable_map_get(from, get);
+}
+
+function do_has_key(key, map) {
+ return !isEqual(get(map, key), new Error(undefined));
+}
+
+export function has_key(map, key) {
+ return do_has_key(key, map);
+}
+
+export function insert(map, key, value) {
+ return mutable_map_insert(key, value, map);
+}
+
+function insert_pair(map, pair) {
+ return insert(map, pair[0], pair[1]);
+}
+
+export function update(map, key, fun) {
+ let _pipe = map;
+ let _pipe$1 = get(_pipe, key);
+ let _pipe$2 = $option.from_result(_pipe$1);
+ let _pipe$3 = fun(_pipe$2);
+ return ((_capture) => {
+ return insert(map, key, _capture);
+ })(_pipe$3);
+}
+
+export function delete$(map, key) {
+ return mutable_map_remove(key, map);
+}
+
+function fold_list_of_pair(loop$list, loop$initial) {
+ while (true) {
+ let list = loop$list;
+ let initial = loop$initial;
+ if (list.hasLength(0)) {
+ return initial;
+ } else if (list.atLeastLength(1)) {
+ let x = list.head;
+ let rest = list.tail;
+ loop$list = rest;
+ loop$initial = insert(initial, x[0], x[1]);
+ } else {
+ throw makeError(
+ "case_no_match",
+ "gleam/map",
+ 98,
+ "fold_list_of_pair",
+ "No case clause matched",
+ { values: [list] }
+ );
+ }
+ }
+}
+
+function do_from_list(list) {
+ return fold_list_of_pair(list, new$());
+}
+
+export function from_list(list) {
+ return do_from_list(list);
+}
+
+function do_fold(loop$list, loop$initial, loop$fun) {
+ while (true) {
+ let list = loop$list;
+ let initial = loop$initial;
+ let fun = loop$fun;
+ if (list.hasLength(0)) {
+ return initial;
+ } else if (list.atLeastLength(1)) {
+ let k = list.head[0];
+ let v = list.head[1];
+ let tail = list.tail;
+ loop$list = tail;
+ loop$initial = fun(initial, k, v);
+ loop$fun = fun;
+ } else {
+ throw makeError(
+ "case_no_match",
+ "gleam/map",
+ 558,
+ "do_fold",
+ "No case clause matched",
+ { values: [list] }
+ );
+ }
+ }
+}
+
+export function fold(map, initial, fun) {
+ let _pipe = map;
+ let _pipe$1 = to_list(_pipe);
+ return do_fold(_pipe$1, initial, fun);
+}
+
+function do_map_values(f, map) {
+ let f$1 = (map, k, v) => {
+ return insert(map, k, f(k, v));
+ };
+ let _pipe = map;
+ return fold(_pipe, new$(), f$1);
+}
+
+export function map_values(map, fun) {
+ return do_map_values(fun, map);
+}
+
+function do_filter(f, map) {
+ let insert$1 = (map, k, v) => {
+ let $ = f(k, v);
+ if ($) {
+ return insert(map, k, v);
+ } else {
+ return map;
+ }
+ };
+ let _pipe = map;
+ return fold(_pipe, new$(), insert$1);
+}
+
+export function filter(map, property) {
+ return do_filter(property, map);
+}
+
+function do_keys_acc(loop$list, loop$acc) {
+ while (true) {
+ let list = loop$list;
+ let acc = loop$acc;
+ if (list.hasLength(0)) {
+ return reverse_and_concat(acc, toList([]));
+ } else if (list.atLeastLength(1)) {
+ let x = list.head;
+ let xs = list.tail;
+ loop$list = xs;
+ loop$acc = toList([x[0]], acc);
+ } else {
+ throw makeError(
+ "case_no_match",
+ "gleam/map",
+ 276,
+ "do_keys_acc",
+ "No case clause matched",
+ { values: [list] }
+ );
+ }
+ }
+}
+
+function do_keys(map) {
+ let list_of_pairs = (() => {
+ let _pipe = map;
+ return to_list(_pipe);
+ })();
+ return do_keys_acc(list_of_pairs, toList([]));
+}
+
+export function keys(map) {
+ return do_keys(map);
+}
+
+function reverse_and_concat(loop$remaining, loop$accumulator) {
+ while (true) {
+ let remaining = loop$remaining;
+ let accumulator = loop$accumulator;
+ if (remaining.hasLength(0)) {
+ return accumulator;
+ } else if (remaining.atLeastLength(1)) {
+ let item = remaining.head;
+ let rest = remaining.tail;
+ loop$remaining = rest;
+ loop$accumulator = toList([item], accumulator);
+ } else {
+ throw makeError(
+ "case_no_match",
+ "gleam/map",
+ 269,
+ "reverse_and_concat",
+ "No case clause matched",
+ { values: [remaining] }
+ );
+ }
+ }
+}
+
+function do_values_acc(loop$list, loop$acc) {
+ while (true) {
+ let list = loop$list;
+ let acc = loop$acc;
+ if (list.hasLength(0)) {
+ return reverse_and_concat(acc, toList([]));
+ } else if (list.atLeastLength(1)) {
+ let x = list.head;
+ let xs = list.tail;
+ loop$list = xs;
+ loop$acc = toList([x[1]], acc);
+ } else {
+ throw makeError(
+ "case_no_match",
+ "gleam/map",
+ 314,
+ "do_values_acc",
+ "No case clause matched",
+ { values: [list] }
+ );
+ }
+ }
+}
+
+function do_values(map) {
+ let list_of_pairs = (() => {
+ let _pipe = map;
+ return to_list(_pipe);
+ })();
+ return do_values_acc(list_of_pairs, toList([]));
+}
+
+export function values(map) {
+ return do_values(map);
+}
+
+function insert_taken(loop$map, loop$desired_keys, loop$acc) {
+ while (true) {
+ let map = loop$map;
+ let desired_keys = loop$desired_keys;
+ let acc = loop$acc;
+ let insert$1 = (taken, key) => {
+ let $ = get(map, key);
+ if ($.isOk()) {
+ let value = $[0];
+ return insert(taken, key, value);
+ } else {
+ return taken;
+ }
+ };
+ if (desired_keys.hasLength(0)) {
+ return acc;
+ } else if (desired_keys.atLeastLength(1)) {
+ let x = desired_keys.head;
+ let xs = desired_keys.tail;
+ loop$map = map;
+ loop$desired_keys = xs;
+ loop$acc = insert$1(acc, x);
+ } else {
+ throw makeError(
+ "case_no_match",
+ "gleam/map",
+ 411,
+ "insert_taken",
+ "No case clause matched",
+ { values: [desired_keys] }
+ );
+ }
+ }
+}
+
+function do_take(desired_keys, map) {
+ return insert_taken(map, desired_keys, new$());
+}
+
+export function take(map, desired_keys) {
+ return do_take(desired_keys, map);
+}
+
+function fold_inserts(loop$new_entries, loop$map) {
+ while (true) {
+ let new_entries = loop$new_entries;
+ let map = loop$map;
+ if (new_entries.hasLength(0)) {
+ return map;
+ } else if (new_entries.atLeastLength(1)) {
+ let x = new_entries.head;
+ let xs = new_entries.tail;
+ loop$new_entries = xs;
+ loop$map = insert_pair(map, x);
+ } else {
+ throw makeError(
+ "case_no_match",
+ "gleam/map",
+ 451,
+ "fold_inserts",
+ "No case clause matched",
+ { values: [new_entries] }
+ );
+ }
+ }
+}
+
+function do_merge(map, new_entries) {
+ let _pipe = new_entries;
+ let _pipe$1 = to_list(_pipe);
+ return fold_inserts(_pipe$1, map);
+}
+
+export function merge(map, new_entries) {
+ return do_merge(map, new_entries);
+}
+
+export function drop(loop$map, loop$disallowed_keys) {
+ while (true) {
+ let map = loop$map;
+ let disallowed_keys = loop$disallowed_keys;
+ if (disallowed_keys.hasLength(0)) {
+ return map;
+ } else if (disallowed_keys.atLeastLength(1)) {
+ let x = disallowed_keys.head;
+ let xs = disallowed_keys.tail;
+ loop$map = delete$(map, x);
+ loop$disallowed_keys = xs;
+ } else {
+ throw makeError(
+ "case_no_match",
+ "gleam/map",
+ 514,
+ "drop",
+ "No case clause matched",
+ { values: [disallowed_keys] }
+ );
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-23 06:35:58 +0000