-
Notifications
You must be signed in to change notification settings - Fork 0
/
22.cpp
154 lines (127 loc) · 4.46 KB
/
22.cpp
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
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <cstdlib>
#include <cmath>
using namespace std;
template<typename T>
class Matrix
{
vector<T> data;
int w, h;
public:
Matrix(int w, int h) : w(w), h(h)
{
data.resize(w * h);
}
T& operator()(int x, int y)
{
return data[w * y + x];
}
int width() { return w; }
int height() { return h; }
};
int main(int argc, char **argv)
{
if (argc < 4) {
cerr << "usage: %s depth target_x target_y" << endl;
return 1;
}
int depth = atoi(argv[1]);
int target_x = atoi(argv[2]);
int target_y = atoi(argv[3]);
auto erosion_level = [depth](long geologic_index) {
return (geologic_index + depth) % 20183;
};
Matrix<long> matrix(target_x * 5, target_y * 3);
matrix(0, 0) = erosion_level(0);
matrix(target_x, target_y) = erosion_level(0);
for(int x = 1; x < matrix.width(); ++x) {
matrix(x, 0) = erosion_level((long)x * 16807);
}
for(int y = 1; y < matrix.height(); ++y) {
matrix(0, y) = erosion_level((long)y * 48271);
}
for(int x = 1; x < matrix.width(); ++x) {
for(int y = 1; y < matrix.height(); ++y) {
if (x != target_x || y != target_y) {
matrix(x, y) = erosion_level(matrix(x - 1, y) * matrix(x, y - 1));
}
}
}
long risk = 0;
for(int x = 0; x <= target_x; ++x) {
for(int y = 0; y <= target_y; ++y) {
risk += matrix(x, y) % 3;
}
}
cout << risk << endl;
// and now, for something completely different...
// ... but kind of the same
// topography tooling
// . 0 T C 0 1
// = 1 C N 1 2
// | 2 T N 0 2
// so we will model this as a three-dimensional maze with height 3
// where the z axis wraps around, and there is an open vertical space
// of height 2 in every (x, y) coordinate, starting at z = risk/topo.
// where we start at (0, 0, 0) and end at (target_x, target_y, 0).
// it costs 7 to move in z, and 1 to move in (x, y).
// now I get to implement A* yet again!
struct Coord {
int x, y, z;
bool operator==(const Coord& rhs) const {
return x == rhs.x && y == rhs.y && z == rhs.z;
}
bool operator<(const Coord& rhs) const {
return z < rhs.z ||
(z == rhs.z && y < rhs.y) ||
(z == rhs.z && y == rhs.y && x < rhs.x);
}
};
struct QueueEntry {
Coord c;
int est_total_time;
bool operator<(const QueueEntry& rhs) const {
return est_total_time > rhs.est_total_time;
}
};
Coord home{0, 0, 0};
Coord target{target_x, target_y, 0};
auto time_bound = [&target](const Coord& coord) {
return abs(target.x - coord.x) + abs(target.y - coord.y) + ((coord.z > 0) ? 7 : 0);
};
auto open_cell = [&matrix](const Coord& coord) {
int topo = matrix(coord.x, coord.y) % 3;
return coord.z != (topo + 2) % 3;
};
priority_queue<QueueEntry> fringe;
fringe.push({home, time_bound(home)});
map<Coord, int> best_time_to = {{home, 0}};
while (!fringe.empty()) {
auto current = fringe.top();
fringe.pop();
int time_so_far = best_time_to[current.c];
if (current.c == target) {
cout << time_so_far << endl;
return 0;
}
auto consider_neighbor = [&](Coord c, int sub_time) {
if (open_cell(c)) {
if (!best_time_to.contains(c) || sub_time < best_time_to[c]) {
best_time_to[c] = sub_time;
fringe.push({c, sub_time + time_bound(c)});
}
}
};
if (current.c.x > 0) consider_neighbor({current.c.x - 1, current.c.y, current.c.z}, time_so_far + 1);
if (current.c.y > 0) consider_neighbor({current.c.x, current.c.y - 1, current.c.z}, time_so_far + 1);
if (current.c.x < matrix.width() - 1) consider_neighbor({current.c.x + 1, current.c.y, current.c.z}, time_so_far + 1);
if (current.c.y < matrix.height() - 1) consider_neighbor({current.c.x, current.c.y + 1, current.c.z}, time_so_far + 1);
consider_neighbor({current.c.x, current.c.y, (current.c.z + 1) % 3}, time_so_far + 7);
consider_neighbor({current.c.x, current.c.y, (current.c.z + 2) % 3}, time_so_far + 7);
}
cout << "no path found :(" << endl;
return 1;
}