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 that we can parse the actual Letter Boxed puzzle:
pub struct Vertices(u16);
impl Index<u8> for Vertices {
type Output = bool;
fn index(&self, index: u8) -> &Self::Output {
match (self.0 >> index) & 0x1 {
0 => &false,
_ => &true,
}
}
}
impl Add for Vertices {
type Output = Vertices;
fn add(self, rhs: Self) -> Self::Output {
Vertices(self.0 | rhs.0)
}
}
impl Display for Vertices {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
write!(f, "{:012b}", self.0)
}
}
pub struct LetterBox(St);
impl LetterBox {
pub fn new(b: St) -> LetterBox {
if b.len() != 12 {
panic!("Out of range");
}
LetterBox(b)
}
fn next(&self, index: u8) -> Vertices {
match index {
0 | 1 | 2 => Vertices(0b111111111000),
3 | 4 | 5 => Vertices(0b111111000111),
6 | 7 | 8 => Vertices(0b111000111111),
9 | 10 | 11 => Vertices(0b000111111111),
_ => panic!("Out of range"),
}
}
}
impl Display for LetterBox {
fn fmt(&self, f: &mut Formatter) -> fmt::Result {
self.0.fmt(f)
}
}
impl Index<u8> for LetterBox {
type Output = Ch;
fn index(&self, index: u8) -> &Self::Output {
&self.0[index]
}
}
Yes, it is true that Rust has a crate for supporting bit vectors, which would perhaps render Vertices redundant. But we’ll go with a hand-rolled version for now, to match the C# solver implementation.
Next, we need the data and algorithms for searching for words, and thus, solving the puzzle. We’ll start with the LetterBoxWords collection, and its private implementation detail Word:
#[derive(Eq, PartialEq)]
struct Word {
word: St,
verts: Vertices,
}
impl Word {
fn last(&self) -> Ch {
self.word[self.word.len() - 1]
}
fn is_solution_with(&self, other: &Word) -> bool {
let v = self.verts + other.verts;
v.is_complete()
}
}
impl Hash for Word {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
self.word.hash(state)
}
}
pub struct LetterBoxWords {
words: HashMap<Ch, HashSet<Word>>,
count: usize,
}
impl LetterBoxWords {
fn new() -> LetterBoxWords {
let words = HashMap::new();
let count = 0;
LetterBoxWords { words, count }
}
fn insert(&mut self, word: St, verts: Vertices) {
let k = word[0];
let w = Word { word, verts };
if let Some(v) = self.words.get_mut(&k) {
if v.insert(w) {
self.count += 1;
}
} else {
let mut v = HashSet::new();
v.insert(w);
self.words.insert(k, v);
self.count += 1;
}
}
fn find<F>(&self, mut found: F)
where
F: FnMut(St, St),
{
for w1 in self.words.values().flat_map(|v| v) {
if let Some(v) = self.words.get(&w1.last()) {
for w2 in v {
if w1.is_solution_with(&w2) {
found(w1.word, w2.word);
}
}
}
}
}
fn len(&self) -> usize {
self.count
}
}
Let’s pause for a few observations. Only LetterBoxWords is public here which makes Word akin to a private inner type in the C# version. We also see usage of flat_map as the equivalent of LINQ SelectMany.
At last, we are almost done. Since Rust allows non-member functions (AKA “free functions“) directly at the module level, we can finish off the search module with a search(...) function. No ceremony or artificial class wrappers here:
pub fn search<F>(trie: &StTrie, b: LetterBox, mut found: F)
where
F: FnMut(St, Vertices),
{
for v1 in 0..12 {
let c = b[v1];
let verts = Vertices::new(1 << v1);
search_next(St::empty() + c, v1, verts, &trie, &b, &mut found);
}
}
fn search_next<F>(str: St, v1: u8, verts: Vertices, trie: &StTrie, b: &LetterBox, found: &mut F)
where
F: FnMut(St, Vertices),
{
let kind = trie.find(str);
if kind == NodeKind::None {
return;
}
if kind == NodeKind::Terminal {
found(str, verts);
}
if str.len() == 12 {
return;
}
let next = b.next(v1);
for v2 in 0..12 {
if next[v2] {
let c = b[v2];
let next_verts = verts + Vertices::new(1 << v2);
search_next(str + c, v2, next_verts, &trie, b, found);
}
}
}
In both code snippets there is an FnMut type constraint, essentially allowing us to pass any closure we want with any capture mode. In practice, we’ll use LetterBoxWords in the search closure, and a simple println! macro in the LetterBoxWords::find closure. Here is the final Rust solver app:
use letter_boxed_solver::{
core::{LetterBox, St},
search::{LetterBoxWords, search},
trie::StTrie
};
use std::{env::args, fs::File, time::Instant};
fn main() {
let start = Instant::now();
let args: Vec<String> = args().skip(1).collect();
if args.len() != 2 {
println!("Please specify a Letter Boxed puzzle and a word list file.");
return;
}
let b = LetterBox::new(args[0].parse::<St>().unwrap());
log(start, "Loading trie...");
let mut stream = File::open(&args[1]).unwrap();
let trie = StTrie::load(&mut stream);
log(start, format!("Loaded {} words.", trie.len()).as_str());
let mut words = LetterBoxWords::new();
log(start, "Finding valid words...");
search(&trie, b, |w, v| words.insert(w, v));
log(start, format!("Found {} valid words.", words.len()).as_str());
log(start, "Finding solutions...");
words.find(|w1, w2| println!("{}-{}", w1, w2));
log(start, "Done.");
}
fn log(start: Instant, message: &str) {
println!("[{:07.3}] {}", start.elapsed().as_secs_f64(), message);
}
Was it all worth it? Let’s check the timing results for our two benchmark puzzles:
> letter_boxed_solver.exe RMEWCLTGKAPI words.txt [000.000] Loading trie... [000.039] Loaded 162309 words. [000.039] Finding valid words... [000.042] Found 754 valid words. [000.042] Finding solutions... MARKETPLACE-EARWIG WIGWAM-MARKETPLACE PRAGMATIC-CAKEWALK [000.044] Done. > letter_boxed_solver.exe ERGBIDNCFTAO words.txt [000.000] Loading trie... [000.039] Loaded 162309 words. [000.039] Finding valid words... [000.043] Found 1436 valid words. [000.043] Finding solutions... DOGCART-TENEBRIFIC -- snipped 72 other solutions -- NONBRAND-DEFECTING [000.072] Done.
That’s right, the Rust implementation is at least 10% faster than the best C++ benchmark. Thanks, Rust — you’ve more than earned that oh-so-rare unqualified success badge!