9
\$\begingroup\$

Input/Output:

Input: A uniformly random, infinitely long, string of '0's and '1's, taken from stdin. The string is assumed to be truly random, not pseudo-random. It is uniform in that each character is equally likely to be a '0' or '1'.

Careful! The input is infinitely long, so you can't store it all in memory using a function like raw_input() in python. If I'm not mistaken, golfscript will fail with infinite input, since it pushes the entire input onto the stack prior to running.

Output: A uniformly random shuffled standard deck, without jokers. It is uniform in that all orderings are equally likely.

Each card in the output is it's rank, A, 2-9, T, J, Q or K concatenated with it's suit, c, d, h or s. For example, the 10 of spades is Ts

The cards of the deck should be separated by spaces.

You may not use built-in random libraries or functions because they are not truly random, only pseudo-random.

Example input

You may use the following python script to pipe input into your program:

import sys, random try: while True: sys.stdout.write(str(random.randint(0,1))) except IOError: pass

If you save the script as rand.py, test your program with python rand.py | your_program

In python 3 it runs as expected, but in python 2.7 I get an error message after my program's output, but only after everything's done, so just ignore the error message.

Example output:

Here's how the deck should be printed if it happened to be shuffled into a sorted order:

Ac 2c 3c 4c 5c 6c 7c 8c 9c Tc Jc Qc Kc Ad 2d 3d 4d 5d 6d 7d 8d 9d Td Jd Qd Kd Ah 2h 3h 4h 5h 6h 7h 8h 9h Th Jh Qh Kh As 2s 3s 4s 5s 6s 7s 8s 9s Ts Js Qs Ks

Scoring:

This is a code golf. Shortest code wins.

Example program:

Here is a python 2.7 solution, not golfed.

import sys def next(): return int(sys.stdin.read(1))==1 def roll(n): if n==1: return 0 if n%2==0: r=roll(n/2) if next(): r+=n/2 return r else: r=n while(r==n): r=roll(n+1) return r deck = [rank+suit for suit in 'cdhs' for rank in 'A23456789TJQK'] while len(deck)>0: print deck.pop(roll(len(deck))),
Improve this question
\$\endgroup\$
3
  • 3
    \$\begingroup\$ "If I'm not mistaken, golfscript will fail with infinite input, since it pushes the entire input onto the stack prior to running." Well, that's one way to take it out of the running. \$\endgroup\$ Commented Nov 1, 2012 at 12:50
  • \$\begingroup\$ I'm a little bit confused, forgive me. What does the input have to do with the actual deck shuffling? Perhaps I just need a little clarification. \$\endgroup\$ Commented Nov 1, 2012 at 17:58
  • 1
    \$\begingroup\$ You can't use pseudo-random functions in your code, so you need to use the input (which we're assuming is truly random) to generate randomness. For example, in python you can use (sys.stdin.read(1)=='1') to get a random boolean, but you can't use (random.randint(0,1)==1), because it's only pseudo-random. \$\endgroup\$ Commented Nov 1, 2012 at 20:11

7 Answers 7

Reset to default
7
\$\begingroup\$

Ruby, 89 87 characters

l=*0..51;l.map{l-=[i=l[gets(6).to_i 2]||redo];$><<'A23456789TJQK'[i/4]+'cdhs'[i%4]+' '}

Edit: previous version

l=*0..51;(l-=[i=l[gets(6).to_i 2]];i&&$><<'A23456789TJQK'[i/4]+'cdhs'[i%4]+' ')while l[0]
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Python 122

import sys D=[R+S for S in'cdhs'for R in'A23456789TJQK'] while(D): x=int(sys.stdin.read(6),2) if x<len(D):print D.pop(x)

Explanation:

Unused cards are stored in D. This simply gets the next valid random index from the input stream and pops that element from D.

Unless I am missing something, there shouldn't be a bias. The script will throw out any invalid indices > len(D), but this doesn't result in a bias for lower numbers because each successive pop will reduce the index of each element past than i.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ So you discard most of the (infinite) random input? I.e. you stop shuffling once you have no "unused" cards? \$\endgroup\$ Commented Nov 9, 2012 at 15:34
3
\$\begingroup\$

Perl, 80 chars

here is another implementation that does not suffer from the bias and is two characters shorter:

$/=1x9;$_=A23456789TJQK;s/./$&s$&c$&d$&h/g;%h=map{<>.$_,"$_ "}/../g;say values%h

old implementation (82 chars):

$/=1x9;$_=A23456789TJQK;s/./$&s$&c$&d$&h/g;say map/..$/&&$&.$",sort map<>.$_,/../g

old implementation description:

# set input record separator (how internal readline() delimits lines) to "11111111" $/ = 1x9; # constructs a string representation of all 52 cards: "AsAc(...)KdKh" $_ = A23456789TJQK; s/./$&s$&c$&d$&h/g; # for each pair of characters (each card) in the string $_ foreach $card (/../g) { # read from STDIN until $/ is found (this may NEVER occur!), which # results in a random string of 1s and 0s $weight = <>; # append the card identifier onto the random string $card = $weight . $card; # add this new card identifier to a new list push @cards, $card; } # sort the cards with their random string prefix sort @cards; # for each card in the "randomly sorted" list foreach $card (@cards) { # capture the final two characters from the card (the rank and suit), # and append a space onto them $card =~ /..$/; $card = $card . $"; print $card; }
Improve this answer
\$\endgroup\$
8
  • \$\begingroup\$ Just curious: can anybody show that this approach produces each deck of cards with same probability? \$\endgroup\$ Commented Nov 2, 2012 at 7:25
  • 2
    \$\begingroup\$ If I'm reading this right (IANAPH), it assigns random 'weights' to each card, and then sorts by weight. When two cards are assigned the same weight, they'll be left in order by sort, resulting in a bias towards alphabetic ordering. \$\endgroup\$ Commented Nov 2, 2012 at 8:14
  • \$\begingroup\$ you are right, @boothby. the sort does leave this solution with a bias in the case that multiple cards have the same "weight". it also can't be guaranteed that this solution will ever produce a result. I'll add a description of how it works so that someone smarter than me can analyze it \$\endgroup\$ Commented Nov 2, 2012 at 15:18
  • \$\begingroup\$ It's perfectly fine if some inputs cause the program to never terminate, as long as the probability that the program terminates approaches 1 as time approaches infinity. The example program never terminates on an input of all '1's. I'm pretty sure it's actually impossible to get uniform randomness while knowing your program terminates after a certain number of bits read. \$\endgroup\$ Commented Nov 2, 2012 at 16:48
  • 1
    \$\begingroup\$ How can you pick a uniformly random number between 1 and 3 with a finite number of bits? You'll need to do that near the end of the Fisher-Yates shuffle, and factorial(52) is divisible by 3 so it shares the same problem. \$\endgroup\$ Commented Nov 3, 2012 at 13:55
3
\$\begingroup\$

C, 197 178 161 chars

EDIT: Using a new random function, which is much shorter - reads a 4-digit integer s and uses s%64. Each 6-digit decimal number made of 0 and 1 only, taken %64 results in a unique result, so the randomness is good.
This approach consumes much more random bits, but is significantly shorter.

B[52],t,s,i=104; r(){scanf("%6d",&s);s%=64;s>i&&r();} main(){ for(;i--;)B[i%52]=i<52 ?r(),t=B[s],B[s]=B[i],printf("%c%c\n","23456789ATJQK"[t/4],"cdhs"[t%4]),t :i-52; }

The basic logic is simple - initialize an array of 52 ints with 0..51, shuffle (randomally replace element x with another from the range 0..x), print formatted (n/4=rank, n%4=suit).
One loop, that runs 104 times, does initialization (first 52 runs), shuffling and printing (last 52 runs).
A random number is generated by pulling n random bits, until 1<<n is at least the desired maximum. If the result is more than the maximum - retry.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ This complicated s>7?"ATJQK"[s-8]:s+50 is longer than the simple "A23456789TJQK"[s]. Second you can use t/4 and t%4 instead of t%13 and t/13. \$\endgroup\$ Commented Nov 2, 2012 at 14:41
  • \$\begingroup\$ Don't need to still put t back into the array when outputting \$\endgroup\$ Commented May 27, 2018 at 17:41
3
\$\begingroup\$

unix shell ~ 350

This is not short or pretty, nor is it efficient, however I was wondering how hard it would be to do this with standard unix shell utilities.

This answer chops up the infinite binary string into 6 bit lengths and only chooses those that are in the correct range (1-52), here the infinite binary string is simulated by urandom and xxd:

</dev/urandom xxd -b | cut -d' ' -f2-7 | tr -d ' \n'

The chopping and selection is done with fold, sed and bc:

random_source | {echo ibase=2; cat | fold -w6 | sed -r 's/^/if(/; s/([^\(]+)$/\1 <= 110100 \&\& \1 > 0) \1/'}

This produces lines such as:

if(101010 <= 110100 && 101010 > 0) 101010

Which can be directed into bc.

From this stream of numbers, the sequence of the deck is chosen like this (I'm using zsh, but most modern shells should be adaptable to this):

deck=({1..52}) seq_of_numbers | while read n; do if [[ -n $deck[n] ]]; then echo $n; deck[n]="" [[ $deck[*] =~ "^ *$" ]] && break fi done

The randomized number sequence now needs to be changed into card names. The card name sequence is easily generated with GNU parallel:

parallel echo '{2}{1}' ::: c d s h ::: A {2..9} T J Q K

Combining the output from the last two commands with paste and sorting on the numbers:

paste random_deck card_names | sort -n | cut -f2 | tr '\n' ' '

The whole thing as one monstrous one-liner (only tested in zsh):

paste \ <(deck=({1..52}); \ </dev/urandom xxd -b | cut -d' ' -f2-7 | tr -d ' \n' | {echo ibase=2; fold -w6 | sed -r 's/^/if(/; s/([^\(]+)$/\1 <= 110100 \&\& \1 > 0) \1/'} | bc | while read n; do if [[ -n $deck[n] ]]; then echo $n; deck[n]="" [[ -z ${${deck[*]}%% *} ]] && break fi done) \ <(parallel echo '{2}{1}' ::: c d s h ::: A {2..9} T J Q K) | sort -n | cut -f2 | tr '\n' ' '

Edit - added bash version

Here is a version that works in bash. I removed the in-shell { } and array indexes are zero based. Array emptiness is checked with parameter expansion, slightly more efficient and also adopted in the example above. 

paste \ <(deck=($(seq 52)); \ </dev/urandom xxd -b | cut -d' ' -f2-7 | tr -d ' \n' | (echo ibase=2; fold -w6 | sed -r 's/^/if(/; s/([^\(]+)$/\1 <= 110100 \&\& \1 > 0) \1/') | bc | while read n; do if [[ -n ${deck[n-1]} ]]; then echo $n deck[n-1]="" [[ -z ${deck[*]%% *} ]] && break fi done \ ) \ <(parallel echo '{2}{1}' ::: c d s h ::: A {2..9} T J Q K) | sort -n | cut -f2 | tr '\n' ' '; echo
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

K&R c -- 275

  • v3 Index into the string literals directly
  • v2 Suggestion from luser droog in the comments to use strings and replaced remaining char literals with int literals

Golfed:

#define F for(i=52;--i;) #define P putchar M=1<<9-1,i,j,k,t,v,s,a[52];r(){t=0,j=9;while(--j)t=t<<1|(getchar()==49); return t;}main(){F a[i]=i;F{k=i+1;do{j=r();}while(j>M/k*k-1);j%=i;t=a[i]; a[i]=a[j];a[j]=t;}F{s=a[i]&3;v=a[i]>>2;P(v>7?"TJQKA"[v-8]:v+50); P("cdhs"[s]);P(32);}}

Pretty much brute force here. I just read nine bits from the input to form a minimal RNG output, and make the usual redraw-if-the-unused-values-at-the-end modulus reduction to get uniform output to power a selection shuffle.

This un-golfed version differs in that it takes the input from /dev/urandom rather than from the described input format.

#include <stdio.h> M=1<<8-1, /* RANDMAX */ i, j, k, /* counters */ t, /* temporary for swapping, and accumulating */ a[52]; /* the deck */ r(){ /* limited, low precision rand() that depends on a random stream of '0' and '1' from stdin */ t=0,j=9; while(--j)t=t<<1|(getchar()&1); return t; } main(){ for(i=52;--i;)a[i]=i; /* initialize the deck */ for(i=52;--i;){ /* printf("shuffling %d...\n",i); */ k=i+1; do { /* draw *unifromly* with a a-unifrom generator */ j=r(); /* printf("\t j=0x%o\n",j); */ }while(j>M/k*k-1); /* discard values we can't mod into evently */ j%=i; t=a[i];a[i]=a[j];a[j]=t; /* swap */ } for(i=52;--i;){ /* output the deck */ j=a[i]&3; k=a[i]>>2; putchar(k>7?"TJQKA"[k-8]:k+'2'); putchar("cdhs"[j]); putchar(' '); } }
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ +1 I have much to learn. BTW, why not "TJQKA" and "cdhs"? \$\endgroup\$ Commented Nov 2, 2012 at 4:46
  • \$\begingroup\$ Oh. Right. ints. I get it. Might still be worth it to save all the punctuation. Might even factor the char out of getchar and putchar with a crazy pasty macro... \$\endgroup\$ Commented Nov 2, 2012 at 4:50
  • 1
    \$\begingroup\$ Macro substitutions need to gain a lot because they have to start with #define N and end with a newline that counts as a character and that's 11, plus the bit you are replacing. There are certainly a few more characters in replacing some or all of the character literals with int literals, but it's late here...maybe I'll do it another time. \$\endgroup\$ Commented Nov 2, 2012 at 5:10
  • \$\begingroup\$ @luserdroog Clearer headed now. Of course strings are better--though you have to specify the type--because characters are just short integers. Plus I can combine them and the ASCII substitutions get a bunch of strokes in one go. \$\endgroup\$ Commented Nov 2, 2012 at 14:28
0
\$\begingroup\$

PHP, 158 chars

Newlines have been added to stop the code block gaining scrollbars, they can safely be removed.

for($i=52,$x='shdcKQJT98765432A';$i--;$c[]=$x[4+$i%13].$x[$i/13]); while(ord($i=fgetc(STDIN)))$c[$i]^=$c[$a]^=$c[$i]^=$c[$a=2+($a+++$i)%50]; die(join(' ',$c));

Before I get told to add a <?php, let it be known you can invoke PHP without this tag quite easily, using: cat golf.php | php -a

De-golfed and commented:

// Abuse of the for construct to save a bit of space, and to make things more obscure looking in general. for ( // Card suit and number are reversed because we're using a decrementor to count // down from 52, instead of up to 52 $i = 52, $x = 'shdcKQJT98765432A'; // Condition AND per-loop decrement $i--; // Add a new element to the array comprising of $i mod 13 + 4 (to skip suit ids) // followed by simply $i divided by 13 to pick a suit id. $c[] = $x[4 + $i % 13] . $x[$i / 13] ); while( // Assignment inside the condition, a single character from input. ord($i = fgetc(STDIN)) ) // In-place swap. Shorter than using a single letter temporary variable. // This is the pseudo-random shuffle. $c[$i] ^= $c[$a] ^= $c[$i] ^= $c[ // We use the input (0 or 1) to identify one of two swap locations at the // start of the array. The input is also added to an accumulator (to make // the increments "random") that represents a swap destination. $a = 2 + ($a++ + $i) % 50 ]; // Dramatic way of doing "echo" in the same space. die( join(' ', $c) );

There are two expected errors, that do not affect the output of the program.

The first is because $a is not initialised, but the NULL is converted to 0 and the program continues.

The second is because the character stream seems to get a newline from somewhere, even if it's not supplied (good ol' PHP), and that is an undefined index in the array. It's the last character of input, and does not affect output.

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.