solution09.cc

#include "advent/answer.h"

#include <numeric>

namespace advent2020 {
void Solution9(std::istream &input, advent::Answer &ans) {
  std::vector<uint64_t> nums;
  ans.ParseInts(input, nums);

  // part1
  constexpr size_t window_size = 25;
  uint64_t target = 0;
  for (auto i = nums.begin() + window_size; i != nums.end(); ++i) {
    for (auto j = i - window_size; j < i - 1; ++j) {
      for (auto k = j + 1; k < i; ++k) {
        if (*i == *j + *k) {
          goto outer;
        }
      }
    }
    target = *i;
    break;
  outer:;
  }
  ASSERT_DEBUG(target != 0);
  ans.Part1(target);

  // part2
  for (auto i = nums.begin(), j = i + 2; j < nums.end();) {
    uint64_t sum = std::accumulate(i, j, 0);
    if (sum == target) {
      const auto [min, max] = std::minmax_element(i, j);
      ans.Part2(*min + *max);
      break;
    } else if (sum < target) {
      ++j;
    } else {
      ++i;
      ASSERT_DEBUG(std::distance(i, j) >= 2);
    }
  }
}
}  // namespace advent2020