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.