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
|
// This code was made to try and touch as many different rust concepts as possible
// To make it faster I would probably use slice equality somehow
#![feature(test)]
use std::error::Error;
const WORDS: [&str; 18] = [
"1", "2", "3", "4", "5", "6", "7", "8", "9", "one", "two", "three", "four", "five", "six",
"seven", "eight", "nine",
];
const REVERSE_WORDS: [&str; 18] = [
"1", "2", "3", "4", "5", "6", "7", "8", "9", "eno", "owt", "eerht", "ruof", "evif", "xis",
"neves", "thgie", "enin",
];
#[derive(Debug)]
struct Node {
char: char,
children: Vec<Node>,
num: Option<i32>,
}
fn build_trees(words: [&str; 18]) -> Vec<Node> {
let mut roots: Vec<Node> = words
.iter()
.map(|w| w.chars().nth(0).unwrap())
.collect::<std::collections::HashSet<char>>()
.into_iter()
.map(|c| Node {
char: c,
children: vec![],
num: None,
})
.collect();
for iw in 0..words.len() {
let w = words[iw];
let mut node: &mut Node = roots
.iter_mut()
.find(|n| n.char == w.chars().nth(0).unwrap())
.unwrap();
for c in w.chars().skip(1) {
if let Some(idx) = node.children.iter().position(|n| n.char == c) {
node = &mut node.children[idx];
} else {
node.children.push(Node {
char: c,
children: vec![],
num: None,
});
node = node.children.last_mut().unwrap();
}
}
node.num = Some(((iw % 9) + 1).try_into().unwrap())
}
roots
}
fn find_match<I: Iterator<Item = char> + Clone>(trees: &Vec<Node>, iter: I) -> Option<i32> {
let mut it = iter.peekable();
let mut node: Option<&Node> = None;
while let Some(ch) = it.next() {
if node.is_none() {
node = trees.iter().find(|t| t.char == ch);
}
if let Some(mut r) = node {
let orig = it.clone();
loop {
if r.num.is_some() {
return r.num;
}
if let Some(c) = it.peek() {
if let Some(n) = r.children.iter().find(|t| t.char == *c) {
if n.num.is_some() {
return n.num;
}
it.next();
r = n;
continue;
} else {
node = None;
it = orig;
break;
}
}
}
}
}
None
}
fn main() -> Result<(), Box<dyn Error>> {
let trees = build_trees(WORDS);
let rev_trees = build_trees(REVERSE_WORDS);
let mut sum = 0;
for line in std::fs::read_to_string("input/1/in.txt")?.lines() {
let left = find_match(&trees, line.chars()).unwrap_or(0);
let right = find_match(&rev_trees, line.chars().rev()).unwrap_or(0);
sum += 10 * left + right;
}
println!("{}", sum);
Ok(())
}
extern crate test;
#[cfg(test)]
mod tests {
use super::*;
use test::Bencher;
#[bench]
fn other(b: &mut Bencher) {
b.iter(|| main());
}
}
|
