SPOJ.com - Problem PROG0542

PROG0542 - Hat check

One hundred people stand in a line, all facing in the same direction. Each is wearing a red or a blue hat, assigned at random. Each person can see all the hats before him in the line, but not his own or those of the people behind him. Starting at the back of the line, each person in turn must guess the color of his own hat. Each person can hear all the prior guesses. If the group are allowed to discuss a strategy beforehand, how many can be sure of guessing correctly?

The answer, surprisingly, is 99 — the first guess may be wrong, but everyone else can guess correctly. The strategy needed to accomplish this takes two successive steps.

Before any guesses are made, each person in the line counts the red hats before him. If the total is odd, he prepares the answer red. If it's even (including 0), he prepares the answer blue.

Now, while awaiting his turn to speak, each person listens to the guesses behind him. Each time he hears red, he switches the color of his own prepared guess from red to blue or back again. When his turn comes to speak, he gives his prepared guess.

In addition, this strategy works irrespective of the number of people that stand in the line. The above figure explains the strategy using a line of five people. First, each person counts the red hats he sees before him. The first persons sees no red hats, the second and third person each see one red hat, the forth person sees two red hats and the last person sees three red hats. The first and forth person see an even number of red hats, and thus keep the color blue in mind. The other people heel the color red in mind because they see an odd number of red hats.

After the initial counting, the last person in the line comes first to guess the color of his own hat. Because he keeps the color red in mind, this is the color he says out loud (herewith making a wrong guess). The first four people hear the color red, and switch the color they keep in mind. The penultimate person now keeps the color red in mind, and comes next to guess the color of his own hat. Because the first three people again hear the color red, they again switch the color they keep in mind. This continues until finally the first person in the line says the color he keeps in mind at that time.

Assignment

In this assignment the letters R and B respectively represent the colors red and blue. A line of people that each have an associated color (either the color of the hat on their head, or the color they keep in mind) is represented by a sequence (a list, a tuple or a string) of letters. Your task is to write two functions that implement the first and the second step of the strategy outlined in the introduction.

Write a function see that takes a line of people that each have a red of blue colored hat on their head. The function must return a tuple that contains the colors that each of the persons in the line keep in mind based on the number of red heads they see in from of them. An odd number of red hats corresponds to the color red, and an even number of red hats (including 0) corresponds to the color blue.
Write a function say that takes a line of people that each keep a color in mind, being the color they have determined based on the number of red hats they see in front of them. The function must return a tuple containing the colors that each person will finally say out loud after they have followed the second step of the strategy outlined in the introduction.

Example

>>> see(('R', 'B', 'R', 'R', 'B'))
('B', 'R', 'R', 'B', 'R')
>>> see(['R', 'R', 'B', 'R', 'R', 'B', 'R', 'B', 'R', 'R'])
('B', 'R', 'B', 'B', 'R', 'B', 'B', 'R', 'R', 'B')
>>> see('BBRBRBRBBRBR')
('B', 'B', 'B', 'R', 'R', 'B', 'B', 'R', 'R', 'R', 'B', 'B')

>>> say(('B', 'R', 'R', 'B', 'R'))
('R', 'B', 'R', 'R', 'R')
>>> say(['B', 'R', 'B', 'B', 'R', 'B', 'B', 'R', 'R', 'B'])
('R', 'R', 'B', 'R', 'R', 'B', 'R', 'B', 'R', 'B')
>>> say('BBRBRBRBBRBB')
('B', 'R', 'R', 'R', 'R', 'R', 'R', 'B', 'R', 'R', 'B', 'B')

Notice that the first two test cases correspond to the example given in the introduction of this assignment.

Honderd personen staan achter elkaar in een rij, en kijken allemaal in dezelfde richting. Er worden willekeurig rode en blauwe hoeden op de hoofden van deze personen gezet. Elke persoon kan alle hoeden voor hem zien, maar niet zijn eigen hoed of deze achter hem. Te beginnen achteraan de rij, moet elke persoon om de beurt raden welke kleur van hoed hij op zijn hoofd heeft. Elke persoon kan alle kleuren horen die de personen achter hem raden. Als de groep personen op voorhand mag overleggen over een strategie, hoeveel personen kunnen dan gegarandeerd de juiste kleur raden van de hoed op hun eigen hoofd?

Het antwoord is verrassend genoeg 99 — de eerste gok kan verkeerd zijn, maar alle anderen kunnen de juiste kleur raden. De strategie die hiervoor moet gebruikt worden bestaat uit twee stappen.

Alvorens de persoon achteraan de rij begint te raden, telt elke persoon het aantal rode hoeden die hij voor zich ziet. Als het aantal rode hoeden oneven is, dan houdt hij de kleur rood in zijn hoofd. Als het aantal rode hoeden even is (inclusief 0), dan houdt hij de kleur blauw in zijn hoofd.

Daarna luistert elke persoon naar de kleuren die achter hem geraden worden, totdat het zijn eigen beurt is om de kleur van zijn hoed te raden. Elke keer hij de kleur rood hoort, wisselt hij de kleur die hij in zijn hoofd hield (rood wordt blauw, en omgekeerd). Als hij aan de beurt komt om een kleur te raden, zegt hij de kleur die hij op dat moment in zijn hoofd houdt.

Bovendien werkt deze strategie ongeacht het aantal personen in de rij. Bovenstaande figuur illustreert dit met een voorbeeld waarbij er slechts vijf personen in de rij staan. Eerst telt elke persoon het aantal rode hoeden die hij voor zich ziet. De eerste persoon ziet geen rode hoeden, de tweede en derde persoon zien er elk één, de vierde persoon ziet er twee en de laatste persoon ziet er drie. De eerste en vierde persoon zien een even aantal rode hoeden, en houden dus de kleur blauw in hun hoofd. De overige personen houden de kleur rood in hun hoofd omdat ze een oneven aantal rode hoeden zien.

Daarna komt de persoon achteraan de rij als eerste aan de beurt om de kleur van zijn hoed te raden. Omdat hij de kleur rood in zijn hoofd heeft, zegt hij deze kleur luidop (en maakt daarmee de verkeerde keuze). De eerste vier personen horen de kleur rood, en wisselen de kleur die ze in hun hoofd hielden. De voorlaatste persoon heeft nu de kleur rood in zijn hoofd, en is als volgende aan de beurt om deze kleur luidop te zeggen. Omdat de eerst drie personen opnieuw de kleur rood achter zich horen zeggen, wisselen ze terug de kleur die ze in hun hoofd hielden. Dit gaat zo verder totdat uiteindelijk de eerste persoon uit de rij de kleur zegt die hij op dat moment in zijn hoofd heeft.

Opgave

In deze opgave stellen we de kleuren rood en blauw respectievelijk voor door de letters R en B. Een rij van personen die elk een geassocieerde kleur hebben (hetzij de kleur van de hoed op hun hoofd, hetzij een kleur die ze in hun hoofd houden) wordt voorgesteld door een reeks (een lijst, een tuple of een string) letters. Gevraagd wordt om de volgende twee functies te schrijven, die een implementatie vormen van de eerste en de tweede stap uit de strategie die in de inleiding werd uiteengezet.

Schrijf een functie zien waaraan een rij van personen moet doorgegeven worden, die elk een rode of een blauwe hoed op hun hoofd hebben. De functie moet een tuple teruggeven, dat de kleuren bevat die de personen uit de gegeven rij in hun hoofd houden op basis van het aantal rode hoeden die ze voor zich zien in de rij. Een oneven aantal rode hoeden correspondeert met de kleur rood, en een even aantal rode hoeden (inclusief 0) correspondeert met de kleur blauw.
Schrijf een functie zeggen waaraan een rij van personen moet doorgegeven worden, die elk een kleur (rood of blauw) in hun hoofd houden, zijnde de kleur die ze bepaald hebben op basis van het aantal rode hoeden die ze voor zich zien. De functie moet een tuple teruggeven, dat de kleuren bevat die de personen uiteindelijk zullen zeggen als ze de tweede stap uit de strategie volgen die in de inleiding wordt uiteengezet.

Voorbeeld

>>> zien(('R', 'B', 'R', 'R', 'B'))
('B', 'R', 'R', 'B', 'R')
>>> zeggen(('B', 'R', 'R', 'B', 'R'))
('R', 'B', 'R', 'R', 'R')

>>> zien(['R', 'R', 'B', 'R', 'R', 'B', 'R', 'B', 'R', 'R'])
('B', 'R', 'B', 'B', 'R', 'B', 'B', 'R', 'R', 'B')
>>> zeggen(['B', 'R', 'B', 'B', 'R', 'B', 'B', 'R', 'R', 'B'])
('R', 'R', 'B', 'R', 'R', 'B', 'R', 'B', 'R', 'B')

>>> zien('BBRBRBRBBRBR')
('B', 'B', 'B', 'R', 'R', 'B', 'B', 'R', 'R', 'R', 'B', 'B')
>>> zeggen('BBRBRBRBBRBB')
('B', 'R', 'R', 'R', 'R', 'R', 'R', 'B', 'R', 'R', 'B', 'B')

Merk op dat de eerste twee testgevallen corresponderen met het voorbeeld dat in de inleiding werd besproken.

Submit solution!

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