Mutable references in recursive function

Question

I have a vector of character stacks called crates. Those stacks are represented using VecDeque<char> and thus the vector of those is a Vec<VecDeque<char>>. This data structure isn't really a stack but I'd like to use it as if it were one and just iterate through them from back to front and add elements to the back.

I want to move k last chars of a stack to another, but I want to keep them in order.

Example:

stack_a = [ 1 <- 2 <- 3 <- 4 ]
stack_b = [ 5 <- 6 ]

# movement from a to b with k=3
stack_b = [ 5 <- 6 <- 2 <- 3 <- 4 ]

You can notice that this is not something very easy to do with a stack. It would be easy if you had the right to change the order of elements added to the other stack because you could just repeat k times: push(stack_b, pop(stack_a))

But here we need to reorder the calls, to pop k times, keep the k values in memory and then push them. This can easily be expressed with a recursive function.

This is what my code looks like:

// I'm extracting my stack ids from a regex capture
let source_id = usize::from_str(&cap[2]).unwrap() - 1;
let target_id = usize::from_str(&cap[3]).unwrap() - 1;
// My simple function
fn move_crates_simultaneously(
    amount: usize,
    source: Rev<Iter<char>>,
    target: &mut VecDeque<char>,
) {
    if amount == 0 {
        return;
    }
    let value = source.next();
    move_crates_simultaneously(amount - 1, source, target);
    target.push_back(*(value.unwrap()));
}
// My function call
move_crates_simultaneously(
    usize::from_str(&cap[1]).unwrap(),
    crates[source_id].iter().rev(),
    &crates[target_id],
);

But there is a problem: &crates[target_id] is &VecDeque<char, Global> while the function needs a &mut VecDeque<char, Global>. From my understanding it doesn't seem to be possible to find a solution because there is now way for the compiler to know that my source and my target are not the same stack and thus to let me create my mutable ref for target. Does that mean it is not possible to solve this kind of problem that way in Rust?

Answer 1

You write that what you want to do isn't easily done with stacks.

I'll give you a hint that lets you avoid the problem, given that I assume you already solved part 1 of day 5 of the 2022 advent of code challenge :p

In part 1, you grab an element via pop and put it on the other stack via push. Then you do that num times. Easy enough.

Now for part 2, you need the order of the popped elements to be reversed. So why not use another stack to keep track of them? To move elements from one stack A to stack B while maintaining order, you can first move them from stack A to stack C with the simple "pop-push" algo from part 1, and then move them from stack C to stack B again with the simple pop-push algo:

Stack A: 1 2 3 4
Stack B: 
Stack C:

do the pop-push 4 times

Stack A:
Stack B:
Stack C: 4 3 2 1

do the pop-push 4 times

Stack A:
Stack B: 1 2 3 4
Stack C

This avoids the "double mutable reference" issue, because you don't need to have two mutable references to the VecDequeue alive at the same time.

EDIT: As an aside: When dealing with recursion and running into issues, the issues can often be avoided by explicitly creating and managing a stack.