rust astar experiments

astar-room-search.rs

extern crate astar; // from https://github.com/mboeh/astar.git

use std::vec::MoveItems;

#[deriving(Eq)]
#[deriving(Hash)]
struct Room<'a> {
    id: int,
    difficulty: int,
    exits: Vec<&'a Room<'a>>
}

impl<'a> PartialEq for Room<'a> {
    fn eq(&self, other: &Room<'a>) -> bool { self.id == other.id }
}

// Can I make std::iter::Counter<int> an Iterator instead? If so, how?
fn room<'a>(ids: &mut std::iter::Counter<int>, exits: Vec<&'a Room<'a>>) -> Room<'a> {
    Room{
        id: ids.next().expect("no more ids"), 
        difficulty: 1,
        exits: exits
    }
}

struct RoomSearch<'a> {
    start: &'a Room<'a>,
    end: &'a Room<'a>
}

// Is all of this lifetime annotation really necessary?
impl<'a> astar::SearchProblem<&'a Room<'a>, int, MoveItems<(&'a Room<'a>, int)>> for RoomSearch<'a> {
    fn start<'b>(&self) -> &'b Room<'a> { self.start }
    fn is_end<'b>(&self, room: &'b &Room<'a>) -> bool { *room == self.end }
    fn heuristic<'b>(&self, room: &'b &Room<'a>) -> int {
        if *room == self.end { 0 }
        else { room.difficulty }
    }
    fn neighbors<'b>(&self, at: &'b &Room<'a>) -> MoveItems<(&'a Room<'a>, int)> {
        let mut v  = vec![];
        for r in at.exits.iter() {
            v.push((*r, r.difficulty))
        }
        v.into_iter()
    }
}

fn main() {
    let mut ids : std::iter::Counter<int> = std::iter::count(1,1);
    let ext = &room(&mut ids, vec![]);
    let r0 = &room(&mut ids, vec![]);
    let r1 = &room(&mut ids, vec![ext]);
    let r2 = &room(&mut ids, vec![r0, r1]);
    let ent = &room(&mut ids, vec![r0, r2]);
    let search = RoomSearch{start: ent, end: ext};
    match astar::astar(search) {
        Some(path) => {
                        for room in path.iter() {
                            println!("room = {}", room.id)
                        }
                      },
        None    => { println!("No path") }
    }
}

astar-string-jumble.rs

#![feature(slicing_syntax)]

extern crate astar; // from https://github.com/mboeh/astar.git

use std::vec::MoveItems;

struct StringJuggler<'a> {
    start: &'a str,
    end: &'a str
}

impl<'a> StringJuggler<'a> {
    fn juggle(&self) -> Option<std::collections::ring_buf::RingBuf<String>> {
        if !self.is_completeable() { return None }
        astar::astar(*self)
    }
    fn is_completeable(&self) -> bool {
        let mut fbytes = self.start.to_string().into_bytes();
        let mut tbytes = self.end.to_string().into_bytes();
        tbytes.sort();
        fbytes.sort();

        fbytes == tbytes
    }
}

impl<'a> astar::SearchProblem<String, int, MoveItems<(String, int)>> for StringJuggler<'a> {
    fn start(&self) -> String { self.start.to_string() }
    fn is_end(&self, at: &String) -> bool { at.as_slice() == self.end }
    fn heuristic(&self, at: &String) -> int {
        self.start.lev_distance(at.as_slice()) as int
    }
    fn neighbors(&self, at: &String) -> MoveItems<(String, int)> {
        let mut v  = vec![];

        for i in range(0, at.len()-1) {
            let mut permut = at[0..i].to_string();
            permut.push_str(at[i+1..i+2]);
            permut.push_str(at[i..i+1]);
            permut.push_str(at[i+2..]);

            let dist = self.end.lev_distance(permut[]) as int;

            v.push((permut, dist));
        }
        v.into_iter()
    }
}

fn main() {
    let args = std::os::args();
    let from = args[1][];
    let to = args[2][];
    
    let search = StringJuggler{
        start: from,
        end: to,
    };
    
    println!("Juggling from {} to {}:", search.start, search.end);
    match search.juggle() {
        Some(path) => {
                        for (i,word) in path.iter().enumerate() {
                            println!("{}. {}", i+1, word)
                        }
                      },
        None    => { println!("No path") }
    }
}

/*** example:
% cargo run bacon ncboa
     Running `target/astar-string-jumble bacon ncboa`
Juggling from bacon to ncboa:
1. bacon
2. bcaon
3. bcoan
4. bcona
5. bcnoa
6. bncoa
7. nbcoa
8. ncboa
*/