boggle solver

boggle.rs

use std::io::{BufReader, BufRead, Error};
use std::io;
use std::cmp;
use std::fs::File;
use std::collections::HashSet;

extern crate core;

struct TrieDict {
    word : Option<String>,
    children : Vec<(char, Box<TrieDict>)>
}

impl TrieDict {
    fn new() -> TrieDict {
        TrieDict { word : None,
                   children: Vec::new() }
    }   

    fn insert(&mut self, chars : &[char], word : &str) {
        if let Some((first, rest)) = chars.split_first() {
            let i = match self.children.binary_search_by(|t| t.0.cmp(first)) {
                Err(i) => {
                    let ch = Box::new(TrieDict::new());
                    self.children.insert(i, (*first, ch));
                    i   
                },  
                Ok(i) => i
            };  
            let mut sub = self.children.get_mut(i).unwrap().1.as_mut();
            sub.insert(rest, word);
        } else {
            self.word = Some(word.to_owned());
        }   
    }   

    fn descend(&self, idx : char) -> Option<&TrieDict> {
        if let Ok(i) = self.children.binary_search_by(|t| t.0.cmp(&idx)) {
            let t = self.children.get(i).expect("Bad Trie Vec");
            Some(t.1.as_ref())
        } else {
            None
        }   
    }   
}

fn sanitize(word : &String) -> Option<Vec<char>> {
    let mut vec = Vec::with_capacity(word.len());
    for c in word.chars() {
        if let Some(c) = c.to_lowercase().next() {
            vec.push(c);
        } else {
            return None;
        }
    }
    return Some(vec);
}

fn read_dict (fname : &str) -> Result<TrieDict, Error> {
    let f = try!(File::open(fname));
    let reader = BufReader::new(f);

    let mut trie = TrieDict::new();

    for line in reader.lines() {
        let l = try!(line);
        let s = l.to_owned();
        match sanitize(&l) {
            None => (),
            Some(v) => trie.insert(v.as_slice(), &s)
        };
    }

    Ok(trie)
}
fn solve(board : &Vec<Vec<char>>, (r, c) : (i32, i32), visited : i32,
         trie: &TrieDict, words : & mut HashSet<String>) {

    let visited = visited | 1 << (4 * r + c);

    trie.word.clone().map(|w| words.insert(w));

    for r in cmp::max(0,r-1)..cmp::min(4,r+2) {
        for c in cmp::max(0,c-1)..cmp::min(4,c+2) {
            if visited & 1 << (4 * r + c) != 0 { continue; }
            let ch = board.get(r as usize).and_then(|row| row.get(c as usize)).
                expect("Invalid board");
            match *ch {
                'q' => trie.descend('q').and_then(|t| t.descend('u')),
                ch => trie.descend(ch)
            }.map(|sub| solve(board, (r,c), visited, sub, words));
        }
    }

}

fn solver(trie : &TrieDict, board : &Vec<Vec<char>>) -> HashSet<String> {
    let mut ret = HashSet::new();

    for r in 0..4 {
        for c in 0..4 {
            solve(board, (r, c), 0, trie, & mut ret);
        }
    }

    ret
}

fn main() {
    let trie = read_dict("american.dict").unwrap();

    let mut board = Vec::new();
    for _ in 0..4 {
        let mut line = String::new();

        io::stdin().read_line(&mut line)
            .expect("Failed to read a line.");
        line.pop();
        let v = sanitize(&line).expect("Failed to sanitize board.");
        board.push(v);
    }

    for word in solver(&trie, &board) {
        println!("{}", word);
    }
}