Kings simulator

kings.go

// Copyright © 2012 Josh Holland <jrh@joshh.co.uk>

// Kings is a program to play the card game of Kings.
package main

import (
	"flag"
	"fmt"
	"io"
	"io/ioutil"
	"math/rand"
	"os"
	"runtime"
	"strconv"
	"time"
)

const (
	NumSuits = 4
	NumRanks = 13
	NumCards = NumSuits * NumRanks
)

func init() { rand.Seed(time.Now().Unix()) }

type Card struct {
	Rank
	Suit
}

func (c Card) String() string {
	return fmt.Sprintf("%v of %v", c.Rank, c.Suit)
}

// Rank represents the face value of a card (e.g. Ace, 5, Jack).
type Rank uint8

func (r Rank) String() string {
	switch r {
	case Ace:
		return "Ace"
	case Jack:
		return "Jack"
	case Queen:
		return "Queen"
	case King:
		return "King"
	}
	return fmt.Sprint(uint8(r))
}

// These constants are for referring to named cards symbolically
// instead of by numerical values.
const (
	Ace   Rank = 1
	Jack  Rank = 11
	Queen Rank = 12
	King  Rank = 13
)

// Suit represents the suit of a card.
type Suit uint8

func (s Suit) String() string {
	switch s {
	case Clubs:
		return "Clubs"
	case Diamonds:
		return "Diamonds"
	case Spades:
		return "Spades"
	case Hearts:
		return "Hearts"
	}
	panic("unreachable")
}

const (
	Clubs Suit = iota
	Diamonds
	Spades
	Hearts
)

// Deck represents a deck of cards, as a stack.
type Deck struct {
	data []Card
}

func (d *Deck) String() string {
	if d.Len() != 0 {
		return d.Peek().String()
	}
	return "(empty)"
}

// Pop removes the top card from the deck and returns it. Trying to Pop
// a card from an empty deck will panic.
func (d *Deck) Pop() Card {
	c := d.data[len(d.data)-1]
	d.data = d.data[:len(d.data)-1]
	return c
}

// Push puts the given card on top of the deck.
func (d *Deck) Push(c Card) {
	d.data = append(d.data, c)
}

// Peek returns the top card (i.e. the one that would be returned by Pop)
// but without removing it. The result of Peeking an empty deck is a panic.
func (d *Deck) Peek() Card {
	return d.data[len(d.data)-1]
}

// Len returns the length of the stack.
func (d *Deck) Len() int {
	return len(d.data)
}

// NewDeck returns a newly created randomly ordered 52-card deck
// of cards.
func NewDeck() *Deck {
	d := make([]Card, NumCards)

	// Use the in-place variant of the Fisher-Yates shuffle
	// to initialise the slice.
	// http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
	d[0] = Card{Ace, Clubs}
	for i := 1; i < NumCards; i++ {
		j := rand.Intn(i + 1)
		d[i] = d[j]
		r := Rank(i%NumRanks + 1)
		s := Suit(i / NumRanks)
		d[j] = Card{r, s}
	}

	return &Deck{d}
}

// Game represents a game of Kings.
type Game struct {
	// The main piles which the cards are played onto.
	Piles [NumSuits]*Deck
	// The location for putting eliminated cards.
	Discard *Deck
	// The remaining cards yet to be dealt.
	Stock *Deck
	// Where to log informational messages to.
	Log io.Writer
}

func NewGame(log io.Writer) *Game {
	p := [NumSuits]*Deck{}
	for i := range p {
		p[i] = &Deck{make([]Card, 0, NumRanks)}
	}
	return &Game{
		Piles:   p,
		Discard: new(Deck),
		Stock:   NewDeck(),
		Log:     log,
	}
}

// Run plays a game of Kings, returning whether the game is "out" or not.
func (g *Game) Run() bool {
	fmt.Fprintln(g.Log, "Starting a new game of Kings. Parameters:")
	fmt.Fprintln(g.Log, "Suits:", NumSuits)
	fmt.Fprintln(g.Log, "Ranks:", NumRanks)

	for g.Stock.Len() != 0 {
		g.deal()
		g.discard()
		if g.moveKings() {
			g.discard()
		}
	}

	// If we have discarded all but NumSuits cards, the game has come out.
	if g.Discard.Len() == NumCards-NumSuits {
		return true
	}
	return false
}

// String returns a human-readable representation of a game in terms of the
// cards currently on top of the piles.
func (g *Game) String() string {
	return fmt.Sprint("Top cards are ", g.Piles)
}

// deal deals cards from the stock onto the playing piles.
func (g *Game) deal() {
	fmt.Fprintln(g.Log)
	fmt.Fprintln(g.Log, "Dealing a new round.")
	for _, pile := range g.Piles {
		pile.Push(g.Stock.Pop())
	}
	fmt.Fprintln(g.Log, g)
	fmt.Fprintln(g.Log, g.Stock.Len(), "cards left")
	fmt.Fprintln(g.Log)
}

// discard recursively clears out-ranked cards from the in-play piles.
func (g *Game) discard() {
	for g.canDiscard() {
		g.discardOne()
		fmt.Fprintln(g.Log, g)
	}
	fmt.Fprintln(g.Log)
}

// canDiscard is a predicate to show whether there are cards available to
// be discarded.
func (g *Game) canDiscard() bool {
	fmt.Fprintln(g.Log, "Checking for cards to discard...")

	// Keep track of whether we have seen a suit on top.
	seen := make(map[Suit]bool)

	for _, pile := range g.Piles {
		// Skip empty piles
		if pile.Len() == 0 {
			continue
		}

		suit := pile.Peek().Suit

		if _, ok := seen[suit]; ok {
			fmt.Fprintln(g.Log, "Two", suit, "found")
			return true
		}

		seen[suit] = true
	}

	fmt.Fprintln(g.Log, "No discards available")
	return false
}

// discardOne discards a single card if a discard is possible, and does
// nothing otherwise.
func (g *Game) discardOne() {
	// suits maps Suit types back to the index of the pile whose top card
	// is of that suit.
	suits := make(map[Suit]int)

	for i := range g.Piles {
		// We can't do anything with an empty pile.
		if g.Piles[i].Len() == 0 {
			continue
		}

		suit := g.Piles[i].Peek().Suit
		if j, ok := suits[suit]; ok {
			var c Card
			rankI := g.Piles[i].Peek().Rank
			rankJ := g.Piles[j].Peek().Rank
			if rankI < rankJ {
				c = g.Piles[i].Pop()
			} else {
				c = g.Piles[j].Pop()
			}
			g.Discard.Push(c)
			fmt.Fprintln(g.Log, "Discarded", c)
			return
		}
		suits[suit] = i
	}
}

// moveKings moves kings to empty spaces, if any are free. It does this
// in a fairly simplistic manner, first checking for empty spaces from
// left to right, then placing the leftmost king in it. The return value
// is whether a move was possible.
func (g *Game) moveKings() bool {
	fmt.Fprintln(g.Log, "Trying to move kings...")

	kings := make(chan int)
	spaces := make(chan int)

	go func(ch chan<- int) {
		ch <- g.findKings()
	}(kings)

	go func(ch chan<- int) {
		ch <- g.findSpaces()
	}(spaces)

	kingIndex, spaceIndex := <-kings, <-spaces

	if kingIndex != -1 && spaceIndex != -1 {
		c := g.Piles[kingIndex].Pop()
		fmt.Fprintln(g.Log, "Moving", c, "to pile", spaceIndex+1)
		g.Piles[spaceIndex].Push(c)
		fmt.Fprintln(g.Log, g)
		fmt.Fprintln(g.Log)
		return true
	}

	fmt.Fprintln(g.Log, "No possible moves found")
	fmt.Fprintln(g.Log)
	return false
}

// findKings looks for a top-ranked card along the piles.
// It returns the index of the pile containing it if found
// or -1 on failure.
func (g *Game) findKings() int {
	for i := range g.Piles {
		if g.Piles[i].Len() == 0 {
			continue
		}
		if g.Piles[i].Peek().Rank == NumRanks {
			return i
		}
	}
	return -1
}

// findSpaces looks for empty piles. It returns the index of an
// empty pile or -1 if none are empty
func (g *Game) findSpaces() int {
	for i := range g.Piles {
		if g.Piles[i].Len() == 0 {
			return i
		}
	}
	return -1
}

var (
	nThreads = flag.Int("threads", 1, "Number of threads to use")
)

func main() {
	runtime.GOMAXPROCS(runtime.NumCPU())
	flag.Parse()

	var ret int
	switch len(flag.Args()) {
	case 0:
		ret = runOne()
	case 1:
		n, err := strconv.Atoi(flag.Arg(0))
		if err != nil {
			fmt.Println("Argument must be an integer, not", flag.Arg(0))
			ret = 127
			break
		}
		ret = runMany(n, *nThreads)
	default:
		fmt.Println("Run with 0 or 1 arguments only.")
		ret = 127
	}
	os.Exit(ret)
}

func runOne() int {
	g := NewGame(os.Stdout)
	if g.Run() {
		fmt.Println("Success!")
		return 0
	}

	fmt.Println("Failure :(")
	return 1
}

func worker(in chan *Game, res chan bool) {
	for g := range in {
		res <- g.Run()
	}
}

func runMany(n, nThreads int) int {
	numWin := 0
	in := make(chan *Game, n)
	out := make(chan bool, n)

	for i := 0; i < nThreads; i++ {
		go worker(in, out)
	}

	for i := 0; i < n; i++ {
		in <- NewGame(ioutil.Discard)
	}
	close(in)

	for i := 0; i < n; i++ {
		if <-out {
			numWin++
		}
	}

	fmt.Println()
	percent := float64(numWin) / float64(n) * 100.0
	fmt.Printf("%v wins, %v losses (%.2f%%)\n", numWin, n-numWin, percent)
	return 0
}