aboutsummaryrefslogtreecommitdiff
path: root/src/day16.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/day16.cpp')
-rw-r--r--src/day16.cpp132
1 files changed, 0 insertions, 132 deletions
diff --git a/src/day16.cpp b/src/day16.cpp
deleted file mode 100644
index 93c7479..0000000
--- a/src/day16.cpp
+++ /dev/null
@@ -1,132 +0,0 @@
1#include <array>
2#include <chrono>
3#include <fstream>
4#include <iostream>
5#include <map>
6#include <queue>
7#include <set>
8#include <string>
9#include <vector>
10using namespace std;
11
12vector<string>
13read_file(string_view filename)
14{
15 fstream input{ filename };
16 vector<string> data;
17
18 for ( string line; getline(input, line); ) {
19 data.emplace_back(line);
20 }
21
22 return data;
23}
24
25const unsigned DIR_UP = 0;
26const unsigned DIR_RIGHT = 1;
27const unsigned DIR_DOWN = 2;
28const unsigned DIR_LEFT = 3;
29
30size_t
31solve(const vector<string>& lines, tuple<size_t, size_t, unsigned int> start)
32{
33 static const array<tuple<size_t, size_t>, 4> movement{
34 make_tuple(0, -1),
35 make_tuple(1, 0),
36 make_tuple(0, 1),
37 make_tuple(-1, 0),
38 };
39
40 map<tuple<size_t, size_t, unsigned int>, bool> visited;
41
42 queue<tuple<size_t, size_t, unsigned int>> positions;
43
44 positions.emplace(start);
45
46 while ( !positions.empty() ) {
47 auto [row, col, dir] = positions.front();
48 positions.pop();
49
50 while ( true ) {
51 col += get<0>(movement.at(dir % 4));
52 row += get<1>(movement.at(dir % 4));
53
54 if ( row >= lines.size() || col >= lines[0].size() ) {
55 break;
56 }
57
58 if ( visited[{ row, col, dir }] ) {
59 break;
60 }
61
62 visited[{ row, col, dir }] = true;
63
64 const auto chr = lines[row][col];
65
66 if ( (chr == '|' && (dir == DIR_LEFT || dir == DIR_RIGHT)) ||
67 (chr == '-' && (dir == DIR_UP || dir == DIR_DOWN)) ) {
68 dir = dir + 1;
69 positions.emplace(row, col, dir + 2);
70 }
71 else if ( (chr == '/' && (dir == DIR_LEFT || dir == DIR_RIGHT)) ||
72 (chr == '\\' && (dir == DIR_UP || dir == DIR_DOWN)) ) {
73 dir = dir + 3;
74 }
75 else if ( (chr == '\\' && (dir == DIR_LEFT || dir == DIR_RIGHT)) ||
76 (chr == '/' && (dir == DIR_UP || dir == DIR_DOWN)) ) {
77 dir = dir + 1;
78 }
79
80 dir %= 4;
81 }
82 }
83
84 set<tuple<size_t, size_t>> foo;
85 for ( const auto& bar: visited ) {
86 foo.emplace(get<0>(bar.first), get<1>(bar.first));
87 }
88 return foo.size();
89}
90
91void
92part1(const vector<string>& lines)
93{
94 auto start = chrono::steady_clock::now();
95
96 auto sum = solve(lines, { 0, -1, DIR_RIGHT });
97
98 auto duration = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
99
100 cout << sum << " (" << duration << "ms)" << endl;
101}
102
103void
104part2(const vector<string>& lines)
105{
106 const auto rows = lines.size();
107 const auto cols = lines[0].size();
108
109 auto start = chrono::steady_clock::now();
110
111 size_t sum = 0;
112 for ( size_t row = 0; row != rows; ++row ) {
113 sum = max(sum, solve(lines, { row, -1, DIR_RIGHT }));
114 sum = max(sum, solve(lines, { row, cols, DIR_LEFT }));
115 }
116 for ( size_t col = 0; col != cols; ++col ) {
117 sum = max(sum, solve(lines, { -1, col, DIR_DOWN }));
118 sum = max(sum, solve(lines, { rows, col, DIR_UP }));
119 }
120
121 auto duration = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();
122
123 cout << sum << " (" << duration << "ms)" << endl;
124}
125
126int
127main()
128{
129 const auto lines = read_file("data/day16.txt");
130 part1(lines);
131 part2(lines);
132}