#include <iostream>
#include <ranges>
#include <vector>

template<typename T>
void print_vector(const std::vector<T>& v) {
    for (auto&& i : v) {
        std::cout << i << " ";
    }
}

struct Hanoi {
    std::vector<int> a;
    std::vector<int> b;
    std::vector<int> c;
    size_t n;
    size_t moves;

    Hanoi(size_t n) : n(n), moves(0) {
        auto r = std::ranges::reverse_view(std::ranges::iota_view(1, int(n)+1));
        a = std::vector<int>(r.begin(), r.end());
    }

    void hanoi(std::vector<int>& from, std::vector<int>& to, std::vector<int>& buf, size_t n) {
        // Invariant: from, to, buf are all sorted. from.size() >= n.
        if (n == 0)
            return;
        if (n == 1) {
            to.push_back(from.back());
            from.pop_back();
            moves++;
            return;
        }
        hanoi(from, buf, to, n-1);
        print_hanoi();
        hanoi(from, to, buf, 1);
        print_hanoi();
        hanoi(buf, to, from, n-1);
    }

    void do_it() {
        print_hanoi();
        hanoi(a, c, b, n);
        std::cout << "== after ==\n";
        print_hanoi();
    }

    void print_hanoi() {
        std::cout << "A: ";
        print_vector(this->a);
        std::cout << " B: ";
        print_vector(this->b);
        std::cout << " C: ";
        print_vector(this->c);
        std::cout << "\n";
    }

    size_t predict_moves(size_t N) {
        if (N == 1) return 1;
        return 1 + 2*predict_moves(N-1);
    }
};


int main(void) {
    Hanoi h(4);
    h.do_it();
    std::cout << "took " << h.moves << " moves.\n";
    std::cout << "predicted " << h.predict_moves(h.n) << " moves.\n";
    std::cout << "\n";
}