De chef-kok van een restaurant is nogal van het slordige type. Als hij een stapel pannenkoeken moet bakken dan zijn er nooit twee pannenkoeken met dezelfde grootte. De maitre d'hotel eist echter dat de kelners alle pannenkoeken in een stapel eerst van klein naar groot sorteren — met de kleinste pannenkoek van boven en de grootste van onder — voor ze die naar de tafelgasten brengen.

pannenkoeken sorteren
De kelners moeten een stapel pannenkoeken van klein naar groot sorteren, waarbij de kleinste pannenkoek bovenaan de stapel komt te liggen en de grootste onderaan.

Om een stapel pannenkoeken te sorteren, kunnen de kelners echter slechts één handeling uitvoeren: ze schuiven een spatel onder één van de pannenkoeken in de stapel, wentelen alle pannenkoeken op de spatel samen om en leggen die terug bovenop het resterende deel van de stapel. Ze kunnen deze handeling verschillende keren na elkaar uitvoeren, waarbij ze de spatel telkens onder een andere pannenkoek kunnen schuiven. Om snel te kunnen werken, maken de kelners er een sport van om een stapel te sorteren met zo weinig mogelijk wentelingen.

pannenkoeken wentelen
Met een bakspatel wordt de bovenste stapel van zes pannenkoeken gewenteld.

De uitdaging wordt nog groter als de chef-kok weer eens te diep in het glas gekeken heeft, waardoor hij de onderkant van alle pannenkoeken heeft laten aanbranden. De maitre d'hotel verwacht dan immers niet alleen dat zijn kelners de pannenkoeken van klein naar groot sorteren, maar dat ze er ook voor zorgen dat de aangebrande kant van de pannenkoeken van onder ligt.

aangebrande pannenkoeken sorteren
De kelners moeten een stapel pannenkoeken van klein naar groot sorteren, waarbij de kleinste pannenkoek bovenaan de stapel komt te liggen en de grootste onderaan. Bovendien moeten alle pannenkoeken na het sorteren ook met hun aangebrande kant naar onder liggen.

Bij het wentelen van een aantal aangebrande pannenkoeken aan de bovenkant van de stapel, verandert in dat geval niet alleen de volgorde van de pannenkoeken, maar keren ook alle pannenkoeken om. Daardoor zal een pannenkoek die met de aangebrande kant naar onder lag na het wentelen met de aangebrande kant naar boven liggen, en omgekeerd.

aangebrande pannenkoeken wentelen
Met een bakspatel wordt de bovenste stapel van zes aangebrande pannenkoeken gewenteld. Hierdoor verandert niet alleen de volgorde van de pannenkoeken, maar keren ook alle pannenkoeken om. Een pannenkoek die met de aangebrande kant naar onder lag, zal na het wentelen met de aangebrande kant naar boven liggen, en omgekeerd.

Er bestaat een eenvoudig algoritme om een stapel van $$n$$ pannenkoeken te sorteren. We leggen het uit door de posities van de pannenkoeken van boven naar onder te nummeren vanaf 1. Elke sorteerstap van het algoritme zorgt ervoor dat de grootste van de $$m$$ ($$1 \leq m \leq n$$) bovenste pannenkoeken op positie $$m$$ komt te liggen, en ook met de aangebrande kant naar onder als het een stapel aangebrande pannenkoeken is.

  1. zoek de positie $$i$$ ($$1 \leq i \leq m$$) van de grootste pannenkoek in de bovenste $$m$$ pannenkoeken

  2. wentel de bovenste $$i$$ pannenkoeken, waardoor de grootste pannenkoek bovenaan komt te liggen

  3. enkel voor aangebrande pannenkoeken: wentel de bovenste pannenkoek als die met de aangebrande kant naar onder ligt, zodat die met de aangebrande kant naar boven komt te liggen

  4. wentel de bovenste $$m$$ pannenkoeken waardoor de grootste pannenkoek op positie $$m$$ komt te liggen (en ook met de aangebrande kant naar onder als het een stapel aangebrande pannenkoeken is)

Om de volledige stapel pannenkoeken te sorteren, volstaat het dan om deze sorteerstap achtereenvolgens uit te voeren voor de bovenste $$n$$ pannenkoeken ($$m = n$$), de bovenste $$n-1$$ pannenkoeken ($$m = n-1$$), …, de bovenste $$2$$ pannenkoeken ($$m = 2$$) en de bovenste pannenkoek ($$m = 1$$).

Opgave

Een pannenkoek wordt voorgesteld door een getal $$p \in \mathbb{Z}_0$$ (int). Voor niet-aangebrande pannenkoeken geldt dat $$p \in \mathbb{N}_0$$, waarbij de waarde $$p$$ de grootte van de pannenkoek aangeeft. Voor aangebrande pannenkoeken geeft de absolute waarde $$|p|$$ de grootte van de pannenkoek aan en geeft het teken van $$p$$ aan waar de aangebrande kant ligt: onderaan als $$p > 0$$ en bovenaan als $$p < 0$$.

Een stapel van $$n$$ pannenkoeken wordt voorgesteld door een tuple (tuple) met de voorstellingen van de $$n$$ pannenkoeken in de stapel, opgelijst van boven naar onder. In een stapel zijn er nooit twee pannenkoeken met dezelfde grootte. Met andere woorden, de voorstelling van elke pannenkoek in de stapel heeft een unieke absolute waarde. In een stapel zijn ofwel alle pannenkoeken aan één kant aangebrand, ofwel zijn er geen aangebrande pannenkoeken.

Je opdracht bestaat erin om een gegeven stapel van $$n \in \mathbb{N}_0$$ pannenkoeken te sorteren aan de hand van het eenvoudig algoritme uit de inleiding. Hiervoor moet je de volgende functies schrijven, waaraan als eerste argument telkens een stapel met $$n$$ pannenkoeken moet doorgegeven worden. Behalve de functie zoek_grootste, hebben alle andere functies een optionele parameter aangebrand waaraan een Booleaanse waarde kan doorgegeven worden (standaardwaarde: False). Deze parameter geeft aan of de gegeven stapel pannenkoeken aangebrand is (True) of niet (False).

Voorbeeld

>>> wentel((9, 2, 7, 5, 8, 1, 4, 6, 3))
(3, 6, 4, 1, 8, 5, 7, 2, 9)
>>> wentel((-9, -2, -7, 5, 8, -1, -4, -6, 3), aangebrand=True)
(-3, 6, 4, 1, -8, -5, 7, 2, 9)

>>> wentel_bovenste((1, 4, 6, 3, 5, 2, 7, 8, 9), 3)
(6, 4, 1, 3, 5, 2, 7, 8, 9)
>>> wentel_bovenste((6, 4, 1, 3, 5, 2, 7, 8, 9), 6)
(2, 5, 3, 1, 4, 6, 7, 8, 9)
>>> wentel_bovenste((-1, -4, -6, 3, -5, -2, 7, 8, 9), 3, aangebrand=True)
(6, 4, 1, 3, -5, -2, 7, 8, 9)
>>> wentel_bovenste((6, 4, 1, 3, -5, -2, 7, 8, 9), 1, aangebrand=True)
(-6, 4, 1, 3, -5, -2, 7, 8, 9)
>>> wentel_bovenste((-6, 4, 1, 3, -5, -2, 7, 8, 9), 6, aangebrand=True)
(2, 5, -3, -1, -4, 6, 7, 8, 9)

>>> zoek_grootste((1, 4, 6, 3, 5, 2, 7, 8, 9), 6)
3
>>> zoek_grootste((-1, -4, -6, 3, -5, -2, 7, 8, 9), 6)
3

>>> sorteerstap((1, 4, 6, 3, 5, 2, 7, 8, 9), 6)
(2, 5, 3, 1, 4, 6, 7, 8, 9)
>>> sorteerstap((-1, -4, -6, 3, -5, -2, 7, 8, 9), 6, aangebrand=True)
(2, 5, -3, -1, -4, 6, 7, 8, 9)

>>> sorteerstappen((1, 8, 5, 7, 2, 9, 4, 6, 3))
[(1, 8, 5, 7, 2, 9, 4, 6, 3), (3, 6, 4, 1, 8, 5, 7, 2, 9), (2, 7, 5, 3, 6, 4, 1, 8, 9), (1, 4, 6, 3, 5, 2, 7, 8, 9), (2, 5, 3, 1, 4, 6, 7, 8, 9), (4, 1, 3, 2, 5, 6, 7, 8, 9), (2, 3, 1, 4, 5, 6, 7, 8, 9), (1, 2, 3, 4, 5, 6, 7, 8, 9)]
>>> sorteerstappen((1, -8, -5, 7, 2, 9, -4, -6, 3), aangebrand=True)
[(1, -8, -5, 7, 2, 9, -4, -6, 3), (-3, 6, 4, 1, -8, -5, 7, 2, 9), (-2, -7, 5, -3, 6, 4, 1, 8, 9), (-1, -4, -6, 3, -5, -2, 7, 8, 9), (2, 5, -3, -1, -4, 6, 7, 8, 9), (4, 1, 3, 2, 5, 6, 7, 8, 9), (-2, -3, -1, 4, 5, 6, 7, 8, 9), (1, -2, 3, 4, 5, 6, 7, 8, 9), (1, 2, 3, 4, 5, 6, 7, 8, 9)]

Epiloog

Het eenvoudige algoritme uit deze opgave minimaliseert allerminst het aantal wentelingen dat nodig is om een stapel pannenkoeken te sorteren. Zoeken naar het minimaal aantal wentelingen blijkt echter een heel moeilijke opdracht te zijn. In 1979 publiceerde de oprichter van Microsoft — Bill Gates1 (toen nog William Gates) — samen met Christos Papadimitriou2 (toen op Harvard, nu in Columbia) zijn enige bekende wetenschappelijk artikel getiteld Bounds for sorting by prefix reversal, waarin ze een veel efficiënter algoritme beschrijven om stapels pannenkoeken te sorteren. Ook David X. Cohen3 (toen nog David S. Cohen) — maker van de animatiereeks Futurama4 — publiceerde een wetenschappelijk artikel met een efficiënt algoritme om stapels verbrande pannenkoeken te sorteren. Daarvoor werkte hij samen met Manuel Blum5 (toen op Berkeley, nu aan de Carnegie Mellon University).

In 2008 bouwde een groep studenten een bacteriële computer die in staat was om een eenvoudig stapel met verbrande pannenkoeken te sorteren. Ze deden dit door E. coli bacteriën zo te programmeren dat ze in staat zijn tot het omkeren van DNA-segmenten die analoog zijn aan verbrande pannenkoeken. DNA heeft immers een oriëntatie (5' en 3') en een volgorde. Hoewel de rekenkracht die wordt gerealiseerd door het omkeren van DNA behoorlijk laag is, levert het grote aantal bacteriën in een kweek een grote parallelle computer op. De bacteriën laten weten wanneer ze de pannenkoeken gesorteerd hebben door resistent te worden voor antibiotica.

Bronnen