Solution to part 2 of www.adventofcode.com/2018/day/1

aoc1_gist.cpp

// Copyright 2018 Google LLC.
// SPDX-License-Identifier: Apache-2.0
// Solution to part 2 of www.adventofcode.com/2018/day/1
#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <unordered_map>
#include <vector>

struct Point {
  size_t x;
  int fx;
};

bool operator<(Point const &lhs, Point const &rhs) { return lhs.fx < rhs.fx; }

int comp(std::vector<int> const &vec) {
  int M = 0;
  for (int el : vec) {
    M += el;
  }
  assert(M > 0);
  int subtotal = 0;
  std::unordered_map<size_t, std::vector<Point>> buckets;
  for (size_t i = 0; i < vec.size(); ++i) {
    auto normalised = subtotal / M;
    auto bucket = subtotal % M;
    if (subtotal < 0) {
      normalised -= 1;
      bucket += M;
    }
    Point const p{i + 1, normalised};
    buckets[bucket].push_back(p);
    subtotal += vec[i];
  }
  size_t best_runs = size_t(-1);
  size_t best_index = size_t(-1);
  int best_value = 0;
  for (auto &kvp : buckets) {
    auto const &mod = kvp.first;
    auto &bucket = kvp.second;
    std::sort(bucket.begin(), bucket.end());

    for (size_t i = 1; i < bucket.size(); ++i) {
      size_t runs = bucket[i].fx - bucket[i - 1].fx;
      size_t index = bucket[i - 1].x;
      size_t value = bucket[i].fx * M + mod;
      if (runs < best_runs || (runs == best_runs && index < best_index)) {
        best_runs = runs;
        best_index = index;
        best_value = value;
      }
    }
  }
  return best_value;
}

int main() {
  std::vector<int> data;
  std::copy(std::istream_iterator<int>{std::cin}, std::istream_iterator<int>{},
            std::back_inserter(data));
  std::cout << comp(data) << '\n';
}