Rust Bytes weekly challenge solution - zigzag merge

1 
// Rust Bytes Challenge Issue #94 Zigzag Merge Iterator

use std::iter;

pub fn zigzag_merge(
    iter1: impl Iterator<Item = i32>,
    iter2: impl Iterator<Item = i32>,
) -> impl Iterator<Item = i32> {
    let mut p1 = iter1.peekable();
    let mut p2 = iter2.peekable();
    let mut p1_to_be_consumed    = true;
    iter::from_fn(move || match (p1.peek(), p2.peek()) {
        (Some(_), Some(_)) => {
            if p1_to_be_consumed {
                p1_to_be_consumed = false;
                p1.next()
            } else {
                p1_to_be_consumed = true;
                p2.next()
            }
        },
        (Some(_), None) => p1.next(),
        (None, Some(_)) => p2.next(),
        _ => None,
    })
}


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

    #[test]
    fn test_equal_length() {
        let i1 = vec![1, 3, 5].into_iter();
        let i2 = vec![2, 4, 6].into_iter();
        let result: Vec<i32> = zigzag_merge(i1, i2).collect();
        assert_eq!(result, vec![1, 2, 3, 4, 5, 6]);
    }

    #[test]
    fn test_iter1_shorter() {
        let i1 = vec![1, 3].into_iter();
        let i2 = vec![2, 4, 6].into_iter();
        let result: Vec<i32> = zigzag_merge(i1, i2).collect();
        assert_eq!(result, vec![1, 2, 3, 4, 6]);
    }

    #[test]
    fn test_iter2_shorter() {
        let i1 = vec![1, 3, 5].into_iter();
        let i2 = vec![2, 4].into_iter();
        let result: Vec<i32> = zigzag_merge(i1, i2).collect();
        assert_eq!(result, vec![1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_both_empty() {
        let i1 = vec![].into_iter();
        let i2 = vec![].into_iter();
        let result: Vec<i32> = zigzag_merge(i1, i2).collect();
        assert_eq!(result, vec![]);
    }

    #[test]
    fn test_one_empty() {
        let i1 = vec![1, 2, 3].into_iter();
        let i2 = vec![].into_iter();
        let result: Vec<i32> = zigzag_merge(i1, i2).collect();
        assert_eq!(result, vec![1, 2, 3]);
    }

    #[test]
    fn test_negatives() {
        let i1 = vec![-1, -3].into_iter();
        let i2 = vec![-2, -4].into_iter();
        let result: Vec<i32> = zigzag_merge(i1, i2).collect();
        assert_eq!(result, vec![-1, -2, -3, -4]);
    }

    #[test]
    fn test_duplicates() {
        let i1 = vec![1, 1].into_iter();
        let i2 = vec![1, 1].into_iter();
        let result: Vec<i32> = zigzag_merge(i1, i2).collect();
        assert_eq!(result, vec![1, 1, 1, 1]);
    }
}

(Playground)

Output:


running 7 tests
test tests::test_both_empty ... ok
test tests::test_duplicates ... ok
test tests::test_iter1_shorter ... ok
test tests::test_iter2_shorter ... ok
test tests::test_negatives ... ok
test tests::test_one_empty ... ok
test tests::test_equal_length ... ok

test result: ok. 7 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)
    Finished `test` profile [unoptimized + debuginfo] target(s) in 0.73s
     Running unittests src/lib.rs (target/debug/deps/playground-13b5416e510cb238)
   Doc-tests playground
2 Likes
2

I never realised that the compilation process prints to standard error, which is why you've put the "Error" there, though there aren't any.

What's the URL for the exercise?

PS: found it in the last newsletter.

3

Hi,
I did not put it there - I guess that is how the rust playground works...

--- cheers atul

4

My solution: https://docs.rs/itertools/latest/itertools/trait.Itertools.html#method.interleave

3 Likes
5

Awesome @jendrikw - Cool so there is already a method - and that is wow! :ok_hand:

6

Just gave it a shot myself, pretty pleased with this one:

pub fn zigzag_merge(
    mut iter1: impl Iterator<Item = i32>,
    mut iter2: impl Iterator<Item = i32>,
) -> impl Iterator<Item = i32> {
    let mut switch = true;

    std::iter::from_fn(move || {
        if switch {
            switch = false;
            iter1.next().or_else(|| iter2.next())
        } else {
            switch = true;
            iter2.next().or_else(|| iter1.next())
        }
    })
}
7

Note that this doesn't work as expected for iterators that return None, then loop again. This isn't common (or very good practice IMO), but it is possible.

8

TBF I never care what happens when the iterator is non-fused, as long as it's not UB. Like come on, just use Item = Option<T> if you want to return None.

2 Likes
9

Ah, good point! Easy enough to fix, though, I think:

    let mut iter1 = iter1.fuse();
    let mut iter2 = iter2.fuse();
    let mut switch = true;

...

Though, there's an argument that in the context of the Rust Bytes exercise, if the inner iterators loop, then the zigzag iterator should also loop...

10

True, it would be ideal, but how would it loop? Would it loop identically each time, as if the inner iterators were fused and the joined one was looped? Or would it be as if each inner iterator was looped without ever returning None? Should the joined iterator ever return None, or loop seamlessly? I think implementing each of these could be interesting, and might shed some insight on which one is more natural.

11

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.