#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <set>
#include <string>
#include <string_view>
#include <random>
#include <ranges>
#include <string_view>
#include <vector>

int childsteps(int n) {
    if (n == 1) {
        return 1;
    } else if (n < 1) {
        return 0;
    } else {
        int whole = n <= 3 ? 1 : 0;
        return whole + childsteps(n-1) + childsteps(n-2) + childsteps(n-3);
    }
}

int robot(int x0, int y0, int x, int y) {
    // Go from 0,0 (upper left) to x,y. How many ways are there?
    if (std::abs(x0-x) + std::abs(y0-y) == 1) {
        return 1;
    } else if (x0 == x && y0 == y) {
        return 0;
    } else {
        int down = y0 < y ? robot(x0, y0+1, x, y) : 0;
        int right = x0 < x ? robot(x0+1, y0, x, y) : 0;
        return down+right;
    }
}

int magicindex(const std::vector<int>& v, int from=0, int to=-1) {
    if (to < 0) {
        to = v.size()-1;
    }
    std::cout << from << " " << v[from] << " " << to << " " << v[to] << "\n";

    // Termination conditions
    if (from == to) {
        if (v[from] == from) {
            return from;
        } else {
            return -1;
        }
    } else if (v[from] < from && v[to] < to) {
        // No crossing.
        return -1;
    } else if (v[from] > from && v[to] > to) {
        return -1;
    } else if ((v[from] <= from && v[to] >= to) ||
            (v[from] >= from && v[to] <= to)) {
        // Magic element between from/to.
        int mid = (from+to)/2;
        int left_candidate = magicindex(v, from, mid);
        int right_candidate = magicindex(v, mid+1, to);
        if (left_candidate + right_candidate < 0)
            return -1;
        return std::max(left_candidate, right_candidate);
    } else {
        return -1;
    }
}

template<typename T>
std::set<std::set<T>> subsets(std::set<T> set) {
    if (set.size() == 1) {
        return std::set<std::set<T>>{set, std::set<T>{}};
    } else {
        std::set<std::set<T>> newset{set};
        for (const T& e : set) {
            std::set<T> subset = set;
            subset.erase(e);
            newset.merge(subsets(subset));
        }
        return newset;
    }
}

std::vector<std::string> permutations(const std::string& str) {
    std::vector<std::string> perms{};
    if (str.size() == 1) {
        perms.push_back(str);
    }
    for (int i = 0; i < str.size(); i++) {
        std::string substr = str.substr(0, i) + str.substr(i+1, str.size()-i-1);
        std::vector<std::string> inner_perms = permutations(substr);
        for (const std::string& s : inner_perms) {
            perms.push_back(str.substr(i, 1) + s);
        }
    }
    return perms;
}

int main(void) {
    auto before = std::chrono::steady_clock::now();
    for (const std::string& s : permutations("abcdefg")) {
        std::cout << s << "\n";
    }
    auto after = std::chrono::steady_clock::now();
    std::cout << "Took: " << std::chrono::duration_cast<std::chrono::microseconds>( after-before ).count() << "µs\n";
}