Historian Hysteria | Yuvrajsinh Gohil

Problem Overview

Two lists of location IDs need to be reconciled. Part 1 calculates total distance by pairing sorted elements. Part 2 calculates similarity score using frequency counting.

Part 1: Distance Calculation

Sort both lists and sum absolute differences between corresponding pairs.

#include<bits/stdc++.h>
using namespace std;

int main() {
  ifstream file("input.txt");
  string line;
  vector<string> location_id1, location_id2;

  while(getline(file, line)) {
      location_id1.push_back(line.substr(0, 5));
      location_id2.push_back(line.substr(8, 12));
  }

  sort(location_id1.begin(), location_id1.end());
  sort(location_id2.begin(), location_id2.end());

  int ans = 0;
  for (int i = 0; i < location_id1.size(); ++i) {
      ans += abs(atoi(location_id1[i].c_str()) - atoi(location_id2[i].c_str()));
  }

  cout << ans << endl;
  return 0;
}

Part 2: Similarity Score

Count frequencies and multiply each left list number by its frequency in the right list.

#include<bits/stdc++.h>
using namespace std;

int main() {
  ifstream file("input.txt");
  string line;
  vector<string> location_id1, location_id2;

  while(getline(file, line)) {
      location_id1.push_back(line.substr(0, 5));
      location_id2.push_back(line.substr(8, 12));
  }

  map<int, int> mp1, mp2;

  for (int i = 0; i < location_id1.size(); ++i) {
      mp1[atoi(location_id1[i].c_str())]++;
      mp2[atoi(location_id2[i].c_str())]++;
  }

  int ans = 0;
  for (auto it: mp1) {
      ans += (it.first * mp2[it.first]);
  }

  cout << ans << endl;
  return 0;
}