def ist_sortiert(stapel):
	for i in range(1, len(stapel)):
		if stapel[i-1] < stapel[i]: return False
	return True

def umdrehen(stapel, index):
	unten = stapel[:index]
	oben = list(reversed(stapel[index:]))
	return unten + oben
	
def finde_beste_wendungen(stapel):	
	# Jeder Plinsenstapel lässt sich mit weniger als 2n Wendungen ordnen
	optimal_wendungen = [0] * (2*len(stapel)) 
	# Breitensuche
	warteschlange = [(stapel, [])]
	while warteschlange:
		stapel, wendungen = warteschlange[0]
		warteschlange.pop(0)
		if ist_sortiert(stapel):
			if len(wendungen) < len(optimal_wendungen):
				optimal_wendungen = wendungen
		else:
			if len(wendungen) + 1 < len(optimal_wendungen):
				for pos in range(len(stapel)-1):
					if not wendungen or pos != wendungen[-1]:
						neuer_stapel = umdrehen(stapel, pos)
						neue_wendungen = wendungen + [pos]
						warteschlange += [(neuer_stapel, neue_wendungen)]
	return optimal_wendungen

def main():
	stapel = [1,4,2,3]
	print(ist_sortiert(stapel))
	einstichhöhen = finde_beste_wendungen(stapel)
	print(f'Einstichhöhen: {einstichhöhen} -> {len(einstichhöhen)} Wendungen')

if __name__ == '__main__':
	main()
