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
113
114
115
116
117
118
119
120
121
use std::cmp;
use std::collections::HashMap;
use std::collections::VecDeque;
pub type Config = Vec<(String, char)>;
type WordInProgress = VecDeque<char>;
pub fn default_config() -> Config {
(b'A' .. b'Z'+1)
.map(|b|
((b - b'A' + 1).to_string(),
b as char))
.collect()
}
pub struct Parser {
max_lookahead: usize,
table: HashMap<Vec<char>, char>
}
impl Parser {
pub fn new(config: &Config) -> Parser {
Parser {
max_lookahead: config
.iter()
.map(|&(ref s, _)|
s.len())
.fold(0, cmp::max),
table: config
.iter()
.map(|&(ref s, c)|
(s.chars().collect(), c))
.collect()
}
}
pub fn parse(&self, digits: &str) -> Vec<String> {
let v = digits.chars().collect::<Vec<char>>();
let parsed = self.parse_list(&v[..]);
parsed
.into_iter()
.map(|char_list| {
char_list
.into_iter()
.collect()
})
.collect()
}
fn parse_list(&self, ds: &[char]) -> Vec<WordInProgress> {
if ds.is_empty() {
vec![VecDeque::new()]
} else {
let max_lookahead_index = cmp::min(self.max_lookahead, ds.len());
let prefix = &ds[..max_lookahead_index];
(1 .. max_lookahead_index+1)
.flat_map(|lookahead_index| {
let unparsed_index = cmp::min(lookahead_index,
max_lookahead_index);
let token_slice = &prefix[..unparsed_index];
self.table.get(token_slice).map_or_else(
|| vec![],
|&c| {
let unparsed = &ds[unparsed_index..];
self.parse_list(unparsed)
.into_iter()
.map(|mut s| {
s.push_front(c);
s
})
.collect::<Vec<WordInProgress>>()
})
.into_iter()
})
.collect()
}
}
}
#[cfg(test)]
mod test {
use super::default_config;
use super::Parser;
use std::collections::HashSet;
#[test]
fn it_works() {
let parser = Parser::new(&default_config());
let expected = ["ABCD", "AWD", "LCD"];
let expected_set = expected
.iter()
.map(|s| s.to_string())
.collect::<HashSet<String>>();
let actual = parser.parse("1234");
let actual_set = actual
.into_iter()
.collect::<HashSet<String>>();
assert_eq!(actual_set, expected_set)
}
}