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
122
123
124
125
126
127
|
use std::{
collections::HashSet,
io::{stdin, Read},
mem,
};
fn to_str(v: &[u8]) -> String {
let mut res = String::with_capacity(v.len() * 3 / 2);
for &c in v {
res.push(match c {
b'a'..=b'z' => c as char,
b'1' => 'å',
b'2' => 'ä',
b'3' => 'ö',
_ => unreachable!(c),
});
}
res
}
fn main() {
let mut input = String::new();
let _ = stdin().lock().read_to_string(&mut input);
let lines: Vec<Vec<u8>> = input
.lines()
.map(|l| {
l.chars()
.map(|c| match c {
'a'..='z' => c as u32 as u8,
'å' => b'1',
'ä' => b'2',
'ö' => b'3',
'#' => b'#',
_ => unreachable!(),
})
.collect()
})
.collect();
let (wordlist, words) = {
let mut s = lines.splitn(2, |l| l == &[b'#']);
(s.next().unwrap(), s.next().unwrap())
};
let mut wordset = HashSet::new();
let mut chars = vec![HashSet::<u8>::new(); 42];
for w in wordlist {
wordset.insert(w);
for (i, &c) in w.iter().enumerate() {
chars[i].insert(c);
}
}
let longest = wordlist.iter().fold(0, |acc, w| acc.max(w.len()));
let shortest = wordlist.iter().fold(69, |acc, w| acc.min(w.len()));
for start in words {
let mut curr = vec![start.clone()];
let mut next: Vec<Vec<u8>> = vec![];
let mut visited = HashSet::new();
let mut found = vec![];
let mut depth = 0;
loop {
for mut w in curr.drain(..) {
if visited.contains(&w) {
continue;
}
visited.insert(w.clone());
if wordset.contains(&w) {
found.push(w);
continue;
}
if !found.is_empty() {
continue;
}
for i in 0..w.len() {
let orig_c = w[i];
for &c in b"qwfpbkluy2arstgmneio1zxcdvjh3" {
if !chars[i].contains(&c) {
continue;
}
w[i] = c;
next.push(w.clone());
}
w[i] = orig_c;
if w.len() < longest {
for &c in b"qwfpbkluy2arstgmneio1zxcdvjh3" {
if !chars[i].contains(&c) {
continue;
}
let mut cpy = w[..i].to_owned();
cpy.push(c);
cpy.append(&mut w[i..].to_owned());
next.push(cpy);
}
}
if w.len() > shortest {
let mut cpy = w[..i].to_owned();
cpy.append(&mut w[i + 1..].to_owned());
next.push(cpy);
}
}
if w.len() < longest {
for &c in b"qwfpbkluy2arstgmneio1zxcdvjh3" {
if !chars[w.len()].contains(&c) {
continue;
}
let mut cpy = w.clone();
cpy.push(c);
next.push(cpy);
}
}
}
if !found.is_empty() {
break;
}
mem::swap(&mut curr, &mut next);
depth += 1;
}
found.sort();
print!("{} ({})", to_str(&start), depth);
for w in found {
print!(" {}", to_str(&w));
}
println!();
}
}
|
