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
|
#pragma once
#include "common.h"
#include <algorithm>
#include <vector>
namespace aoc2017 {
struct spiral_grid {
int dim;
std::vector<int> cells;
struct pos {
int x;
int y;
bool operator>(pos other) const noexcept { return x > other.x && y == other.y; }
};
int get(pos p) const noexcept {
int x = dim / 2;
int y = dim / 2;
return (p.y + y) * dim + p.x + x;
}
int value(pos p) const noexcept {
if (std::abs(p.x) > dim / 2 || std::abs(p.y) > dim / 2) {
return 0;
}
return cells[get(p)];
}
// 3, 5, 7, 9
spiral_grid(int d) : dim(d), cells(dim * dim, 0) {
cells[get({0, 0})] = 1;
cells[get({1, 0})] = 1;
cells[get({1, -1})] = 2;
}
pos last() const noexcept { return {dim / 2, dim / 2}; }
pos first() const noexcept { return {1, -1}; }
static pos left(pos p) { return {p.x - 1, p.y}; }
static pos down(pos p) { return {p.x, p.y + 1}; }
static pos right(pos p) { return {p.x + 1, p.y}; }
static pos up(pos p) noexcept { return {p.x, p.y - 1}; }
typedef pos (*mov)(pos);
void collect(pos* p, std::vector<pos>& ps, mov f, int times) const noexcept {
while (times-- > 0) {
*p = f(*p);
ps.emplace_back(*p);
}
}
std::vector<pos> circle() const noexcept {
// left, down, right, up
int sides[] = {2, 2, 3, 3};
mov ms[] = {left, down, right, up};
std::vector<pos> ps{};
pos p = first();
bool is_last{false};
while (!is_last) {
for (int i : {0, 1, 2, 3}) {
collect(&p, ps, ms[i], sides[i]);
if (p > last()) {
is_last = true;
break;
}
sides[i] += 2;
}
}
return ps;
}
int set(pos p) {
auto p1 = value({p.x, p.y + 1});
auto p2 = value({p.x, p.y - 1});
auto p3 = value({p.x - 1, p.y});
auto p4 = value({p.x + 1, p.y});
auto p5 = value({p.x + 1, p.y + 1});
auto p6 = value({p.x + 1, p.y - 1});
auto p7 = value({p.x - 1, p.y + 1});
auto p8 = value({p.x - 1, p.y - 1});
size_t i = get(p);
cells[i] = p1 + p2 + p3 + p4 + p5 + p6 + p7 + p8;
// printf("(%d, %d) -> %d (%d,%d,%d,%d,%d,%d,%d,%d)\n", p.x, p.y, cells[i], p1, p2, p3, p4, p5, p6, p7, p8);
return cells[i];
}
int fill_until(int t) {
auto ps = circle();
for (auto& p : ps) {
int x = set(p);
if (x > t) {
return x;
}
}
return 0;
}
};
int day3(int);
int day3part2(int);
} // namespace aoc2017
|
