day_9_felix2.cpp

#include <bits/stdc++.h>
using namespace std;
const bool DEBUG = true;

#define ll long long

vector <ll> fileid;
vector <ll> filesize;
vector <ll> filestart;

vector <ll> holestart;
vector <ll> holesize;

void readInput() {
    char c;
    ll i = 0;
    bool iseven = true;
    ll pos = 0;
    while (cin >> c) {
        if (iseven) {
            fileid.push_back(i);
            filesize.push_back(c-'0');
            filestart.push_back(pos);
            i++;
            pos += c-'0';
        } else {
            holestart.push_back(pos);
            holesize.push_back(c-'0');
            pos += c-'0';
        }
        iseven = !iseven;
    }
}


void rearrange() {
    DEBUG && cout << "Rearranging files" << endl;

    for (int file = filesize.size()-1; file >= 0; file--) {
        for (int hole = 0; hole < file; hole++) {
            if (holesize[hole] >= filesize[file]) {
                // insert file into hole
                DEBUG && cout << "Inserting file " << fileid[file] << " into hole pos " << holestart[hole] << endl;
                holesize[hole] -= filesize[file];
                filestart[file] = holestart[hole];
                holestart[hole] += filesize[file];
                break;
            }
        }
    }
}

ll fileValue(int file) {
    ll val = 0;
    for (ll i = 0; i < filesize[file]; i++) {
        val += filestart[file] + i;
    }
    return val * fileid[file];
}

ll checkSum() {
    ll sum = 0;
    for (int file = 0; file < fileid.size(); file++) {
        sum += fileValue(file);
    }
    return sum;
}

int main () {   
    readInput();
    rearrange();

    long long part2 = checkSum();
    cout << "Part 2: " << part2 << endl;
    return 0;
}