Rust language solution to an ancient "Perl Quiz of the Week" (qotw21)

qotw21_main.rs

/*
 * This program solves the puzzle
 *     https://perl.plover.com/qotw/e/021
 *
 * (In case that link goes away, a brief summary of the problem
 * is to consider the free non-abelian group with 26 generators
 * 'a' through 'z', under the equivalence relation that any two
 * words found in the dictionary that are anagrams of each other
 * are equivalent. Now determine which letters commute with which
 * other letters, and specifically which letters are in the center.)
 *
 * It does so by reading the dictionary to determine all anagram
 * pairs and then applying two strategies over and over again
 * to ever known pair of equivalent strings, manipulating the
 * set of everything known until it can't any further at which
 * point it prints out a table of the letters which are known
 * to commute and the list of other equivalences that are known
 * and not derivable from the commutativity table.
 *
 * It's a bit surprising that this relatively simple approach
 * suffices to wring every piece of information out of the
 * Web2 word list, but it does. Presumably, more advanced reasoning
 * strategies could be required for different dictionaries; however,
 * the list of "Leftover facts" printed at the end should be
 * enough to know whether this simple approach was enough for a given
 * dictionary.
 */
use std::{
    cell::Cell,
    collections::{HashMap, HashSet},
    fs::File,
    io::{prelude::*, BufReader},
    path::Path,
};

#[derive(Hash, Eq, PartialEq, Debug)]
struct Fact {
    lhs: String,
    rhs: String,
}

impl Fact {
    // store facts sorted, so that we know that
    // abcd=bcda is the same fact as bcda=abcd
    fn new(lhs: &str, rhs: &str) -> Fact {
        if lhs <= rhs {
            Fact {
                lhs: lhs.to_string(),
                rhs: rhs.to_string(),
            }
        } else {
            Fact {
                lhs: rhs.to_string(),
                rhs: lhs.to_string(),
            }
        }
    }
}

struct WorldState {
    // In a WorldState, we store single-letter-commutes facts (e.g. on=no) in 'single_commutes'
    // and only use 'facts' for facts about longer strings
    single_commutes: HashMap<char, HashSet<char>>,
    facts: HashSet<Fact>,
}

impl WorldState {
    fn new() -> WorldState {
        WorldState {
            single_commutes: HashMap::new(),
            facts: HashSet::new(),
        }
    }

    fn new_with_singles(single_commutes: &HashMap<char, HashSet<char>>) -> WorldState {
        let mut singles = HashMap::new();
        for (c, nbhs) in single_commutes {
            singles.insert(*c, nbhs.clone());
        }
        WorldState {
            single_commutes: singles,
            facts: HashSet::new(),
        }
    }

    fn add_fact(&mut self, lhs: &str, rhs: &str) {
        if lhs.ne(rhs) {
            match lhs.len() {
                0 => (),
                1 => (),
                2 => {
                    self.single_commutes
                        .entry(lhs.chars().next().unwrap())
                        .or_default()
                        .insert(rhs.chars().next().unwrap());
                    self.single_commutes
                        .entry(rhs.chars().next().unwrap())
                        .or_default()
                        .insert(lhs.chars().next().unwrap());
                }
                _ => {
                    self.facts.insert(Fact::new(lhs, rhs));
                }
            }
        }
    }
}

fn reduce(state: WorldState) -> (WorldState, bool) {
    // Take each fact and remove common characters from front/back of both sides
    let mut retval = WorldState::new_with_singles(&state.single_commutes);
    let mut found_something = false;
    for fact in state.facts {
        let lhsbytes = fact.lhs.as_bytes();
        let rhsbytes = fact.rhs.as_bytes();
        let mut i1: usize = 0;
        let mut i2 = fact.rhs.len();
        while i1 + 1 < i2 && lhsbytes[i1] == rhsbytes[i1] {
            i1 += 1;
            found_something = true;
        }
        while i2 > i1 + 1 && lhsbytes[i2 - 1] == rhsbytes[i2 - 1] {
            i2 -= 1;
            found_something = true;
        }

        retval.add_fact(&fact.lhs[i1..i2], &fact.rhs[i1..i2])
    }
    (retval, found_something)
}

fn scramble(state: WorldState) -> (WorldState, bool) {
    // adjust WorldState facts by moving stuff to the front or the back as may
    // help with a later reduce operation
    let mut retval = WorldState::new_with_singles(&state.single_commutes);
    let mut found_something = false;
    for fact in state.facts {
        let ourletters: HashSet<char> = fact.lhs.chars().collect();
        let mut lhscopy: Vec<char> = fact.lhs.chars().collect();
        let mut rhscopy: Vec<char> = fact.rhs.chars().collect();
        let mut local_found: bool = false;

        for c in ourletters {
            // So for each letter, we see whether we can move the letter all
            // the way to the left, or all the way to the right, based on the
            // letters that we know commute. We only move a letter if we can
            // move it all the way left/right on both lhs & rhs of the fact.
            if state.single_commutes.contains_key(&c) {
                let commutes_with = &state.single_commutes[&c];
                let can_swap = Cell::new(true);
                let finder = |c2: &char| {
                    if c == *c2 {
                        true
                    } else {
                        if !commutes_with.contains(c2) {
                            can_swap.replace(false);
                        }
                        false
                    }
                };
                // Can we move c all the way left?
                let idx1: Option<usize> = lhscopy.iter().position(finder);
                let idx2: Option<usize> = rhscopy.iter().position(finder);
                if can_swap.get() {
                    match (idx1, idx2) {
                        (Some(i1), Some(i2)) => {
                            local_found = true;
                            // vec[0], vec[1], .. vec[i1-1], vec[i1] -> vec[i1], vec[0], vec[1], .. vec[i1-1]
                            for i in (0..i1).rev() {
                                lhscopy.swap(i, i + 1);
                            }
                            for i in (0..i2).rev() {
                                rhscopy.swap(i, i + 1);
                            }
                        }
                        (_, _) => (), // shouldn't happen
                    }
                } else {
                    // Can we move c all the way right?
                    can_swap.replace(true);
                    let ridx1: Option<usize> = lhscopy.iter().rposition(finder);
                    let ridx2: Option<usize> = rhscopy.iter().rposition(finder);
                    if can_swap.get() {
                        match (ridx1, ridx2) {
                            (Some(i1), Some(i2)) => {
                                local_found = true;
                                // vec[i1], ..., vec[len()-1] -> vec[i1+1], ..., vec[len()-1], vec[i1]
                                for i in i1..(lhscopy.len() - 1) {
                                    lhscopy.swap(i, i + 1);
                                }
                                for i in i2..(rhscopy.len() - 1) {
                                    rhscopy.swap(i, i + 1);
                                }
                            }
                            (_, _) => (), // shouldn't happen
                        }
                    }
                }
            }
        }
        if local_found {
            let lhsnew: String = lhscopy.into_iter().collect();
            let rhsnew: String = rhscopy.into_iter().collect();
            retval.add_fact(lhsnew.as_str(), rhsnew.as_str());
            found_something = true;
        } else {
            retval.add_fact(fact.lhs.as_str(), fact.rhs.as_str())
        }
    }
    (retval, found_something)
}

fn lines_from_file(filename: impl AsRef<Path>) -> Vec<String> {
    let file = File::open(filename).expect("no such file");
    let buf = BufReader::new(file);
    buf.lines()
        .map(|l| l.expect("Could not parse line"))
        // Comment out the next line to limit us to only words that are already all lowercase
        // (i.e. disallow use of proper nouns)
        .map(|s| s.to_ascii_lowercase())
        .filter(|w| w.chars().all(|f| f.is_lowercase()))
        .collect()
}

fn make_initial_facts(wordlist: &[String]) -> Vec<Fact> {
    let mut anamap: HashMap<String, Vec<&str>> = HashMap::new();
    for word in wordlist {
        let mut cvec: Vec<char> = word.chars().collect();
        cvec.sort();
        let sorted: String = cvec.into_iter().collect();
        anamap.entry(sorted).or_default().push(word.as_str());
    }
    let mut result = Vec::new();

    for value in anamap.values() {
        if value.len() > 1 {
            for n in 1..value.len() {
                result.push(Fact::new(value[n - 1], value[n]));
            }
        }
    }
    result
}

fn main() {
    let mut state = WorldState::new();
    {
        // Web2 is from https://perl.plover.com/qotw/words/Web2.gz
        let lines = lines_from_file("Web2");
        for fact in make_initial_facts(lines.as_slice()) {
            state.add_fact(fact.lhs.as_str(), fact.rhs.as_str());
        }
    }
    let mut working = true;
    while working {
        //println!("Interesting fact size: {}", state.facts.len());
        (state, _) = scramble(state);
        (state, working) = reduce(state);
    }

    println!("Commute summary:");
    println!("  abcdefghijklmnopqrstuvwxyz");
    let empty: HashSet<char> = HashSet::new();
    for a in 'a'..='z' {
        print!("{}:", a);
        let commset = state.single_commutes.get(&a).unwrap_or(&empty);
        let mut in_center = true;
        for b in 'a'..='z' {
            if a == b {
                print!("\\");
            } else if commset.contains(&b) {
                print!("#");
            } else {
                print!(" ");
                in_center = false;
            }
        }
        if in_center {
            print!(" (*)");
        }
        println!();
    }
    println!();
    println!("Leftover facts:");
    for fact in state.facts {
        println!("    {}={}", fact.lhs, fact.rhs);
    }
}