wordle.rs

// # Cargo.toml
// [dependencies]
// memmap = "0.7.0"
// rayon = "1.5.3"

use std::{
    fmt::{Display, Write},
    path::Path,
    time::Instant,
};

use rayon::{
    prelude::{IndexedParallelIterator, IntoParallelIterator, ParallelIterator},
    slice::ParallelSliceMut,
};

const EARIOTNSLCUDPMHGBFYWKVXZJQ: &[u32; 27] = &[
    0,
    1 << 24, // A
    1 << 9,  // B
    1 << 16, // C
    1 << 14, // D
    1 << 25, // E
    1 << 8,  // F
    1 << 10, // G
    1 << 11, // H
    1 << 22, // I
    1 << 27, // J (!)
    1 << 5,  // K
    1 << 17, // L
    1 << 12, // M
    1 << 19, // N
    1 << 21, // O
    1 << 13, // P
    1 << 26, // Q (!)
    1 << 23, // R
    1 << 18, // S
    1 << 20, // T
    1 << 15, // U
    1 << 4,  // V
    1 << 6,  // W
    1 << 3,  // X
    1 << 7,  // Y
    1 << 2,  // Z
];

fn encode_word(raw: &str) -> u32 {
    let mut letters = 0;
    for c in raw.bytes() {
        letters |= EARIOTNSLCUDPMHGBFYWKVXZJQ[(c & 31) as usize];
    }

    letters
}

#[derive(Debug)]
struct Word {
    raw: &'static str,
    letters: u32,
}

fn append_words(words: &mut Vec<Word>, filename: impl AsRef<Path>) {
    // memory map file for the whole program lifetime
    let file = std::fs::File::open(filename).unwrap();
    let mapped = unsafe { memmap::Mmap::map(&file).unwrap() };
    std::mem::forget(file);
    let mapped = std::str::from_utf8(Box::leak(Box::new(mapped))).unwrap();

    words.extend(
        mapped
            .lines()
            .filter(|word| word.len() == 5)
            .map(|raw| Word {
                raw,
                letters: encode_word(raw),
            })
            .filter(|word| word.letters.count_ones() == 5),
    );
}

fn for_iter<I: Copy>(
    init: I,
    mut condition: impl FnMut(I) -> bool,
    mut increment: impl FnMut(I) -> I,
) -> impl Iterator<Item = I> {
    let mut counter = init;

    std::iter::from_fn(move || {
        condition(counter).then(|| {
            let res = counter;
            counter = increment(counter);
            res
        })
    })
}

macro_rules! follow_skip {
    ($skip:ident[$head:expr, $($tail:expr),* $(,)?]) => {
        $skip[$head + follow_skip!($skip[$($tail),*])] as usize
    };
    ($skip:ident[$offset:expr]) => {
        $skip[$offset] as usize
    };
}

fn main() {
    let t0 = Instant::now();

    let mut words = Vec::new();

    append_words(&mut words, "wordle-nyt-answers-alphabetical.txt");
    append_words(&mut words, "wordle-nyt-allowed-guesses.txt");

    const JQ: u32 = 1 << 27 | 1 << 26;

    words.sort_by_key(|word| word.letters ^ JQ);

    let n_words = words.len();

    assert!(u32::try_from(n_words).is_ok()); // assert n_words fits in a u32

    let jq_split = words
        .iter()
        .take_while(|word| word.letters & JQ != 0)
        .count();

    let (proxies, indices): (Vec<_>, Vec<_>) = std::iter::once((words[0].letters, 0))
        .chain((1..n_words).filter_map(|i| {
            (words[i].letters != words[i - 1].letters).then(|| (words[i].letters, i as u32))
        }))
        .unzip();

    let n_proxies = proxies.len();

    assert!(u16::try_from(n_proxies).is_ok()); // assert n_proxies fits in a u16

    let t1 = Instant::now();
    let stride = n_proxies + 1;

    let mut skip = vec![0u16; n_proxies * stride];
    skip.par_chunks_mut(stride)
        .enumerate()
        .for_each(|(i, skip_line)| {
            let mut next = n_proxies as u16;
            skip_line[n_proxies] = next;
            let a = proxies[i];
            for j in (i..n_proxies).rev() {
                let b = proxies[j];
                if (a & b) == 0 {
                    next = j as u16;
                }
                skip_line[j] = next;
            }
        });

    let first = (0..n_proxies)
        .map(|i| skip[i * stride + i])
        .collect::<Vec<_>>();

    let t2 = Instant::now();

    let results = (0..jq_split)
        .into_par_iter()
        .flat_map_iter(|i| {
            let mut results = Vec::new();

            let a = proxies[i];
            let stride_i = i * stride;

            for j in for_iter(
                first[i] as usize,
                |j| j < n_proxies,
                |j| follow_skip!(skip[stride_i + j + 1]),
            )
            .filter(|&j| a & proxies[j] == 0)
            {
                let ab = a | proxies[j];
                let stride_j = j * stride;

                for k in for_iter(
                    first[j] as usize,
                    |k| k < n_proxies,
                    |k| follow_skip!(skip[stride_j, stride_i + k + 1]),
                )
                .filter(|&k| ab & proxies[k] == 0)
                {
                    let abc = ab | proxies[k];
                    let stride_k = k * stride;

                    for l in for_iter(
                        first[k] as usize,
                        |l| l < n_proxies,
                        |l| follow_skip!(skip[stride_k, stride_j, stride_i + l + 1]),
                    )
                    .filter(|&l| abc & proxies[l] == 0)
                    {
                        let abcd = abc | proxies[l];
                        let stride_l = l * stride;

                        for m in for_iter(
                            first[l] as usize,
                            |m| m < n_proxies,
                            |m| follow_skip!(skip[stride_l, stride_k, stride_j, stride_i + m + 1]),
                        )
                        .filter(|&i| abcd & proxies[i] == 0)
                        {
                            results.push(Solution { i, j, k, l, m });
                        }
                    }
                }
            }

            results.into_iter()
        })
        .collect::<Vec<_>>();

    for (n, solution) in results.into_iter().enumerate() {
        println!("{:2}. {}", n + 1, solution.print(&words, &indices));
    }

    let t3 = Instant::now();

    println!();
    println!("{:>12.2?} prepare words", t1 - t0);
    println!("{:>12.2?} compute tables", t2 - t1);
    println!("{:>12.2?} find solutions", t3 - t2);
    println!("{:>12.2?} total", t3 - t0);
}

struct Solution {
    i: usize,
    j: usize,
    k: usize,
    l: usize,
    m: usize,
}

impl Solution {
    fn print<'p>(&'p self, words: &'p [Word], indices: &'p [u32]) -> SolutionPrinter<'p> {
        SolutionPrinter {
            solution: self,
            words,
            indices,
        }
    }
}

struct SolutionPrinter<'p> {
    solution: &'p Solution,
    words: &'p [Word],
    indices: &'p [u32],
}

impl<'p> SolutionPrinter<'p> {
    fn write_anagrams(&self, f: &mut std::fmt::Formatter<'_>, i: usize) -> std::fmt::Result {
        let i = self.indices[i];

        write!(f, "{}", self.words[i as usize].raw)?;

        let letters = self.words[i as usize].letters;

        for i in (i + 1..).take_while(|&i| self.words[i as usize].letters == letters) {
            f.write_char('/')?;
            write!(f, "{}", self.words[i as usize].raw)?;
        }
        Ok(())
    }
}

impl<'p> Display for SolutionPrinter<'p> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let &Solution { i, j, k, l, m } = self.solution;

        self.write_anagrams(f, i)?;
        f.write_char(' ')?;
        self.write_anagrams(f, j)?;
        f.write_char(' ')?;
        self.write_anagrams(f, k)?;
        f.write_char(' ')?;
        self.write_anagrams(f, l)?;
        f.write_char(' ')?;
        self.write_anagrams(f, m)?;

        Ok(())
    }
}

> hyperfine -w 30 -m 500 ./wordle-go ./wordle-rust
Benchmark 1: ./wordle-go
  Time (mean ± σ):      36.3 ms ±   1.0 ms    [User: 319.2 ms, System: 18.9 ms]
  Range (min … max):    34.6 ms …  46.8 ms    500 runs

Benchmark 2: ./wordle-rust
  Time (mean ± σ):      32.2 ms ±   1.2 ms    [User: 350.0 ms, System: 81.7 ms]
  Range (min … max):    29.0 ms …  36.0 ms    500 runs

Summary
  './wordle-rust' ran
    1.13 ± 0.05 times faster than './wordle-go'

Linux 5.19.5-arch1-1

Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         48 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  16
  On-line CPU(s) list:   0-15
Vendor ID:               AuthenticAMD
  Model name:            AMD Ryzen 7 5800X 8-Core Processor