#include <algorithm>
#include <array>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/gmp.hpp>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <random>
#include <sys/ioctl.h>
#include <sys/ioctl.h>
#include <unistd.h>
#include <unistd.h>

using namespace std;
using boost::multiprecision::cpp_int;
using boost::multiprecision::mpf_float;

const array<string, 9> BLOCK_CHARS {" ", "▏", "▎", "▍", "▌", "▋", "▊", "▉", "█"};

// Mathematical helpers

cpp_int factorial(cpp_int n) {
    cpp_int result = 1;

    for (int i = 1; i <= n; i++) {
        result *= i;
    }

    return result;
}

// Progress bar helpers

int get_terminal_width() {
    struct winsize w;
    ioctl(STDOUT_FILENO, TIOCGWINSZ, &w);
    return w.ws_col;
}

void show_progress(cpp_int iteration, cpp_int length) {
    const int terminal_width = get_terminal_width();

    const int length_string_length = 5;//std::to_string(length).length();
    const int progress_bar_width = terminal_width - 2 * length_string_length - 7;

    const double percent = static_cast<double>((800 * iteration) / (length)) / 800;

    const int progress_bar_active_width = percent * progress_bar_width;

    cout << "\r";
    cout << fixed << setprecision(0) << percent * 100 << "% ";
    for (int i = 0; i < progress_bar_width; i++) {
        if (progress_bar_active_width > i) {
            cout << BLOCK_CHARS[8];
        } else if (progress_bar_active_width == i) {
            cout << BLOCK_CHARS[round(8 * (percent * progress_bar_width - progress_bar_active_width))];
        } else {
            cout << " ";
        }
    }
    cout << " " << setfill('0') << setw(length_string_length) << iteration << "/" << length << std::flush;
}

void efficient_show_progress(cpp_int iteration, cpp_int length) {
    if (iteration % (length / 100) == 0 || iteration == length - 1) {
        show_progress(iteration, length);
    }
}

vector<vector<int>> get_permutations(vector<int> items) {
    sort(items.begin(), items.end());

    vector<vector<int>> permutations = {};

    do {
        permutations.insert(permutations.end(), items);
    } while (next_permutation(items.begin(), items.end()));

    return permutations;
}

vector<vector<int>> get_combinations(vector<int> full, int subset) {
    vector<vector<int>> combinations = {};

    // inspired by https://stackoverflow.com/a/9430993
    std::vector<bool> v(full.size());
    std::fill(v.begin(), v.begin() + subset, true);

    do {
        vector<int> combination = {};
        for (int i = 0; i < full.size(); i++) {
            if (v[i]) {
                combination.insert(combination.begin(), full[i]);
            }
        }
        combinations.insert(combinations.begin(), combination);
    } while (std::prev_permutation(v.begin(), v.end()));

    return combinations;
}

vector<vector<int>> get_all_combinations(vector<int> full, int subset) {
    //cpp_int length = (factorial(full.size())) / (factorial(subset) * factorial(full.size() - subset)) * factorial(subset);
    cpp_int length = (factorial(full.size()) * factorial(subset)) / (factorial(subset) * factorial(static_cast<cpp_int>(full.size()) - static_cast<cpp_int>(subset)));
    cout << length << flush;
    //if (length <= 0) throw overflow_error("Limit of long long int exceeded");

    vector<vector<int>> all_combinations = {};

    vector<vector<int>> combinations = get_combinations(full, subset);
    for (vector<int> combination: combinations) {
        vector<vector<int>> permutations = get_permutations(combination);
        for (vector<int> permutation: permutations) {
            efficient_show_progress(all_combinations.size(), 10); //length);

            all_combinations.insert(all_combinations.end(), permutation);
        }
    }

    return all_combinations;
}

bool check_multi_equal(vector<int> values) {
    for (const auto &value: values) {
        if (value != values[0]) return false;
    }

    return true;
}

bool check_magic_square(vector<int> numbers) {
    vector<int> sums {
        numbers[0] + numbers[1] + numbers[2],
        numbers[3] + numbers[4] + numbers[5],
        numbers[6] + numbers[7] + numbers[8],
        numbers[0] + numbers[3] + numbers[6],
        numbers[1] + numbers[4] + numbers[7],
        numbers[2] + numbers[5] + numbers[8],
        numbers[0] + numbers[4] + numbers[8],
        numbers[2] + numbers[4] + numbers[6]
    };
    return check_multi_equal(sums);
}

template <typename T> vector<T> filter_progress(vector<T> items, bool (*function)(T)) {
    vector<T> filtered_items = {};

    int length = items.size();

    // manual loop to get iteration count
    for (int i = 0; i < length; i++) {
        efficient_show_progress(i, length);

        if ((*function)(items[i])) {
            filtered_items.insert(filtered_items.end(), items[i]);
        }
    }
    cout << endl;

    return filtered_items;
}

template <typename T> vector<T> map_progress(vector<T> items, T (*function)(T)) {
    int length = items.size();

    // manual loop to get iteration count
    for (int i = 0; i < length; i++) {
        efficient_show_progress(i, length);

        items[i] = (*function)(items[i]);
    }
    cout << endl;

    return items;
}

vector<int> square_magic_square(vector<int> magic_square) {
    for (int i = 0; i < magic_square.size(); i++) {
        magic_square[i] = pow(magic_square[i], 2);
    }

    return magic_square;
}

int main() {
    vector<int> possible_values(100);
    iota(std::begin(possible_values), std::end(possible_values), 1);

    cout << "[1/3] Getting all possible combinations in range 1 to " << possible_values.size() << "…" << endl;
    vector<vector<int>> combinations = get_all_combinations(possible_values, 9);

    cout << "[2/3] Squaring all numbers…" << endl;
    combinations = map_progress(combinations, square_magic_square);

    cout << "[3/3] Checking combinations for valid magic square…" << endl;
    combinations = filter_progress(combinations, check_magic_square);

    int valid = combinations.size();
    if (valid == 0) {
        cout << "No valid magic square found :(" << endl;
    } else {
        cout << valid << " valid magic squares found" << endl;
        for (const auto& combination: combinations) {
            for (const auto& el: combination) {
                cout << el << " ";
            }
            cout << endl;
        }
    }

    return 0;
}