Detect duplicated elements of a string slice happening in order

user_151150 0
Viewed 326

I need to detect and list string characters of slice that repeat themselves in order more or equal than N times. I managed to write non-higher-order-function solution in Rust already (below), but I wonder if this can be simplified to chaining iter methods.

The idea:

let v = "1122253225";
let n = 2;

Output:

There are 2 repetition of '1'
There are 3 repetition of '2'
There are 2 repetition of '2'

Indexes where repetition happens are not important. Repetition must happen in order (ie. 3 repetition of '2' separated by other values from the other 2 repetition of '2' counts as separate output lines).

My non-iterator solution:

    let mut cur_ch = '\0';
    let mut repeat = 0;

    for ch in v.chars() {
        if ch == cur_ch {
            repeat = repeat + 1;
        }
        else {
            if repeat >= n {
                printf!("There are {} repetition of '{}'", repeat, cur_ch);
            }
            cur_ch = ch;
            repeat = 1;
        }
    }

    if repeat >= n {
        printf!("There are {} repetition of '{}'", repeat, cur_ch);
    }

It works, but is there a better way to do so with chaining iter methods?

rust method-chaining higher-order-functions iterator
2 Answers

Here is a solution that uses scan and filter_map:

fn main() {
    let s = "112225322555";
    let n = 2;

    let i = s
        .chars()
        .map(|v| Some(v))
        .chain(std::iter::once(None))
        .scan((0, None), |(count, ch), v| match ch {
            Some(c) if *c == v => {
                *count += 1;
                Some((None, *count))
            }
            _ => Some((ch.replace(v), std::mem::replace(count, 1))),
        })
        .filter_map(|(ch, count)| match ch {
            Some(Some(ch)) if count >= n => Some((ch, count)),
            _ => None,
        });

    for (ch, num) in i {
        println!("There are {} repititions of {}", num, ch);
    }
}

Playground Link

The first step is to use scan to count the number of adjacent characters. The first argument to scan is a state variable, which gets passed to each call of the closure that you pass as the second argument. In this case the state variable is a tuple containing the current character and the number of times it has been seen.

Note:

  • We need to extend the iteration one beyond the end of the string we are analyzing (otherwise we would miss the case where the end of the string contained a run of characters meeting the criteria). We do this by mapping the iteration into Option<char> and then chaining on a single None. This is better than special-casing a character such as \0, so that we could even count \0 characters.

  • For the same reason, we use Option<char> as the current character within the state tuple.

  • The return value of scan is an iterator over (Option<Option<char>>, i32). The first value in the tuple will be None for each repeated character in the iterator, whereas at each boundary where the character changes it will be Some(Some(char))

  • We use replace to both return the current character and count, at the same time as setting the state tuple to new values

The last step is to use filter_map to:

  • remove the (None, i32) variants, which indicate no change in the incoming character

  • filter out the cases where the count does not reach the limit n.

user_14114570

Here's one attempt at using filter_map():

fn foo(v: &str, n: usize) -> impl Iterator<Item = (usize, char)> + '_ {
    let mut cur_ch = '\0';
    let mut repeat = 0;
    v.chars().chain(std::iter::once('\0')).filter_map(move |ch| {
        if ch == cur_ch {
            repeat += 1;
            return None;
        }
        
        let val = if repeat >= n {
            Some((repeat, cur_ch))
        } else {
            None
        };
        cur_ch = ch;
        repeat = 1;
        val
    })
}

fn main() {
    for (repeat, ch) in foo("1122253225", 2) {
        println!("There are {} repetition of '{}'", repeat, ch);
    }
}

And then you can generalize this to something like this:

fn foo<'i, I, T>(v: I, n: usize) -> impl Iterator<Item = (usize, T)> + 'i
where
    I: Iterator<Item = T> + 'i,
    T: Clone + Default + PartialEq + 'i,
{
    let mut cur = T::default();
    let mut repeat = 0;
    v.chain(std::iter::once(T::default()))
        .filter_map(move |i| {
            if i == cur {
                repeat += 1;
                return None;
            }

            let val = if repeat >= n {
                Some((repeat, cur.clone()))
            } else {
                None
            };
            cur = i;
            repeat = 1;
            val
        })
}

This would be higher-order, but not sure if it's actually much simpler than just using a for loop!

user_1582260
Related