Playing with Rust I—Towers of Hanoi

I've been hearing about Rust recently, a programming language which compiles to native code with an emphasis on memory safety. As the 1.0.0-alpha version was recently announced, I downloaded it from here and decided to write a couple of quick console applications to get a feel for the language.

First up, a Tower of Hanoi solver. As you can see, Rust has a something of a C++ 'look and feel', using several of the same keywords (const, struct, for, while) and use of {} braces to indicate code blocks and <> angle brackets for type variations (called 'generics' in Rust parlance vs. C++ templates).

There are some new keywords as well: let, fn, impl, mut, match among others. For most of these, the intended meanings are reasonably clear (fn is short for 'function', mut is short for 'mutable'; Rust tends towards extremely terse terminology).

I don't want to get into a detail-by-detail exposition of every aspect of the Rust syntax—I'm hoping that the general form of the code should be fairly clear to C++ readers, at least. I will touch on a few things though:

• struct is used to define a type's data members, impl is used to add methods to an existing type. Per-object methods can take either &self or &mut self, methods which don't have a self parameter are static. It is conventional to define a static new() method for each type which can be used to create new instances of that type. This listing attempts to follow that convention.
• This listing is currently hardcoded to solve the case of 5 pegs on 3 poles. The initial state of the Scene is hardcoded in Scene::new() (create the poles, place pegs on the first pole), and the HanoiSolver is initialized to operate on that state. It would probably not be too hard to fix the code to allow general solutions of m pegs on n poles.
• Scene is responsible for drawing the current state of the simulation onto the TTY (from its show() method, using the println!() macro). move_peg() attempts a valid move of a peg from one pole to another, returning true if it can, or false if it can't. (The solver only attempts valid moves if it is set up correctly so this should be a non-issue, but it could be extended to support e.g. a human player.)
• I quite like the impl Iterator for HanoiSolver {} syntax for implementing traits, that seems nice. The HanoiSolver just builds all the states it wants to visit in its new() function and stores them in a Vec of (from, to) move co-ordinates, which makes the implementation of next() extremely simple.
One particularly interesting piece of syntax to note is the presence or absence of a ; at the end of a {} block. If the ; is present, the block has no return value (to be precise, it returns ()). But if it's absent, then the final expression of the block becomes the return value. This might sound confusing, but I actually found it to be fairly intuitive, and I tried to make use of this idiom when I felt it was appropriate. You can of course use return to return a value from a block at any point.
• The match construct is pretty powerful, similar to something you'd see in a functional language Haskell or Standard ML. You can think of it as a superpowered version of a switch statement. The syntax if let/while let is somewhat related to match—it attempts to bind structured variables to an expression, and conditionally executes some code if the binding succeeds. Rust's type system is quite rich, it supports concepts such as Option<T> (which has constructors Some(t) and None), which work well with matching and let-binding.
• I consider this code to be at least semi-idiomatic; I attempted to follow the established conventions of the language as I understood them—suggestions from Rust experts are welcome though!

Without further comment, here's the complete listing. The expected output is at the end of the post.

//------------------------------------------------------------------------------

const PEG_COUNT: usize = 5;
const POLE_COUNT: usize = 3;
const NO_PEG: u32 = 0xffffffff;


struct Peg(u32);


struct Pole {
    pegs: Vec,
    smallest: u32,
}


struct Scene {
    poles: Vec,
}


impl Pole {
    fn new() -> Pole {
        Pole {
            pegs: Vec::with_capacity(PEG_COUNT),
            smallest: NO_PEG,
        }
    }

    fn push(&mut self, p: Peg) -> bool {
        let Peg(v) = p;

        if v < self.smallest {
            self.pegs.push(p);
            self.smallest = v;
            true

        } else {
            println!("ERR: tried to push size {} onto pole {}.", v, self.smallest);
            false
        }
    }

    fn pop(&mut self) -> Option {
        let mut smallest = NO_PEG;
        let mut pegs = &mut self.pegs;
        let result = pegs.pop();

        for i in 0..(pegs.len()) {
            let Peg(v) = pegs[i];
            if v < smallest {
                smallest = v
            }
        }

        self.smallest = smallest;
        result
    }
}


impl Scene {
    fn new() -> Scene {
        let mut result = Scene {
            poles: Vec::with_capacity(POLE_COUNT),
        };

        for _ in 0..(POLE_COUNT) {
            result.poles.push(Pole::new());
        };

        for j in 0..(PEG_COUNT) {
            result.poles[0].push(Peg((PEG_COUNT - j) as u32));
        };

        result
    }

    fn move_peg(&mut self, from: usize, to: usize) -> bool {
        if let Some(Peg(v)) = self.poles[from].pop() {
            if self.poles[to].push(Peg(v)) {
                return true
            } else {
                self.poles[from].push(Peg(v));
            }
        }
        false
    }

    fn get(&self, pole: usize, peg: usize) -> Option<&Peg> {
        let poles = &self.poles;

        if poles.len() > pole {
            let pegs = &poles[pole].pegs;

            if pegs.len() > peg {
                return Some(&pegs[peg])
            }
        }
        None
    }

    fn show(&self) {
        println!("");
        for i in 0..(PEG_COUNT) {
            let mut string = "".to_string();

            for j in 0..(POLE_COUNT) {
                match self.get(j, (PEG_COUNT-1)-i) {

                    Some(&Peg(p)) => {
                        let fmt = format!("  {:02}  ", p).to_string();
                        string.push_str(fmt.as_slice());
                    }

                    None => {
                        string.push_str("  ||  ");
                    }
                }
            }

            println!("{}", string);
        }
        let mut string = "".to_string();
        for _ in 0..(POLE_COUNT) {
            string.push_str("_/||\\_")
        }
        println!("{}", string);
        println!("");
    }
}


//------------------------------------------------------------------------------

struct HanoiMove {
    from: usize,
    to: usize,
}


struct HanoiState {
    n: usize,
    from: usize,
    to: usize,
    via: usize,
}


struct HanoiSolver {
    step: usize,
    route: Vec,
}


impl HanoiState {
    fn new(n: usize, from: usize, to: usize, via: usize) -> HanoiState {
        HanoiState { n: n, from: from, to: to, via: via }
    }

    fn iter(&self, out: &mut Vec) {
        let &HanoiState { n, from, to, via } = self;
        if n > 0 {
            HanoiState::new(n - 1, from, via, to).iter(out);
            out.push(HanoiMove { from: from, to: to });
            HanoiState::new(n - 1, via, to, from).iter(out);
        }
    }
}


impl HanoiSolver {
    fn new(n: usize, from: usize, to: usize, via: usize) -> HanoiSolver {
        let mut result = HanoiSolver {
            step: 0,
            route: Vec::new(),
        };
        let state = HanoiState::new(n, from, to, via);
        state.iter(&mut result.route);
        result
    }
}


impl Iterator for HanoiSolver {
    type Item = HanoiMove;
    fn next(&mut self) -> Option {

        let &mut HanoiSolver { step, ref route } = self;

        if step < route.len() {
            let HanoiMove{ from, to } = route[step];
            self.step += 1;
            return Some(HanoiMove { from: from, to: to })
        }
        None
    }
}


//------------------------------------------------------------------------------

fn main() {
    let mut scene = Scene::new();
    let mut solver = HanoiSolver::new(PEG_COUNT, 0, 2, 1);

    scene.show();

    while let Some(HanoiMove { from, to }) = solver.next() {

        println!("Move from {} --> {}", from, to);
        scene.move_peg(from, to);
        scene.show();
    }
}

And if you can get that to compile and run, you should see some output like the following:

  01    ||    ||  
  02    ||    ||  
  03    ||    ||  
  04    ||    ||  
  05    ||    ||  
_/||\__/||\__/||\_

Move from 0 --> 2

  ||    ||    ||  
  02    ||    ||  
  03    ||    ||  
  04    ||    ||  
  05    ||    01  
_/||\__/||\__/||\_

Move from 0 --> 1

  ||    ||    ||  
  ||    ||    ||  
  03    ||    ||  
  04    ||    ||  
  05    02    01  
_/||\__/||\__/||\_

Move from 2 --> 1

  ||    ||    ||  
  ||    ||    ||  
  03    ||    ||  
  04    01    ||  
  05    02    ||  
_/||\__/||\__/||\_

Move from 0 --> 2

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    ||  
  04    01    ||  
  05    02    03  
_/||\__/||\__/||\_

Move from 1 --> 0

  ||    ||    ||  
  ||    ||    ||  
  01    ||    ||  
  04    ||    ||  
  05    02    03  
_/||\__/||\__/||\_

Move from 1 --> 2

  ||    ||    ||  
  ||    ||    ||  
  01    ||    ||  
  04    ||    02  
  05    ||    03  
_/||\__/||\__/||\_

Move from 0 --> 2

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    01  
  04    ||    02  
  05    ||    03  
_/||\__/||\__/||\_

Move from 0 --> 1

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    01  
  ||    ||    02  
  05    04    03  
_/||\__/||\__/||\_

Move from 2 --> 1

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    ||  
  ||    01    02  
  05    04    03  
_/||\__/||\__/||\_

Move from 2 --> 0

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    ||  
  02    01    ||  
  05    04    03  
_/||\__/||\__/||\_

Move from 1 --> 0

  ||    ||    ||  
  ||    ||    ||  
  01    ||    ||  
  02    ||    ||  
  05    04    03  
_/||\__/||\__/||\_

Move from 2 --> 1

  ||    ||    ||  
  ||    ||    ||  
  01    ||    ||  
  02    03    ||  
  05    04    ||  
_/||\__/||\__/||\_

Move from 0 --> 2

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    ||  
  02    03    ||  
  05    04    01  
_/||\__/||\__/||\_

Move from 0 --> 1

  ||    ||    ||  
  ||    ||    ||  
  ||    02    ||  
  ||    03    ||  
  05    04    01  
_/||\__/||\__/||\_

Move from 2 --> 1

  ||    ||    ||  
  ||    01    ||  
  ||    02    ||  
  ||    03    ||  
  05    04    ||  
_/||\__/||\__/||\_

Move from 0 --> 2

  ||    ||    ||  
  ||    01    ||  
  ||    02    ||  
  ||    03    ||  
  ||    04    05  
_/||\__/||\__/||\_

Move from 1 --> 0

  ||    ||    ||  
  ||    ||    ||  
  ||    02    ||  
  ||    03    ||  
  01    04    05  
_/||\__/||\__/||\_

Move from 1 --> 2

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    ||  
  ||    03    02  
  01    04    05  
_/||\__/||\__/||\_

Move from 0 --> 2

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    01  
  ||    03    02  
  ||    04    05  
_/||\__/||\__/||\_

Move from 1 --> 0

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    01  
  ||    ||    02  
  03    04    05  
_/||\__/||\__/||\_

Move from 2 --> 1

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    ||  
  ||    01    02  
  03    04    05  
_/||\__/||\__/||\_

Move from 2 --> 0

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    ||  
  02    01    ||  
  03    04    05  
_/||\__/||\__/||\_

Move from 1 --> 0

  ||    ||    ||  
  ||    ||    ||  
  01    ||    ||  
  02    ||    ||  
  03    04    05  
_/||\__/||\__/||\_

Move from 1 --> 2

  ||    ||    ||  
  ||    ||    ||  
  01    ||    ||  
  02    ||    04  
  03    ||    05  
_/||\__/||\__/||\_

Move from 0 --> 2

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    01  
  02    ||    04  
  03    ||    05  
_/||\__/||\__/||\_

Move from 0 --> 1

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    01  
  ||    ||    04  
  03    02    05  
_/||\__/||\__/||\_

Move from 2 --> 1

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    ||  
  ||    01    04  
  03    02    05  
_/||\__/||\__/||\_

Move from 0 --> 2

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    03  
  ||    01    04  
  ||    02    05  
_/||\__/||\__/||\_

Move from 1 --> 0

  ||    ||    ||  
  ||    ||    ||  
  ||    ||    03  
  ||    ||    04  
  01    02    05  
_/||\__/||\__/||\_

Move from 1 --> 2

  ||    ||    ||  
  ||    ||    02  
  ||    ||    03  
  ||    ||    04  
  01    ||    05  
_/||\__/||\__/||\_

Move from 0 --> 2

  ||    ||    01  
  ||    ||    02  
  ||    ||    03  
  ||    ||    04  
  ||    ||    05  
_/||\__/||\__/||\_