tic_tac_toe.go

package main

import (
	"fmt"
	"math"
	"strings"
)

func main() {
	g := Game{
		X, O, O,
		O, X, O,
		O, X, X,
	}

	wins := WinHashes()

	fmt.Println(g)
	if wins[g.Hash(X)] {
		fmt.Println("X Wins!")
	}
	if wins[g.Hash(O)] {
		fmt.Println("O Wins!")
	}
}

// State is the state of a specific place on the game board
type State rune

const (
	E State = '_'
	X State = 'X'
	O State = 'O'
)

// Game represents a tic-tac-toe 3x3 game state.
// The coordinate system places x=0,y=0 at the top-left corner.
type Game []State

// New returns an empty game instance
func New() Game {
	return make(Game, 9)
}

// Reset the game state.
func (g Game) Reset() {
	for i := 0; i < len(g); i++ {
		g[i] = E
	}
}

// State returns the State at the x,y coordinate.
func (g Game) State(x, y int) State {
	return g[(y*3)+x]
}

// Set the state at the specified coordinate.
func (g Game) Set(x, y int, s State) {
	g[(y*3)+x] = s
}

// Hash returns a hash of the game state for a specific state.
// The return value is guaranteed to be collision free.
func (g Game) Hash(s State) uint16 {
	var h uint16
	for i := 0; i < len(g); i++ {
		if g[i] == s {
			h |= 1 << i
		}
	}
	return h
}

// RestoreHash sets the game state from a hash returned from the Hash method.
func (g Game) RestoreHash(hash uint16, s State) {
	for i := 0; i < len(g); i++ {
		if hash&(1<<i) != 0 {
			g[i] = s
		} else {
			g[i] = E
		}
	}
}

// Won returns true if the provided s is in a winning configuration.
func (g Game) Won(s State) bool {
	switch {
	case g[0] == s && g[1] == s && g[2] == s: // top row
	case g[3] == s && g[4] == s && g[5] == s: // middle row
	case g[6] == s && g[7] == s && g[8] == s: // bottom row
	case g[0] == s && g[3] == s && g[6] == s: // left column
	case g[1] == s && g[4] == s && g[7] == s: // middle column
	case g[2] == s && g[5] == s && g[8] == s: // right column
	case g[0] == s && g[4] == s && g[8] == s: // top-left to bottom-right
	case g[6] == s && g[4] == s && g[2] == s: // bottom-left to top-right
	default:
		return false
	}
	return true
}

// String returns a string representation of the game state
func (g Game) String() string {
	var b strings.Builder
	for y := 0; y < 3; y++ {
		for x := 0; x < 3; x++ {
			if x > 0 {
				b.WriteRune(' ')
			}
			b.WriteRune(rune(g.State(x, y)))
		}
		b.WriteRune('\n')
	}
	return b.String()
}

// WinHashes returns a map of all possible win configuration hashes
func WinHashes() map[uint16]bool {
	hashes := map[uint16]bool{}
	g := New()
	for hash := uint16(0); hash < math.MaxUint16; hash++ {
		g.RestoreHash(hash, X)
		if g.Won(X) {
			hashes[hash] = true
		}
	}
	return hashes
}