boggle_maker/
simple_genetic_boggle_maker.rs

1use crate::boggle_board::Board;
2use word_trie::trie::{Trie,TrieNode};
3use rand::Rng;
4use rand::distr::{Distribution, Uniform};
5use std::collections::{HashSet,HashMap};
6
7pub struct GeneticBoard{
8    board:Board,
9    age:u32,
10    score:usize,
11}
12
13impl GeneticBoard{
14    pub fn get_board(dictionary:&Trie, minimum_score:usize, board_x:usize,board_y:usize)->Board{
15        const POPULATION_SIZE:usize = 10;
16        let mut choromosomes : Vec<GeneticBoard> = Self::init_population(dictionary,POPULATION_SIZE, board_x, board_y);
17
18        let mut generation = 0;
19        loop{
20            
21            //stop mating if the minimum requiremet is met.
22            if let Some(x) = choromosomes.first() {
23                println!("hello board, genetic generated : {} : {} : {}", x.board.hash(),x.age,x.score);
24                if x.score > minimum_score || generation>20 {
25                    return x.board.copy();
26                }
27            }
28
29            choromosomes = Self::evolve_population(dictionary,POPULATION_SIZE,&choromosomes);
30            generation+=1;
31        }
32
33    }
34
35    // fn tournament_select(choromosomes : &Vec<GeneticBoard>, uniform: &Uniform<u32>, rng: &mut impl Rng)->usize{
36    //     let mut a = uniform.sample(&mut rng);
37    //     for i in 0..4 {
38    //         let b = uniform.sample(&mut rng);
39    //         if choromosomes[b].score > choromosomes[a].score {
40    //             a = b;
41    //         }
42    //     }
43    //     return a;
44    // }
45    fn evolve_population(dictionary:&Trie,size:usize, prev_generation : &Vec<GeneticBoard>) -> Vec<GeneticBoard>{
46        let mut choromosomes : Vec<GeneticBoard> = Vec::new();
47        let new_borns : HashSet<String> = HashSet::new();
48        let uniform = Uniform::try_from(0..size).unwrap();
49        let mut rng = rand::rng();
50        while choromosomes.len() < size*10 {            
51            let mut a;
52            {
53                a = uniform.sample(&mut rng);
54                for _i in 0..1 {
55                    let c = uniform.sample(&mut rng);
56                    if prev_generation[c].score > prev_generation[a].score {
57                        a = c;
58                    }
59                }
60            }
61            let mut b = a;
62            while b==a {
63                b = uniform.sample(&mut rng);
64                for _i in 0..1 {
65                    let c = uniform.sample(&mut rng);
66                    if prev_generation[c].score > prev_generation[b].score {
67                        b = c;
68                    }
69                }
70            }
71
72            //let b = Self::tournament_select(prev_generation, &between,&mut rng);
73            let mut born = prev_generation[a].merge(&prev_generation[b]);
74            let key = born.board.hash();
75            if new_borns.contains(&key) {
76                continue;
77            }
78            born.score = Self::get_board_score(dictionary,&born.board);
79            choromosomes.push(born);
80        }
81        for i in 0..1 {
82            if let Some(x) = prev_generation.get(i) {
83                let key = x.board.hash();
84                if !new_borns.contains(&key) {                
85                    choromosomes.push(Self{
86                        board:x.board.copy(),
87                        age:x.age,
88                        score:x.score
89                    });
90                }
91            }
92        }
93
94        choromosomes.sort_by(|a,b| b.score.cmp(&a.score));
95        choromosomes.truncate(size);
96
97        choromosomes
98    }
99    fn init_population(dictionary:&Trie,size:usize, board_x:usize,board_y:usize) -> Vec<GeneticBoard>{
100        let mut choromosomes : Vec<GeneticBoard> = Vec::new();
101        let mut new_borns = HashSet::new();
102        while new_borns.len()<size {
103            let brd = Board::new_random(board_x,board_y);
104            let key = brd.hash();
105            if new_borns.contains(&key) {
106                continue;
107            }
108            let score = Self::get_board_score(dictionary,&brd);
109
110            let gen_board = Self{
111                board:brd,
112                age:0,
113                score:score
114            };
115            new_borns.insert(key);
116            choromosomes.push(gen_board);
117        }
118        choromosomes.sort_by(|a,b| b.score.cmp(&a.score));
119
120        choromosomes
121    }
122
123    fn merge(&self, other : &GeneticBoard) -> Self {
124        let boards = Self::order(&self,other);
125
126        let mut merged = Self{
127            board:boards.0.board.copy(),
128            age:boards.0.age+1,
129            score:0
130        };
131
132        let similarity = Self::similarity(&boards.0.board,&boards.1.board);
133
134        let first_share = if similarity < 0.80 { 70 } else { 70 };
135        let second_share = if similarity < 0.80 { 99 } else { 80 };
136
137        let uniform = Uniform::try_from(0..101).unwrap();
138        let uniform2 = Uniform::try_from(0..26).unwrap();
139        let mut rng = rand::rng();
140
141        for i in 0..boards.0.board.width() {
142            for j in 0..boards.0.board.length() {
143                let rand = uniform.sample(&mut rng);
144                if rand < first_share {continue;}//the board cell can stay the initilized value.
145                else if rand < second_share {merged.board.set(i,j,boards.1.board.get(i,j).expect("must have value always"));} // get chromosoms from the second board
146                else {
147                    //mutate
148                    let rnd = uniform2.sample(&mut rng);
149                    let random_char = (b'A' + rnd) as char;
150                    merged.board.set(i,j,random_char);
151                }
152            }
153        }        
154        
155        merged
156    }
157
158    //this function's return type contains a borrowed value, but the signature does not say whether it is borrowed from `this` or `that`
159    //help: consider introducing a named lifetime parameter
160    fn order<'a>(this: &'a GeneticBoard,that: &'a GeneticBoard)->(&'a GeneticBoard,&'a GeneticBoard){
161        if this.score>that.score { return (this,that); }
162        if this.score<that.score { return (that,this); }
163        let mut rng = rand::rng();
164        let rnd = rng.random_range(0..=1);
165        if rnd==0 { return (this,that);}
166        (that,this)
167    }
168
169    fn similarity(this:&Board, that:&Board) -> f32{
170        let mut same:f32 = 0.0;
171        for i in 0..this.width() {
172            for j in 0..this.length() {
173                let ch1 = this.get(i,j).expect("must have value always");
174                let ch2 = that.get(i,j).expect("must have value always");
175                if ch1==ch2 { same+=1.0;}
176            }
177        }
178        same/(this.width() as f32 * this.length() as f32)
179    }
180
181    /// gets the score of a boggle board.
182    ///
183    /// # Examples
184    ///
185    /// ```
186    /// use word_trie::TrieBuilder;
187    /// use boggle_maker::Board;
188    /// let trie = TrieBuilder::new()
189    /// .from_file("words.txt")
190    /// .expect("Failed to load trie from file");
191    ///
192    /// //SERSPATGLINESERS
193    /// let sample = Board::new(
194    ///         vec!['S','E','R','S','P','A','T','G','L','I','N','E','S','E','R','S']
195    ///         ,4,4, None);
196    /// //SOTGPRNSEAIESTTL
197    /// let sample2 = Board::new(
198    ///     vec!['S','O','T','G','P','R','N','S','E','A','I','E','S','T','T','L']
199    ///     ,4,4,None);
200    /// // let score = get_board_score(&trie,&sample);
201    /// //assert!(score>3999);
202    /// //let score = get_board_score(&trie,&sample2);
203    /// //assert!(score>3999);
204    /// ```
205    fn get_board_score(dictionary:&Trie,brd:&Board) -> usize{         
206        let mut set = HashMap::new();
207        let mut visited = HashMap::new(); 
208
209        let mut current = String::new();
210        for i in 0..brd.width(){
211            for j in 0..brd.length(){
212                Self::get_board_score_from(&dictionary.root,brd,&mut set,&mut visited,i,j,&mut current);
213            }
214        }
215
216        let mut score = 0;
217
218        for (_, val) in &set {
219            score += val;
220        }
221
222        score
223    }
224
225    fn get_board_score_from(mut node:&TrieNode ,
226            brd:&Board,
227            set:&mut HashMap<String,usize>,
228            visited:&mut HashMap<usize,bool>,
229            x:usize,
230            y:usize,
231            current:&mut String
232        ){
233        
234        let cell_index = x*brd.width() + y;
235        let is_visited = visited.entry(cell_index).or_insert(false);
236        //if the board's current cell is visited then return.
237        if *is_visited {
238            return;
239        }
240        
241        //mark the current board's cell as visited
242        *is_visited = true;
243        let ch = brd.get(x,y).expect("the board must has value in all cells");
244        
245        //check if the trie has this node
246        let ch_index = ch.to_ascii_lowercase();        
247        match node.nodes.get(&ch_index){
248            Some(next_node) => node = next_node,
249            None => {
250                //if the trie current node does not have the board's current cell's letter then revert the status and return 
251                visited.insert(cell_index,false);
252                return;
253            },
254        }
255        //add current cell's letter to the current word
256        current.push(ch);
257
258        //check if the current word is a valid word in the dictionary 
259        //if yes then check if it's not been added to the result set yet
260        //if not added then add it to the result set with a proper calculated score
261        if node.is_word && !set.contains_key(current) {                
262            set.insert(current.to_string(),Self::get_score(current.len()));
263        }
264
265        //Recursively check all neighbour cells 
266        for (a,b) in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]{
267            let next_x = x as i8 + a;
268            let next_y = y as i8 + b;
269            if (0..brd.width() as i8).contains(&next_x) && (0..brd.length() as i8).contains(&next_y){
270                Self::get_board_score_from(node,brd, set, visited,next_x as usize,next_y as usize, current); 
271            }           
272        }
273
274        //Remove current visited cell letter from current word end.
275        current.pop();
276
277        //mark the current cell as not visited 
278        visited.insert(cell_index,false);        
279    }
280
281    fn get_score(len:usize)->usize{
282        match len{
283            0..=2 => 0,
284            3..=4 => 1,
285            5 => 2,
286            6 => 3,
287            7 => 5,
288            _ => 11
289        }
290    }
291}
boggle_maker/simple_genetic_boggle_maker.rs

boggle_maker/
simple_genetic_boggle_maker.rs
