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, 0 insertions, 438 deletions
diff --git a/aoc2023/build/packages/gap/src/gap.gleam b/aoc2023/build/packages/gap/src/gap.gleam deleted file mode 100644 index 7eb0e7f..0000000 --- a/aoc2023/build/packages/gap/src/gap.gleam +++ /dev/null @@ -1,438 +0,0 @@ -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) -} |