def spread_the_coins(piles, left, right): Some coins have been placed on the integer line ℤ so that for every i in range(len(piles)) , the position i initially contains piles[i] coins. The other positions on the set of integers ℤ, both positive and negative, are initially empty. A position that contains at least left+right coins is defined to be unstable. As long as some position i is unstable, exactly left coins from that position i spill into its predecessor position i-1, and exactly right coins spill into its successor position i+1. Repeat until every position is stable. The unique terminal state of this back-and-forth dance will necessarily be reached after a finite number of steps, independent of the order of processing the unstable positions in the interim. This function should return this terminal state as tuple (start, coins) where start is the leftmost position that contains at least one coin. The second component lists the coins that ended in each position, this list spanning the positions from start up to the last non-empty position. To speed up this process, note how whenever some pile contains k*(left+right) coins, you can scoop k*left coins into the predecessor and k*right coins into the successor pile as a single move. The new difficulty of this problem is handling the negative positions during computation, and also quickly finding some unstable position to process next.
Everybody come do the Scrooge Shuffle
def spread_the_coins(piles, left, right):
Some coins have been placed on the integer line ℤ so that for every i in range(len(piles)) , the position i initially contains piles[i] coins. The other positions on the set of integers ℤ, both positive and negative, are initially empty. A position that contains at least left+right coins is defined to be unstable. As long as some position i is unstable, exactly left coins from that position i spill into its predecessor position i-1, and exactly right coins spill into its successor position i+1. Repeat until every position is stable.
The unique terminal state of this back-and-forth dance will necessarily be reached after a finite number of steps, independent of the order of processing the unstable positions in the interim. This function should return this terminal state as tuple (start, coins) where start is the leftmost position that contains at least one coin. The second component lists the coins that ended in each position, this list spanning the positions from start up to the last non-empty position.
To speed up this process, note how whenever some pile contains k*(left+right) coins, you can scoop k*left coins into the predecessor and k*right coins into the successor pile as a single move. The new difficulty of this problem is handling the negative positions during computation, and also quickly finding some unstable position to process next.
| piles | left | right | Expected result |
| [0, 0, 2] | 1 | 1 | (1, [1, 0, 1]) |
| [20] | 3 | 2 | (-4, [3, 1, 4, 2, 4, 2, 4]) |
| [8, 4] | 3 | 2 | (-2, [3, 1, 3, 3, 2]) |
| [111, 12, 12] | 19 | 6 | (-6, [19, 13, 13, 13, 13, 13, 10, 23, 18]) |
| [101] | 1 | 1 | (a tuple whose first element equals -50 and the second element is a list of 101 copies of 1) |
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
