aboutsummaryrefslogtreecommitdiff
path: root/aoc2023/build/packages/gap/src/gap.erl
diff options
context:
space:
mode:
Diffstat (limited to 'aoc2023/build/packages/gap/src/gap.erl')
-rw-r--r--aoc2023/build/packages/gap/src/gap.erl538
1 files changed, 538 insertions, 0 deletions
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}.
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-23 02:08:22 +0000