diff options
Diffstat (limited to 'aoc2023/build/packages/gap/src/gap.gleam')
| -rw-r--r-- | aoc2023/build/packages/gap/src/gap.gleam | 438 |
1 files changed, 438 insertions, 0 deletions
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) +} |