Converting nested array to vec

I got to a next leetcode crossword. Even before I got to the core of the problem I was puzzled with tests, or, to be precise, with input data.

Test requires me to accept grid: Vec<Vec<char>>, but examples are in a form of arrays:

let grid  = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
];

Which has type of [[&str;5];4]. I definitely don’t want to do conversion by hands, so I need to write function from [[&str;T];U] into Vec<Vec<char>>.

I causally wrote [&str;U], but is this a reasonable way to define generic? I got to the wobbly feeling around slice, therefore, I’ll focus on this problem.

… and, bumer. Core Rust array types [T; N] can’t be used generically with respect to N...

Sad. But, do I need it? Can we live with &[]?

Let’s try to write a simple function to accept any array and returning it’s length.

Yes, we totally can.

fn foo(arr: &[u8]) -> usize {
  arr.len()
}

Can we take &[&[...]] and return the length of the outer array?

fn foo(arr: &[&[u8]]) -> usize {
  arr.len()
}

and test:

#[test]
fn test_1(){
  let data = [&[1,2], &[3,4]];
  assert_eq!(foo(&data), 3);
}

The error was a bit confusing:

expected slice `[&[u8]]`, found array `[&[{integer}; 2]; 2]`

Wut? It’s really unexpected, as I assumed that Rust totally can infer that data is [&[u8]] instead of {integer}. What’s going on?

If I comment out ‘assert’, Rust can show me guessed type for data:

&[&[i32; 2]; 2]

which is not &[&[u8]] (ignore u8), which is not &[&[u32]].

Let’s step back.

let data = &[1,2];  // type &[i32; 2]

But we can pass it as an argument with signature &[i32].

There is some interesting conversion between reference to array and reference to a slice. I may be very much wrong, but it looks like .as_ref() call.

I can write

let z: &[i32] = data.as_ref()
// or just
let z: &[i32] = data; // implicit call to .as_ref()?

But there is no implicit call into .as_ref() for nested references… Can I do them explicitly?

let data = [
  &[1,2].as_ref(),
  &[3,4].as_ref()
].as_ref();

Resulting type is &[&&[i32]]. Not exactly… but…

let data = [
  [1,2].as_ref(),
  [3,4].as_ref()
].as_ref();

Yes, now we have type we want: &[&&[i32]].

But why first version hadn’t worked? Oh, it’s precedence…

let data = (&[
    (&[1,2]).as_ref(),
    (&[3,4]).as_ref()
]).as_ref();

This version worked too, but with more buttons pushed. I think I got the problem, so let’s go back to original issue:

ops, nope. Rust is biting back:

Basically, I create an array which is dropped at the end of ‘]’, therefore, invalidating references. Huh. I can’t just use ‘let’ for each line. Can I use original array of arrays to construct array of borrows?

Reminder to myself: the reason I want an array of reference is because I want to write a function to accept any kind of array without specific dimensions in signatures.

let data = [
  [1,2],
  [3,4],
];
let refs = data.map(|x| x.as_ref()).as_ref();

Nope, Rust is in a full bite mode:

error: returns a reference to data owned by the current function

Looks like a dead end.

I found this one: https://practice.rs/generics-traits/const-generics.html

Bingo! Bingo! Bingo!

fn foo<const N:usize, const M:usize>(arr: [[u8;M];N]) -> usize {
  arr.len()
}
#[test]
fn test_1(){
  let data = [
    [1,2],
    [3,4],
  ];
  assert_eq!(foo(data), 2);
}

It worked, and it worked as amazing as I never dreamed it would.

I read a bit about const generics in recent release notes (not recent … time flies), but never got to use them. This is the first time, and I was very much salvaged by them.

Implementing array -> Vec<Vec<>>

Now I can write my conversion function.

fn convert<
  T: std::clone::Clone,
  const N: usize,
  const M: usize
>(arr: [[T; M]; N]) -> Vec<Vec<T>> {
  let mut ret = Vec::with_capacity(N);
  for v in arr.iter() {
    ret.push(v.to_vec());
  }
  ret
}

Rust was to the rescue and said I need to have T: std::clone::Clone, but it looks like it worked!

(actually, I needed also to convert &str[0] into char, but it’s a small thing).

Conclusion

There are const generics in Rust and they allow to implement generics for arrays of arbitrary length.

P.S.

The actual conversion function:

fn convert<const N: usize, const M: usize>
(arr: [[&str; M]; N]) -> Vec<Vec<char>> {
  let mut ret = Vec::with_capacity(N);
  for row in arr.iter(){
    let mut vec_row = Vec::with_capacity(M);
    for cell in (*row).iter(){
      let char = (*cell).chars().next().unwrap();
      vec_row.push(char);
    }
    ret.push(vec_row)
  }
  ret
}

… and I got ‘100% faster’ on the first attempt!

https://leetcode.com/problems/number-of-islands/