aocpp/2019/12.cpp

#include <algorithm>
#include <array>
#include <cinttypes>
#include <cstdint>
#include <cstdio>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

#include <aocpp/Startup.hpp>

namespace {

struct Particle {
  std::int64_t pos;
  std::int64_t vel;
  auto operator==(Particle const& x) const -> bool = default;
};

auto Step(std::vector<Particle> & ps) {
  // apply gravity to update velocities
  auto n = ps.size();
  for (std::size_t i = 0; i+1 < n; i++) {
    for (std::size_t j = i+1; j < n; j++) {
      auto v = (ps[i].pos < ps[j].pos) - (ps[i].pos > ps[j].pos);
      ps[i].vel += v;
      ps[j].vel -= v;
    }
  }
  // apply velocities to update positions
  for (auto & p : ps) {
    p.pos += p.vel;
  }
}

auto CycleLength(std::vector<Particle> const& particles) -> std::int64_t {
  auto ps = particles;
  std::int64_t n = 0;
  do {
    Step(ps);
    n++;
  } while (!std::equal(ps.begin(), ps.end(), particles.begin()));
  return n;
}

/// Parse input as a vector of particle systems by axis.
auto Parse(std::istream & in) -> std::array<std::vector<Particle>,3> {
  std::array<std::vector<Particle>,3> result;
  std::string line;
  while (std::getline(in, line)) {
    std::int64_t x, y, z;
    auto res =
      std::sscanf(
        line.c_str(),
        "<x=%" SCNi64 ", y=%" SCNi64 ", z=%" SCNi64 ">",
        &x, &y, &z);
    if (3 != res) { throw std::runtime_error{"bad input"}; }
    result[0].push_back({x,0});
    result[1].push_back({y,0});
    result[2].push_back({z,0});
  }
  return result;
}

/// Compute part 1 by iterating the simulation step and compute the resulting
/// system energy.
auto Part1(std::array<std::vector<Particle>, 3> system, std::int64_t const n) {
  for (auto && ps : system) {
    for (std::int64_t i = 0; i < n; i++) { Step(ps); }
  }

  std::int64_t result = 0;
  for (std::size_t i = 0; i < system[0].size(); i++) {
    std::int64_t xsum = 0;
    std::int64_t vsum = 0;
    for (auto && ps : system) {
       xsum += std::abs(ps[i].pos);
       vsum += std::abs(ps[i].vel);
    }
    result += xsum * vsum;
  }
  return result;
}

auto Part2(std::array<std::vector<Particle>, 3> const& ps) {
  std::int64_t n = 1;
  for (auto && p : ps) {
    n = std::lcm(n, CycleLength(p));
  }
  return n;
}

} // namespace

auto Main(std::istream & in, std::ostream & out) -> void
{
  auto ps = Parse(in);
  auto const part2 = Part2(ps);
  auto const part1 = Part1(std::move(ps), 1000);

  out << "Part 1: " << part1 << std::endl;
  out << "Part 2: " << part2 << std::endl;
}