3
\$\begingroup\$

I'm particularly concerned here that I'm copying more often than I need to, and that's slowing things down; obviously, given the algorithm/approach, I need to do some copying, but I don't want to be doing more than necessary. Code also available at https://gist.github.com/fizbin/905a219af86adb95a6e7fd4bd26a507e

/*
 * 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);
    }
}
```
\$\endgroup\$
0

1 Answer 1

1
\$\begingroup\$

The code looks pretty good overall. I'm not going to comment on the algorithm, mainly because I don't entirely understand the problem. Still, there are some issues here, and the biggest one is something that I often do as well.

Don't take inputs by reference if you are just going to clone them

You do this all over the place in the code, with the worst offender being WorldState::new_with_singles, where you perform the clone manually, rather than just calling .clone(). While doing this does make the code more general, it also causes a sneaky performance hit, especially if the caller already has an owned value they no longer need. The fix varies on a per-method basis- new_with_singles should probably just take in an owned HashMap, but Fact::new and WorldState::add_fact should probably take in an impl Into<String>.

scramble and reduce should be methods

It's a bit awkward to use them as free functions, especially when they are just performing a transformation on WorldState instances. Rewriting them to have the signatures

impl WorldState{
    fn scramble(&mut self) -> bool;
    fn reduce(&mut self) -> bool;
}

would be ideal.

Rewrite reduce to use Iterators

Always prefer to use iterators instead of indexing, especially when dealing with strings. They are faster, less brittle, and in this case, won't try to split strings in the middle of multibyte characters.

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 mut lhs = fact.lhs.chars();
        let mut rhs = fact.rhs.chars();
        //fun fact: the bitwise operators work on bools
        //There aren't too many uses for it, but it does occasionally come in handy
        found_something |= lhs 
            .by_ref()
            .zip(rhs.by_ref())
            .take_while(|(l, r)| l == r)
            .last()
            .is_some();
        found_something |= lhs
            .by_ref()
            .rev()
            .zip(rhs.by_ref().rev())
            .take_while(|(l, r)| l == r)
            .last()
            .is_some();

        retval.add_fact(lhs.as_str(), rhs.as_str())
    }
    (retval, found_something)
}

Fair warning, I did not test this beyond compiling it, so verifying that it does what I think it does is left as an exercise to the reader.

Use Cell::set instead of Cell::replace

Fairly self-explanatory, but in the scramble function, you call the Cell::replace method which returns the old value, and then immediately discard it, which is the entire point of Cell::set.

Handle unreachable states

In a couple of places, you have match statements that look like this:

match (idx1, idx2) {
    (Some(i1), Some(i2)) => {
        /* elided for brevity */
    }
    (_, _) => (), // shouldn't happen
}

Don't explicitly do nothing in an unreachable state. When it comes to unreachable states, explicitly crashing the program is usually the best (with the unreachable macro), especially since rustc is usually pretty good about optimizing out paths that truly are unreachable**. Also, you're using a match statement with only one pattern, which is also bad, and brings me to my next point.

Use Clippy

Rust ships with the clippy linter* which contains a bunch of useful lints that don't make sense to have in the compiler itself. I'll let what I got from clippy speak for itself:

warning: you seem to be trying to use `match` for destructuring a single pattern. Consider using `if let`
   --> src/main.rs:168:21
    |
168 | /                     match (idx1, idx2) {
169 | |                         (Some(i1), Some(i2)) => {
170 | |                             local_found = true;
171 | |                             // vec[0], vec[1], .. vec[i1-1], vec[i1] -> vec[i1], vec[0], vec[1], .. vec[i1-1]
...   |
179 | |                         (_, _) => (), // shouldn't happen
180 | |                     }
    | |_____________________^
    |
    = note: `#[warn(clippy::single_match)]` on by default
    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#single_match
help: try this
    |
168 ~                     if let (Some(i1), Some(i2)) = (idx1, idx2) {
169 +                         local_found = true;
170 +                         // vec[0], vec[1], .. vec[i1-1], vec[i1] -> vec[i1], vec[0], vec[1], .. vec[i1-1]
171 +                         for i in (0..i1).rev() {
172 +                             lhscopy.swap(i, i + 1);
173 +                         }
174 +                         for i in (0..i2).rev() {
175 +                             rhscopy.swap(i, i + 1);
176 +                         }
177 +                     }
    |

warning: you seem to be trying to use `match` for destructuring a single pattern. Consider using `if let`
   --> src/main.rs:187:25
    |
187 | /                         match (ridx1, ridx2) {
188 | |                             (Some(i1), Some(i2)) => {
189 | |                                 local_found = true;
190 | |                                 // vec[i1], ..., vec[len()-1] -> vec[i1+1], ..., vec[len()-1], vec[i1]
...   |
198 | |                             (_, _) => (), // shouldn't happen
199 | |                         }
    | |_________________________^
    |
    = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#single_match
help: try this
    |
187 ~                         if let (Some(i1), Some(i2)) = (ridx1, ridx2) {
188 +                             local_found = true;
189 +                             // vec[i1], ..., vec[len()-1] -> vec[i1+1], ..., vec[len()-1], vec[i1]
190 +                             for i in i1..(lhscopy.len() - 1) {
191 +                                 lhscopy.swap(i, i + 1);
192 +                             }
193 +                             for i in i2..(rhscopy.len() - 1) {
194 +                                 rhscopy.swap(i, i + 1);
195 +                             }
196 +                         }

Use a bunch of line comments instead of a block comment

I know this probably seems weird, but for comments, the rust community has decided to prefer a bunch of line comments rather than a single block comment when multiline comments are called for. Purely a stylistic thing, but your block comment doesn't match up with the community's style.

Needless block in main function

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());
        }
    }
   // other stuff...
}

There is no reason for that extra block, it should be removed.

On performance

You mentioned that you were concerned about performance. The first step is to make sure you're running an optimized build. There's a reason why every StackOverflow question involving rust and performance has a comment to the effect of "Did you build it the --release flag?". Also, fair warning, the advice I'm about to give is based on what I think might be slowing down the program. If you want to get serious about improving performance, use cargo flamegraph or something and figure out what's actually slowing your code down, and go from there.

The default hasher is slow

Rust's default Hashmap and Hashset use a hashdos resistant hash function with mediocre but consistent performance. While this is fine for most use cases, when you are doing lots of hashing of small and reasonably trusted input it's fine to swap in a faster hash function such as the Fowler-Noll-Vo or potentially even swapping out the HashMaps entirely for BtreeMaps instead and seeing how it performs.

Lots of Small strings and needless copies

Obviously, copies of large heap-based data structures and creating boatloads of small strings are fairly expensive operations. I've mentioned above how smarter function definitions can help prevent needless copies. Additionally, it may be worth creating an interner of some form or storing sufficiently small strings inline tinyvec style. Just using a Vec<char> as a string might yield some performance gains as well, since you convert to and from it regularly.

Final notes

Your code looks pretty good overall. I'd love to dig into it a little bit deeper, but again, I don't understand the task or algorithm well enough to do so. Make sure you pay attention to Unicode- rust is Unicode aware by default, and you should be too. Your code would almost certainly panic if someone decided to, say, pass in a Chinese dictionary instead of an English one.

*Typically invoked with cargo clippy. If it's not installed on your local machine, install it via rustup component add clippy

**If rustc doesn't optimize out an unreachable path, and you're really sure it can't be reached, std::hint::unreachable_unchecked is always an option.

\$\endgroup\$
5
  • \$\begingroup\$ Well, your rewrite of reduce doesn't work at all, and I couldn't figure out how to write it with iterators; however, I did switch it to using Vec<char> the way scramble does. This actually slowed things a bit, I think, but I do like the results better. I was unable to get flamegraph to help me; it made an empty flamegraph, but maybe I need to test on non-windows. Current version: gist.github.com/fizbin/2f8c32a16f477ea08f58a1eb234c7c54 \$\endgroup\$ Oct 8, 2022 at 20:30
  • \$\begingroup\$ @DanielMartin To get flamegraph to work on windows, you need to install dtrace and then run cargo flamegraph with admin permissions. It should be less of an adventure on Mac and Linux but I haven't personally done that. As far as using Vec<char> you'll want to store them that way in Fact or else you're going to waste a bunch of time converting between the two. I think my implementation of reduce goes wrong by consuming one more character off of each end than is needed. There doesn't seem to be... \$\endgroup\$
    – Aiden4
    Oct 8, 2022 at 23:47
  • \$\begingroup\$ ... a good way to fix that with iterators, even though it seems like there should be. Your revised version seems like the best option. \$\endgroup\$
    – Aiden4
    Oct 8, 2022 at 23:48
  • \$\begingroup\$ I did install dtrace and ran "cargo flamegraph" with admin permissions and flamegraph seemed to work, but the resulting flamegraph file had no data in it. Maybe the initial program is too fast already to be adequately profiled with flamegraph? \$\endgroup\$ Oct 9, 2022 at 6:50
  • \$\begingroup\$ @DanielMartin It likely wouldn't be the program being too fast that's the issue, it would be that rustc is inlining aggressively enough that there isn't really a meaningful stack trace to get in the hot loop. The other things I'd check are that dtrace is set up properly (ensure dtrace -l fills up the terminal) and that your program is being built with debug info turned on. \$\endgroup\$
    – Aiden4
    Oct 9, 2022 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.