9
\$\begingroup\$

I recently made a boggle solver in Rust to compensate for the fact that I'm really bad at boggle. This has also been a good Rust learning experience. The code does what it's supposed to quite well but it is a bit slow, even when compiling with the -O flag. Since I'm new to Rust, I'm not sure where the slow spots could be. I'm using a hashset to lookup the words, so I assume the lookup isn't the bottleneck. Any tips? (Also, if I'm doing any kind of bad practice, you can let me know). Thanks.

use std::collections::HashSet;
use std::fs;

const MAX_WORD_LEN: usize = 12;


#[derive(Clone, Debug, Copy)]
struct Coordinate {
    row: i64,
    col: i64
}


impl Coordinate {
    // Returns a new coordinate if the move is valid. None otherwise.
    fn move_c(&self, a: i64, b: i64, h: i64, w: i64) -> Option<Coordinate> {
        let h_range = 0..h;
        let w_range = 0..w;
        if h_range.contains(&(self.row + a)) && w_range.contains(&(self.col + b)) {
            Some(Coordinate {row: self.row + a, col: self.col + b}) 
        } 
        else {
            None
        } 
    }
}

impl PartialEq for Coordinate {
    fn eq(&self, other: &Self) -> bool {
        self.row == other.row && self.col == other.col
    } 
}


fn boggle_solve(grid: &Vec<Vec<char>>, dict: &HashSet<String>) {
    for (i, row) in grid.iter().enumerate() {
        for (j, ch) in row.iter().enumerate() {
            boggle_solve_help(grid, dict, ch.to_string(), Coordinate{row: i as i64, col: j as i64}, vec![Coordinate{row: i as i64, col: j as i64}])
        }
    }

}


fn boggle_solve_help(grid: &Vec<Vec<char>>, dict: &HashSet<String>, word: String, c: Coordinate, path: Vec<Coordinate>) {
    // Base case.
    // No more work if the string is long enough
    if word.len() > MAX_WORD_LEN {
        return;
    }

    if word.len() > 3 && dict.contains(&word) {
        println!("{}", word);
    }

    // For every possible direction the path can take, if it is valid, take it.
    for a in -1..=1 {
        for b in -1..=1 {
           match c.move_c(a, b, grid.len() as i64, grid[0].len() as i64) {

                Some(new_c) if !path.contains(&new_c) => {
                    let mut new_path = path.clone();
                    new_path.push(new_c);
                    let new_word = format!("{}{}", &word, &grid[new_c.row as usize][new_c.col as usize]);

                    boggle_solve_help(grid, dict, new_word, new_c, new_path);
                },

                Some(_) => (),

                None => ()

           } 
        }
    } 
}

fn main() {
    let contents = fs::read_to_string("words_alpha.txt").unwrap();
    let dict: HashSet<String> = contents.split_whitespace().map(|s| s.to_string()).collect();

    let grid: Vec<Vec<char>> = vec![
        vec!['c', 's', 't', 'e', 't'],
        vec!['a', 'i', 'r', 'l', 's'],
        vec!['p', 'd', 'a', 'e', 's'],
        vec!['u', 'e', 'c', 's', 'e'],
        vec!['r', 'o', 't', 'r', 'i']
    ];

    boggle_solve(&grid, &dict)

}


\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

The main thing that's going to get you a speed boost is returning early from the search if there's no word that starts with what you have so far.

One simple way to do this is to keep a HashSet of all the prefixes of words in the dictionary. Or, better yet, a HashMap where the value indicates whether the prefix is actually a word or not.

struct PrefixMap<'a>(HashMap<&'a str, bool>);

impl<'a> PrefixMap<'a> {
    fn new(words: impl IntoIterator<Item = &'a str>) -> Self {
        let mut map = HashMap::new();
        for word in words {
            // note that this gets every prefix except the whole word
            for (ending, _) in word.char_indices() {
                map.entry(&word[..ending]).or_insert(false);
            }
            map.insert(word, true);
        }
        Self(map)
    }

    fn is_word(&self, word: &str) -> bool {
        self.0.get(word).copied().unwrap_or(false)
    }

    fn is_prefix(&self, prefix: &str) -> bool {
        self.0.contains_key(prefix)
    }
}

Then, in the first part of boggle_solve_help, we can use is_word and is_prefix to determine whether to print the word or return early.

if !dict.is_prefix(&word) {
    return;
}

if word.len() > 3 && dict.is_word(&word) {
    println!("{}", word);
}

While this isn't the most efficient thing possible, that simple step makes the program run almost instantly on my computer (less than a second). If you still want to improve more, look up tries for a memory efficient and quick way to do the same thing. Since creating the index of words takes a little while, you might try to cache it between runs using serde or something similar.


Now for some more suggestions.

  1. Derive PartialEq. Right now you implement PartialEq for Coordinate manually, but the same implementation can be done by adding PartialEq to the derive attribute.

  2. Use descriptive variable names. The main offenders are the arguments to move_c and later on c in boggle_solve_help. I know sometimes this is annoying, but even just changing a and b to dy and dx (calculus shorthand for "change in y/x") makes everything clearer. It's probably worth spelling out height and width to make it clear that that's what you mean.

  3. Don't forget to use cargo fmt. It's a simple step and will instantly make your code more standardized and easier to read for other Rust programmers.

  4. Encapsulate the grid into its own type. Right now, you're using Vec<Vec<char>> directly, which is fine, but means that lots of annoying details are strewn about the functions that use it. The type can still be Vec<Vec<char>> under the surface, but having a method like grid.get(coordinate) rather than grid[coordinate.row as usize][coordinate.col as usize] makes things easier to read and make sense of. As a plus, this will also silence Clippy's complaint about using &Vec<_> instead of &[_].

  5. Consider switching to an iterative algorithm. You won't run into stack overflow here since you have a hard cap on how deep the recursion can go. Still, if you want a slightly faster algorithm, a depth-first search can be memory efficient and avoid the repeated String allocations you currently have (with format!).

  6. Bonus: don't show duplicate words. Right now, a word will be duplicated if can be spelled with a different path of letters on the board. For example, "trees" can be written three different ways near the bottom right corner of the board so it gets printed 3 times. It also shows up in a few other places. I might suggest keeping a HashSet of all the words you've found so far to eliminate duplicates.

Here's the code after applying the early return and the first three of my suggestions. I'll let you figure out the other two.

use std::collections::HashMap;
use std::fs;

const MAX_WORD_LEN: usize = 12;

#[derive(Clone, Debug, Copy, PartialEq)]
struct Coordinate {
    row: i64,
    col: i64,
}

impl Coordinate {
    // Returns a new coordinate if the move is valid. None otherwise.
    fn move_coord(&self, dy: i64, dx: i64, height: i64, width: i64) -> Option<Coordinate> {
        let height_range = 0..height;
        let width_range = 0..width;
        if height_range.contains(&(self.row + dy)) && width_range.contains(&(self.col + dx)) {
            Some(Coordinate {
                row: self.row + dy,
                col: self.col + dx,
            })
        } else {
            None
        }
    }
}

// Keys consist of all prefixes of words
// Values say whether the prefix is a word
// Since we keep references rather than `String`s,
// the lifetime of the map can't exceed the lifetime of wherever
// the `&str`s come from.
// If you decide to make this more persistent, using `String` rather than `&str`
// might be appropriate.
struct PrefixMap<'a>(HashMap<&'a str, bool>);

impl<'a> PrefixMap<'a> {
    // We can produce this from any iterator of `&str`s.
    fn new(words: impl IntoIterator<Item = &'a str>) -> Self {
        let mut map = HashMap::new();
        for word in words {
            // note that this gets every prefix except the whole word
            for (ending, _) in word.char_indices() {
                map.entry(&word[..ending]).or_insert(false);
            }
            map.insert(word, true);
        }
        Self(map)
    }

    fn is_word(&self, word: &str) -> bool {
        self.0.get(word).copied().unwrap_or(false)
    }

    fn is_prefix(&self, prefix: &str) -> bool {
        self.0.contains_key(prefix)
    }
}

fn boggle_solve(grid: &Vec<Vec<char>>, dict: &PrefixMap) {
    for (i, row) in grid.iter().enumerate() {
        for (j, ch) in row.iter().enumerate() {
            boggle_solve_help(
                grid,
                dict,
                ch.to_string(),
                Coordinate {
                    row: i as i64,
                    col: j as i64,
                },
                vec![Coordinate {
                    row: i as i64,
                    col: j as i64,
                }],
            )
        }
    }
}

fn boggle_solve_help(
    grid: &Vec<Vec<char>>,
    dict: &PrefixMap,
    word: String,
    coord: Coordinate,
    path: Vec<Coordinate>,
) {
    // Base case.
    // No more work if the string is long enough
    if word.len() > MAX_WORD_LEN {
        return;
    }

    if !dict.is_prefix(&word) {
        return;
    }

    if word.len() > 3 && dict.is_word(&word) {
        println!("{}", word);
    }

    // For every possible direction the path can take, if it is valid, take it.
    for dy in -1..=1 {
        for dx in -1..=1 {
            match coord.move_coord(dy, dx, grid.len() as i64, grid[0].len() as i64) {
                Some(new_coord) if !path.contains(&new_coord) => {
                    let mut new_path = path.clone();
                    new_path.push(new_coord);
                    let new_word = format!(
                        "{}{}",
                        &word, &grid[new_coord.row as usize][new_coord.col as usize]
                    );

                    boggle_solve_help(grid, dict, new_word, new_coord, new_path);
                }

                Some(_) => (),

                None => (),
            }
        }
    }
}

fn main() {
    let contents = fs::read_to_string("words_alpha.txt").unwrap();
    let dict = PrefixMap::new(contents.split_whitespace());

    let grid: Vec<Vec<char>> = vec![
        vec!['c', 's', 't', 'e', 't'],
        vec!['a', 'i', 'r', 'l', 's'],
        vec!['p', 'd', 'a', 'e', 's'],
        vec!['u', 'e', 'c', 's', 'e'],
        vec!['r', 'o', 't', 'r', 'i'],
    ];

    boggle_solve(&grid, &dict)
}

(playground - but note that words_alpha.txt doesn't exist, so you can't run it)

\$\endgroup\$
1
  • \$\begingroup\$ Brilliant! Thank you! I realized that a lot of time was wasted on paths that could never become words as they went along, so killing them early should be a good idea. Thanks for the other suggestions, too. \$\endgroup\$
    – tcallred
    Commented Dec 31, 2019 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.