rambunctious_recitation.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;
/*
Advent of Code 2020 - Day 15
*/


/*
// V1
int main() {
  // actual input
  vector<int> input = {5, 1, 9, 18, 13, 8, 0};
  // sample input 
  // vector<int> input = {0, 3, 6};
  vector<int> mem;

  // start of by putting the inputs in the memory
  for(auto i: input) {
    mem.push_back(i);
  }
  int count_ = mem.size();
  while(count_ <= (2020-1)) {
    int recently_spoken_number = mem.back();
    int number_count = count(mem.begin(), mem.end(), recently_spoken_number);
    if(number_count == 1) {
      mem.push_back(0);
    }
    else {
      auto it = find(++mem.rbegin(), mem.rend(), recently_spoken_number);
      auto res = it - mem.rbegin();
      mem.push_back(res);
    }
    ++count_;
  }
  cout << mem.back() << endl;
  return 0;
}
*/

/// V2
int main() {
  // actual input
  vector<int> input = {5, 1, 9, 18, 13, 8, 0};
  // sample input 
  // vector<int> input = {0, 3, 6};
  map<int, int> last_pos_map;
  map<int, int> ele_count_map;
  // start of by putting initiliazing the values in our ds
  int i = 1;
  int last_ele = 0;
  for(auto ele: input) {
    last_pos_map[ele] = i;
    ele_count_map[ele] = 1;
    ++i;
    last_ele = ele;
  }
  
  while(i <= (30000000)) {
    int ele_count = ele_count_map[last_ele];
    int next_last_ele = 0;
    if (ele_count == 1) {
      ++ele_count_map[0];
      next_last_ele = 0;
    } else {
      int pos_diff = i - last_pos_map[last_ele] -1;
      next_last_ele = pos_diff;
      ++ele_count_map[next_last_ele];
    }
    last_pos_map[last_ele] = i-1;
    last_ele = next_last_ele;    
    ++i;
  }
  return 0;
}