betabear/
lib.rs

1//! Utility functions to solve small word puzzles.
2
3/// Checks whether word can be written with the given letters.
4///
5/// ```rust
6/// let letters = ['a', 'p', 'p', 'l', 'e', 'x', 'y', 'z'];
7/// let word = "apple";
8///
9/// assert!(betabear::build_with_letters(&letters, word));
10/// ```
11pub fn build_with_letters(given_letters: &[char], word: &str) -> bool {
12    let mut given_letters = given_letters.to_vec();
13
14    for letter in word.chars() {
15        // We could use binary search here, but it doesn't matter performance wise for the small
16        // words (i.e. element counts) we are dealing with. Also, we would need to ensure that the
17        // given letters were sorted.
18        if let Some(index) = given_letters.iter().position(|&x| x == letter) {
19            // We used a letter, remove it from the stash.
20            given_letters.remove(index);
21        } else {
22            // Word uses a letter we don't have (any more)
23            return false;
24        }
25    }
26
27    true
28}
29
30/// Filter dictionary by words that can be written with the given letters
31///
32/// Returns a vector of valid words.
33///
34/// ```rust
35/// let letters = "applepie";
36/// let dictionary = vec!["apple", "pie", "beer"];
37///
38/// let solution = betabear::search_for_words(&letters, dictionary.into_iter());
39///
40/// assert_eq!(solution, vec![("apple", 5), ("pie", 3)]);
41/// ```
42pub fn search_for_words<'l, 'dict, D>(letters: &'l str, dictionary: D) -> Vec<(&'dict str, usize)>
43    where D: Iterator<Item = &'dict str>
44{
45    let letters = letters.trim().chars().collect::<Vec<char>>();
46
47    let mut matches = dictionary.filter(|word| build_with_letters(&letters, word))
48                                .map(|word| (word, word.chars().count()))
49                                .collect::<Vec<(&str, usize)>>();
50
51    // Sort the vec so that the words with the most letters used are on top
52    matches.sort_by(|a, b| b.1.cmp(&a.1));
53
54    matches
55}
56
57#[test]
58fn find_trivial_word() {
59    let letters = "banana";
60    let words = vec!["banana"];
61
62    assert_eq!(search_for_words(letters, words.into_iter()),
63               vec![("banana", 6)]);
64}
65
66#[test]
67fn find_in_order() {
68    let letters = "banana";
69    let words = vec!["banana", "ban"];
70
71    assert_eq!(search_for_words(letters, words.into_iter()),
72               vec![("banana", 6), ("ban", 3)]);
73}
betabear/lib.rs

betabear/
lib.rs
