In-place backtracking and mutable aliasing

help
1

Hello Everyone,
I wanted to solve a certain puzzle (if you must know it is Alphametics in Rust on Exercism). I tried backtracking to solve it and the solution worked but was too slow, so I attempted to do in-place backtracking. This was still too slow, alas, but I still have a question that I'm curious enough about to ask here. I represented the puzzle using a struct Puzzle, initially with the following methods for its associated trait:

impl Puzzle {
fn frontier(&self) -> Box<dyn Iterator<Item = Move> + '_> {..}
fn try_move(&mut self, &m:Move) -> Result<Change, MoveError> {..}
fn undo_move(&self, m: Move, delta: Change) {..}
fn solve(&self) -> Option<Solution> {
   if [puzzle finished] {
       [return solution]
   }
   for m in self.frontier() {
      if let Ok(change) = self.try_move(&m) {
          if let Some(sol) = self.solve() {
               return Some(sol)
          } else {
               self.undo_move(m, change)
         }
      } 
   }
   return None;
  }
}

Here I simply called the type of solutions Solution, the type of ways to extend an incomplete solution into a more complete one Move, and the type of changes to *self caused by applying a move Change. If you want more explicit details, they are available here. The problem with this strategy is that the iterator self.frontier() borrows *self as immutable while try_move and undo_move have to borrow it as mutable. So I have to change its type to fn frontier(&self) -> Vec<Move> {..}, to make explicit that I need the frontier fixed before doing/undoing any moves. I have two questions:

  1. Is there any way to use a type like Box<dyn Iterator> for the return value of frontier()?
  2. Do I lose any performance for the fact that I have to allocate a Vec<Move> for all the moves which I then prompty discard, or is the compiler somehow smart enough to inline that away?
2

At first glance it sounds like the error is saving you from iterator invalidation, since you mutate env in try_move and undo_move while iterating over it. At a slightly longer glance, perhaps once the iterator reaches some index i, you only modify fields <= i, so there's no logical invalidation? Even if so, that would take some sort of global analysis which isn't supported. (Intentionally mostly -- the signature try_move allows it modify things the iterator is still referencing).

Assuming no logic errors, there may be some refactoring that could work around it. Or you could probably use Cells. However, looking at the types, you can probably just do something like this instead:

impl Environment {
    // Iterator doesn't borrow self anymore                 vvvvv
    pub fn free_digits(&self) -> impl Iterator<Item = u8> + use<> {
        // Copy 20 bytes or so
        let dtv = self.digit_to_var;
        (0u8..10).filter(move |&d| dtv[usize::from(d)].is_none())
    }
}

impl Puzzle {
    // Iterator doesn't borrow self anymore (no `+ '_`)
    fn frontier(&self) -> Box<dyn Iterator<Item = Move>> {
        ...

Or even just make an owning custom iterator for frontier to return, which would be a handful of bytes large and not require boxing and type erasure.

1 Like
3

Thank you, copying the important bit of the environment works! For the owning iterator idea I suppose you mean that it would own something like dtv right?

4

You mainly need to do the work that was in the closure in your implementation of the Iterator trait instead somehow. One common way is to wrap an iterator that has a concrete name you can use, which is the case with most non-closure-taking iterators in std. For example:

use std::array::IntoIter;
use std::iter::Enumerate;

struct FreeDigits {
    inner: Enumerate<IntoIter<Option<u8>, 10>>,
}

impl Iterator for FreeDigits {
    type Item = u8;
    fn next(&mut self) -> Option<Self::Item> {
        while let Some((idx, opt)) = self.inner.next() {
            if opt.is_none() {
                return Some(idx as u8);
            }
        }
        
        None
    }
}

impl Environment {
    pub fn free_digits(&self) -> FreeDigits {
        let inner = self.digit_to_var.into_iter().enumerate();
        FreeDigits { inner }
    }
}