Advent of Code - Day 13 Shuttle Search

day13_shuttle_search.cpp

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include "tmpl.h"

using namespace std;

int bs_part1(int, int);
ll mod_mult_inverse(ll, ll);
ll chinese_remainder(vi &, vi &);

int main() {
    // read inputs
    ifstream fin("inputs/13.txt");
    vi busses;
    vi times;

    int earliest, time=0;
    string line, bus_id;
    fin >> earliest >> line;
    istringstream comma(line);
    while(getline(comma, bus_id, ',')) {
        if (bus_id != "x") {
            busses.pb(stoi(bus_id));
            times.pb(time);
        }
        time ++;
    }

    // part 1
    int p1_min=1e9, bid, dep_time;
    fore(bus, busses) {
        dep_time = bs_part1(bus, earliest);
        if (bus*dep_time < p1_min){
            p1_min = bus*dep_time;
            bid = bus;
        }
    }
    cout << "Part 1: " << bid*(p1_min-earliest) << endl;

    // part 2
    vi remainders;
    forn(i, 0, busses.size()) remainders.pb(busses[i]-times[i]);
    remainders[0] = 0;
    cout << "Part 2: " << chinese_remainder(busses, remainders) << endl;
    return 0;
}

int bs_part1(int bid, int target) {
    int left=1, right=target, middle;
    while(left < right) {
        middle = (left+right)/2;
        if (bid*middle == target) return middle;
        else if (bid*middle < target) left = middle+1;
        else right = middle;
    }
    return right;
}

// https://cp-algorithms.com/algebra/chinese-remainder-theorem.html
ll chinese_remainder(vi &nums, vi &rems) {
    /*
    x =  ( ∑ (rems[i]*pp[i]*inv[i]) ) % prod
    Where 0 <= i <= n-1

    rems[i] is given array of remainders

    prod is product of all given numbers
    prod = nums[0] * nums[1] * ... * nums[k-1]

    pp[i] is product of all divided by nums[i]
    pp[i] = prod / nums[i]

    inv[i] = Modular Multiplicative Inverse of pp[i] with respect to nums[i]
    */
    ll prod = 1;
    fore(n, nums) prod *= n;

    vll pp;
    fore(n, nums) pp.pb(prod/n);

    vll inv;
    forn(i, 0, nums.size()) inv.pb(mod_mult_inverse(pp[i], nums[i]));

    ll x = 0;
    forn(i, 0, nums.size()) x += (rems[i]*pp[i]*inv[i]);
    return x % prod;
}

// https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
ll mod_mult_inverse(ll a, ll m) {
    if (m == 1) return 0;

    ll m0 = m;
    ll y = 0, x = 1;
    while (a > 1) {
        // q is quotient
        ll q = a / m;
        ll t = m;

        // m is remainder now, process same as Euclid's algo
        m = a % m, a = t;
        t = y;

        // Update y and x
        y = x - q * y;
        x = t;
    }
    // Make x positive
    if (x < 0) x += m0;

    return x;
}