5
\$\begingroup\$

Optimizing/parsing files into semi-complex data-structures more efficiently

To preface, I'd like to say that this code is part of the Advent of Code 2019 solutions I have been working on. Particularly #14.

--- Day 14: Space Stoichiometry ---

As you approach the rings of Saturn, your ship's low fuel indicator turns on. There isn't any fuel here, but the rings have plenty of raw material. Perhaps your ship's Inter-Stellar Refinery Union brand nanofactory can turn these raw materials into fuel.

You ask the nanofactory to produce a list of the reactions it can perform that are relevant to this process (your puzzle input). Every reaction turns some quantities of specific input chemicals into some quantity of an output chemical. Almost every chemical is produced by exactly one reaction; the only exception, ORE, is the raw material input to the entire process and is not produced by a reaction.

You just need to know how much ORE you'll need to collect before you can produce one unit of FUEL.

Each reaction gives specific quantities for its inputs and output; reactions cannot be partially run, so only whole integer multiples of these quantities can be used. (It's okay to have leftover chemicals when you're done, though.) For example, the reaction 1 A, 2 B, 3 C => 2 D means that exactly 2 units of chemical D can be produced by consuming exactly 1 A, 2 B and 3 C. You can run the full reaction as many times as necessary; for example, you could produce 10 D by consuming 5 A, 10 B, and 15 C.

Suppose your nanofactory produces the following list of reactions:

10 ORE => 10 A
1 ORE => 1 B
7 A, 1 B => 1 C
7 A, 1 C => 1 D
7 A, 1 D => 1 E
7 A, 1 E => 1 FUEL

The first two reactions use only ORE as inputs; they indicate that you can produce as much of chemical A as you want (in increments of 10 units, each 10 costing 10 ORE) and as much of chemical B as you want (each costing 1 ORE). To produce 1 FUEL, a total of 31 ORE is required: 1 ORE to produce 1 B, then 30 more ORE to produce the 7 + 7 + 7 + 7 = 28 A (with 2 extra A wasted) required in the reactions to convert the B into C, C into D, D into E, and finally E into FUEL. (30 A is produced because its reaction requires that it is created in increments of 10.)

Or, suppose you have the following list of reactions:

9 ORE => 2 A
8 ORE => 3 B
7 ORE => 5 C
3 A, 4 B => 1 AB
5 B, 7 C => 1 BC
4 C, 1 A => 1 CA
2 AB, 3 BC, 4 CA => 1 FUEL

The above list of reactions requires 165 ORE to produce 1 FUEL:

Consume 45 ORE to produce 10 A.
Consume 64 ORE to produce 24 B.
Consume 56 ORE to produce 40 C.
Consume 6 A, 8 B to produce 2 AB.
Consume 15 B, 21 C to produce 3 BC.
Consume 16 C, 4 A to produce 4 CA.
Consume 2 AB, 3 BC, 4 CA to produce 1 FUEL.

For this particular problem I have the following input formatting:

9 ORE => 2 A
8 ORE => 3 B
7 ORE => 5 C
3 A, 4 B => 1 AB
5 B, 7 C => 1 BC
4 C, 1 A => 1 CA
2 AB, 3 BC, 4 CA => 1 FUEL

Which I am parsing into my data-structure using the following:

typedef struct Reagent {
    std::int64_t units;
    std::string chemical;
} Reagent;

using Reactions = std::map<std::string, std::pair<std::int64_t, std::vector<Reagent>>>;

Reactions parse(std::string filename) {
    auto split = [](std::string input) { // Lambda to split each quantity into the reagent struct.
        Reagent reagent;
        std::istringstream parsable(input);
        parsable >> reagent.units >> reagent.chemical;
        return reagent;
    };
    Reactions reactions; // Map to store everything inside.
    std::fstream data(filename);
    std::string line;
    while(std::getline(data, line)) {
        std::vector<Reagent> inputs;
        std::string input, output;
        std::int64_t found;
        if((found = line.find(" => ")) != std::string::npos) { // Split each line into inputs and output by using the ' => '.
            input = line.substr(0, found);
            output = line.substr(found + 4, std::string::npos);
        }
        Reagent result = split(output);
        std::istringstream chemicals(input); // Split the input into a list of reagents.
        std::string str;
        while(std::getline(chemicals, str, ',')) {
            inputs.push_back(split(str));
        }
        reactions.insert({result.chemical, {result.units, inputs}});
    }
    return reactions;
}

I was wondering if there is a better, more concise/cleverer way to do this, perhaps stuff in the standard library would make it easier, or any simple code changes as well.

I would like to keep the same data structure however.

For example an entry would currently be something like:

Reactions["Fuel"] = {1, Vector of Reagents (AB, BC, CA)}.

Thank you for any advice!

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to code review, I've copied the problem statement from the website to provide the necessary description of the problem. In the future when you are doing a programming challenge please provide the description of the problem because links may go bad in the future. \$\endgroup\$ – pacmaninbw Dec 15 '19 at 18:50
  • \$\begingroup\$ @pacmaninbw Duly noted! Thanks. \$\endgroup\$ – Rietty Dec 16 '19 at 2:42
7
\$\begingroup\$

Here are some things that may help you improve your code.

Decompose your code into smaller functions

All of the logic here is in a single parse function. It would make the code easier to read, understand and maintain if it were decomposed into smaller functions.

Think carefully about signed vs. unsigned integers

The found variable is specified as std::int64_t but it's compared with std::string::npos which isn't necessarily that. To make sure they match most easily we could simply use auto and initialize the variable:

auto found{std::string::npos};

Provide complete code to reviewers

This is not so much a change to the code as a change in how you present it to other people. Without the full context of the code and an example of how to use it, it takes more effort for other people to understand your code. This affects not only code reviews, but also maintenance of the code in the future, by you or by others. Here's the test code I used to drive your code.

#include <string>
#include <map>
#include <vector>
#include <sstream>
#include <iostream>
#include <fstream>
#include <cstdint>
#include <iterator>

// posted code goes here

std::ostream& operator<<(std::ostream& out, const Reagent& r) {
    return out << r.units << ' ' << r.chemical;
}

std::ostream& operator<<(std::ostream& out, const std::vector<Reagent>& v) {
    std::copy(v.begin(), v.end(), std::ostream_iterator<Reagent>{out, ", "});
    return out;
}

int main() {
    auto reactions{parse("test.in")};
    for (const auto &r : reactions) {
        std::cout << r.second.first << ' ' << r.first << " <== " << r.second.second << '\n';
    }
}

Use std::istream instead of file name as input

This could be much more general and testable if, instead of requiring a string for a filename, the parse function took a std::istream reference instead. That would, for instance, allow the use of a string_stream for testing.

Prefer unordered_map to map for performance

There is not really a compelling reason to maintain order in for the list of Reactions here, so a std::unordered_map would work as well as a std::map but likely have better perfomance. In general, the unordered varieties of map, set, multimap and multiset should be preferred if the ordering is not needed.

Reconsider the approach

Right now, each input line is effectively cloned and scanned multiple times. This isn't really necessary because one could perform the parsing differently. One way would be to use std::regex but while it is flexible, that approach is not very fast. Another way would be to simply scan one word at a time and use a state machine to keep track of what token is expected next. This would also help with the next suggestion. Here's an example of the state machine approach:

Reactions parse(std::istream& in) {
    Reactions reactions; 
    Reagent current;
    std::vector<Reagent> inputs;
    bool expecting_qty{true};
    bool expecting_output{false};
    std::string token;
    while (in >> token) {
        if (token == "=>") {
            expecting_output = true;
        } else if (expecting_qty && std::isdigit(token[0])) {
            current.units = std::stol(token);
            expecting_qty = false;
        } else if (!expecting_qty) {
            if (token.back() == ',') {
                token.pop_back();
            }
            current.chemical = token;
            if (expecting_output) {
                reactions.insert({current.chemical, {current.units, inputs}});
                inputs.clear();
                expecting_output = false;
            } else {
                inputs.push_back(current);
            }
            expecting_qty = true;
        } else {
            in.setstate(std::ios_base::failbit);
            return reactions;
        }
    }
    return reactions;
}

Consider emitting diagnostics on input errors

If anything in the input fails, nothing good or useful happens in the code. I'd suggest that at the minimum, the code should do this:

in.setstate(std::ios_base::failbit);

That would allow the caller to at least know that something had failed.

Eliminate redundant typedef

We have this struct within the code:

typedef struct Reagent {
    std::int64_t units;
    std::string chemical;
} Reagent;

While common in C, the typedef is wholly unnecessary in C++.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you so much! That's very useful. Couple of points. I didn't post full code because it didn't really pertain to how I solved the problem, I was asking for advice on how to handle the parsing, which is what I wrote about. How would you structure splitting this into separate functions? \$\endgroup\$ – Rietty Dec 17 '19 at 3:41
  • \$\begingroup\$ I do like the token based approach, it feels much much cleaner. I will def keep it in mind for future problems. \$\endgroup\$ – Rietty Dec 17 '19 at 3:43
  • \$\begingroup\$ “In general, the unordered varieties should be preferred” why? The unordered assoc containers introduce a lot of overhead over the ordered ones and should only be used for large data sets after measuring. \$\endgroup\$ – L. F. Dec 18 '19 at 8:14
  • \$\begingroup\$ (See stackoverflow.com/a/4694961) \$\endgroup\$ – L. F. Dec 18 '19 at 8:19
  • \$\begingroup\$ For small data sets, the overhead will be too small to notice and for larger ones the unordered containers generally win. Measuring bears this out in my testing. As always, measurement is king. \$\endgroup\$ – Edward Dec 18 '19 at 8:22
6
\$\begingroup\$

A quick skim shows some things that could be improved:

typedef struct Reagent

There's no need for such typedefs in C++, as we can use the structure tag as a type name.

auto split = [](std::string input) {

Perhaps better to pass a const std::string& here?

    parsable >> reagent.units >> reagent.chemical;

I would expect some checking that the stream is still good afterwards.

Having this split function here at all is surprising - we'd normally normally just write an operator>>() to stream into a Reagent object.

    std::int64_t found;
    if((found = line.find(" => "))

That's a strange choice of type, given that std::string::find() returns a std::string::size_type, aka std::size_t: we should avoid unnecessary conversions between signed and unsigned types.

In this case, it's simpler to let the compiler determine the most suitable type:

if (auto found = line.find(" => "); found != std::string::npos)
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.