Een groep personen staat voor de deur van een kamer. Elke persoon draagt ofwel een rode of een blauwe hoed. Iedereen kan de hoed zien op het hoofd van de anderen, maar niet de hoed op zijn of haar eigen hoofd. Als een bepaald teken gegeven wordt, gaat iedereen één voor één de kamer binnen en stelt zich op in een rij, zodat alle personen met een rode hoed vooraan staan en alle personen met een blauwe hoed achteraan. Hoe slagen ze er in om dat te doen, zonder met elkaar te communiceren?

De eerste persoon vormt het begin van de rij (bv. Alice in bovenstaand voorbeeld). Daarna volgt elke persoon die vervolgens de kamer binnenkomt dezelfde vuistregel. Als de volgende persoon ziet dat alle personen in de rij een rode hoed dragen, dan gaat die persoon achteraan in de rij staan (bv. Bob in bovenstaand voorbeeld). Als de volgende persoon ziet dat alle personen in de rij een blauwe hoed dragen, dan gaat die persoon vooraan in de rij staan. Als de volgende persoon ziet dat er zich reeds een rij gevormd heeft waarbij de personen met rode hoeden vooraan staan en de personen met blauwe hoeden achteraan, dan zet die persoon zich in de rij tussen de personen met de rode hoeden en de personen met de blauwe hoeden (bv. Claire, Dave en Elsa in bovenstaand voorbeeld).

Opgave

Schrijf een functie lineup waaraan een reeks (list of tuple) van personen moet doorgegeven worden. Hierbij wordt elke persoon voorgesteld door een tuple met twee elementen: de naam (str) van de persoon en de kleur (str) van de hoed die de persoon op zijn/haar hoofd heeft (R voor rood of B voor blauw). De functie moet een lijst (list) met de namen (str) van de personen teruggeven, in de volgorde waarin ze finaal in de rij staan nadat ze één na één de kamer zijn binnen gegaan in de volgorde van de gegeven reeks, en zich in de rij geplaatst hebben op de manier die in de inleiding wordt omschreven.

Voorbeeld

Het eerste voorbeeld in onderstaande interactieve sessie, komt overeen met de afbeelding uit de inleiding van deze opgave.

>>> lineup([('Alice', 'R'), ('Bob', 'B'), ('Claire', 'R'), ('Dave', 'R'), ('Elsa', 'B')])
['Alice', 'Claire', 'Dave', 'Elsa', 'Bob']
>>> lineup([('Sparkle', 'R'), ('Rolf', 'R'), ('Eileen', 'R'), ('Madie', 'R')])
['Sparkle', 'Rolf', 'Eileen', 'Madie']
>>> lineup((('Brian', 'B'), ('Margot', 'B'), ('Hans', 'B'), ('Lucinda', 'B')))
['Lucinda', 'Hans', 'Margot', 'Brian']