wordle_solver/
solver.rs

1use lazy_static::lazy_static;
2//use std::borrow::Borrow;
3use itertools::Itertools;
4use std::cell::RefCell;
5use std::collections::{BTreeSet, HashMap, HashSet};
6use std::error;
7use std::fmt;
8use std::hash::Hash;
9
10lazy_static! {
11    static ref EMPTYSET: HashSet<&'static String> = HashSet::new();
12}
13
14struct ScoredString<'a> {
15    s: &'a String,
16    score: f64,
17}
18
19// See https://stackoverflow.com/questions/70978841/lifetime-in-mutable-structure-with-hashset/70979198#70979198
20// impl Borrow<str> for ScoredString<'_>{
21//     fn borrow(&self) -> &str {
22//         self.s
23//     }
24// }
25
26impl<'a> ScoredString<'a> {
27    fn new(s: &'a String, score: f64) -> ScoredString<'a> {
28        ScoredString { s, score }
29    }
30}
31impl Eq for ScoredString<'_> {}
32impl Hash for ScoredString<'_> {
33    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
34        self.s.hash(state);
35    }
36}
37impl PartialEq for ScoredString<'_> {
38    fn eq(&self, other: &Self) -> bool {
39        self.s == other.s
40    }
41}
42impl PartialOrd for ScoredString<'_> {
43    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
44        Some(self.cmp(other))
45    }
46}
47impl Ord for ScoredString<'_> {
48    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
49        if self.score > other.score {
50            std::cmp::Ordering::Greater
51        } else {
52            std::cmp::Ordering::Less
53        }
54    }
55}
56
57/// A wordle solver build from a dictionary
58pub struct Solver<'a> {
59    candidates: RefCell<BTreeSet<ScoredString<'a>>>,
60    exists_letters: RefCell<HashSet<char>>,
61    by_letter: HashMap<char, HashSet<&'a String>>,
62    by_letter_position: HashMap<(char, usize), HashSet<&'a String>>,
63}
64
65/// A convenience struct to give a hint about
66/// a letter in the given position
67#[derive(Clone)]
68pub struct Hint {
69    pub hint: HintType,
70    pub letter: char,
71    pub position: usize,
72}
73
74/// The nature of the hint given by wordle
75#[derive(Clone, PartialEq)]
76pub enum HintType {
77    WellPlaced,
78    Exists,
79    Invalid,
80}
81
82#[derive(Debug)]
83pub enum HintParseError {
84    InvalidCode(String),
85}
86impl fmt::Display for HintParseError {
87    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
88        write!(f, "Cannot parse hint '{:?}'", self)
89    }
90}
91impl error::Error for HintParseError {}
92
93impl std::str::FromStr for HintType {
94    type Err = HintParseError;
95    fn from_str(s: &str) -> Result<Self, Self::Err> {
96        match s {
97            "x" => Ok(HintType::Invalid),
98            "e" => Ok(HintType::Exists),
99            "g" => Ok(HintType::WellPlaced),
100            _ => Err(HintParseError::InvalidCode(s.to_string())),
101        }
102    }
103}
104
105fn word_score(w: &str, lf: &HashMap<char, i32>) -> f64 {
106    w.chars()
107        .unique()
108        .flat_map(|c| lf.get(&c))
109        .map(|n| (*n as f64).log10())
110        .sum()
111}
112
113impl<'a> Solver<'a> {
114    /// Builds a new Solver
115    /// # Example
116    /// ```
117    ///  use std::collections::HashSet;
118    ///  use wordle_solver::solver::Solver;
119    ///
120    ///  let dictionary = ["class", "clock"].iter().map(|&s| String::from(s))
121    ///                   .collect::<HashSet<String>>();
122    ///  let solver = Solver::new(&dictionary);
123    /// ```
124    pub fn new(dictionary: &HashSet<String>) -> Solver {
125        let letter_freq =
126            dictionary
127                .iter()
128                .flat_map(|w| w.chars())
129                .fold(HashMap::new(), |mut m, c| {
130                    *m.entry(c).or_insert(0) += 1;
131                    m
132                });
133
134        let score_of = |s| word_score(s, &letter_freq);
135
136        let candidates = dictionary
137            .iter()
138            .map(|s| ScoredString::new(s, score_of(s)))
139            .collect();
140
141        let by_letter = dictionary.iter().fold(HashMap::new(), |mut h, v| {
142            for c in v.chars() {
143                let entry = h.entry(c).or_insert_with(HashSet::new);
144                entry.insert(v);
145            }
146            h
147        });
148        let by_letter_position = dictionary.iter().fold(HashMap::new(), |mut h, v| {
149            for (p, c) in v.chars().enumerate() {
150                let entry = h.entry((c, p)).or_insert_with(HashSet::new);
151                entry.insert(v);
152            }
153            h
154        });
155        let exists_letters = HashSet::new();
156        Solver {
157            candidates: RefCell::new(candidates),
158            exists_letters: RefCell::new(exists_letters),
159            by_letter,
160            by_letter_position,
161        }
162    }
163
164    /// The current size of the words candidates pool
165    pub fn n_candidates(&self) -> usize {
166        self.candidates.borrow().len()
167    }
168
169    /// The first candidate. Try this in wordle
170    ///
171    /// This is updated after each hint (see `add_hint`), so the more hints
172    /// you give, the more likely this first candidate will win
173    /// the game.
174    ///
175    /// If you give inconsistent hints, this might return `none`.
176    pub fn first_candidate(&self) -> Option<&String> {
177        return self.candidates.borrow().iter().rev().next().map(|v| {
178            println!("Candidate {} score: {}", v.s, v.score);
179            v.s
180        });
181    }
182
183    fn with_letter(&self, l: &char) -> &HashSet<&String> {
184        self.by_letter.get(l).unwrap_or(&EMPTYSET)
185    }
186    fn with_letter_in_position(&self, l: &char, p: &usize) -> &HashSet<&String> {
187        self.by_letter_position.get(&(*l, *p)).unwrap_or(&EMPTYSET)
188    }
189
190    /// Ingests a bunch of Hints together,
191    /// ensuring logical consistency between them.
192    pub fn ingest_hints(&mut self, fhs: Vec<Hint>) {
193        let (valid, invalid): (Vec<_>, Vec<_>) =
194            fhs.iter().partition(|&h| h.hint != HintType::Invalid);
195        for fh in valid {
196            self.add_hint(fh.clone());
197        }
198        for fh in invalid {
199            self.add_hint(fh.clone());
200        }
201    }
202
203    /// Just add one Hint
204    pub fn add_hint(&mut self, fh: Hint) {
205        match fh.hint {
206            HintType::WellPlaced => self.add_well_placed(&fh.letter, &fh.position),
207            HintType::Exists => self.add_exists(&fh.letter, &fh.position),
208            HintType::Invalid => self.add_invalid(&fh.letter),
209        }
210    }
211
212    /// In case you dont want to use the Hint struct
213    pub fn add_raw_hint(&mut self, l: &char, p: &usize, h: HintType) {
214        self.add_hint(Hint {
215            hint: h,
216            letter: *l,
217            position: *p,
218        })
219    }
220
221    fn add_well_placed(&self, l: &char, p: &usize) {
222        //println!("Restricting to words containing an {} at position {}" , l, p);
223        let to_retain = self.with_letter_in_position(l, p).clone();
224        self.candidates
225            .borrow_mut()
226            .retain(|s| to_retain.contains(s.s));
227        self.exists_letters.borrow_mut().insert(*l);
228    }
229
230    fn add_exists(&self, l: &char, p: &usize) {
231        //println!("Restricting to words containing an {}" , l);
232
233        let to_retain = self.with_letter(l).clone();
234        self.candidates
235            .borrow_mut()
236            .retain(|s| to_retain.contains(s.s));
237
238        //println!("Removing words with an {} at position {}" , l, p);
239        let to_remove = self.with_letter_in_position(l, p).clone();
240        self.candidates
241            .borrow_mut()
242            .retain(|s| !to_remove.contains(s.s));
243        self.exists_letters.borrow_mut().insert(*l);
244    }
245
246    fn add_invalid(&self, l: &char) {
247        if self.exists_letters.borrow().contains(l) {
248            println!(
249                "This letter {} has been hinted as existing already. Not removing it.",
250                l
251            );
252        } else {
253            //println!("Removing words with an {}" , l);
254            let to_remove = self.with_letter(l).clone();
255            self.candidates
256                .borrow_mut()
257                .retain(|s| !to_remove.contains(s.s));
258        }
259    }
260}
261
262impl<'a> Solver<'a> {
263    /// Some words might be in your dictionary but not
264    /// in wordle. Use this to discard them
265    pub fn discard_word(&self, s: &str) {
266        let mut candidates = self.candidates.borrow_mut();
267        candidates.retain(|ss| !ss.s.eq(s))
268    }
269}
270
271#[cfg(test)]
272mod tests {
273    use super::*;
274    #[test]
275    fn build_solver() {
276        let words: HashSet<String> = vec![String::from("boudin"), String::from("blanc")]
277            .into_iter()
278            .collect();
279        let solver = Solver::new(&words);
280        let llen = |l| solver.with_letter(l).len();
281        let lplen = |l, p| solver.with_letter_in_position(l, p).len();
282
283        assert!(solver.first_candidate().is_some());
284        assert_eq!(llen(&'b'), 2);
285        assert_eq!(llen(&'o'), 1);
286        assert_eq!(llen(&'u'), 1);
287        assert_eq!(llen(&'d'), 1);
288        assert_eq!(llen(&'i'), 1);
289        assert_eq!(llen(&'n'), 2);
290
291        assert_eq!(llen(&'l'), 1);
292        assert_eq!(llen(&'a'), 1);
293        assert_eq!(llen(&'c'), 1);
294        assert_eq!(llen(&'z'), 0);
295
296        assert_eq!(lplen(&'b', &0), 2);
297        assert_eq!(lplen(&'o', &0), 0);
298        assert_eq!(lplen(&'o', &1), 1);
299        assert_eq!(lplen(&'u', &1), 0);
300        assert_eq!(lplen(&'u', &2), 1);
301    }
302}
wordle_solver/solver.rs

wordle_solver/
solver.rs
