1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112

use std::collections::HashMap;
use std::iter::once;

pub fn abbrev<'a>(xs: &'a [&str]) -> HashMap<String, &'a str> {
    let mut result = HashMap::new();
    let mut sorted = xs.to_owned();

    sorted.sort();
    sorted
        .iter()
        .zip(sorted.iter().skip(1).chain(once(&"")))
        .fold(0, |matched, (&curr, &next)| {
            if *curr == *next {
                return matched;
            }

            let matches = curr
                .chars()
                .zip(next.chars())
                .take_while(|(a, b)| a == b)
                .count();

            let max = matches.max(matched);
            for n in (max + 1)..curr.len() {
                result.insert(curr.chars().take(n).collect(), curr);
            }

            // one can always be accessed by itself
            result.insert(curr.to_string(), curr);

            matches
        });

    result
}

#[cfg(test)]
mod tests {
    use abbrev;

    #[test]
    fn with_nothing() {
        let words = vec![];
        let map = abbrev(&words);

        assert!(map.is_empty());
    }

    #[test]
    fn with_one_only() {
        let words = vec!["foo"];
        let map = abbrev(&words);

        for key in vec!["f", "fo", "foo"] {
            assert_eq!(&"foo", map.get(key).unwrap());
        }

        assert_eq!(3, map.len());
    }

    #[test]
    fn with_two_same() {
        let words = vec!["foo", "foo"];
        let map = abbrev(&words);

        for key in vec!["f", "fo", "foo"] {
            assert_eq!(&"foo", map.get(key).unwrap());
        }

        assert_eq!(3, map.len());
    }

    #[test]
    fn with_two_different() {
        let words = vec!["foo", "bar"];
        let map = abbrev(&words);

        for key in vec!["f", "fo", "foo"] {
            assert_eq!(&"foo", map.get(key).unwrap());
        }

        for key in vec!["b", "ba", "bar"] {
            assert_eq!(&"bar", map.get(key).unwrap());
        }

        assert_eq!(6, map.len());
    }

    #[test]
    fn well_done() {
        let words = vec!["foo", "fool", "folding", "flop"];
        let map = abbrev(&words);

        for key in vec!["fl", "flo", "flop"] {
            assert_eq!(&"flop", map.get(key).unwrap());
        }

        for key in vec!["fol", "fold", "foldi", "foldin", "folding"] {
            assert_eq!(&"folding", map.get(key).unwrap());
        }

        for key in vec!["foo"] {
            assert_eq!(&"foo", map.get(key).unwrap());
        }

        for key in vec!["fool"] {
            assert_eq!(&"fool", map.get(key).unwrap());
        }

        assert_eq!(10, map.len());
    }
}