day_20b.cpp

#include <algorithm>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

void print(std::vector<int> prev, std::vector<int> next, std::vector<int> init_values, int start) {
  std::cout << "Order: ";
  int count = 0;
  int index = start;
  while(count < init_values.size()) {
    std::cout << init_values[index] << ' ';
    index = next[index];
    count++;
  }
  std::cout << '\n';
  index = prev[start];
  std::vector<long long> temp;
  count = 0;
  std::cout << "Order: ";
  while(count < init_values.size()) {
    temp.push_back(init_values[index]);
    index = prev[index];
    count++;
  }
  std::reverse(std::begin(temp), std::end(temp));
  for (const auto ele : temp) std::cout << ele << ' ';
  std::cout << '\n';
}

void print(std::vector<int> values) {
  for (const auto& ele : values) {
    std::cout << ele << ' ';
  }
  std::cout << '\n';
}

int main(int argc, char * argv[]) {
  std::string input = "../input/day_20_input";
  if (argc > 1) {
    input = argv[1];
  }
  std::string line;
  std::fstream file(input);

  std::vector<long long> init_values;
  constexpr long long decryption_key = 811589153;
  while(std::getline(file, line)) {
    init_values.push_back(std::stoi(line) * decryption_key);
  }

  std::vector<int> next(init_values.size());
  std::vector<int> prev(init_values.size());
  for (int i = 0; i < init_values.size(); i++) {
    next[i] = i + 1;
    prev[i] = i - 1;
  }
  prev[0] = prev.size() - 1;
  next[next.size() - 1] = 0;
  int start  = 0;

  for (int n = 0; n < 10; n++) {
    for (int i = 0; i < init_values.size(); i++) {
      // std::cout << "Moving value: " << init_values[i] << '\n';
      long long delta = init_values[i];
      long long dd = (delta == 0) ? 0 : delta/std::abs(delta);
      int current = i;
      if (i == start ) {
        if (init_values[start] != 0) {
          start = next[start];
        }
      }
      if (dd > 0) {
        delta = delta % (init_values.size()-1);
        next[prev[i]] = next[i];
        prev[next[i]] = prev[i];
        while (delta != 0) {
          // std::cout << init_values[i] << " jumps in front of " << init_values[next[current]] << '\n';
          current = next[current];
          delta -= dd;
        }
        next[i] = next[current];
        prev[next[current]] = i;
        prev[i] = current;
        next[current] = i;
        // std::cout << init_values[i] << " is now prev to "<< init_values[next[current]] << '\n';
        // std::cout << init_values[current] << " is now prev to "<< init_values[i] << '\n';
      } else if (dd < 0) {
        delta = -(std::abs(delta) % (init_values.size() - 1));
        next[prev[i]] = next[i];
        prev[next[i]] = prev[i];
        while (delta != 0) {
          // std::cout << init_values[i] << " jumps behind " << init_values[prev[current]] << '\n';
          current = prev[current];
          delta -= dd;
        }

        next[i] = current;
        next[prev[current]] = i;
        prev[i] = prev[current];
        prev[current] = i;
      }
      // print(prev, next, init_values, start);
      // std::cout << '\n';
    }
    // print(prev, next, init_values, start);
  }

  auto temp = std::vector<long long>();
  int count = 0;
  int index = start;
  while(count < init_values.size()) {
    temp.push_back(init_values[index]);
    index = next[index];
    count++;
  }
  // std::cout << (temp.size() == init_values.size()) << '\n';
  long long ans = 0;
  // print(temp);
  auto index_0 = std::find(std::begin(temp), std::end(temp), 0) - std::begin(temp);
  // std::cout << index_0 << '\n';
  index = (1000 % init_values.size() + index_0) % init_values.size();
  // std::cout << temp[index] << ' ';
  ans += temp[index];
  index = (2000 % init_values.size() + index_0) % init_values.size();
  // std::cout << temp[index] << ' ';
  ans += temp[index];
  index = (3000 % init_values.size() + index_0) % init_values.size();
  // std::cout << temp[index] << ' ';
  ans += temp[index];
  // std::cout << '\n';
  std::cout << ans << '\n';
}