gistfile1.txt

// https://leetcode.com/problems/median-of-two-sorted-arrays/description/
package main

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

func p(format string, a ...interface{}) {
	fmt.Printf(format, a...)
}

// check if `small` is a subset of `large`. They're both sorted.
func subset(small []int, large []int) bool {
	l := 0
	s := 0
	for s < len(small) && l < len(large) {
		if small[s] < large[l] {
			return false
		}
		//p("%2d,  %2d\n", small[s], large[l])
		if small[s] == large[l] {
			s++
		}
		l++
	}
	return s == len(small)
}

func check(selected []int) bool {
	bingos := [][]int{
		//horizontal
		{0, 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},
		//vertical
		{0, 6, 12, 18, 24, 30},
		{1, 7, 13, 19, 25, 31},
		{2, 8, 14, 20, 26, 32},
		{3, 9, 15, 21, 27, 33},
		{4, 10, 16, 22, 28, 34},
		{5, 11, 17, 23, 29, 35},
		//diagonal
		{0, 7, 14, 21, 28, 35},
		{5, 10, 15, 20, 25, 30},
	}
	for _, b := range bingos {
		if subset(b, selected) {
			return true
		}
	}
	return false
}

func try(r *rand.Rand) bool {
	selected := r.Perm(36)[:15]
	sort.Ints(selected)
	//return check(selected)
	ret := check(selected)
	if ret {
		//p("Bingo: %v\n", selected)
	}
	return ret
}

func report(succ, total int) {
	p("success/total =%8d/%8d = %.2f%%\n", succ, total, float64(succ*100)/float64(total))
}

func test() {
	tries := 1000 * 1000
	r := rand.New(rand.NewSource(time.Now().UnixNano()))

	success := 0
	for i := 0; i < tries; i++ {
		if i%10000 == 1 {
			report(success, i+1)
		}
		for j := 0; j < 6; j++ {
			if try(r) {
				success += 1
				break
			}
		}
	}
	report(success, tries)
}
func main() {
	test()
}