Chained `filter_map`

1

Hi,

trying to learn Rust by doing this year's adventofcode, and really struggling with a double filter_map.

Would appreciate some help in understanding what needs fixing in my code. Also alternative ways to solve this are welcome.

Basically I have multi line string with digits. I want to map the coordinates (row, col) of all zero digits in this string.

Example input string:

let input_str = "
102
010
123
".trim();

First I parse that into a Vec<Vec<u32>>:

let input_vec: Vec<Vec<u32>> =
    input_str
        .lines()
        .map(|line| 
            line.chars().map(|c|
                c.to_digit(10).unwrap()).collect()
        ).collect();

Then I try to do a double filter_map, first to filter only the rows that have 0s, indexed with i, then only the digits that are 0, indexed j:

// creates a tuple (row, col) with all occurences of `0`
// in the example above, it would be
// `[(0, 1), (1, 0), (1, 2)]`
let zeros_idx = input_vec
    .iter()
    .enumerate()
    .filter(|(i, row)| row.contains(&0))
    .filter_map(|(i, row)| {
        row.iter().enumerate().filter_map(|(j, &c)| 
            (c == 0).then_some(Some((i, j))))
        }
    )
    .collect();

Rust compiler is not happy with my code :frowning: telling me this:

 | /             row.iter().enumerate().filter_map(|(j, &c)| 
 | |                 (c == 0).then_some(Some((i, j))))
 | |_________________________________________________^ expected `Option<_>`, found `FilterMap<Enumerate<...>, ...>`

Link to this example here: Playground

I tried to collect() something at that location:

(c == 0).then_some(Some((i, j)))).collect::<Option<(usize, usize)>>()

Then the compiler's rant gets nastier:

 |                 (c == 0).then_some(Some((i, j)))).collect::<Option<(usize, usize)>>()
 |                                                   -------   ^^^^^^^^^^^^^^^^^^^^^^ the trait `Extend<usize>` is not implemented for `usize`, which is required by `Option<(usize, usize)>: FromIterator<Option<(usize, usize)>>`
 |                                                   |
 |                                                   required by a bound introduced by this call

This example here: Playground

2 
let zeros_idx = input_vec
    .iter()
    .enumerate()
    .flat_map(|(i, row)| {
        row.iter().enumerate().filter_map(move |(j, &c)| (c == 0).then_some((i, j)))
    })
    .collect::<Vec<(usize, usize)>>();

The .filter(|(i, row)| row.contains(&0)) can be omitted since it is redundant with the filtering of filter_map, unless perhaps you're trying to micro-optimize.

Some explanation, if it helps: When you make nested calls to filter_map this creates a nested structure. This is one reason the compiler errors were confusing. The other reason is that then_some(Some((i, j)))) creates a nested Option, since then_some wraps its arg in an Option.

One more reason for the errors is that when you call collect you have to specify the type of the collection (e.g., Vec). This can be the annotated type of the variable being assigned, or the turbofish .collect::<Vec<(usize, usize)>>() can be used. I included the (usize, usize) for clarity, but this can be inferred using Vec<_> instead.

Since you want a flat result - a Vec of x-y pairs - you could do the map and then call flatten:

            let zeros_idx = input_vec
                .iter()
                .enumerate()
                .map(|(i, row)| {
                    row.iter().enumerate().filter_map(move |(j, &c)| (c == 0).then_some((i, j)))
                })
                .flatten() // <<<<<<<<
                .collect::<Vec<(usize, usize)>>();

This works, but can be more succinct by combining the map and flatten in a single call to flat_map.

2 Likes