optiver_hr_q2.cpp

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

struct Node;
struct Edge;

struct Route {
    std::list<Node*> edges;
};

struct Edge {
    explicit Edge(Node* from, Node* to, long distance) : parent(from), destination(to), length(distance) {}

    Node* parent;
    Node* destination;
    int length;
};

struct Node {
    explicit Node(std::string name_) : name(name_) {}

    void AddEdge(Node* to, long distance) {
        m_edges.emplace_back(this, to, distance);
    }

    std::vector<Edge> m_edges;
    std::string name;
    bool visited{false}; // make it easy to find out if we have been here
};
std::unordered_map<std::string, Node> NODES;

void UpdateNodeStructure(std::string instruction) {
    std::vector<std::string> instructions;

    // Parse comma seperated instructions and push into 
    // the list of instructions
    size_t pos = 0;
    std::string token;
    std::string delimiter = ",";
    while ((pos = instruction.find(delimiter)) != std::string::npos) {
        instructions.push_back(instruction.substr(0, pos));
        instruction.erase(0, pos + delimiter.length());
    }
    instructions.push_back(instruction);

    // Find the from node
    auto from_node_itr{NODES.find(instructions[0])};
    if (from_node_itr == NODES.end()) {
        from_node_itr = NODES.emplace(instructions[0], instructions[0]).first;
    }

    // Find the dest node
    auto to_node_itr{NODES.find(instructions[1])};
    if (to_node_itr == NODES.end()) {
        to_node_itr = NODES.emplace(instructions[1], instructions[1]).first;
    }

    // Link nodes
    try {
        long distance{std::stol(instructions[2])};
        from_node_itr->second.AddEdge(&to_node_itr->second, distance);
    } catch (...) {
        std::cout << "E1";
        exit(0);
    }
}

void ParseNodeInput() {
    std::string all_nodes_text;
    std::getline(std::cin, all_nodes_text);

    size_t pos = 0;
    std::string node_delim = "]";
    std::string token;
    while ((pos = all_nodes_text.find(node_delim)) != std::string::npos) {
        token = all_nodes_text.substr(1, pos-1);
        all_nodes_text.erase(0, pos + node_delim.length() + 1);
        token = token;
        UpdateNodeStructure(token);
    }
}

struct RouteRequest {
    RouteRequest(Node& from_, Node& to_, long dist_) : from(from_), to(to_), dist(dist_) {}
    Node& from;
    Node& to;
    long dist;
};

RouteRequest ParseRouteRequest() {
    std::string search_request;
    std::getline(std::cin, search_request);

    auto from_end = search_request.find("->");
    std::string from = search_request.substr(0, from_end);
    search_request.erase(0, from.length() + 2);

    auto to_end = search_request.find(",");
    std::string to = search_request.substr(0, to_end);
    search_request.erase(0, to.length() + 1);

    long max_travel{0};
    try {
        max_travel = std::stol(search_request);
    } catch (...) {
        std::cout << "E1";
        exit(0);
    }


    auto from_node_itr{NODES.find(from)};
    if (from_node_itr == NODES.end()) {
        std::cout << "E2";
        exit(0);
    }

    auto to_node_itr{NODES.find(to)};
    if (to_node_itr == NODES.end()) {
        std::cout << "E2";
        exit(0);
    }

    RouteRequest route_request(from_node_itr->second, to_node_itr->second, max_travel);
    return route_request;
}

// true if has route segment
bool FindRoute(Route& route, RouteRequest& request, Node* current) {
    route.edges.emplace_back(current);
    current->visited = true;

    if (&request.to == current) {
        std::vector<Node*> node_path;

        for (auto& node : route.edges) {
            node_path.push_back(node);
        }

        for (int i = 0; i < (node_path.size()-1); ++i) {
            std::cout << node_path[i]->name << "->";
        }

        std::cout << node_path.back()->name;
    }

    for (auto& con : current->m_edges) {
        if (con.destination->visited) continue;
        if (!FindRoute(route, request, con.destination)) {
            route.edges.pop_back();
        }
    }

    return false;
}

using namespace std;
int main() {
    ParseNodeInput();
    auto route_request{ParseRouteRequest()};

    Route route;
    FindRoute(route, route_request, &route_request.from);

    return 0;
}