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

void print(std::vector<int> 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> stapel)
{
	// Jeder Plinsenstapel lässt sich mit weniger als 2n Wendungen ordnen
	auto optimal_wendungen = std::vector<int>(2*stapel.size(), 0); 
	// Breitensuche
	using kandidat = std::pair<std::vector<int>, std::vector<int>>;
	auto warteschlange = std::queue<kandidat>{};
	warteschlange.push(kandidat{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(kandidat{neuer_stapel, neue_wendungen});
					}
				}
			}
		}
	}
	return optimal_wendungen;
}

int main()
{
	auto stapel = std::vector{ 1,4,2,3 };
	auto w = finde_beste_wendungen(stapel);
	std::cout << w.size() << " Wendungen: ";
	print(w);
}
