SPOJ.com - Problem PROG0582

PROG0582 - Lineup

A group of persons are standing outside a room. Each wears a hat that's either red or blue. Each person can see the other person's hats but not his or her own. At a signal they enter the room one by one and arrange themselves in a line partitioned by hat color: all persons wearing a red hat are in front of the line and all persons wearing a blue hat are at the back of the line. How do they manage this without communicating?

The first person starts the line (eg. Alice in the example above). Thereafter each person entering the room follows the room. If the next person sees that all persons in the line wear red hats, that person joins the row at its end (e.g. Bob in the example above). If the next person sees that all persons in the row wear blue hats, that person joins the row upfront. If the next person sees that a line has already been formed with some people wearing red hats at the start of the line and some people wearing blue hats at the end of the line, that person inserts himself or herself at the break between the two colors (e.g. Claire, Dave and Elsa in the example above).

Assignment

Write a function lineup that takes a sequence (a list or a tuple) of persons. Each person is represented by a tuple of two elements: the first element is a string containing the name of the person, and the second element is a string that indicates the color of the hat the person wears on his/her hat (R for red and B for blue). The function must return a list containing the names of all persons in the given sequence, in the order they are lined up after they have entered the room one by one following the procedure that has been outlined in the introduction.

Example

The first example in the following interactive session corresponds to the figure in the introduction of this assignment.

>>> 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']

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). 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 (een lijst of een tuple) van personen moet doorgegeven worden. Hierbij wordt elke persoon voorgesteld door een tuple met twee elementen: het eerste element is een string die de naam van de persoon bevat, en het tweede element een string die de kleur van de hoed omschrijft die de persoon op zijn/haar hoofd heeft (R voor rood of B voor blauw). De functie moet een lijst met de namen 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']

Submit solution!

Added by:	Peter Dawyndt
Date:	2015-10-24
Time limit:	10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	PY_NBC