0

I'm solving a problem from Leetcode and encountered the fact that Rust won't let me execute it efficiently. What am I doing wrong? I know about the book article about references and borrowing and would like to know how to solve this problem despite the peculiarities of the language.

I am trying to create one reference for a vec that should change and another for a vec that will not change. Rust won't let me do that. The program works, but only when using .clone(), which will be very slow and not necessary (last_row does not change anywhere, only the values are derived from there).

Here is the working code:

use std::cmp; fn minimum_total(mut triangle: Vec<Vec<i32>>) -> i32 { for i in (0..triangle.len()-1).rev() { // from penultimate (last - 1) to first let last_row = & triangle[i+1].clone(); let current_row = &mut triangle[i]; for j in 0..current_row.len() { current_row[j] = cmp::min(last_row[j], last_row[j+1]) + current_row[j]; } } triangle[0][0] } fn main() { println!("{}", minimum_total(vec![vec![2],vec![3,4],vec![6,5,7],vec![4,1,8,3]])); }

As you can see, I used .clone() to fix the borrow checker errors that show up when you try to write a program using references:

use std::cmp; fn minimum_total(mut triangle: Vec<Vec<i32>>) -> i32 { for i in (0..triangle.len()-1).rev() { // from penultimate (last - 1) to first let current_row = &mut triangle[i]; let last_row = &triangle[i+1]; for j in 0..current_row.len() { current_row[j] = cmp::min(last_row[j], last_row[j+1]) + current_row[j]; } } triangle[0][0] } fn main() { println!("{}", minimum_total(vec![vec![2],vec![3,4],vec![6,5,7],vec![4,1,8,3]])); }

Terminal:

error[E0502]: cannot borrow `triangle` as immutable because it is also borrowed as mutable --> src\main.rs:6:25 | 5 | let current_row = &mut triangle[i]; | -------- mutable borrow occurs here 6 | let last_row = &triangle[i+1]; | ^^^^^^^^ immutable borrow occurs here 7 | for j in 0..current_row.len() { | ----------------- mutable borrow later used here For more information about this error, try `rustc --explain E0502`.

However, when trying to write a program poorly everything works without any problems:

use std::cmp; fn minimum_total(mut triangle: Vec<Vec<i32>>) -> i32 { for i in (0..triangle.len()-1).rev() { // from penultimate (last - 1) to first for j in 0..triangle[i].len() { triangle[i][j] = cmp::min(triangle[i+1][j], triangle[i+1][j+1]) + triangle[i][j]; } } triangle[0][0] } fn main() { println!("{}", minimum_total(vec![vec![2],vec![3,4],vec![6,5,7],vec![4,1,8,3]])); }
Improve this question
9
  • 2
    your "poor" code generates smaller assembly too. do you mean because you prefer the variable names rather than triangle[][]? Commented Jun 20, 2022 at 19:23
  • 1
    Cloning is the right way to go. You are trying to iterate through triangle while editing it using two different references. Your double for loop code is probably the better way to do it. Just because it is a double for loop does not mean it is automatically worse Commented Jun 20, 2022 at 19:25
  • @rodrigo The two extra lines make the code in the first listing easier to analyze, read and modify. Of course, there will be no difference in the speed of execution, but I'm frustrated by the lack of ability to write code that is not only safe, but also of high quality. Commented Jun 20, 2022 at 19:27
  • 1
    Please don't edit the answer into the question! Instead, just accept the answer that helped you (which you did), or write an answer to your own question (yes, you may do that) to share the solution you ended up using. Commented Jun 21, 2022 at 12:02
  • 1
    @FZs You can rollback in those cases. Commented Jun 22, 2022 at 0:40

2 Answers 2

Reset to default
2

You can accomplish this via the split_at_mut() method, which comes from the primitive slice type (which Vec auto-derefs to). This method allows you to safely take a mutable slice and split it into two mutable slices at a given index, since it's guaranteed that the two slices won't overlap. (Note this is zero-copy, as slices are just fat pointers borrowing an existing contiguous sequence.)

The two slices then are independent for the purposes of borrow checking, so you can borrow mutably from both slices at the same time (or, in your case, mutably from one and immutably from the other).

use std::cmp; fn minimum_total(mut triangle: Vec<Vec<i32>>) -> i32 { for i in (0..triangle.len()-1).rev() { // from penultimate (last - 1) to first let (left, right) = triangle.split_at_mut(i + 1); let current_row = left.last_mut().unwrap(); let last_row = right.first().unwrap(); for j in 0..current_row.len() { current_row[j] = cmp::min(last_row[j], last_row[j+1]) + current_row[j]; } } triangle[0][0] } fn main() { println!("{}", minimum_total(vec![vec![2],vec![3,4],vec![6,5,7],vec![4,1,8,3]])); }
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

Yes, that's the thing with Rust -- you have to code in a way that the compiler can tell it is safe. Sometimes that requires a bit of thought, but often in the end you have code that is cleaner than you would have written otherwise.

Imagine having a function that could walk through items two at a time, calling a function you specify on them, with the first being immutable, and the second being mutable. Call it pairs_mut, and calling it with function f on a,b,c,d it would result in calls to f(&a, &mut b), f(&b, &mut c), and f(&c, &mut d). A non-generic version is not that hard to write. I am hesitant to put the code here because you are trying to learn from the exercise.

NOTE: I suspect that such a facility (or perhaps something more general) exists somewhere in the Rust ecosystem, but I have looked in Iterator and the itertools crate and didn't find anything. If you know of an existing facility like this, please share a link in a comment. Otherwise perhaps I should try to get something added to itertools.

Now given pairs_mut, I hope you can see that minimum_total could run it on triangle.rev() and do that bit of dynamic programming to come up with the minimum sum. Let me know if you want me to put some actual code here, but I encourage you to try it yourself first.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.