AdventOfCode/2015/19-Medicine-for-Rudolph.cpp at main · JoeBlakeB/AdventOfCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
// Copyright (C) 2023 Joe Baker (JoeBlakeB)
// Advent of Code 2015 - Day 19: Medicine for Rudolph
// Usage:
//     scripts/cppRun.sh 2015/19-Medicine-for-Rudolph.cpp < 2015/inputs/19.txt

#include <algorithm>
#include <iostream>
#include <vector>

#include "utils.cpp"

using namespace std;

struct Replacement {
    string from;
    string to;
};

vector<Replacement> getPossibleReplacements() {
    vector<string> inputLines = getInputLinesVector();
    vector<Replacement> possibleReplacements;

    for (string line : inputLines) {
        unsigned short arrowPosition = line.find("=>");
        possibleReplacements.push_back({
            line.substr(0, arrowPosition - 1),
            line.substr(arrowPosition + 3)});
    }

    return possibleReplacements;
}

int getPossibleReplacementCount(
    const string& molecule,
    vector<Replacement>& possibleReplacements
) {
    unsigned int possibleChanges = 0;
    vector<string> otherMolecules;

    for (unsigned int i = 0; i < molecule.size(); i++) {
        string thisAtom = "";
        unsigned short atomSize = 1;
        for (; atomSize <= 2; atomSize++)
        {
            string atomToFind = molecule.substr(i, atomSize);
            if (find_if(possibleReplacements.begin(), possibleReplacements.end(),
                    [&](const Replacement& replacement) {
                        return replacement.from == atomToFind;
                    }) != possibleReplacements.end()) {
                thisAtom = molecule.substr(i, atomSize);
                break;
            }
        }
        if (thisAtom == "") continue;

        for (const Replacement& replacement : possibleReplacements) {
            if (replacement.from != thisAtom) continue;

            string newMolecule = molecule.substr(0, i) +
                replacement.to + molecule.substr(i+atomSize);

            if (find(otherMolecules.begin(), otherMolecules.end(), newMolecule)
                    == otherMolecules.end()) {
                possibleChanges++;
                otherMolecules.push_back(newMolecule);
            }
        }
    }

    return possibleChanges;
}

int stepsToGetE(
    const string& fromMolecule,
    vector<Replacement>& possibleReplacements
) {
    string molecule = fromMolecule;
    unsigned int steps = 0;
    for (unsigned int i = 0; i < 1024; i++) {
        for (const Replacement& replacement : possibleReplacements) {
            size_t position = molecule.find(replacement.to);
            if (position == string::npos) continue;

            molecule.replace(position, replacement.to.size(), replacement.from);
            steps++;
        }
        if (molecule == "e") return steps;
    }
    cout << "Error: no solution found after 1024 iterations" << endl;
    exit(1);
}

int main() {
    vector<Replacement> reactions = getPossibleReplacements();
    string medicineMolecule = getInputLinesVector()[0];

    cout << "Number of possible distinct molecules: "
         << getPossibleReplacementCount(medicineMolecule, reactions) << endl;

    cout << "Steps to create the medicine molecule: "
         << stepsToGetE(medicineMolecule, reactions) << endl;

    return 0;
}