Advent of Code 2020 - Day 7 Handy Haversacks

day07_handy_haversacks.cpp

#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

#define endl '\n'
#define pb push_back
#define forn(i, n) for (int i = 0; i < (int)n; i++)
typedef vector<string> vs;
typedef vector<int> vi;

bool find(string, string);
int search(string);

unordered_map<string, vs> mappings;
unordered_map<string, vi> quantities;

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

    // ugly inputs read
    string line, main_bag, rest, token;
    int pos;
    while (getline(cin, line)) {
        pos = line.find("bags contain");
        main_bag = line.substr(0, pos - 1);
        rest = line.substr(pos + 12, line.size() - pos - 13);  //without .
        if (rest != " no other bags") {
            vs inside_bags;
            vi inside_qtys;
            istringstream comma(rest);
            while (getline(comma, token, ',')) {
                int qty = stoi(token.substr(1, 1));
                pos = token.find(" bag");
                string bag = token.substr(3, pos - 3);

                inside_bags.pb(bag);
                inside_qtys.pb(qty);
            }
            mappings[main_bag] = inside_bags;
            quantities[main_bag] = inside_qtys;
        }
    }

    string target = "shiny gold";

    // part 1
    int answer1 = 0;
    for (auto &p : mappings) {
        if (p.first == target) continue;
        answer1 += find(p.first, target);
    }
    cout << "Part 1: " << answer1 << endl;

    // part 2
    cout << "Part 2: " << search(target) - 1 << endl;
    return 0;
}

bool find(string node, string target) {
    bool found = false;
    for (auto neigh : mappings[node]) {
        if (neigh == target) return true;
        found = find(neigh, target);
        if (found) break;
    }
    return found;
}

int search(string node) {
    int bags_cnt = 1, qty;
    string neigh;
    forn(i, mappings[node].size()) {
        neigh = mappings[node][i];
        qty = quantities[node][i];
        bags_cnt += qty * search(neigh);
    }
    return bags_cnt;
}