1extern crate generic_matrix;
3
4use generic_matrix::Matrix;
5use std::io;
6use std::time::{Duration, Instant};
7
8mod words;
9
10pub fn run(num_rounds: u32, num_words: u32) {
13 let mut mistake_count = 0;
14 let mut char_count = 0;
15 let mut word_count = 0;
16 let mut elapsed_time: Duration = Duration::from_secs(0);
17
18 for _ in 0..num_rounds {
19 let result = play_one_round(num_words);
20 mistake_count += result.mistakes;
21 char_count += result.answer.chars().count();
22 word_count += num_words;
23 elapsed_time += result.time;
24
25 if result.mistakes == 0 {
26 println!("Correct!\n");
27 } else {
28 println!("Number of mistakes: {}\n", result.mistakes);
29 }
30 }
31
32 print_results(mistake_count, char_count, word_count, elapsed_time);
33}
34
35fn play_one_round(num_words: u32) -> RoundResult {
37 let line = generate_string(num_words);
38
39 println!("{}", line);
40 let mut answer = String::new();
41
42 let begin = Instant::now();
43 io::stdin()
44 .read_line(&mut answer)
45 .expect("Failed to read from console.");
46 let end = Instant::now();
47
48 let answer = String::from(answer.trim());
49 let mistakes = edit_distance(line.trim(), &answer);
50
51 RoundResult {
52 answer,
53 mistakes,
54 time: end - begin,
55 }
56}
57
58struct RoundResult {
60 answer: String,
61 mistakes: u32,
62 time: Duration,
63}
64
65fn print_results(mistake_count: u32, char_count: usize, word_count: u32, elapsed_time: Duration) {
66 if word_count == 0 || elapsed_time.as_secs() == 0 {
68 println!("No data to calculate.");
69 return;
70 }
71
72 let secs = elapsed_time.as_secs() as f64;
73
74 println!(
75 "{:30}{:>.3}\n\
76 {:30}{:>.3}\n",
77 "Mistakes per word:",
78 mistake_count as f64 / word_count as f64,
79 "Characters per second:",
80 char_count as f64 / secs,
81 );
82}
83
84fn generate_string(num_words: u32) -> String {
87 (0..num_words)
88 .map(|_| words::get_word())
89 .collect::<Vec<_>>()
90 .join(" ")
91}
92
93fn edit_distance(a: &str, b: &str) -> u32 {
95 let a: Vec<char> = a.chars().collect();
96 let b: Vec<char> = b.chars().collect();
97
98 let mut distances = Matrix::from_fn(a.len() + 1, b.len() + 1, |_, _| 0);
99
100 for j in 1..=b.len() {
102 distances[(0, j)] = j as u32;
103 }
104
105 for i in 1..=a.len() {
106 distances[(i, 0)] = i as u32;
107 }
108
109 use std::cmp::min;
110
111 for i in 1..=a.len() {
112 for j in 1..=b.len() {
113 let compare = if a[i - 1] == b[j - 1] { 0 } else { 1 };
114 let distance = min(
115 distances[(i, j - 1)] + 1,
116 min(
117 distances[(i - 1, j)] + 1,
118 distances[(i - 1, j - 1)] + compare,
119 ),
120 );
121 distances[(i, j)] = distance;
122 }
123 }
124
125 distances[(a.len(), b.len())]
126}
127
128#[cfg(test)]
129mod tests {
130 use super::*;
131
132 #[test]
133 fn test_edit_distance_short_cases() {
134 assert_eq!(0, edit_distance("", ""));
135 assert_eq!(0, edit_distance("a", "a"));
136 assert_eq!(1, edit_distance("x", ""));
137 assert_eq!(1, edit_distance("", "q"));
138 assert_eq!(1, edit_distance("p", "q"));
139 assert_eq!(1, edit_distance("ap", "p"));
140 assert_eq!(2, edit_distance("ap", "b"));
141 }
142
143 #[test]
144 fn test_edit_distance_normal_words() {
145 assert_eq!(3, edit_distance("hector", "extort"));
146 assert_eq!(4, edit_distance("abcd", "defg"));
147 }
148
149 #[test]
150 fn test_non_ascii_characters() {
151 assert_eq!(
152 4,
153 edit_distance("Добрый день", "Добрый вечер")
154 );
155 }
156
157 #[test]
158 fn test_edit_distance_big_difference() {
159 assert_eq!(10, edit_distance("", "1234567890"));
160 assert_eq!(10, edit_distance("abc", "1234567890abc"));
161 assert_eq!(10, edit_distance("abc", "abc1234567890"));
162 assert_eq!(13, edit_distance("abc", "abc1234567890abc"));
163
164 assert_eq!(10, edit_distance("1234567890", ""));
165 assert_eq!(10, edit_distance("1234567890abc", "abc"));
166 assert_eq!(10, edit_distance("abc1234567890", "abc"));
167 assert_eq!(13, edit_distance("abc1234567890abc", "abc"));
168 }
169}