Boggle solver

boggle.rs

#![allow(dead_code)]

use std::path::posix::Path;
use std::io::fs::File;
use std::io::{BufferedReader, Reader, stdin};
use std::vec::Vec;
use std::collections::{Set, HashSet, MutableSet, Bitv};
use std::cmp::{min, max};

type Grid = Vec<String>;

struct Trie {
    children: [Option<Box<Trie>>, .. 26],
    is_word: bool
}

impl Trie {
    pub fn new() -> Trie {
        Trie{
            children: [None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None],
            is_word: false,
        }
    }

    pub fn add(&mut self, string: &str) {
        if string.len() == 0 {
            self.is_word = true;
            return
        }

        let offset = to_index(string.char_at(0));

        if self.children[offset].is_none() {
            self.children[offset] = Some(box Trie::new())
        }

        self.children[offset].as_mut().unwrap().add(string.slice_from(1))
    }

    pub fn contains(&self, string: &str) -> bool {
        if string.len() == 0 {
            return self.is_word
        }

        let offset = to_index(string.char_at(0));

        match self.children[offset].as_ref() {
            Some(child) => child.contains(string.slice_from(1)),
            None => false
        }
    }

    fn _find_words(&self, visited: &mut Bitv, grid: &Grid, words: &mut MutableSet<String>, word_buffer: &mut Vec<char>, x: uint, y: uint) {
        if self.is_word {
            words.insert(word_buffer.iter().map(|c| c.clone()).collect());
        }

        for x2 in range(max(x as int - 1, 0) as uint, min(x + 2, grid.len())) {
            for y2 in range(max(y as int - 1, 0) as uint, min(y + 2, grid.len())) {
                if (x2 == x && y2 == y) || visited.get(x2 * grid.len() + y2) {
                    continue
                }
                let c = (*grid)[y2].as_slice().char_at(x2);

                self.children[to_index(c)].as_ref().map(|child| {
                    word_buffer.push(c);
                    visited.set(x * grid.len() + y, true);

                    child._find_words(visited, grid, words, word_buffer, x2, y2);

                    visited.set(x * grid.len() + y, false);
                    word_buffer.pop();
                });
            }
        }
    }

    pub fn find_words(&self, grid: &Grid) -> HashSet<String> {
        let mut words = HashSet::new();
        let size = grid.len();
        let mut word_buffer: Vec<char> = Vec::new();
        let mut visited = Bitv::with_capacity(size * size, false);

        for y in range(0, size) {
            for x in range(0, size) {
                self._find_words(&mut visited, grid, &mut words, &mut word_buffer, x, y);
            }
        }

        words
    }
}

fn to_index(c: char) -> uint {
    let u = c.to_lowercase() as uint;

    if u >= 'a' as uint && u <= 'z' as uint {
        u - 'a' as uint
    } else {
        fail!("Invalid character '{}'!", c)
    }
}

fn get_line<T: Reader>(input: &mut BufferedReader<T>) -> String {
    input.read_line().ok().unwrap().as_slice().trim().to_string()
}

fn main() {
    let mut trie = Trie::new();

    {
        let f = File::open(&Path::new("/usr/share/dict/words")).ok().expect("Dictionary not found!");
        let reader = &mut BufferedReader::new(f);

        for line in reader.lines() {
            let word = line.as_ref().ok().expect("Failed to read line!").as_slice().trim();
            if word.len() > 1 && !word.contains_char('-') {
                trie.add(word)
            }
        }
    }

    let mut grid: Grid = Vec::new();
    let mut input = stdin();

    grid.push(get_line(&mut input));

    let size = grid[0].len();
    for _ in range(1, size) {
        let line = get_line(&mut input);
        assert_eq!(size, line.len());
        grid.push(line)
    }

    let mut words: Vec<String> = trie.find_words(&grid).into_iter().collect();

    words.sort_by(|a, b|
        match b.len().cmp(&a.len()) {
            Equal => a.cmp(b),
            other => other,
        }
    );

    for word in words.slice_to(min(words.len(), 20)).iter() {
        println!("{}", word)
    }
}

example.md

$ ./boggle-solver
nalokiaelplfxpyuoqys
maddgtcgydjmtjczxbbk
ozgasdbfeepjspbmgaid
ggubcbeibqtxzedawqjn
qnvwodnibiiqxbzzlrff
palhpputezlileuxhhqb
qqxwkqzbmtjwsjbxjxkc
fcdthnyyujeeuhkiotju
fczntfinidwkfcvzhohx
kgrfcblrqtwcazokxpui
zztywrefniwdkupesdxz
frvrlyxfhqmsivlmeldo
urfvruastdfuacnyfxlb
lcxyorhogauidanhblge
gkmteuxcnhegokvcqsoe
pqafermzjtfwxgaxdylu
ffbqzioxaygtjvlbljdj
pxzbviurhelbwffdubgh
zleqokjeoibccyrbbffx
mjtgxhpdklkwedyhidap

definitude
inquietude
bobbinite
cobdenite
analogic
caodaism
cosharer
definite
feretory
finitude
humorize
obbenite
quietude
undefied
whodunit
antheia
beliked
belleek
bivouac
bleared