4
\$\begingroup\$

I have written this program to find anagrams in a "pile" of letters (it'd be an effective way to cheat at Scrabble...)

Run it like anagram abcedeede to get a list of all the words that can be made from the letters abcedeede (you might want to pipe to head, since there will be many).

This is my first "major" attempt to write something in Rust--it is an adaptation of a Python program I wrote a while ago. I would love comments both on style and on any "stupid"/non-idiomatic things I've done that lead to problems in Rust.

// main.rs
#![feature(test)]
extern crate test;
use std::collections::HashMap;
use std::env;
use std::fs::File;
use std::io;
use std::io::prelude::*;
use std::io::BufReader;

/// A struct containing a string "word" and its "hash," a map between characters and counts
pub struct CountedWord {
    /// The "pretty" version of the word that has been counted
    word: String,
    /// A map of characters to counts of characters for the word
    letter_counter: HashMap<char, u32>,
}

impl CountedWord {
    /// Create a `CountedWord` from an input `&str`
    pub fn new(word: &str) -> CountedWord {
        CountedWord {
            word: word.to_string(),
            letter_counter: CountedWord::hash(word),
        }
    }

    /// Compute the "hash" for the input word
    ///
    /// The "hash" is the count of each of the letters in the word.
    /// i.e. for "attack" the hash is "2 a's, 1 c, 1 k, and 2 t's"
    fn hash(word: &str) -> HashMap<char, u32> {
        let clean_word = word.trim().to_lowercase();
        let mut letter_counter = HashMap::new();
        for ch in clean_word.chars().filter(|ch| ch.is_alphabetic()) {
            letter_counter
                .entry(ch)
                .and_modify(|e| *e += 1)
                .or_insert(1);
        }
        letter_counter
    }

    /// Determine if the other `CountedWord` can be made from the letters in `self`.
    /// (That is--is `self` an anagram of `other`, with some letters allowed to be left over in
    /// `self`?)
    ///
    /// Returns `true` if it can be made, `false` otherwise.
    pub fn is_possibility(&self, other: &CountedWord) -> bool {
        let mut iter_other_chars = other.letter_counter.iter();

        loop {
            let item = iter_other_chars.next();
            match item {
                Some((character, number_in_other)) => {
                    let number_in_self = self.letter_counter.get(character);
                    match number_in_self {
                        Some(number_in_self) => {
                            if number_in_self >= number_in_other {
                                // this letter doesn't rule it out
                                continue;
                            } else {
                                // we don't have enough of this letter, not a possibility
                                break false;
                            }
                        }
                        // we don't have this letter, not a possiblity
                        None => break false,
                    }
                }
                // we didn't fail above, so this word must be a possibility
                None => break true,
            }
        }
    }
}

fn main() {
    // process all the words in the dictionary
    let f = File::open("/usr/share/dict/words").expect("dictionary not found");
    let lines = BufReader::new(f).lines();
    let mut dictionary_words = Vec::new();
    for word in lines {
        match word {
            Ok(word) => {
                dictionary_words.push(CountedWord::new(&word));
            }
            Err(_e) => continue,
        };
    }

    // process the "pile" of letters we have to anagram from the arguments
    // spaces are ignored--everything except the program name is collected here
    let pile = CountedWord::new(&env::args().collect::<Vec<String>>()[1..].join(""));

    // determine what words from the dictionary can be made from the letters in the pile
    let mut possibilities = Vec::new();
    for word in dictionary_words.iter() {
        if pile.is_possibility(&word) {
            possibilities.push(word)
        }
    }

    // output the possiblities in alphabetical order by length
    let mut stdout = io::stdout();
    possibilities.sort_unstable_by_key(|k| (-(k.word.len() as i32), k.word.to_lowercase()));
    for possibility in possibilities {
        // using `if let` and `writeln!` here so if you pipe to (e.g.) head, we can catch the panic when the pipe is closed early
        if let Err(_) = writeln!(stdout, "{}", possibility.word) {
            break;
        }
    }
}

#[cfg(test)]
mod tests {

    use super::*;
    use test::Bencher;

    /// Test `CountedWord::hash`
    #[test]
    fn test_counted_word_hash() {
        let counter = CountedWord::hash("test");

        let mut test_counter = HashMap::new();
        test_counter.insert('t', 2);
        test_counter.insert('e', 1);
        test_counter.insert('s', 1);

        assert_eq!(counter, test_counter);
    }

    /// Test `CountedWord::new`
    #[test]
    fn test_create_counted_word() {
        let test_word = CountedWord::new("test");

        assert_eq!(test_word.word, "test");

        let mut test_counter = HashMap::new();
        test_counter.insert('t', 2);
        test_counter.insert('e', 1);
        test_counter.insert('s', 1);

        assert_eq!(test_word.letter_counter, test_counter);
    }

    /// Test `CountedWord::is_possibility`
    #[test]
    fn test_counted_word_is_possiblity() {
        let test_word_1 = CountedWord::new("test");
        let test_word_2 = CountedWord::new("assessment");

        let input_letters = CountedWord::new("tssettioupuqwerwe");

        assert!(input_letters.is_possibility(&test_word_1));
        assert!(!input_letters.is_possibility(&test_word_2));
    }

    /// Benchmark `CountedWord::hash`
    #[bench]
    fn bench_hashing_word(b: &mut Bencher) {
        b.iter(|| CountedWord::hash("tssettioupuqwerwe"));
    }

    /// Benchmark `CountedWord::is_possibility` when `is_possibility` is true
    #[bench]
    fn bench_checking_possibility_true(b: &mut Bencher) {
        let test_word = CountedWord::new("test");
        let input_letters = CountedWord::new("tssettioupuqwerwe");

        b.iter(|| input_letters.is_possibility(&test_word));
    }

    /// Benchmark `CountedWord::is_possibility` when `is_possibility` is false
    #[bench]
    fn bench_checking_possibility_false(b: &mut Bencher) {
        let test_word = CountedWord::new("assessment");
        let input_letters = CountedWord::new("tssettioupuqwerwe");

        b.iter(|| input_letters.is_possibility(&test_word));
    }
}
\$\endgroup\$
  • \$\begingroup\$ Also, I've noticed ~4s run times with debug builds and sub-0.5s run times with release builds. This seems like a large discrepancy--is there a particular reason for this in my code? \$\endgroup\$ – Scott Colby Aug 3 '18 at 10:10
  • 1
    \$\begingroup\$ I'm not shocked: I made a little game that was almost unplayable in debug mode but had hundreds of fps in release mode. \$\endgroup\$ – French Boiethios Aug 3 '18 at 10:19
3
\$\begingroup\$
  1. I don't think "anagram" usually means "can have letters left over". You may want to find a better term.

  2. Modern Rust uses braced imports to import multiple things from the same crate / module instead of separate lines.

  3. I appreciate the documentation, but it's fairly close to reiterating what the types in the code already tell us. User-facing documentation in general shouldn't explain the internals of an implementation, otherwise you are promising more than you might mean to. Describe what the type can do, not how it does it.

  4. Instead of scare-quoting "hash" everywhere, promote it to its own type and use the name. Since you seem to want to shy away from "hash", I'll use "fingerprint", but you could also use "letter counter", as you did in one place.

  5. Note that extracting a type allows the CountedWord::hash method to become a constructor on Fingerprint.

  6. It's more common to use or_insert(0) += 1 instead of using Entry::and_modify.

  7. If it's important, instead of documenting a field as "pretty", name the field "pretty". In addition, explain what "pretty" means.

  8. Don't describe what the return value means when it's a boolean. Any programmer should already know that. In most cases, see if you can use a type that encodes those comments.

  9. Instead of a loop with break, use a for loop and some return statements.

  10. Use unwrap_or to provide a default count of 0.

    for (character, &number_in_other) in &other.0 {
        let number_in_self = self.0.get(character).cloned().unwrap_or(0);
        if number_in_self < number_in_other {
            // we don't have enough of this letter, not a possibility
            return false;
        }
    }
    
    true
    
  11. You can then simplify the superset method with Iterator::all.

  12. Extract a function to load the dictionary. This removes the mutability from dictionary_words from main.

  13. Instead of iterating over lines with a for loop, use Iterator combinators like flat_map and map, finishing with collect.

  14. Likewise, use filter and collect together.

  15. Iterator::skip can skip the first argument instead of using slicing.

  16. You can collect an iterator of strings into one String, no need to join a Vec<String>.

  17. Calling to_lowercase when sorting is wasteful as it may be called multiple times. Unfortunately, sort_by_cached_key is unstable.

  18. Use cmp::Reverse instead of negating an integer.

  19. Don't use if let if you don't care about the Err body, use is_err instead.

  20. Matching on a Result isn't catching a panic; it's preventing it from panicking.

  21. Don't prefix test functions with the word "test"; they are in a test module and have the test attribute. Don't document them as a test either - that should be obvious from the test name

  22. Directly poking into the implementation of Fingerprint in tests is brittle and won't hold up to refactoring. Poking into the implementation of Fingerprint via CountedWord is doubly bad.

  23. is_possibility is too ambiguous. Use a name with a more clear "directionality".

use std::{
    cmp,
    collections::HashMap,
    env,
    fs::File,
    io::{self, prelude::*, BufReader},
};

// A map of characters to counts of characters for the word
struct Fingerprint(HashMap<char, u32>);

impl Fingerprint {
    fn new(word: &str) -> Self {
        let clean_word = word.trim().to_lowercase();
        let mut counts = HashMap::new();
        for ch in clean_word.chars().filter(|ch| ch.is_alphabetic()) {
            *counts.entry(ch).or_insert(0) += 1;
        }
        Fingerprint(counts)
    }

    fn is_superset_of(&self, other: &Fingerprint) -> bool {
        other.0.iter().all(|(character, number_in_other)| {
            let number_in_self = self.0.get(character).unwrap_or(&0);
            number_in_self >= number_in_other
        })
    }
}

pub struct CountedWord {
    word: String,
    fingerprint: Fingerprint,
}

impl CountedWord {
    pub fn new(word: &str) -> CountedWord {
        CountedWord {
            word: word.to_string(),
            fingerprint: Fingerprint::new(word),
        }
    }

    /// Determine if the other `CountedWord` can be made from the letters in `self`.
    /// (That is--is `self` an anagram of `other`, with some letters allowed to be left over in
    /// `self`?)
    pub fn can_create(&self, other: &CountedWord) -> bool {
        self.fingerprint.is_superset_of(&other.fingerprint)
    }
}

fn load_dictionary_words() -> Vec<CountedWord> {
    let f = File::open("/usr/share/dict/words").expect("dictionary not found");

    BufReader::new(f)
        .lines()
        .flat_map(|l| l)
        .map(|l| CountedWord::new(&l))
        .collect()
}

fn main() {
    let dictionary_words = load_dictionary_words();

    // process the "pile" of letters we have to anagram from the arguments
    // spaces are ignored--everything except the program name is collected here
    let letters: String = env::args().skip(1).collect();
    let pile = CountedWord::new(&letters);

    // determine what words from the dictionary can be made from the letters in the pile
    let mut possibilities: Vec<_> = dictionary_words
        .iter()
        .filter(|word| pile.can_create(word))
        .collect();

    // output the possiblities in alphabetical order by length
    possibilities.sort_unstable_by_key(|k| (cmp::Reverse(k.word.len()), k.word.to_lowercase()));

    let mut stdout = io::stdout();
    for possibility in possibilities {
        // Prevent the panic when the pipe is closed early and exit instead
        if writeln!(stdout, "{}", possibility.word).is_err() {
            break;
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn fingerprint_new() {
        let counter = Fingerprint::new("test");

        let mut test_counter = HashMap::new();
        test_counter.insert('t', 2);
        test_counter.insert('e', 1);
        test_counter.insert('s', 1);

        assert_eq!(counter.0, test_counter);
    }

    #[test]
    fn counted_word_new() {
        let test_word = CountedWord::new("test");

        assert_eq!(test_word.word, "test");

        let mut test_counter = HashMap::new();
        test_counter.insert('t', 2);
        test_counter.insert('e', 1);
        test_counter.insert('s', 1);

        assert_eq!(test_word.fingerprint.0, test_counter);
    }

    #[test]
    fn counted_word_is_possiblity() {
        let test_word_1 = CountedWord::new("test");
        let test_word_2 = CountedWord::new("assessment");

        let input_letters = CountedWord::new("tssettioupuqwerwe");

        assert!(input_letters.can_create(&test_word_1));
        assert!(!input_letters.can_create(&test_word_2));
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for the thorough review! I benchmarked sort_unstable_by_key vs. sort_by_cached_key: the cached version is an order of magnitude faster on my test vector of words. \$\endgroup\$ – Scott Colby Sep 1 '18 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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