/
day13.cpp
165 lines (142 loc) · 4.46 KB
/
day13.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
155
156
157
158
159
160
161
162
163
164
165
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <unordered_set>
struct pos_t{
int x = 0;
int y = 0;
};
bool operator==(const pos_t& a, const pos_t& b){ return std::tuple(a.x,a.y) == std::tuple(b.x,b.y); }
pos_t& operator+=(pos_t& a, const pos_t& b){ a.x += b.x; a.y += b.y; return a; }
struct pos_hash {
size_t operator()(const pos_t& pos) const {
return (pos.x + pos.y + 1) * (pos.x + pos.y) / 2 + pos.y; // cantor
}
};
struct pattern_t{
std::unordered_set<pos_t,pos_hash> map;
int width;
int height;
};
using pattens_t = std::vector<pattern_t>;
pattens_t load_input(const std::string& file){
pattens_t ret;
std::ifstream fs(file);
std::string line;
int y = 0;
ret.push_back(pattern_t());
while (std::getline(fs, line)) {
if(line.empty()){
ret.push_back(pattern_t());
y = 0;
continue;
}
for(int x=0; x<line.size(); ++x){
if(line[x] == '#'){
ret.back().map.insert({x,y});
}
}
y++;
ret.back().width = (int)line.size();
ret.back().height = y;
}
return ret;
}
int reflect(int relect_point, int pos){ return relect_point + (relect_point - pos - 1); }
int reflectable(int point, int extent){ return point >= 0 && point < extent; }
pos_t find_reflection(const pattern_t& pattern, int smudge_x, int smudge_y)
{
pos_t ref;
auto mirrored_in_y = [](const pattern_t& pattern, int y){
for(auto& rock : pattern.map){
pos_t mirrored = { rock.x, reflect(y, rock.y) };
if(reflectable(mirrored.y, pattern.height) && !pattern.map.count(mirrored)){
return false;
}
}
return true;
};
for(int y=1; y<pattern.height; ++y){
if(mirrored_in_y(pattern, y)){
if(smudge_y != -1 && !reflectable(reflect(y, smudge_y), pattern.height)){
continue; // only counts if smudge_y row is in reflection
}
ref.y = y;
break;
}
}
if(!ref.y)
{
auto mirrored_in_x = [](const pattern_t& pattern, int x){
for(auto& rock : pattern.map){
pos_t mirrored = { reflect(x, rock.x), rock.y };
if(reflectable(mirrored.x, pattern.width) && !pattern.map.count(mirrored)){
return false;
}
}
return true;
};
for(int x=1; x<pattern.width; ++x){
if(mirrored_in_x(pattern, x)){
if(smudge_x != -1 && !reflectable(reflect(x, smudge_x), pattern.width)){
continue; // only counts if smudge_x col is in reflection
}
ref.x = x;
break;
}
}
}
return ref;
}
size_t part1(const pattens_t& patterns)
{
pos_t sum;
for(auto& pattern : patterns){
sum += find_reflection(pattern, -1, -1);
}
return sum.x + 100 * sum.y;
}
size_t part2(pattens_t& patterns)
{
auto find_new_reflection = [](pattern_t& pattern)
{
for(int y=0; y<pattern.height; ++y){
for(int x=0; x<pattern.width; ++x){
bool removed = false;
bool inserted = false;
if(pattern.map.count({x,y})){
pattern.map.erase({x,y}); // # -> .
removed = true;
}else{
pattern.map.insert({x,y}); // . -> #
inserted = true;
}
pos_t ref = find_reflection(pattern, x, y);
if(ref.x || ref.y){
return ref;
}
if(removed){
pattern.map.insert({x,y}); // change back . -> #
}else if(inserted){
pattern.map.erase({x,y}); // change back # -> .
}
}
}
return pos_t{};
};
pos_t sum;
for(auto& pattern : patterns){
sum += find_new_reflection(pattern);
}
return sum.x + 100 * sum.y;
}
void main()
{
auto test_values = load_input("../src/day13/test_input.txt");
auto actual_values = load_input("../src/day13/input.txt");
std::cout << "part1: " << part1(test_values) << std::endl;
std::cout << "part1: " << part1(actual_values) << std::endl;
std::cout << "part2: " << part2(test_values) << std::endl;
std::cout << "part2: " << part2(actual_values) << std::endl;
}