boggle_maker/
boggle_dfs.rs

1use word_trie::trie::{Trie,TrieNode};
2
3/// gets the word score 
4pub fn get_word_score(word: &str) -> u32{
5    let len = word.len();
6    match len {
7        3 => 1,
8        4 => 1,
9        5 => 2,
10        6 => 3,
11        7 => 5,
12        _ if len >= 8 => 11,
13        _ => 0,
14    }
15}
16
17/// The boggle dfs context struct.
18#[derive(Debug, Clone)]
19pub struct BoggleDfsContext<'a> {
20    dictionary: &'a Trie,
21    length: usize,
22    width: usize,
23}
24
25impl <'a> BoggleDfsContext<'a> {
26    /// initiate a new boggle dfs context.
27    pub fn new(dictionary : &'a Trie, width:usize, length:usize)->Self{
28        Self{
29            dictionary,
30            length,
31            width,
32        }
33    }
34
35    /// get boggle board's width
36    pub fn width(&self) -> usize {
37        self.width
38    }
39
40    /// get boggle board's length
41    pub fn length(&self) -> usize {
42        self.length
43    }
44
45    /// gets the trie for the boggle board dfs
46    pub fn dictionary(&self) -> &'a Trie {
47        self.dictionary
48    }
49
50    /// gets the boggle board characters count.
51    pub fn count(&self) -> usize {
52        self.width * self.length
53    }
54}
55
56/// The word visitor trait 
57pub trait WordVisitor {
58    fn visit(&mut self, word: &str, path: &Vec<u16>);    
59}
60
61/// The boggle DFS struct
62pub struct BoggleDfs<'a> {    
63    context: &'a BoggleDfsContext<'a>,
64    visitors: Vec<&'a mut dyn WordVisitor>,
65    visited: Vec<bool>,
66    current: String,
67    board: &'a Vec<char>,
68    path: Vec<u16>,
69}
70
71impl<'a> BoggleDfs<'a>{
72    ///initiate a new boggle dfs instance
73    pub fn new(context : &'a BoggleDfsContext<'a>,board: &'a Vec<char>) -> Self {
74        let visited = vec![false; context.count()];
75        let current = String::new();
76        let path = Vec::new();
77        Self{
78            context,
79            visitors: Vec::new(),
80            visited,
81            current,
82            board,
83            path,
84        }
85    }
86
87    /// add a visitor to be triggered on dfs result found events
88    pub fn with_visitor(&mut self, visitor: &'a mut dyn WordVisitor) -> &mut Self{
89        self.visitors.push(visitor);
90
91        self
92    }
93
94    /// trigger the dfs search
95    pub fn search(&mut self){   
96        for i in 0..self.context.width {
97            for j in 0..self.context.length {
98                self.dfs(&self.context.dictionary().root, i, j);
99            }
100        }
101    }
102
103    fn dfs(&mut self,mut node: &TrieNode ,x: usize,y: usize)
104    {        
105        let cell_index = x * self.context.width() + y;
106        //if the board's current cell is visited then return.
107        if self.visited[cell_index] {
108            return;
109        }
110        
111        //mark the current board's cell as visited
112        self.visited[cell_index] = true;
113        let ch = self.cell_value(cell_index);
114        
115        //check if the trie has this node
116        let ch_index = ch.to_ascii_lowercase();        
117        match node.nodes.get(&ch_index){
118            Some(next_node) => node = next_node,
119            None => {
120                //if the trie current node does not have the board's current cell's letter then revert the status and return 
121                self.visited[cell_index] = false;
122                return;
123            },
124        }
125        //add current cell's letter to the current word
126        self.current.push(ch);
127        self.path.push(cell_index as u16);
128
129        //check if the current word is a valid word in the dictionary 
130        if node.is_word { 
131            self.visit();    
132        }
133
134        //Recursively check all neighbour cells 
135        for (a,b) in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]{
136            let next_x = x as i8 + a;
137            let next_y = y as i8 + b;
138            if (0..self.context.width() as i8).contains(&next_x) && (0..self.context.length() as i8).contains(&next_y){
139                self.dfs(node, next_x as usize, next_y as usize); 
140            }           
141        }
142
143        //Remove current visited cell letter from current word end.
144        self.current.pop();
145        self.path.pop();
146
147        //mark the current cell as not visited 
148        self.visited[cell_index] = false;      
149    }
150
151    fn visit(&mut self) {
152        // this part needs to be enhanced to use async 
153        for visitor in self.visitors.iter_mut() {
154            visitor.visit(&self.current, &self.path);    
155        } 
156    }
157
158    fn cell_value(&self, index: usize) -> char {
159        self.board[index]
160    }
161}
boggle_maker/boggle_dfs.rs

boggle_maker/
boggle_dfs.rs
