lib_wpsr/boxed/solution/
letters_boxed.rs

1use std::collections::VecDeque;
2
3mod edge;
4mod shuffle;
5mod weighted_word;
6
7use edge::Edge;
8use rand::{SeedableRng, seq::SliceRandom};
9use rand_chacha::ChaCha20Rng;
10pub use shuffle::Shuffle;
11use weighted_word::WeightedWord;
12
13use crate::Error;
14
15#[derive(Debug)]
16pub struct LettersBoxed {
17    letters: Vec<char>,
18    words: Vec<String>,
19    invalid_pairs: Vec<(char, char)>,
20    word_chain: Vec<String>,
21    edges: Vec<Edge>,
22    max_chain: Option<usize>,
23    shuffle_depth: Option<i8>,
24}
25
26impl Default for LettersBoxed {
27    fn default() -> Self {
28        let letters = vec!['o', 'u', 'h', 'i', 'm', 'a', 'g', 'p', 'l', 'r', 'y', 'f'];
29        let edges = vec![
30            Edge::new('o', 'u', 'h'),
31            Edge::new('i', 'm', 'a'),
32            Edge::new('g', 'p', 'l'),
33            Edge::new('r', 'y', 'f'),
34        ];
35        Self {
36            letters,
37            words: Vec::new(),
38            invalid_pairs: Vec::new(),
39            word_chain: Vec::new(),
40            edges,
41            max_chain: None,
42            shuffle_depth: None,
43        }
44    }
45}
46
47impl LettersBoxed {
48    pub fn new(letters: &[char], words: &[String]) -> Self {
49        let mut s = Self::default();
50        if !letters.is_empty() {
51            s.letters = Vec::from(letters);
52            s.generate_edges();
53        }
54        if !words.is_empty() {
55            s.words = Vec::from(words);
56        }
57
58        s
59    }
60
61    pub fn set_max_chain(&mut self, value: usize) -> &mut Self {
62        self.max_chain = Some(value);
63        self
64    }
65
66    pub fn set_shuffle_depth(&mut self, value: i8) -> &mut Self {
67        self.shuffle_depth = Some(value);
68        self
69    }
70
71    #[tracing::instrument(skip(self))]
72    pub fn filter_words_with_letters_only(&mut self) -> &mut Self {
73        let filtered = self
74            .words
75            .iter()
76            .filter(|word| word.chars().all(|c| self.letters.contains(&c)))
77            .map(|w| w.to_string())
78            .collect::<Vec<String>>();
79
80        tracing::info!("Filtered to {} words", filtered.len());
81        self.words = filtered;
82        self
83    }
84
85    #[tracing::instrument(skip(self))]
86    fn generate_edges(&mut self) -> &mut Self {
87        let mut deque = VecDeque::from(self.letters.clone());
88
89        let mut edges = Vec::new();
90
91        while !deque.is_empty() {
92            let edge = Edge::new(
93                deque.pop_front().unwrap(),
94                deque.pop_front().unwrap(),
95                deque.pop_front().unwrap(),
96            );
97
98            edges.push(edge);
99        }
100
101        self.edges = edges;
102
103        self
104    }
105
106    #[tracing::instrument(skip(self))]
107    fn generate_invalid_pairs(&mut self) -> &mut Self {
108        let mut invalid_pairs = Vec::new();
109        for edge in self.edges.iter() {
110            for pair in edge.pairs() {
111                if !self.invalid_pairs.contains(&pair) {
112                    invalid_pairs.push(pair);
113                }
114            }
115        }
116
117        tracing::debug!("Generated {} invalid pairs", invalid_pairs.len());
118        tracing::trace!("Invalid pairs: {:#?}", invalid_pairs);
119        self.invalid_pairs = invalid_pairs;
120
121        self
122    }
123
124    #[tracing::instrument(skip(self))]
125    pub fn filter_exclude_invalid_pairs(&mut self) -> &mut Self {
126        self.generate_invalid_pairs();
127
128        let filtered = self
129            .words
130            .iter()
131            .filter(|word| {
132                let chars = word.chars().collect::<Vec<char>>();
133                let mut a = chars[0];
134                for b in chars.iter().skip(1) {
135                    if self.invalid_pairs.contains(&(a, *b))
136                        || self.invalid_pairs.contains(&(*b, a))
137                    {
138                        return false;
139                    }
140                    a = *b;
141                }
142                true
143            })
144            .map(|w| w.to_string())
145            .collect::<Vec<String>>();
146
147        tracing::info!("Filtered to {} words", filtered.len());
148        self.words = filtered;
149        self
150    }
151
152    #[tracing::instrument(skip(self, shuffle))]
153    pub fn build_word_chain(&mut self, shuffle: &mut Shuffle) -> Result<(), Error> {
154        tracing::info!("Building word chain");
155        // Get the first word from the list of words
156        let mut rng = ChaCha20Rng::from_os_rng();
157        let all_words = self.words.clone();
158        let words_list = all_words.clone();
159        let word_chain = Vec::new();
160        let unused_letters = String::from_iter(self.letters.clone());
161        let shuffle_depth = self.shuffle_depth.unwrap_or(-1);
162
163        let word_chain = get_word(
164            all_words,
165            words_list,
166            word_chain,
167            unused_letters,
168            &mut rng,
169            shuffle,
170            self.max_chain,
171            shuffle_depth,
172        )?;
173
174        self.word_chain = word_chain;
175        Ok(())
176    }
177
178    #[tracing::instrument(skip(self))]
179    pub fn solution_string(&self) -> String {
180        self.word_chain.join(" -> ").to_string()
181    }
182
183    #[tracing::instrument(skip(self))]
184    pub fn chain_length(&self) -> usize {
185        self.word_chain.len()
186    }
187}
188
189#[allow(clippy::too_many_arguments)]
190#[tracing::instrument(skip(
191    all_words,
192    words_list,
193    word_chain,
194    unused_letters,
195    rng,
196    shuffle,
197    max_chain,
198    shuffle_depth
199))]
200pub fn get_word(
201    all_words: Vec<String>,
202    mut words_list: Vec<String>,
203    mut word_chain: Vec<String>,
204    mut unused_letters: String,
205    rng: &mut ChaCha20Rng,
206    shuffle: &mut Shuffle,
207    max_chain: Option<usize>,
208    mut shuffle_depth: i8,
209) -> Result<Vec<String>, Error> {
210    let initial_unused_letters = unused_letters.clone();
211    tracing::trace!("Starting word chain: {}", word_chain.join(" -> "));
212    tracing::trace!(
213        "Shuffle set to: {} and word list length: {}",
214        shuffle,
215        words_list.len()
216    );
217
218    // Shuffle the starting words list to get a random starting word
219    if shuffle == &Shuffle::Twice {
220        tracing::debug!("Shuffling words list.");
221        words_list.shuffle(rng);
222    }
223    let mut words_list = words_list
224        .iter()
225        .map(|word| WeightedWord::new(word.clone(), unused_letters.clone()))
226        .collect::<Vec<WeightedWord>>();
227    words_list.sort_by_key(|ww| ww.weight);
228    let words_list = words_list
229        .iter()
230        .rev()
231        .map(|ww| ww.word.to_string())
232        .collect::<Vec<String>>();
233
234    // shuffle the top of to the words list to randomize the first word while keeping a good weight
235    let mut words = if shuffle != &Shuffle::None && shuffle_depth != 0 {
236        tracing::debug!("Shuffling top half of weighted words list.");
237        let words_list = shuffle_top_half(words_list, rng);
238        VecDeque::from(words_list)
239    } else {
240        VecDeque::from(words_list)
241    };
242
243    // find a word that increases the letters used
244
245    loop {
246        tracing::trace!(
247            "List of {} words starting with: {:?}",
248            words.len(),
249            words.front()
250        );
251        let Some(word) = words.pop_front() else {
252            return Err(Error::NoWordFound);
253        };
254
255        let letter_count = &unused_letters.len();
256        tracing::trace!("Letters unused before check: {}", unused_letters);
257        for letter in word.chars() {
258            if let Some(idx) = unused_letters.find(letter) {
259                unused_letters.remove(idx);
260            }
261        }
262        tracing::trace!("Letters unused after check: {}", unused_letters);
263
264        // if all of the letters are used then we have the final word chain
265        if unused_letters.is_empty() {
266            word_chain.push(word);
267            break;
268        }
269        tracing::trace!(
270            "Still {} letters unused: {}",
271            unused_letters.len(),
272            unused_letters
273        );
274
275        // if the word extends the chain add it to the chain and start again
276        if unused_letters.len() < *letter_count {
277            if let Some(max_chain) = max_chain {
278                if word_chain.len() >= max_chain {
279                    return Err(Error::ChainTooLong);
280                }
281            }
282            let mut next_word_chain = word_chain.clone();
283            let next_unused_letters = unused_letters.clone();
284            let next_all_words = all_words.clone();
285            let last_letter = word.chars().last().unwrap();
286            let words_list = all_words
287                .iter()
288                .filter(|w| w.chars().next().unwrap() == last_letter)
289                .map(|w| w.to_string())
290                .collect::<Vec<String>>();
291            if words.is_empty() {
292                return Err(Error::NoWordFound);
293            }
294            next_word_chain.push(word);
295            if shuffle_depth > 0 {
296                shuffle_depth -= 1;
297            }
298            match get_word(
299                next_all_words,
300                words_list,
301                next_word_chain,
302                next_unused_letters,
303                rng,
304                shuffle,
305                max_chain,
306                shuffle_depth,
307            ) {
308                Ok(chain) => {
309                    word_chain = chain;
310                    break;
311                }
312                Err(e) => {
313                    tracing::debug!("No word found, resetting");
314                    if e == Error::ChainTooLong {
315                        return Err(e);
316                    }
317                    unused_letters = initial_unused_letters.clone();
318                    continue;
319                }
320            };
321        }
322    }
323
324    tracing::debug!("Current word chain: {}", word_chain.join("-"));
325
326    Ok(word_chain)
327}
328
329fn shuffle_top_half(mut words: Vec<String>, rng: &mut ChaCha20Rng) -> Vec<String> {
330    let half_len = words.len() / 2;
331    let mut top_half = words.drain(..half_len).collect::<Vec<String>>();
332    let bottom_half = words.iter().map(|w| w.to_string()).collect::<Vec<String>>();
333    top_half.shuffle(rng);
334    top_half.extend(bottom_half);
335    top_half
336}
337
338#[cfg(test)]
339mod tests {
340    use std::vec;
341
342    use super::*;
343    #[test]
344    fn test_filter_words_with_letters_only() {
345        let letters = vec!['o', 'u', 'h', 'i', 'd', 'a', 'g', 'e', 'l', 'r', 'y', 'w'];
346        let words = vec![
347            "hello".to_string(),
348            "world".to_string(),
349            "foo".to_string(),
350            "bar".to_string(),
351            "baz".to_string(),
352        ];
353
354        let mut letters_boxed = LettersBoxed::new(&letters, &words);
355        letters_boxed.filter_words_with_letters_only();
356        assert_eq!(letters_boxed.words.len(), 2);
357        assert_eq!(letters_boxed.words[0], "hello".to_string());
358        assert_eq!(letters_boxed.words[1], "world".to_string());
359    }
360
361    #[test]
362    fn test_filter_words_with_invalid_pairs() {
363        let letters = vec!['o', 'u', 'm', 'i', 'd', 'a', 'g', 'e', 'l', 'r', 'y', 'w'];
364        let words = vec![
365            "embolden".to_string(),
366            "world".to_string(),
367            "foo".to_string(),
368            "dire".to_string(),
369            "glow".to_string(),
370            "game".to_string(),
371            "quux".to_string(),
372            "corse".to_string(),
373            "gaunt".to_string(),
374            "grape".to_string(),
375            "waldo".to_string(),
376            "fred".to_string(),
377        ];
378
379        let mut letters_boxed = LettersBoxed::new(&letters, &words);
380
381        println!("{:#?}", letters_boxed.edges);
382
383        letters_boxed.filter_words_with_letters_only();
384        println!("{:#?}", letters_boxed.words);
385
386        letters_boxed.filter_exclude_invalid_pairs();
387        println!("{:#?}", letters_boxed.words);
388
389        assert_eq!(letters_boxed.words.len(), 3);
390        assert_eq!(letters_boxed.words[0], "world".to_string());
391        assert_eq!(letters_boxed.words[1], "game".to_string());
392        assert_eq!(letters_boxed.words[2], "waldo".to_string());
393    }
394
395    #[test]
396    fn test_shuffle_top_half() {
397        let words = vec![
398            "hello".to_string(),
399            "world".to_string(),
400            "foo".to_string(),
401            "bar".to_string(),
402            "baz".to_string(),
403        ];
404        println!("before: {words:?}");
405        let mut rng = ChaCha20Rng::seed_from_u64(1);
406        let shuffled = shuffle_top_half(words, &mut rng);
407        println!("after: {shuffled:?}");
408        assert_eq!(shuffled.len(), 5);
409        assert_eq!(shuffled[0], "world".to_string());
410        assert_eq!(shuffled[1], "hello".to_string());
411        assert_eq!(shuffled[2], "foo".to_string());
412        assert_eq!(shuffled[3], "bar".to_string());
413        assert_eq!(shuffled[4], "baz".to_string());
414    }
415}
lib_wpsr/boxed/solution/letters_boxed.rs

lib_wpsr/boxed/solution/
letters_boxed.rs
