-
Notifications
You must be signed in to change notification settings - Fork 0
/
day1.cc
214 lines (189 loc) · 7.13 KB
/
day1.cc
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include <iostream>
#include "absl/flags/flag.h"
#include "absl/flags/parse.h"
#include "absl/strings/str_cat.h"
#include "absl/status/statusor.h"
#include "absl/container/flat_hash_set.h"
#include <fstream>
#include <string>
#include <iostream>
#include <cstdlib>
#include <memory>
ABSL_FLAG(std::string, input_file, "", "Input file to process");
// Which direction we search through a line of text.
enum SearchDirection { FORWARD, REVERSE };
// Represents a position in a tree of all remaining possible matches for a given
// attempt. For example, if the last two characters are "on", then we'd have an
// instance of this WordTree that's got one more possibilty left - if the next
// letter is "e", then we've matched 1.
// If the previous letter was "t", then this WordTree state has two possible
// matches remaining: (t)wo, (t)hree.
class WordTree;
// Builds a WordTree for searching for words from the left.
std::unique_ptr<const WordTree> BuildForwardWordTree();
// Builds a WordTree for searching for words from the right.
std::unique_ptr<const WordTree> BuildReverseWordTree();
// Finds the first digit from either the left or right, given the input WordTree.
absl::StatusOr<int> FindFirstDigit(const std::string& line,
SearchDirection search_direction,
std::unique_ptr<const WordTree>& word_tree);
// Builds two WordTrees, one for each direction we're searching:
// - Forward: index words "one", "two", "three", etc
// - Backward: index words "eno", "owt", "eerht", etc
// Read each line from the input file, traverse from the left with the
// forward index, and from the right with the backward index, keeping
// a collection of running matches, stopping traversal once we find
// a digit, either as a single digit character, or a digit spelled out.
int main(int argc, char* argv[]) {
absl::ParseCommandLine(argc, argv);
// Build an index for each forward and backward searching.
std::unique_ptr<const WordTree> forward_tree = BuildForwardWordTree();
std::unique_ptr<const WordTree> reverse_tree = BuildReverseWordTree();
std::string file_name = absl::GetFlag(FLAGS_input_file);
std::cout << "Loading: " << file_name << std::endl << std::endl;
std::ifstream file(absl::StrCat(file_name));
if (!file.is_open()) {
std::cerr << "Unable to open file\n";
return 1;
}
std::string line;
int sum = 0;
while (std::getline(file, line)) {
absl::StatusOr<int> left = FindFirstDigit(line, FORWARD, forward_tree);
absl::StatusOr<int> right = FindFirstDigit(line, REVERSE, reverse_tree);
if (!left.ok() || !right.ok()) {
std::cout << "ERROR\n";
return 2;
}
int this_num = *left * 10 + *right;
std::cout << this_num << ": " << line << "\n";
sum += this_num;
}
std::cout << "\nSum: " << sum << "\n\n";
return 0;
}
class WordTree {
public:
// Creates a new tree with no matching digit at this node.
WordTree()
: digit_(-1)
{}
// Creates a new tree with a matching digit at this node.
WordTree(int digit)
: digit_(digit)
{
for (int i = 0; i < 26; i++) {
next_[i] = nullptr;
}
}
~WordTree() {
for (int i = 0; i < 26; i++) {
delete(next_[i]);
next_[i] = nullptr;
}
}
// Returns the digit found, or -1 if nothing yet.
int DigitFound() const {
return digit_;
}
// Finds the WordTree at the next letter, or nullptr if end of line.
WordTree* Find(char letter) const {
return next_[Normalize(letter)];
}
// Indexes a string into the tree as a possible match.
void IndexString(std::string str, int digit) {
if (str.size() == 0) {
std::cout << "ERROR! Size is zero\n";
exit(-1);
}
// ensure target home
int letter_index = Normalize(str.at(0));
if (next_[letter_index] == nullptr) {
next_[letter_index] = new WordTree(str.size() == 1 ? digit : -1);
}
if (str.size() > 1) {
next_[letter_index]->IndexString(str.substr(1), digit);
}
}
private:
// Normalizes the letter for our 26-position index, moving 'a' to index 0,
// 'z' to index 25.
static int Normalize(char letter) {
int ret = (int)(letter - 'a');
if (ret >= 26) {
std::cout << "Found invalid letter: '" << letter << "'\n";
exit(-2);
}
return ret;
}
// if set to something other than -1, we've found a spelled-out digit.
const int digit_;
// child nodes of remaining possibile matches, where 'a' is the 0-index,
// 'z' is the 25th.
WordTree* next_[26];
};
absl::StatusOr<int> FindFirstDigit(
const std::string& line,
SearchDirection search_direction,
std::unique_ptr<const WordTree>& word_tree) {
absl::flat_hash_set<WordTree*> possible_matches;
int start = search_direction == FORWARD ? 0 : line.size() - 1;
int step = search_direction == FORWARD ? 1 : -1;
for (int pos = start; pos >= 0 && pos < line.size(); pos += step) {
// check for digit
// Note: could have indexed these too, but this is simpler, and keeps the index smaller.
int digit = line.at(pos) - '0';
if (digit >= 0 && digit <= 9) {
return digit;
}
// we're spelling - evaluate matches we're in the middle of
absl::flat_hash_set<WordTree*> new_matches;
char this_letter = line.at(pos);
for (auto it = possible_matches.begin(); it != possible_matches.end(); it++) {
WordTree* found = (*it)->Find(this_letter);
if (found != nullptr) {
// match is ongoing - see if finished
if (int digit_found = found->DigitFound(); digit_found != -1) {
// found match!
return digit_found;
}
new_matches.insert(found);
}
}
// start a new search
WordTree* next_possible_match = word_tree->Find(this_letter);
if (next_possible_match != nullptr) {
new_matches.insert(next_possible_match);
}
possible_matches = new_matches;
}
return absl::InvalidArgumentError("Couldn't find any digit");
}
std::unique_ptr<const WordTree> BuildForwardWordTree() {
std::unique_ptr<WordTree> ret = std::make_unique<WordTree>();
ret->IndexString("one", 1);
ret->IndexString("two", 2);
ret->IndexString("three", 3);
ret->IndexString("four", 4);
ret->IndexString("five", 5);
ret->IndexString("six", 6);
ret->IndexString("seven", 7);
ret->IndexString("eight", 8);
ret->IndexString("nine", 9);
ret->IndexString("zero", 0);
return ret;
}
std::unique_ptr<const WordTree> BuildReverseWordTree() {
std::unique_ptr<WordTree> ret = std::make_unique<WordTree>();
ret->IndexString("eno", 1);
ret->IndexString("owt", 2);
ret->IndexString("eerht", 3);
ret->IndexString("ruof", 4);
ret->IndexString("evif", 5);
ret->IndexString("xis", 6);
ret->IndexString("neves", 7);
ret->IndexString("thgie", 8);
ret->IndexString("enin", 9);
ret->IndexString("orez", 0);
return ret;
}