Reddit

#include <SFML/Graphics.hpp>

#include <iostream>
#include <memory>
#include <algorithm>
#include <vector>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cmath>

#include "random.hpp"
using Random = effolkronium::random_static;

int count = 0;

int dist(std::vector<sf::Vector2f>, std::vector<int>);
double factorial(int);
bool nextOrder(std::vector<int>&, sf::Text&);

// template<class T> void splice(std::vector<T>&, int);
template<class T> std::vector<T> splice(std::vector<T>, int, int);

int main() {
    // Setting up basic window properties
    int width = 700, height = 900;
    const unsigned fps = 60, depth = 32;

    sf::RenderWindow app;
        app.create(sf::VideoMode(width, height, depth), "Main Window");
        app.setFramerateLimit(fps);


    // Randomly generated dots that are represent cities
    int totalCities = 5;
    bool isFinished = false;
    std::vector<int> order;

    std::vector<sf::Vector2f> cities;
    for (int i = 0; i != totalCities; ++i) {
        auto xPos = Random::get(0, width);
        auto yPos = Random::get(0, height/2);

        cities.push_back(sf::Vector2f(xPos, yPos));
        order.push_back(i);
    }

    // Tracking te best, smallest distance between two dots
    int recordDist = 0;
    std::vector<int> bestEver;

    int d = dist(cities, order);
    recordDist = d;
    std::copy(order.begin(), order.end(), std::back_inserter(bestEver));


    // Graphical representation of cities and connections
    sf::CircleShape city;
        city.setRadius(8);
        city.setOrigin(city.getRadius(), city.getRadius());
        city.setFillColor(sf::Color::Black);

    std::vector<sf::Vector2f> actPath;
    std:copy(cities.begin(), cities.end(), std::back_inserter(actPath));
    for (auto& t : cities) t = sf::Vector2f(t.x, t.y+(height/2));

    sf::VertexArray lines(sf::LinesStrip, totalCities);
    for (int i = 0; i != totalCities; ++i) {
        lines[i].position = actPath[i];
        lines[i].color = sf::Color::Black;
    }

    sf::VertexArray bestLines(sf::LinesStrip, totalCities);
    for (int i = 0; i != totalCities; ++i) {
        int n = bestEver[i];
        bestLines[i].position = cities[n];
        bestLines[i].color = sf::Color::Red;
    }

    // Calculating overall percentage of the process
    double totalPerms = factorial(totalCities);
    double percent = 0;

    sf::Font font;
        font.loadFromFile("arial.ttf");
    sf::Text progress;
        progress.setFont(font);
        progress.setCharacterSize(30);
        progress.setPosition(sf::Vector2f(20, 20));
        progress.setFillColor(sf::Color::Black);
    sf::Text lex;
        lex.setFont(font);
        lex.setCharacterSize(20);
        lex.setPosition(sf::Vector2f(10, height-30));
        lex.setFillColor(sf::Color::Black);

    // Main draw loop
    while(app.isOpen()) {
        sf::Event event;
        while(app.pollEvent(event)) {
            if (event.type == sf::Event::Closed) app.close();
        } app.clear(sf::Color(230, 230, 250));


        // Setting up precision for displaying text on the screen from double
        percent = 100*(count/totalPerms);
            std::ostringstream sob;
            sob << std::fixed;
            sob << std::setprecision(2);
            sob << percent;
        std::string txt = sob.str();
        // std::cout << txt << std::endl;

        if (!isFinished) {
            progress.setString(std::to_string(percent) + '%');
            app.draw(lines);
        }
        // } else progress.setString("100%");

        std::string tmp = " ";
        std::string lexo = " ";
        for (auto o : order) tmp += std::to_string(o);

        lexo = tmp;
        lex.setString(lexo);
        app.draw(lex);


        for (auto c : cities) {
            city.setPosition(c);

            app.draw(city);
            app.draw(bestLines);
            app.draw(progress);
        }

        // Checking all of the possible connections
        for (int i = 0; i != order.size(); ++i) {
            int n = order[i];
            // lines[i].position = cities[n];
            lines[i].position = actPath[n];
        }
        for (int i = 0; i != order.size(); ++i) {
            int n = bestEver[i];
            bestLines[i].position = cities[n];
        }

        // Tracking te best, smallest distance between two dots... Again.
        int d = dist(cities, order);
        if (d < recordDist) {
            recordDist = d;
            bestEver.resize(0);  // This is needed for std::copy in the every next iteration
            std::copy(order.begin(), order.end(), std::back_inserter(bestEver));
            std::cout << recordDist << std::endl;
        } isFinished = nextOrder(order, lex);

        std::cout << "bestEver" << std::endl;
        for (auto b : bestEver) std::cout << b << ' ';
        std::cout << std::endl;

        std::cout << "order" << std::endl;
        for (auto o : order) std::cout << o << ' ';
        std::cout << std::endl;

        app.display();
    }

    return 0;
}

int dist(std::vector<sf::Vector2f> points, std::vector<int> order) {
    count++;
    int sum = 0;
    for (int i = 0; i != order.size()-1; ++i) {
        auto cityA = points[order[i]];
        auto cityB = points[order[i+1]];

        int xd = abs(cityA.x - cityB.x);
        int yd = abs(cityA.y - cityB.y);
        int d = sqrt(xd*xd + yd*yd);

        sum += d;
    }
    return sum;
}

double factorial(int n) {
    if (n == 1) return 1;
    else return n * factorial(n-1);
}

// Lexicographic order of numbers
bool nextOrder(std::vector<int>& vo, sf::Text& txt) {
        int largI = -1;
        for (int i = 0; i < vo.size()-1; i++) {
            if (vo[i] < vo[i+1]) largI = i;
        } if (largI == -1) return true;

        int largJ = -1;
        for (int j = 0; j < vo.size(); j++) {
            if (vo[largI] < vo[j]) largJ = j;
        } std::swap(vo[largI], vo[largJ]);


        std::vector<int> vc;
        std::copy(vo.begin()+largI+1, vo.begin()+largI+2, std::back_inserter(vc));

        vo.erase(vo.begin()+largI+1);
        vo.insert(vo.end(), vc.begin(), vc.end());

    return false;
}

// template<class T> void splice(std::vector<T>& va, int n) {
//     va.assign(va.begin()+n, va.end());
// }

// template<class T> std::vector<T> splice(std::vector<T> vc, int n, int nn) {
//     std::vector<T> tmp;
//     std::copy(vc.begin()+n, vc.begin()+nn, std::back_inserter(vc));
//     return tmp;
// }