Beads of different colours (given as integers) are threaded on a string, left to right. A run is a maximal block of neighbouring beads of the same colour. The string reacts in waves:
- In one wave, every run of 3 or more beads that exists at that moment vanishes at the same time, and the remaining beads slide together, keeping their order.
- Sliding together can create new long runs, which vanish in the next wave.
- The reaction stops when there is no run of length 3 or more.
Write chain_crush(beads) that returns a tuple (remaining, waves): the list of beads left at
the end and the number of waves in which something vanished. Do not change the input list.
Examples
Input: beads = [3, 1, 1, 1, 3, 3, 2, 2, 2, 3]
Output: ([], 2)
Explanation: wave 1 removes the 1s and the 2s together, leaving [3, 3, 3, 3];
wave 2 removes those.
Input: beads = [1, 2, 2, 1, 1, 2]
Output: ([1, 2, 2, 1, 1, 2], 0)
Input: beads = [4, 5, 5, 6, 6, 6, 5, 4, 4]
Output: ([], 3)
Constraints
0 <= len(beads) <= 3000,0 <= beads[i] <= 9
Goals
- Split a list into maximal runs of equal values
- Apply removals simultaneously by building a new list
- Repeat a pass until nothing changes