/* Copyright (C) 2015 by Alexandru Cojocaru */

/* This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <http://www.gnu.org/licenses/>. */

package main

import (
	"fmt"
	"math/rand"
	"time"
)

// use package-local rand source to avoid excessive locking
var rng *rand.Rand

func shuffle(s, e, len int) []int {
	p := rng.Perm(e - s + 1)[:len]
	for i := 0; i < len; i++ {
		p[i] += s
	}
	return p
}

// column-major
func randomCard() [][]int {
	c := make([][]int, 5)
	for i := 0; i < 5; i++ {
		c[i] = shuffle(i*15+1, (i+1)*15, 5)
	}
	c[2][2] = 0
	return c
}

func wins(b [][]int) bool {
	for i := 0; i < 5; i++ {
		if b[i][0] == 0 && b[i][1] == 0 && b[i][2] == 0 && b[i][3] == 0 && b[i][4] == 0 {
			return true
		}
	}

	for j := 0; j < 5; j++ {
		if b[0][j] == 0 && b[1][j] == 0 && b[2][j] == 0 && b[3][j] == 0 && b[4][j] == 0 {
			return true
		}
	}

	if b[0][0] == 0 && b[1][1] == 0 && b[2][2] == 0 && b[3][3] == 0 && b[4][4] == 0 {
		return true
	}

	if b[0][4] == 0 && b[1][3] == 0 && b[2][2] == 0 && b[3][1] == 0 && b[4][0] == 0 {
		return true
	}

	return false
}

func mark(c [][]int, m int) {
	for i := 0; i < 5; i++ {
		for j := 0; j < 5; j++ {
			if c[i][j] == m {
				c[i][j] = 0
				return
			}
		}
	}
}

func average(nc int) float64 {
	games := 1000
	calls := 0
	c := make([][][]int, nc)
	for i := 0; i < games; i++ {
		called := shuffle(1, 75, 75)
		for j := 0; j < nc; j++ {
			c[j] = randomCard()
		}
		w := false
		for !w {
			calls++
			for j := 0; j < nc; j++ {
				mark(c[j], called[0])
				if wins(c[j]) {
					w = true
					break
				}
			}
			called = called[1:]
		}
	}

	return (float64)(calls) / (float64)(games)
}

func main() {
	rng = rand.New(rand.NewSource(time.Now().UnixNano()))
	fmt.Printf("%v\n", average(1))
	fmt.Printf("%v\n", average(500))
}