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
|
#include <iostream>
#include <fstream>
#include <vector>
#include <tuple>
using Grid = std::pair<std::vector<uint32_t>, std::vector<uint32_t>>;
std::vector<Grid> parse(const char* file)
{
if (std::ifstream input{ file }; input.is_open())
{
std::vector<uint32_t> rows, cols;
std::vector<Grid> grids;
std::string line;
while (not std::getline(input,line).eof())
{
if (cols.size() < line.size())
{
cols.resize(line.size(), 0);
}
if (line.empty())
{
grids.push_back(std::make_pair(std::move(cols), std::move(rows)));
rows = cols = std::vector<uint32_t>{};
continue;
}
int num{};
for (int i = 0; i < line.size(); ++i)
{
num *= 2;
num += line[i] == '#';
cols[i] *= 2;
cols[i] += line[i] == '#';
}
rows.push_back(num);
}
grids.push_back(std::make_pair(std::move(cols), std::move(rows)));
return grids;
}
return {};
}
bool equal(uint32_t a, uint32_t b, bool& smudge)
{
if (a == b) return true;
if (not smudge)
{
int smudges{};
uint32_t diff = a ^ b;
while (diff > 0)
{
smudges += diff % 2;
diff /= 2;
}
return smudge = smudges == 1;
}
return false;
}
int find_symmetry(const std::vector<uint32_t>& v)
{
for (int i = 1; i < v.size(); ++i)
{
bool smudge{ false };
if (equal(v[i-1], v[i], smudge))
{
bool sim{true};
for (int j = 1; j < std::min(i, (int)v.size() - i); ++j)
{
sim = sim && equal(v[i-1-j], v[i+j], smudge);
}
if (sim && smudge) return i;
}
}
return 0;
}
int main(int argc, char* argv[])
{
int answer{};
for (const auto& grid : parse(argv[1]))
{
answer += find_symmetry(grid.first);
answer += 100 * find_symmetry(grid.second);
}
std::cout << answer << std::endl;
return 0;
}
|
