// übersetzt mit GNU C++ https://winlibs.com/
// x86_64-w64-mingw32-g++.exe -O3 -std=c++26 -Wall    P25L32h.cpp  -lstdc++exp -o P25L32h

#include <algorithm>
#include <chrono>
#include <iostream>
#include <queue>
#include <ranges>
#include <utility>
#include <vector>

void print(std::vector<int> const& stapel)
{
	std::cout << "[ ";
	for (auto e : stapel) std::cout << e << ' ';
	std::cout << "]\n";
}

std::vector<int> umdrehen(std::vector<int> stapel, size_t index)
{
	std::reverse(stapel.begin() + index, stapel.end());
	return stapel;
}

std::vector<int> finde_beste_wendungen(std::vector<int> const& stapel)
{
	// Jeder Plinsenstapel lässt sich mit weniger als 2n Wendungen ordnen
	auto optimal_wendungen = std::vector<int>(2*stapel.size(), 0); 
	// Breitensuche
	using eintrag = std::pair<std::vector<int>, std::vector<int>>;
	auto warteschlange = std::queue<eintrag>{};
	warteschlange.push({stapel, {}});
	while (not warteschlange.empty())
	{
		auto [stapel, wendungen] = warteschlange.front();
		warteschlange.pop();
		if (std::ranges::is_sorted(stapel))
		{
			if (wendungen.size() < optimal_wendungen.size())
				optimal_wendungen = wendungen;
		}
		else
		{
			if (wendungen.size() + 1 < optimal_wendungen.size())
			{
				for (size_t pos = 0; pos < stapel.size()-1; ++pos)
				{
					if (wendungen.empty() or pos != static_cast<size_t>(wendungen.back()))
					{
						auto neuer_stapel = umdrehen(stapel, pos);
						auto neue_wendungen = wendungen;
						neue_wendungen.push_back(pos);
						warteschlange.push({std::move(neuer_stapel), std::move(neue_wendungen)});
					}
				}
			}
		}
	}
	return optimal_wendungen;
}

auto erzeuge_stapel(int n)
{
	return std::views::iota(1, n+1) | std::ranges::to<std::vector>();
}

int maximale_anzahl_wendungen(int n)
{
	int maximum = 0;
	auto stapel = erzeuge_stapel(n);
	do
	{
		int anzahl = finde_beste_wendungen(stapel).size();
		maximum = std::max(maximum, anzahl); 
	} while (std::ranges::next_permutation(stapel).found);
	return maximum;;
}
	
int main()
{
	for (int n = 0; n < 10; ++n)
	{
		auto start{std::chrono::steady_clock::now()};
		int max = maximale_anzahl_wendungen(n);
		auto end{std::chrono::steady_clock::now()};
		std::cout << n << '\t' << max<< '\t'
		          << std::chrono::duration<double>{end - start} << '\n'; 
	}
}
