Skip to content

Instantly share code, notes, and snippets.

@JohnCoconut
Created December 6, 2017 13:57
Show Gist options
  • Save JohnCoconut/41b1d52cbf2d872e0bc4050f378d2117 to your computer and use it in GitHub Desktop.
Save JohnCoconut/41b1d52cbf2d872e0bc4050f378d2117 to your computer and use it in GitHub Desktop.
advent of code 2017 day 6 part 1
#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <string>
#include <unordered_set>
#include <vector>
namespace std {
template <> struct hash<std::vector<int>> {
size_t operator()(const std::vector<int> &v) const {
std::size_t seed = v.size();
for (auto &i : v) {
seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
return seed;
}
};
} // namespace std
std::vector<int> readFromFile(const std::string &filename) {
std::ifstream ifs{filename};
std::vector<int> result{std::istream_iterator<int>{ifs}, {}};
return result;
}
std::vector<int> redistribute(std::vector<int> v) {
std::vector<int>::iterator index = std::max_element(v.begin(), v.end());
int maximum = *index;
int quotient = maximum / v.size();
int remainder = maximum % v.size();
*index = 0;
std::for_each(v.begin(), v.end(), [quotient](auto &a) { a += quotient; });
while (remainder > 0) {
++index;
if (index == v.end()) {
index = v.begin();
}
++*index;
--remainder;
}
return v;
}
int find_cycle(std::vector<int> v) {
std::unordered_set<std::vector<int>> s;
int step = 0;
while (true) {
if (s.count(v)) {
return step;
} else {
s.insert(v);
++step;
v = redistribute(v);
}
}
return step;
}
int main() {
std::vector<int> bank = readFromFile("text");
std::cout << find_cycle(bank) << std::endl;
return 0;
}
@JohnCoconut
Copy link
Author

Another solution found on reddit, https://www.reddit.com/r/adventofcode/comments/7hvtoq/2017_day_6_solutions/dqu8p6a/

std::vector<int> banks{std::istream_iterator<int>{std::cin}, {}};
std::map<std::vector<int>,int> unique;
for (int count{0}; unique.emplace(banks, count).second; ++count) {
  auto max = std::max_element(banks.begin(), banks.end());
  for (int iters{std::exchange(*max, 0)}; iters--; ++*max)
    if (++max == banks.end())
      max = banks.begin();
}
std::cout << unique.size() - (part2 ? unique[banks] : 0) << '\n';

It is much cleaner than mine.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment