Advent of Code 2020 - Day 9 Encoding Error

day09_encoding_error.cpp

#include <algorithm>
#include <iostream>
#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

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

const short MAX = 25;

bool is_sum(vi &, int, int);
ll small_plus_large(vi &, int, int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    vi nums;
    vector<ll> sums;

    // inputs
    int x;
    ll sum = 0;
    while (cin >> x) {
        sum += x;
        nums.pb(x);
        sums.pb(sum);
    }

    // part 1
    int part1_ans = 0, i = MAX;
    while (i < nums.size()) {
        if (is_sum(nums, nums[i], i)) {
            i++;
        } else {
            part1_ans = nums[i];
            break;
        }
    }
    cout << "Part 1: " << part1_ans << endl;

    // part 2
    int part2_ans = 0;
    forn(k, 2, nums.size() - 1) {
        forn(i, 0, nums.size() - k - 1) {
            if (sums[i + k] - sums[i - 1] == part1_ans) {
                part2_ans = small_plus_large(nums, i, i + k);
                break;
            }
        }
    }
    cout << "Part 2: " << part2_ans << endl;
    return 0;
}

bool is_sum(vi &arr, int target, int range) {
    forn(x, range - MAX, range - 1) {
        forn(y, x + 1, range) {
            if (target - arr[x] == arr[y]) return true;
        }
    }
    return false;
}

ll small_plus_large(vi &arr, int a, int b) {
    int small = 1e9, large = -1e9;
    forn(i, a, b + 1) {
        small = min(small, arr[i]);
        large = max(large, arr[i]);
    }
    return small + large;
}