tictactoe: initial import

[?]

Dec 22, 2020, 3:02 PM

G5KXCVILVVZVQAAVLZQJ2OKJ6LHNICSSKLDNCA3LXVUAMPWJDYRQC

Dependencies

[2] AUM6AXH7 It is enough to check only half of the string because of symmetry
[3] 2P4Y7M5R palindrome: use slices in the concurrent version too. The single thread version is so fast now, that using channels makes this one slower
[4] O64GEJAP palindrome: do not report one char long palindromes
[5] L5UJYVXW palindrome: Use string slice instead of concatenating, this makes the code WAY faster
[6] MCHVA5DY Palindrome initial import
[7] VUXCDW3L palindrome: move to palindrome package
[8] ZQFONDI4 Add simple version

Change contents

file addition: tictactoe (dxwrx-rx-r)

[4.11]
file addition: tictactoe.go (-xw-x--x--)

[0.12]

package tictactoe

import (
"fmt"
"os"
)

const debug = true

// WinSize sets how many we need next to each other
const WinSize = 3

// Runes for record types
const (
Empty rune = '_'
Pl1 rune = 'x'
Pl2 rune = 'o'
)

func debugPrinter(format string, a ...interface{}) {
if debug {
fmt.Fprintf(os.Stderr, format+"\n", a...)
}
}
file addition: minimax_test.go (-xw-x--x--)

[0.12]

package tictactoe

import (
"math"
"testing"

"github.com/stretchr/testify/assert"
)

func TestMinimax(t *testing.T) {
var testCases = []struct {
scores []int
expected int
}{
{[]int{3, 5}, 5},
{[]int{3, 5, 2, 9}, 3},
{[]int{3, 5, 2, 9, 12, 5, 23, 23}, 12},
{[]int{3, 5, 2, 9, 1, 2, 3}, 3},
}
for _, tc := range testCases {
height := math.Log2(float64(len(tc.scores)))
t.Run("Minimax", func(t *testing.T) {
//debugPrinter("len(scores): %d, height: %v int(height): %d", len(tc.scores), height, int(height))
assert.Equal(t, tc.expected, minimax(0, 0, true, tc.scores, int(height)))
})
}
}
file addition: minimax.go (-xw-x--x--)

[0.12]

package tictactoe

// minimax is for retrieving the optimal value for maximizer
// depth is the current depth in the game tree
// nodeIndex is the current index of node in scores
// scores stores the Game Tree
// isMax is true if the current move is a maximizer
// height is the max height of the Game Tree
func minimax(depth, nodeIndex int, isMax bool, scores []int, height int) int {
// terminate if end of the tree reached
if depth == height {
return scores[nodeIndex]
}
if isMax {
left := minimax(depth+1, nodeIndex*2, false, scores, height)
right := minimax(depth+1, nodeIndex*2+1, false, scores, height)
return max(left, right)
} else {
left := minimax(depth+1, nodeIndex*2, true, scores, height)
right := minimax(depth+1, nodeIndex*2+1, true, scores, height)
return min(left, right)
}
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

func min(a, b int) int {
if a < b {
return a
}
return b
}
file addition: go.mod (-xw-x--x--)

[0.12]

module tictactoe

go 1.15

require github.com/stretchr/testify v1.6.1
file addition: evaluate_test.go (-xw-x--x--)

[0.12]

package tictactoe

import (
"testing"

"github.com/stretchr/testify/assert"
)

func TestEvaluate(t *testing.T) {
var testCases = []struct {
description string
board [][]rune
expected int
}{
{"Nothing", [][]rune{{Pl1, Pl1, Pl2}, {Empty, Empty, Empty}, {Empty, Empty, Empty}}, 0},
{"Pl1 row", [][]rune{{Pl1, Pl1, Pl1}, {Empty, Empty, Empty}, {Empty, Empty, Empty}}, 10},
{"Pl2 col", [][]rune{{Pl1, Pl1, Pl1}, {Pl2, Empty, Empty}, {Pl2, Empty, Empty}}, -10},
{"Pl1 diag", [][]rune{{Pl2, Pl1, Pl1}, {Empty, Pl1, Empty}, {Pl1, Empty, Empty}}, 10},
}
for _, tc := range testCases {
t.Run("Evaluate"+tc.description, func(t *testing.T) {
assert.Equal(t, tc.expected, evaluate(tc.board))
})
}
}
file addition: evaluate.go (-xw-x--x--)

[0.12]

package tictactoe

func evaluate(board [][]rune) int {
for row := range board {
for col := range board[row] {
if checkRow(board, row, col, WinSize, Pl1) == WinSize {
return +10
} else if checkRow(board, row, col, WinSize, Pl2) == WinSize {
return -10
}
if checkCol(board, row, col, WinSize, Pl1) == WinSize {
return +10
} else if checkCol(board, row, col, WinSize, Pl2) == WinSize {
return -10
}
if checkDiag(board, row, col, WinSize, Pl1) == WinSize {
return +10
} else if checkDiag(board, row, col, WinSize, Pl2) == WinSize {
return -10
}
}
}
return 0
}

func checkRow(board [][]rune, row, col, winsize int, player rune) (goodness int) {
for i := 0; i < winsize; i++ {
if row+i < len(board[col]) {
if board[row+i][col] == player {
goodness++
} else {
return goodness
}
}
}
return goodness
}

func checkCol(board [][]rune, row, col, winsize int, player rune) (goodness int) {
for j := 0; j < winsize; j++ {
if col+j < len(board[row]) {
if board[row][col+j] == player {
goodness++
} else {
return goodness
}
}
}
return goodness
}

func checkDiag(board [][]rune, row, col, winsize int, player rune) (goodness int) {
for k := 0; k < winsize; k++ {
if row+k < len(board[col]) && col+k < len(board[row]) {
if board[row+k][col+k] == player {
goodness++
} else {
return goodness
}
}
}
return goodness
}
edit in snippets/palindrome/palindrome.go at line 6

[4.456]

[4.72]

import (
"sync"
)
replacement in snippets/palindrome/palindrome.go at line 40

[3.20]→[4.549:560](∅→∅),[4.549]→[4.549:560](∅→∅)

jobs := 0

[3.20]

[4.560]

var wg sync.WaitGroup
replacement in snippets/palindrome/palindrome.go at line 42

[4.590]→[2.0:37](∅→∅),[2.37]→[4.615:628](∅→∅),[4.615]→[4.615:628](∅→∅),[4.628]→[3.21:54](∅→∅),[3.54]→[4.662:676](∅→∅),[4.662]→[4.662:676](∅→∅)

for k := 0; k < len(str)/2+1; k++ {
if k > 0 {
go palWorker(str, k, results)
jobs++
}

[4.590]

[4.676]

for k := 1; k < len(str)/2+1; k++ {
wg.Add(1)
go func(char string, num int) {
defer wg.Done()
results <- palWorker(char, num)
}(str, k)
replacement in snippets/palindrome/palindrome.go at line 49

[4.679]→[4.679:866](∅→∅)

for {
select {
case candidate := <-results:
jobs--
if len(candidate) > len(longest) {
longest = candidate
}
if jobs == 0 {
close(results)
return longest
}

[4.679]

[4.866]

go func() {
wg.Wait()
close(results)
}()
for candidate := range results {
if len(candidate) > len(longest) {
longest = candidate
edit in snippets/palindrome/palindrome.go at line 58

[4.873]

[4.873]

return longest
replacement in snippets/palindrome/palindrome.go at line 61

[4.876]→[3.55:113](∅→∅)

func palWorker(str string, k int, result chan<- string) {

[4.876]

[3.113]

func palWorker(str string, k int) string {
replacement in snippets/palindrome/palindrome.go at line 70

[4.126]→[3.212:231](∅→∅)

result <- longest

[4.126]

[4.1289]

return longest