A rumour is going round about the savings bank in Hollin. Each depositor has a threshold: she will withdraw her money as soon as she sees that at least that many other depositors have already withdrawn. A threshold of 0 means she withdraws at once; a threshold larger than the number of other depositors means she never will.
Withdrawals happen in rounds. In each round, every depositor who still has her money in the bank looks at how many depositors had withdrawn by the end of the previous round (0 before round 1), and withdraws in this round if that number is at least her threshold. All of them decide at the same time; a withdrawal in this round is only seen in the next round. The run stops after the first round in which nobody new withdraws (that round is not counted).
The bank keeps enough cash to pay reserves depositors. It fails if more than reserves depositors withdraw in total.
Write bank_run(thresholds, reserves) that returns a tuple (withdrawn, rounds, failed): the number of depositors who withdrew in the end, the number of rounds in which someone withdrew, and whether the bank failed.
Examples
Input: thresholds = [0, 1, 2, 3, 4, 5, 6, 7], reserves = 5
Output: (8, 8, True)
Explanation: one depositor goes in round 1, which tips the next one in round 2,
and so on: a chain of eight rounds.
Input: thresholds = [0, 2, 2, 3, 4, 5, 6, 7], reserves = 5
Output: (1, 1, False)
Explanation: after the first withdrawal nobody else's threshold is met, so the run stops.
Input: thresholds = [3, 0, 0, 1, 6, 2, 9], reserves = 4
Output: (5, 3, True)
Explanation: round 1: two depositors (thresholds 0, 0). Round 2: they see 2 and the
thresholds 1 and 2 go. Round 3: they see 4, the threshold 3 goes. 6 and 9 are never met.
Goals
- Simulate a crowd where each person acts once enough others have acted
- Update everyone simultaneously from last round's count, round by round
- See how one changed threshold can stop or start a whole run