Two noodle stalls, A and B, open side by side at the night market in Tavi; one of them is better, and both are equally likely to be. Customers arrive one at a time. Each has a private signal, a hint from a friend that points to A or to B. Every signal is equally reliable (right with the same probability, more than one half), and signals are independent. A customer sees which stall every earlier customer chose, but not their signals.
Each customer believes A is better exactly when she knows of more A signals than B signals (her own plus those she can infer), B when she knows of more B signals, and when the counts are equal she follows her own signal. She then goes to the stall she believes is better.
Everyone knows these rules, so a later customer infers an earlier customer's signal from her choice whenever that choice depended on her signal (she would have chosen the other stall with the other signal). A choice that would have been the same with either signal reveals nothing; that customer is herding.
Some customers are food critics, written in lower case in signals: a critic always goes where her own signal points, and everyone knows it, so a critic's choice always reveals her signal. Ordinary customers are written in upper case.
Write noodle_queue(signals) where signals is a string of "A", "B", "a" and "b". Return a tuple (choices, herders, against): the string of stalls chosen (upper case), the number of customers who herded, and the number who chose against their own signal.
Examples
Input: signals = "ABBAAB"
Output: ('ABBAAB', 0, 0)
Explanation: whenever a customer's signal disagrees with what she inferred, the counts
are equal and she follows her own signal, so every choice reveals a signal.
Input: signals = "AABBBB"
Output: ('AAAAAA', 4, 4)
Explanation: after two revealed A signals, one B signal cannot tip the balance:
everyone from the third customer on goes to A, though most signals say B.
Input: signals = "AABbBA"
Output: ('AAABBA', 1, 1)
Explanation: the critic's B signal is public. The fifth customer infers two A signals
and one B, adds her own B, finds the counts equal and follows her own signal.
Goals
- Track what later people can infer from earlier choices, not from earlier signals
- Recognise when a choice no longer depends on private information (a cascade)
- See how publicly known independent choosers can break a cascade