 #include <iostream>
#include <array>
#include <map>
#include <experimental/coroutine>
#include <experimental/generator>
#include <stack>
#include <map>
#include <vector>
#include <cassert>
#include <cmath>

struct Vertex
{
    int vertex;
    bool isVisited = false;
};

struct Range
{
    float from;
    float to;
};

constexpr inline size_t NodesCount{ 5 };

using TPathCost = std::map<std::pair<int, int>, float>;
using TVertexes = std::array<Vertex, NodesCount>;
using TPath = std::pair<int, int>;
using TPossibilities = std::vector<std::pair<float, TPath>>;

template<typename TValuesHolder>
std::experimental::generator<int> randomGenValues(TValuesHolder holder)
{
    for (auto& value : holder) {
        co_yield value;
    }
}

const auto RandomGenReturns{ std::array{64,39,80} };

TPathCost pathsCost{
    { {1,2},47.f },
    { {1,3},87.f },
    { {1,4},81.f },
    { {1,5} ,53.f },
    { {2,3} ,49.f },
    { {2,4} ,69.f },
    { {2,5} ,71.f },
    { {3,4} ,47.f },
    { {3,5} ,80.f },
    { {4,5} ,46.f }
};

TVertexes nodes
{
    Vertex{1,false},
    Vertex{2,false},
    Vertex{3,false},
    Vertex{4,false},
    Vertex{5,false}
};

auto findPathIt( const TPath& _path)
{
    auto pathIt = pathsCost.find(_path);
    if (pathIt == pathsCost.end())
        pathIt = pathsCost.find(TPath{ _path.second, _path.first });
    return pathIt;
}

float computePathPossibility(const TPath& _path, const std::vector<TPath>& _allPaths )
{
    auto pathIt = findPathIt(_path);
    if (pathIt != pathsCost.end())
    {
        const auto& [path, cost] = *pathIt;

        float divisior{};

        for (const auto& path : _allPaths)
        {
            if (auto nestedPathIt = findPathIt(path); nestedPathIt != pathsCost.end())
            {
                const auto& [pathNested, costNested] = *nestedPathIt;
                divisior += 1000.f/ costNested;
            }
        }
        divisior = round(divisior);
        divisior /= 1000.f;

        const float divisible{ 1.f / cost };

        const float result = 100.f * divisible / divisior;
        return result;
    }
    assert(false);
    return 0.f;
}

TPossibilities computePossibilities(int _currentNode, const TVertexes& _vertexes)
{
    std::vector<TPath> availablePaths;

    for(const auto& vertexItem: _vertexes)
    {
        if( !vertexItem.isVisited)
            availablePaths.push_back({ _currentNode,vertexItem.vertex });
    }        

    TPossibilities possibilities;

    for (const auto& path : availablePaths)
    {
        possibilities.push_back(
            { computePathPossibility(path,availablePaths),path }
        );
    }

    return possibilities;
}

using TRangesVec = std::vector<std::pair<Range, TPath>>;
TRangesVec
computeRanges(const TPossibilities& _possibilities)
{
    TRangesVec ranges;

    float rangePrev{0.f};

    for (const auto& possibility : _possibilities)
    {
        const auto& [pathPossibility, path] = possibility;
        ranges.push_back(
            {
                { rangePrev, rangePrev + possibility.first}, possibility.second
            }
        );
        rangePrev = rangePrev + possibility.first;
    }

    return ranges;
}

int main() {

    nodes[0].isVisited = true;
    int currentNode = 1;
    auto possibilities = computePossibilities(currentNode, nodes);
    auto compuutedRanges = computeRanges(possibilities);

    float resultCost{};
    std::cout << "Visit vertex order:\n";
    std::cout << currentNode << '-';
    for( auto& random: randomGenValues(RandomGenReturns) )
    {
        auto nextRange = std::find_if(
            compuutedRanges.begin(),
            compuutedRanges.end(),
            [&random](const auto& _range)
            {
                const auto& [range, path] = _range;
                return random >= range.from && random <= range.to; }
        );

        const auto PathIt = findPathIt(nextRange->second);
        if (PathIt != pathsCost.end())
            resultCost += PathIt->second;

        if (nextRange != compuutedRanges.end())
        {
            const auto& [range, path] = *nextRange;
            currentNode = path.second;
            nodes[currentNode - 1].isVisited = true;
            possibilities = computePossibilities(currentNode, nodes);
            compuutedRanges = computeRanges(possibilities);
        }
        std::cout << currentNode << '-';
    }
    
    for( const auto& nodeItem: nodes)
    {
        if (!nodeItem.isVisited)
        {
            const auto PathIt = findPathIt(TPath{ currentNode, nodeItem.vertex});
            if (PathIt != pathsCost.end())
            {
                resultCost += PathIt->second;
                currentNode = nodeItem.vertex;
                std::cout << currentNode << '-';
            }
                
        }
    }

    const auto PathIt = findPathIt(TPath{currentNode,1});
    if (PathIt != pathsCost.end())
    {
        resultCost += PathIt->second;
        currentNode = 1;
    }

    std::cout << currentNode << '\n';
    std::cout << "Result path cost:" << resultCost;

    return 0;
}

created 4 years ago

C++ Online Compiler

Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!

Read inputs from stdin

OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.

#include <iostream>
#include <string>
using namespace std;

int main() 
{
    string name;
    cout << "Enter name:";
    getline (cin, name);
    cout << "Hello " << name;
    return 0;
}

About C++

C++ is a widely used middle-level programming language.

Supports different platforms like Windows, various Linux flavours, MacOS etc
C++ supports OOPS concepts like Inheritance, Polymorphism, Encapsulation and Abstraction.
Case-sensitive
C++ is a compiler based language
C++ supports structured programming language
C++ provides alot of inbuilt functions and also supports dynamic memory allocation.
Like C, C++ also allows you to play with memory using Pointers.

Syntax help

Loops

1. If-Else:

When ever you want to perform a set of operations based on a condition If-Else is used.

if(conditional-expression) {
   //code
}
else {
   //code
}

You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.

2. Switch:

Switch is an alternative to If-Else-If ladder.

switch(conditional-expression){    
case value1:    
 // code    
 break;  // optional  
case value2:    
 // code    
 break;  // optional  
......    
    
default:     
 code to be executed when all the above cases are not matched;    
}

3. For:

For loop is used to iterate a set of statements based on a condition.

for(Initialization; Condition; Increment/decrement){  
  //code  
}

4. While:

While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.

while (condition) {  
// code 
}

5. Do-While:

Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.

do {  
 // code 
} while (condition);

Functions

Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.

How to declare a Function:

return_type function_name(parameters);

How to call a Function:

function_name (parameters)

How to define a Function:

return_type function_name(parameters) {  
 // code
}