Bulgarian Solitaire

Question

Bulgarian Solitaire is a single-player game made popular by Martin Gardner in his mathematical column in Scientific American.

You have N identical cards, split into piles. You take a card from each pile and form a new pile with the removed cards. You repeat this process until you reach a state you've already seen and so continuing would repeat the loop.

For example, say you have 8 cards, split into a pile of 5 and a pile of 3. We write the pile sizes in descending order: 5 3. Here's a transcript of the game:

5 3
4 2 2
3 3 1 1 
4 2 2

You first remove a card from each of the two piles, leaving piles of 4 and 2, and a newly-created pile of 2, giving 4 2 2. In the next step, these decrease to 3 1 1 followed with a new pile of 3. Finally, the last step empties the piles of size 1 and produces4 2 2 which has already appeared, so we stop.

Note that the sum of the pile-sizes stays the same.

Your goal is to print such a transcript of the game from a given starting configuration. This is code golf, so fewest bytes wins.

Input

A list of positive numbers in descending order representing the initial pile sizes. Take input via STDIN or function input. You can use any list-like structure you want.

You don't get the total number of cards N as an input.

Output

Print the sequence of pile sizes the game of Bulgarian Solitaire goes through. Note that printing is required, not returning. Each step should be its own line.

Each line should have a sequence of positive numbers in descending order with no 0's. You may have separators and start and end tokens (for example, [3, 3, 1, 1]). The numbers might have multiple digits, so they should be separated somehow.

Print the pile-size splits you see until and including reaching a repeat. So, the first line should be the input, and the last line should be a repeat of a previous line. There shouldn't be any other repeats.

Test cases

>> [1]
1
1

>> [2]
2
1 1
2

>> [1, 1, 1, 1, 1, 1, 1]
1 1 1 1 1 1 1
7
6 1
5 2
4 2 1
3 3 1
3 2 2
3 2 1 1
4 2 1

>> [5, 3]
5 3
4 2 2
3 3 1 1
4 2 2

>> [3, 2, 1]
3 2 1
3 2 1

>> [4, 4, 3, 2, 1]
4 4 3 2 1
5 3 3 2 1
5 4 2 2 1
5 4 3 1 1
5 4 3 2
4 4 3 2 1

Answer 1

Pyth, 40 25

QW!}QY~Y]Q=Q_S+fTmtdQ]lQQ

This is pretty close to a translation of my python 2 answer.

Sample run:

Input:

[4,4,3,2,1]

Output:

[4, 4, 3, 2, 1]
[5, 3, 3, 2, 1]
[5, 4, 2, 2, 1]
[5, 4, 3, 1, 1]
[5, 4, 3, 2]
[4, 4, 3, 2, 1]

How it works:

Q                          Q = eval(input()) # automatic
 W!}QY                     while not Q in Y:
      ~Y]Q                     Y += [Q]
               fTmtdQ                     filter(lambda T: T, map(lambda d: d - 1, Q))
            _S+      ]lQ           sorted(                                             + [len(Q)])[::-1]
          =Q_S+fTmtdQ]lQ       Q = sorted(filter(lambda T: T, map(lambda d: d - 1, Q)) + [len(Q)])[::-1]
                        Q      print(Q)
QW!}QY~Y]Q=Q_S+fTmtdQ]lQQ

Answer 2

CJam, 26 bytes

q{~_:(_,+0-$W%]___&=}g{p}/

Try it online.

Example run

$ cjam <(echo 'q{~_:(_,+0-$W%]___&=}g{p}/') <<< '[5 3]'
[5 3]
[4 2 2]
[3 3 1 1]
[4 2 2]

Answer 3

Ruby, 98

f=->c{g={c=>1}
p *loop{c=(c.map(&:pred)<<c.size).sort.reverse-[0]
g[c]?(break g.keys<<c): g[c]=1}}

Explanation

• Input is taken as the arguments to a lambda. It expects an Array.
• Previous game states are stored in the Hash g.
• To create a new game state, use Array#map to decrease every element by 1, add the length of the Array as an element, sort it in decreasing order and delete the element 0.
• To check if a game state has been seen before, checking if g has a key for new game state is sufficient.

Answer 4

CJam, 35 34 33 bytes

(Damn, this power cut that I was not the first one to post in CJam)

l~{_p:(_,+{},$W%_`_S\#0<\S+:S;}g`

Input:

[1 1 1 1 1 1 1]

Output:

[1 1 1 1 1 1 1]
[7]
[6 1]
[5 2]
[4 2 1]
[3 3 1]
[3 2 2]
[3 2 1 1]
[4 2 1]

Try it online here

Answer 5

Python 2 - 103

p=input()
m=[]
print p
while p not in m:m+=[p];p=sorted([x-1 for x in p if x>1]+[len(p)])[::-1];print p

Similar to Quincunx' answer, but replaces appends with addition, and removes the last two lines.

Sample output:

[4, 4, 3, 2, 1]
[5, 3, 3, 2, 1]
[5, 4, 2, 2, 1]
[5, 4, 3, 1, 1]
[5, 4, 3, 2]
[4, 4, 3, 2, 1]

Answer 6

GolfScript, 50 46

~.p$[]{[1$]+\.{(.!";"*~}%\,+$.-1%p\.2$?)!}do];

Can almost certainly be golfed further. Try it out here.

Answer 7

Haskell, 99

import Data.List
g l=until(nub>>=(/=))(\l->l++[reverse$sort$length(last l):[x-1|x<-last l,x>1]])[l]

Answer 8

CJam, 40 36 34 bytes

]l~{a+_W=_p:(_,+$W%{},1$1$a#0<}gp;

Test it here. Enter input as a CJam-style array, like [5 3], into the STDIN field. Output format is similar, so square brackets and spaces as delimiters.

Even if I golf this down further (which is definitely possible), there's no way to beat Pyth with this. Maybe it's time to learn J. Explanation coming later.

Answer 9

JavaScript (E6) 113

Worst entry so far :(

F=l=>{
  for(k=[];console.log(l),!k[l];)
    k[l]=l=[...l.map(n=>(p+=n>1,n-1),p=1),l.length].sort((a,b)=>b-a).slice(0,p)
}

Test in FireFox/FireBug console

F([4,4,3,2,1])

Output

[4, 4, 3, 2, 1]
[5, 3, 3, 2, 1]
[5, 4, 2, 2, 1]
[5, 4, 3, 1, 1]
[5, 4, 3, 2]
[4, 4, 3, 2, 1]

Answer 10

Python 2, 148 130 101

l=input()
s=[]
print l
while l not in s:s+=l,;l=sorted([i-1for i in l if 1<i]+[len(l)])[::-1];print l

This simply goes remembers all previous iterations, and checks if the new one is in that list. Then, it prints it out.

Sample run:

Input:

[4,4,3,2,1]

Output:

[4, 4, 3, 2, 1]
[5, 3, 3, 2, 1]
[5, 4, 2, 2, 1]
[5, 4, 3, 1, 1]
[5, 4, 3, 2]
[4, 4, 3, 2, 1]

Edit: I reread the specs to golf, plus applied a lot of golfing.

Answer 11

Python 3: 89 chars

g=lambda l,s=[]:print(l)!=l in s or g(sorted([x-1for x in l if~-x]+[len(l)])[::-1],s+[l])

Much like the Python solutions already posted, but with recursive function calls rather than loops. The list s stores the splits already seen, and short-circuits out the recursion in case of a repeat.

The function print() (this is Python 3) just needs to be somehow called in each loop. The tricky thing is that a lambda only allows a single expression, so we can't do print(l);.... Also, it outputs None, which is hard to work with. I wind up putting print(l) on one side of an inequality; == doesn't work for some reason I don't understand.

An alternative approach of sticking it in a list uses equally many characters.

g=lambda l,s=[]:l in s+[print(l)]or g(sorted([x-1for x in l if~-x]+[len(l)])[::-1],s+[l])

Using print(*l) would format the outputs like 4 2 2 rather than [4,2,2].