9
\$\begingroup\$

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
\$\endgroup\$

11 Answers 11

4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 1. You can replace v$input()$ with Q. 2. If you store the list in decreasing order, you don't need N at all: W!}QYQ~Y]Q=Q_S+fTmtdQ]lQ;Q \$\endgroup\$ – Dennis Oct 11 '14 at 4:50
  • \$\begingroup\$ @Dennis Thanks, I couldn't figure out how to do that; I knew there was a way to do so. \$\endgroup\$ – Justin Oct 11 '14 at 4:53
  • 1
    \$\begingroup\$ Here's what I did, totally independently: QW!}QY~Y]Q=Q_S+]lQfTmtdQQ. It's exactly the same, character for character, up to commutativity. \$\endgroup\$ – isaacg Oct 11 '14 at 8:34
3
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ That's some CJam! \$\endgroup\$ – Optimizer Oct 11 '14 at 21:42
  • \$\begingroup\$ Come on!, I know you can make it shorter than Pyth one! \$\endgroup\$ – Optimizer Oct 11 '14 at 21:51
  • \$\begingroup\$ If :p worked, I could... \$\endgroup\$ – Dennis Oct 11 '14 at 21:51
  • 4
    \$\begingroup\$ Stop whining! :p \$\endgroup\$ – Optimizer Oct 11 '14 at 21:52
3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ +1 Really neat Ruby golfing here! However, while the sort_by thing is certainly clever, sort.reverse is actually one character shorter ^^ \$\endgroup\$ – daniero Oct 11 '14 at 21:56
  • \$\begingroup\$ Aww, that's too bad. Thanks. \$\endgroup\$ – britishtea Oct 11 '14 at 22:49
2
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ Umm, similar? This is identical; you simply took the golfing steps that were completely obvious. When I came back to mine, I golfed it, and discovered that this is now a duplicate answer of mine (or vice versa, however you want to view it) \$\endgroup\$ – Justin Oct 11 '14 at 4:47
  • \$\begingroup\$ I discovered your answer only after posting mine. I'm ok with considering them duplicates of each other. \$\endgroup\$ – Nathan Merrill Oct 11 '14 at 12:54
1
\$\begingroup\$

GolfScript, 50 46

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

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

\$\endgroup\$
1
\$\begingroup\$

Haskell, 99

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

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.

\$\endgroup\$
  • \$\begingroup\$ Not sure J will help, I can't get my APL below 38 \$\endgroup\$ – TwiNight Oct 16 '14 at 5:16
1
\$\begingroup\$

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]
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You're allowed to just print the lists as lists. \$\endgroup\$ – xnor Oct 11 '14 at 2:49
  • \$\begingroup\$ @xnor Ooh thanks, completely missed that. \$\endgroup\$ – Justin Oct 11 '14 at 2:53
  • \$\begingroup\$ This won't work with [5,3] \$\endgroup\$ – Nathan Merrill Oct 11 '14 at 4:20
  • \$\begingroup\$ This gives the wrong output for [4,2,2]. There's an easy fix though. \$\endgroup\$ – xnor Oct 14 '14 at 7:17
0
\$\begingroup\$

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].

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.