Deal cards for FreeCell: Difference between revisions

Content added Content deleted

Inline

Revision as of 16:55, 19 September 2011

Free Cell is the solitaire card game that Paul Alfille introduced to the PLATO system in 1978. Jim Horne, at Microsoft, changed the name to FreeCell and reimplemented the game for DOS, then Windows. This version introduced 32000 numbered deals. Later versions have 1 million deals, numbered 1 to 1000000. (The Freecell FAQ tells this history.)

As the game became popular, Jim Horne disclosed the algorithm, and other implementations of FreeCell began to reproduce the Microsoft deals. These deals are numbered from 1 to 32000.

The algorithm uses this linear congruential generator from Microsoft C:

$state_{n+1}\equiv 214013\times state_{n}+2531011{\pmod {2^{31}}}$
$rand_{n}=state_{n}\div 2^{16}$
$rand_{n}$ is in range 0 to 32767.
Rosetta Code has another task, linear congruential generator, with code for this RNG in several languages.

The algorithm follows:

Seed the RNG with the number of the deal.
Create an array of 52 cards: Ace of Clubs, Ace of Diamonds, Ace of Hearts, Ace of Spades, 2 of Clubs, 2 of Diamonds, and so on through the ranks: Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King. The array indexes are 0 to 51, with Ace of Clubs at 0, and King of Spades at 51.
Perform a shuffle (MISSING instructions)
Deal all 52 cards, face up, across 8 columns. The first 8 cards go in 8 columns, the next 8 cards go on the first 8 cards, and so on.

 1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52

Deals can be checked against FreeCell solutions to 1000000 games. (Summon a video solution, and it displays the initial deal.)

C

<lang c>#include <stdio.h>

include <stdlib.h>
include <locale.h>

wchar_t s_suits[] = L"♣♦♥♠", s_nums[] = L"A23456789TJQK";

define RMAX32 ((1U << 31) - 1)
define RMAX ((1U << 15) - 1)

static int seed = 1; int rnd(void) { return (seed = (seed * 214013 + 2531011) & RMAX32) >> 16; } void srnd(int x) { seed = x; }

void show(int *c) { int i; for (i = 0; i < 52; c++) { printf(" \033[%dm%lc\033[m%lc", 32 - (1 + *c) % 4 / 2, s_suits[*c % 4], s_nums[*c / 4]); if (!(++i % 8) || i == 52) putchar('\n'); } }

void deal(int s, int *t) { int i, j; srnd(s);

for (i = 0; i < 52; i++) t[i] = 51 - i; for (i = 0; i < 51; i++) { j = 51 - rnd() % (52 - i); s = t[i], t[i] = t[j], t[j] = s; } }

int main(int c, char **v) { int s, card[52]; if (c < 2 || (s = atoi(v[1])) <= 0) s = 11982;

setlocale(LC_ALL, "");

deal(s, card); printf("Hand %d\n", s); show(card);

return 0; }</lang>

J

Paraphrase of C:

<lang j>deck=: ,/ 'KQJT98765432A' ,"0/ 7 u: '♠♥♦♣'

seed=: do bind 'SEED' srnd=: 3 :'SEED=:{.y,11982' srnd rnd=: (2^16) <.@%~ (2^31) srnd@| 2531011 + 214013 * seed

pairs=: i. <@<@~."1@,. <: - ] (| rnd)@- i. NB. indices to swap, for shuffle swaps=: [: > C.&.>/@|.@; NB. implement the specified shuffle deal=: (swaps pairs@#) bind deck

show=: (,"2)@:(_8 ]\ ' '&,.)</lang>

Example use:

<lang j> show deal srnd 1

J♦ 2♦ 9♥ J♣ 5♦ 7♥ 7♣ 5♥
K♦ K♣ 9♠ 5♠ A♦ Q♣ K♥ 3♥
2♠ K♠ 9♦ Q♦ J♠ A♠ A♥ 3♣
4♣ 5♣ T♠ Q♥ 4♥ A♣ 4♦ 7♠
3♠ T♦ 4♠ T♥ 8♥ 2♣ J♥ 7♦
6♦ 8♠ 8♦ Q♠ 6♣ 3♦ 8♣ T♣
6♠ 9♣ 2♥ 6♥</lang>

Ruby

<lang ruby># Deal cards for FreeCell.

http://rosettacode.org/wiki/Deal_cards_for_FreeCell

require 'optparse'

Parse command-line arguments.
games = ARGV converted to Integeter
No arguments? Pick any of first 32000 games.

games = nil OptionParser.new do |o|

 begin
   o.banner = "Usage: #{o.program_name} number..."
   o.parse!
   games = ARGV.map {|s| Integer(s)}
   games.empty? and games = [rand(32000)]
 rescue => e
   $stderr.puts e, o
   abort
 end

end

Define methods for old Ruby versions.
Enumerable#each_slice appeared in Ruby 1.8.7.
Enumerable#flat_map appeared in Ruby 1.9.2.

unless Enumerable.method_defined? :each_slice

 module Enumerable
   def each_slice(count)
     block_given? or return enum_for(:each_slice, count)
     ary = []
     each {|e|
       ary << e
       ary.length == count and (yield ary; ary.clear)}
     ary.empty? or yield ary
     nil
   end
 end

end unless Enumerable.method_defined? :flat_map

 module Enumerable
   def flat_map
     block_given? or return enum_for(:flat_map)
     ary = []
     each {|e|
       y = yield e
       ary.concat(y) rescue ary.push(y)}
     ary
   end
 end

end

Create original deck of 52 cards, not yet shuffled.

orig_deck = %w{A 2 3 4 5 6 7 8 9 T J Q K }.flat_map {|rank| %w{C D H S}.map {|suit| "#{rank}#{suit}"}}

games.each do |seed|

 deck = orig_deck.dup

 # Shuffle deck with random index from linear congruential
 # generator like Microsoft.
 state = seed
 52.downto(2) do |len|
   state = ((214013 * state) + 2531011) & 0x7fff_ffff
   index = (state >> 16) % len
   last = len - 1
   deck[index], deck[last] = deck[last], deck[index]
 end

 deck.reverse!  # Shuffle did reverse deck. Do reverse again.

 # Deal cards.
 puts "Game ##{seed}"
 deck.each_slice(8) {|row| puts " " + row.join(" ")}

end</lang>

$ ruby freecell.rb 11982 
Game #11982
 AH AS 4H AC 2D 6S TS JS
 3D 3H QS QC 8S 7H AD KS
 KD 6H 5S 4D 9H JH 9S 3C
 JC 5D 5C 8C 9D TD KH 7C
 6C 2C TH QH 6D TC 4S 7S
 JD 7D 8H 9C 2H QD 4C 5H
 KC 8D 2S 3S

Tcl

Translation of: C

<lang tcl>proc rnd Template:*r seed {

   upvar 1 ${*r} r
   expr {[set r [expr {($r * 214013 + 2531011) & 0x7fffffff}]] >> 16}

} proc show cards {

   set suits {\u2663 \u2666 \u2665 \u2660}
   set values {A 2 3 4 5 6 7 8 9 T J Q K}
   for {set i 0} {$i < 52} {incr i} {

set c [lindex $cards $i] puts -nonewline [format " \033\[%dm%s\033\[m%s" [expr {32-(1+$c)%4/2}] \ [lindex $suits [expr {$c % 4}]] [lindex $values [expr {$c / 4}]]] if {($i&7)==7 || $i==51} {puts ""}

} proc deal {seed} {

   for {set i 0} {$i < 52} {incr i} {lappend cards [expr {51 - $i}]}
   for {set i 0} {$i < 51} {incr i} {

set j [expr {51 - [rnd]%(52-$i)}] set tmp [lindex $cards $i] lset cards $i [lindex $cards $j] lset cards $j $tmp

   }
   return $cards

}

if {![scan =[lindex $argv 0]= =%d= s] || $s <= 0} {

   set s 11982

} set cards [deal $s] puts "Hand $s" show $cards</lang>