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?

lineup strategy
Illustration of the strategy that assures that persons wearing a red hat are in front of the line and perons wearing a blue hat in the back.

The first person starts the line (eg. Alice in the example above). Thereafter each person entering the room follows the same rule. 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 (list or tuple) of persons. Each person is represented by a tuple of two elements: the name (str) of the person and the color (str) 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 (str) 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']