diff options
author | Leah Neukirchen <leah@vuxu.org> | 2017-12-15 13:52:16 +0100 |
---|---|---|
committer | Leah Neukirchen <leah@vuxu.org> | 2017-12-15 13:52:16 +0100 |
commit | f4e01b6401a224fddc3143b15031c6ef60e15efd (patch) | |
tree | d56265ce9dc32792cc20e613a408c4ab4892c6f0 /day14.cc | |
parent | 84e0e9d9e382344e36103c36cb9b47137a75e7d3 (diff) | |
download | adventofcode2017-f4e01b6401a224fddc3143b15031c6ef60e15efd.tar.gz adventofcode2017-f4e01b6401a224fddc3143b15031c6ef60e15efd.tar.xz adventofcode2017-f4e01b6401a224fddc3143b15031c6ef60e15efd.zip |
day14
Diffstat (limited to 'day14.cc')
-rw-r--r-- | day14.cc | 75 |
1 files changed, 75 insertions, 0 deletions
diff --git a/day14.cc b/day14.cc new file mode 100644 index 0000000..55b02fd --- /dev/null +++ b/day14.cc @@ -0,0 +1,75 @@ +#include <array> +#include <bitset> +#include <functional> +#include <iostream> +#include <numeric> +#include <string> +#include <vector> + +using namespace std; + +template <typename T> +auto knothash(T iter, int n=64) +{ + vector<uint8_t> v(256); + iota(begin(v), end(v), 0); + + uint8_t skip = 0, pos = 0, delta; + + for (int j = 0; j < n; j++) + for (auto i : iter) { + reverse(begin(v), begin(v) + i); + delta = i + skip++; + rotate(begin(v), begin(v) + delta, end(v)); + pos += delta; + } + rotate(begin(v), end(v) - pos, end(v)); + + return move(v); +} + +int +main() { + string line; + cin >> line; + + int p1{0}; + int p2{0}; + + array<array<int, 128>, 128> a; + + for (int i = 0; i < 128; ++i) { + string s = line + "-" + to_string(i); + s.append({17,31,73,47,23}); + + vector<uint8_t> v{knothash(s)}; + + int j = 0; + for (auto r = begin(v); r != end(v); advance(r, 16)) { + bitset<8> b = + accumulate(r, r + 16, 0, bit_xor<uint8_t>()); + p1 += b.count(); + for (int n = 7; n >= 0; n--) + a[i][j++] = -b[n]; + } + } + + std::function<void (int,int,int)> fill = [&](int i, int j, int c) { + if (i < 0 || i >= size(a) || + j < 0 || j >= size(a) || + a[i][j] >= 0) + return; + a[i][j] = c; + fill(i-1, j, c); + fill(i+1, j, c); + fill( i, j-1, c); + fill( i, j+1, c); + }; + + for (int i = 0; i < size(a); i++) + for (int j = 0; j < size(a[i]); j++) + if (a[i][j] < 0) + fill(i, j, ++p2); + + cout << p1 << endl << p2 << endl; // 8226 1128 +} |