Advent of Code 2020 - Day 10 Adapter Array

day10_adapter_array.cpp

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

using namespace std;

#define forn(i, j, n) for (int i = j; i < (int)n; i++)
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()

typedef vector<int> vi;
typedef long long ll;

vector<ll> memo;
set<int> jolts;
int biggest = 0;

ll combine_count(int);

int main() {
    ifstream fin("inputs/10.txt");
    vi adapters;

    int jolt;
    adapters.pb(0);
    while (fin >> jolt) {
        adapters.pb(jolt);
        biggest = max(biggest, jolt);
    }
    biggest += 3;
    adapters.pb(biggest);

    // part 1
    sort(all(adapters));
    int one = 0, three = 0, diff;
    forn(i, 1, adapters.size()) {
        diff = adapters[i] - adapters[i - 1];
        if (diff == 1) one++;
        if (diff == 3) three++;
    }
    cout << "Part 1: " << one << "x" << three << " = " << one * three << endl;

    // part 2
    for (auto &j : adapters) jolts.insert(j);
    memo = vector<ll>(biggest + 1, -1);
    cout << "Part 2: " << combine_count(0) << endl;

    return 0;
}

ll combine_count(int jolt) {
    if (jolt == biggest) return 1;
    if (memo[jolt] != -1) return memo[jolt];

    ll count = 0;
    if (jolts.count(jolt + 1)) count += combine_count(jolt + 1);
    if (jolts.count(jolt + 2)) count += combine_count(jolt + 2);
    if (jolts.count(jolt + 3)) count += combine_count(jolt + 3);
    return memo[jolt] = count;
}