{"id":5832,"date":"2021-04-07T07:00:34","date_gmt":"2021-04-07T14:00:34","guid":{"rendered":"http:\/\/writeasync.net\/?p=5832"},"modified":"2021-04-07T09:16:38","modified_gmt":"2021-04-07T16:16:38","slug":"letter-boxed-rust-impl-part-4-complete-solver","status":"publish","type":"post","link":"http:\/\/writeasync.net\/?p=5832","title":{"rendered":"Letter Boxed: Rust impl, part 4 (complete solver)"},"content":{"rendered":"

After some incremental progress in our Letter Boxed solver<\/a>, we’re now ready to complete the app.<\/p>\n

Our hard-won “expertise” in Rust now makes the last several steps largely mechanical. The first set of changes produces LetterBox<\/code> and Vertices<\/code> structs, so that we can parse the actual Letter Boxed puzzle<\/a>:<\/p>\n

\r\npub struct Vertices(u16);\r\n\r\nimpl Index<u8> for Vertices {\r\n    type Output = bool;\r\n\r\n    fn index(&self, index: u8) -> &Self::Output {\r\n        match (self.0 >> index) & 0x1 {\r\n            0 => &false,\r\n            _ => &true,\r\n        }\r\n    }\r\n}\r\n\r\nimpl Add for Vertices {\r\n    type Output = Vertices;\r\n\r\n    fn add(self, rhs: Self) -> Self::Output {\r\n        Vertices(self.0 | rhs.0)\r\n    }\r\n}\r\n\r\nimpl Display for Vertices {\r\n    fn fmt(&self, f: &mut Formatter) -> fmt::Result {\r\n        write!(f, "{:012b}", self.0)\r\n    }\r\n}\r\n\r\npub struct LetterBox(St);\r\n\r\nimpl LetterBox {\r\n    pub fn new(b: St) -> LetterBox {\r\n        if b.len() != 12 {\r\n            panic!("Out of range");\r\n        }\r\n\r\n        LetterBox(b)\r\n    }\r\n\r\n    fn next(&self, index: u8) -> Vertices {\r\n        match index {\r\n            0 | 1 | 2 => Vertices(0b111111111000),\r\n            3 | 4 | 5 => Vertices(0b111111000111),\r\n            6 | 7 | 8 => Vertices(0b111000111111),\r\n            9 | 10 | 11 => Vertices(0b000111111111),\r\n            _ => panic!("Out of range"),\r\n        }\r\n    }\r\n}\r\n\r\nimpl Display for LetterBox {\r\n    fn fmt(&self, f: &mut Formatter) -> fmt::Result {\r\n        self.0.fmt(f)\r\n    }\r\n}\r\n\r\nimpl Index<u8> for LetterBox {\r\n    type Output = Ch;\r\n\r\n    fn index(&self, index: u8) -> &Self::Output {\r\n        &self.0[index]\r\n    }\r\n}\r\n<\/pre>\n
Yes, it is true that Rust has a crate for supporting bit vectors<\/a>, which would perhaps render Vertices<\/code> redundant. But we’ll go with a hand-rolled version for now, to match the C# solver implementation.<\/p>\n
Next, we need the data and algorithms for searching for words, and thus, solving the puzzle. We’ll start with the LetterBoxWords<\/code> collection, and its private implementation detail Word<\/code>:<\/p>\n
\r\n#[derive(Eq, PartialEq)]\r\nstruct Word {\r\n    word: St,\r\n    verts: Vertices,\r\n}\r\n\r\nimpl Word {\r\n    fn last(&self) -> Ch {\r\n        self.word[self.word.len() - 1]\r\n    }\r\n\r\n    fn is_solution_with(&self, other: &Word) -> bool {\r\n        let v = self.verts + other.verts;\r\n        v.is_complete()\r\n    }\r\n}\r\n\r\nimpl Hash for Word {\r\n    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {\r\n        self.word.hash(state)\r\n    }\r\n}\r\n\r\npub struct LetterBoxWords {\r\n    words: HashMap<Ch, HashSet<Word>>,\r\n    count: usize,\r\n}\r\n\r\nimpl LetterBoxWords {\r\n    fn new() -> LetterBoxWords {\r\n        let words = HashMap::new();\r\n        let count = 0;\r\n        LetterBoxWords { words, count }\r\n    }\r\n\r\n    fn insert(&mut self, word: St, verts: Vertices) {\r\n        let k = word[0];\r\n        let w = Word { word, verts };\r\n        if let Some(v) = self.words.get_mut(&k) {\r\n            if v.insert(w) {\r\n                self.count += 1;\r\n            }\r\n        } else {\r\n            let mut v = HashSet::new();\r\n            v.insert(w);\r\n            self.words.insert(k, v);\r\n            self.count += 1;\r\n        }\r\n    }\r\n\r\n    fn find<F>(&self, mut found: F)\r\n    where\r\n        F: FnMut(St, St),\r\n    {\r\n        for w1 in self.words.values().flat_map(|v| v) {\r\n            if let Some(v) = self.words.get(&w1.last()) {\r\n                for w2 in v {\r\n                    if w1.is_solution_with(&w2) {\r\n                        found(w1.word, w2.word);\r\n                    }\r\n                }\r\n            }\r\n        }\r\n    }\r\n\r\n    fn len(&self) -> usize {\r\n        self.count\r\n    }\r\n}\r\n<\/pre>\n
Let’s pause for a few observations. Only LetterBoxWords<\/code> is public here which makes Word<\/code> akin to a private inner type<\/a> in the C# version. We also see usage of flat_map<\/a> as the equivalent of LINQ SelectMany<\/a>.<\/p>\n
At last, we are almost done. Since Rust allows non-member functions<\/a> (AKA “free functions<\/a>“) directly at the module level, we can finish off the search<\/code> module with a search(...)<\/code> function. No ceremony or artificial class wrappers here:<\/p>\n
\r\npub fn search<F>(trie: &StTrie, b: LetterBox, mut found: F)\r\nwhere\r\n    F: FnMut(St, Vertices),\r\n{\r\n    for v1 in 0..12 {\r\n        let c = b[v1];\r\n        let verts = Vertices::new(1 << v1);\r\n        search_next(St::empty() + c, v1, verts, &trie, &b, &mut found);\r\n    }\r\n}\r\n\r\nfn search_next<F>(str: St, v1: u8, verts: Vertices, trie: &StTrie, b: &LetterBox, found: &mut F)\r\nwhere\r\n    F: FnMut(St, Vertices),\r\n{\r\n    let kind = trie.find(str);\r\n    if kind == NodeKind::None {\r\n        return;\r\n    }\r\n\r\n    if kind == NodeKind::Terminal {\r\n        found(str, verts);\r\n    }\r\n\r\n    if str.len() == 12 {\r\n        return;\r\n    }\r\n\r\n    let next = b.next(v1);\r\n    for v2 in 0..12 {\r\n        if next[v2] {\r\n            let c = b[v2];\r\n            let next_verts = verts + Vertices::new(1 << v2);\r\n            search_next(str + c, v2, next_verts, &trie, b, found);\r\n        }\r\n    }\r\n}\r\n<\/pre>\n
In both code snippets there is an FnMut<\/code> type constraint<\/a>, essentially allowing us to pass any closure we want with any capture mode<\/a>. In practice, we’ll use LetterBoxWords<\/code> in the search<\/code> closure<\/a>, and a simple println!<\/code> macro in the LetterBoxWords::find<\/code> closure<\/a>. Here is the final Rust solver app:<\/p>\n
\r\nuse letter_boxed_solver::{\r\n    core::{LetterBox, St},\r\n    search::{LetterBoxWords, search},\r\n    trie::StTrie\r\n};\r\nuse std::{env::args, fs::File, time::Instant};\r\n\r\nfn main() {\r\n    let start = Instant::now();\r\n    let args: Vec<String> = args().skip(1).collect();\r\n    if args.len() != 2 {\r\n        println!("Please specify a Letter Boxed puzzle and a word list file.");\r\n        return;\r\n    }\r\n\r\n    let b = LetterBox::new(args[0].parse::<St>().unwrap());\r\n\r\n    log(start, "Loading trie...");\r\n    let mut stream = File::open(&args[1]).unwrap();\r\n    let trie = StTrie::load(&mut stream);\r\n    log(start, format!("Loaded {} words.", trie.len()).as_str());\r\n\r\n    let mut words = LetterBoxWords::new();\r\n\r\n    log(start, "Finding valid words...");\r\n    search(&trie, b, |w, v| words.insert(w, v));\r\n    log(start, format!("Found {} valid words.", words.len()).as_str());\r\n\r\n    log(start, "Finding solutions...");\r\n    words.find(|w1, w2| println!("{}-{}", w1, w2));\r\n\r\n    log(start, "Done.");\r\n}\r\n\r\nfn log(start: Instant, message: &str) {\r\n    println!("[{:07.3}] {}", start.elapsed().as_secs_f64(), message);\r\n}\r\n<\/pre>\n
Was it all worth it? Let’s check the timing results for our two benchmark puzzles:<\/p>\n
\r\n> letter_boxed_solver.exe RMEWCLTGKAPI words.txt\r\n[000.000] Loading trie...\r\n[000.039] Loaded 162309 words.\r\n[000.039] Finding valid words...\r\n[000.042] Found 754 valid words.\r\n[000.042] Finding solutions...\r\nMARKETPLACE-EARWIG\r\nWIGWAM-MARKETPLACE\r\nPRAGMATIC-CAKEWALK\r\n[000.044] Done.\r\n\r\n> letter_boxed_solver.exe ERGBIDNCFTAO words.txt\r\n[000.000] Loading trie...\r\n[000.039] Loaded 162309 words.\r\n[000.039] Finding valid words...\r\n[000.043] Found 1436 valid words.\r\n[000.043] Finding solutions...\r\nDOGCART-TENEBRIFIC\r\n -- snipped 72 other solutions --\r\nNONBRAND-DEFECTING\r\n[000.072] Done.\r\n<\/pre>\n
That’s right, the Rust implementation is at least 10% faster than the best C++ benchmark<\/a>. Thanks, Rust — you’ve more than earned that oh-so-rare unqualified success<\/strong> badge!<\/p>\n","protected":false},"excerpt":{"rendered":"
After some incremental progress in our Letter Boxed solver, we’re now ready to complete the app. Our hard-won “expertise” in Rust now makes the last several steps largely mechanical. The first set of changes produces LetterBox and Vertices structs, so… <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[91,101,41],"tags":[],"class_list":["post-5832","post","type-post","status-publish","format-standard","hentry","category-design","category-native","category-tdd"],"_links":{"self":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5832","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5832"}],"version-history":[{"count":2,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5832\/revisions"}],"predecessor-version":[{"id":5834,"href":"http:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5832\/revisions\/5834"}],"wp:attachment":[{"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5832"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5832"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5832"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}