// Rust Bytes Challenge Issue #100 Merging Magical Portals

fn sort_intervals(mut intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
    intervals.sort_unstable_by_key(|p| p.0);
    intervals
}

fn collapse(sorted_intervals: &[(i32, i32)]) -> Vec<(i32, i32)> {
    // Changed parameter type to slice
    let mut result: Vec<(i32, i32)> = Vec::new();
    let mut current_interval = sorted_intervals[0]; // Avoid clone by using reference
    for &interval in &sorted_intervals[1..] {
        // Skip first element since we already have it
        if current_interval.1 >= interval.0 {
            current_interval.1 = current_interval.1.max(interval.1);
        } else {
            result.push(current_interval);
            current_interval = interval;
        }
    }
    result.push(current_interval.clone());
    result
}

fn merge_portals(intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
    if intervals.is_empty() {
        // Handle empty input early
        return vec![];
    }
    let sorted_intervals = sort_intervals(intervals);
    collapse(&sorted_intervals)
}


#[cfg(test)]
mod tests {
    use super::merge_portals;

    #[test]
    fn test_no_portals() {
        assert_eq!(merge_portals(vec![]), vec![]);
    }

    #[test]
    fn test_single_portal() {
        assert_eq!(merge_portals(vec![(5, 10)]), vec![(5, 10)]);
    }

    #[test]
    fn test_no_overlap() {
        let input = vec![(1, 2), (3, 4), (5, 6)];
        let expected = vec![(1, 2), (3, 4), (5, 6)];
        assert_eq!(merge_portals(input), expected);
    }

    #[test]
    fn test_simple_overlap() {
        let input = vec![(1, 3), (2, 4)];
        let expected = vec![(1, 4)];
        assert_eq!(merge_portals(input), expected);
    }

    #[test]
    fn test_touching_edges() {
        let input = vec![(1, 3), (3, 5), (5, 7)];
        let expected = vec![(1, 7)];
        assert_eq!(merge_portals(input), expected);
    }

    #[test]
    fn test_multiple_merges() {
        let input = vec![(6, 8), (1, 5), (2, 4), (7, 9), (10, 12)];
        let expected = vec![(1, 5), (6, 9), (10, 12)];
        assert_eq!(merge_portals(input), expected);
    }

    #[test]
    fn test_all_overlap() {
        let input = vec![(1, 10), (2, 9), (3, 8), (4, 7)];
        let expected = vec![(1, 10)];
        assert_eq!(merge_portals(input), expected);
    }

    #[test]
    fn test_unsorted_input() {
        let input = vec![(5, 6), (1, 3), (2, 4)];
        let expected = vec![(1, 4), (5, 6)];
        assert_eq!(merge_portals(input), expected);
    }
}

(Playground)

Output:

running 8 tests
test tests::test_multiple_merges ... ok
test tests::test_all_overlap ... ok
test tests::test_no_overlap ... ok
test tests::test_no_portals ... ok
test tests::test_simple_overlap ... ok
test tests::test_single_portal ... ok
test tests::test_touching_edges ... ok
test tests::test_unsorted_input ... ok

test result: ok. 8 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s


running 0 tests

test result: ok. 0 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s

Errors:

   Compiling playground v0.0.1 (/playground)
warning: function `sort_intervals` is never used
 --> src/lib.rs:3:4
  |
3 | fn sort_intervals(mut intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
  |    ^^^^^^^^^^^^^^
  |
  = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

warning: function `collapse` is never used
 --> src/lib.rs:8:4
  |
8 | fn collapse(sorted_intervals: &[(i32, i32)]) -> Vec<(i32, i32)> {
  |    ^^^^^^^^

warning: function `merge_portals` is never used
  --> src/lib.rs:25:4
   |
25 | fn merge_portals(intervals: Vec<(i32, i32)>) -> Vec<(i32, i32)> {
   |    ^^^^^^^^^^^^^

warning: function `main` is never used
  --> src/lib.rs:34:4
   |
34 | fn main() {
   |    ^^^^

warning: `playground` (lib) generated 4 warnings
    Finished `test` profile [unoptimized + debuginfo] target(s) in 2.84s
     Running unittests src/lib.rs (target/debug/deps/playground-df1c4bada4e6c02d)
   Doc-tests playground

2 posts - 2 participants

Read full topic