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 traits:

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)
         }
      } 
   }
  }
}

Here I simply called the type of solutions Solution, the type of ways to extend an incomplete solution into a 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 mutable 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?

1 post - 1 participant

Read full topic