Bulgarian solitaire

def bulgarian_solitaire(piles, k):

You are given a row of piles of pebbles, all identical, and a positive integer k so that the total number of pebbles in these piles equals k*(k+1)//2, the arithmetic sum formula that equals the sum of positive integers from 1 to k. Almost as if intended as a metaphor for the bleak daily life behind the Iron Curtain, all pebbles are identical and you don't have any choice in your moves. Each move picks up one pebble from each pile (even if doing so makes that pile vanish), and creates a new pile from the resulting handful. For example, starting with[7, 4, 2, 1, 1], the first move turns this into [6, 3, 1, 5]. The next move turns that into [5, 2, 4, 4], which then turns into the five-pile configuration [4, 1, 3, 3, 4], and so on.

This function should count how many moves are needed to convert the given initial piles into the goal state where each number from 1 to k appears as the size of exactly one pile, and return that count. These numbers from 1 to k may appear in any order inside the list, not necessarily in sorted order. Applying the basic move to this goal state simply leads right back in that same goal state. (In mathematical lingo, the goal state is a fixed point of the transformation function between these configurations of pebbles, so this process gets stuck in that state forever once it falls into it.)

This problem is from the Martin Gardner column "Bulgarian Solitaire and Other Seemingly Endless Tasks". It was used there as an example of a while-loop where it is not immediately obvious that this loop will always eventually reach its goal and terminate, analogous to the behaviour of the Collatz 3x+1 problem back in mathproblems.py. However, unlike in that still annoyingly open problem, a combinatorial proof shows that Bulgarian solitaire can never get stuck, but must terminate from any starting configuration of pyramidal numbers after at most k(k-1)/2 steps.

piles k Expected result [1, 4, 3, 2] 4 0

[8, 3, 3, 1] 5 9

[10, 10, 10, 10, 10, 5] 10 74

[3000, 2050] 100 7325

[2*i-1 for i in range(171, 0, -2)] 171 28418