Output a shuffled deck using random input

Question

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))),

Answer 1

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]

Answer 2

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.

Answer 3

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;
}

Answer 4

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.

Answer 5

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

Answer 6

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(' ');
  }
}

Answer 7

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.