Google Code Jam Round 1A * Problem C. Proper Shuffle

C.go

/*
 *  Google Code Jam Round 1A
 *  Problem C. Proper Shuffle
 *  execute with: go run C.go
 */
package main

import (
	"bufio"
	"fmt"
	"math/rand"
	"os"
	"runtime"
	"strconv"
	"strings"
	"sync"
	"time"
)

const (
	IN  = "C-small-practice.in"
	OUT = "C-small-practice.out"
)

var (
	// Number of test cases.
	T int
	// I/O
	I *os.File
	O *os.File
	S *bufio.Scanner
	W *bufio.Writer
	// Perm list.
	P []*Perm
	// MC Sim
	M *MC
	// Wait group.
	WG sync.WaitGroup
)

type Perm struct {
	Id int
	// Length of permutation.
	N int
	// Values.
	V []int
	// Solution.
	S string
}

func NewPerm(n int) *Perm {
	return &Perm{N: n, V: make([]int, n)}
}

func (p *Perm) Init() {
	for i := range p.V {
		p.V[i] = i
	}
}

// Bounded random int.
func RB(lo, hi int) int {
	d0 := hi - lo
	r0 := rand.Intn(d0)
	return lo + r0
}

func (p *Perm) Good() {
	for i := range p.V {
		j := RB(i, p.N)
		p.V[i], p.V[j] = p.V[j], p.V[i]
	}
}

func (p *Perm) Bad() {
	for i := range p.V {
		j := rand.Intn(p.N)
		p.V[i], p.V[j] = p.V[j], p.V[i]
	}
}

func (p *Perm) Solve() {
	pg := make([]float64, len(p.V))
	pb := make([]float64, len(p.V))
	var sumg, prodg, sumb, prodb float64
	for i := range p.V {
		i0 := i*p.N + p.V[i]
		pg[i] = M.MG[i0]
		pb[i] = M.MB[i0]
	}
	sumg = 0.0
	sumb = 0.0
	prodg = 1.0
	prodb = 1.0
	for i := 0; i < len(pg); i++ {
		sumg += pg[i]
		prodg *= pg[i] * float64(p.N)

	}
	for i := 0; i < len(pb); i++ {
		sumb += pb[i]
		prodb *= pb[i] * float64(p.N)
	}
	if prodb > 1.0 {
		p.S = "BAD"
	} else {
		p.S = "GOOD"
	}
	WG.Done()
}

// Bias Matrix
// MC Simulation
type MC struct {
	// Number of trials.
	N int
	// Perm size
	PN int
	// Bias matrix for good func
	MG []float64
	// Bias matrix for bad func
	MB []float64
}

func NewMC(n, pn int) *MC {
	return &MC{N: n, PN: pn}
}

func (mc *MC) Run() {
	mc.MG = make([]float64, mc.PN*mc.PN)
	mc.MB = make([]float64, mc.PN*mc.PN)
	pg := NewPerm(mc.PN)
	pb := NewPerm(mc.PN)
	for i := 0; i < mc.N; i++ {
		pg.Init()
		pb.Init()
		pg.Good()
		pb.Bad()
		for j := 0; j < mc.PN; j++ {
			d0 := (1.0 / float64(mc.N))
			ig := j*mc.PN + pg.V[j]
			mc.MG[ig] += d0
			ib := j*mc.PN + pb.V[j]
			mc.MB[ib] += d0
		}
	}
}

func Load() {
	var err error
	I, err = os.Open(IN)
	if err != nil {
		fmt.Println(err)
	}
	S = bufio.NewScanner(I)
	O, err = os.Create(OUT)
	if err != nil {
		fmt.Println(err)
	}
	W = bufio.NewWriter(O)
}

func NumCases() {
	S.Scan()
	var err error
	T, err = strconv.Atoi(S.Text())
	if err != nil {
		fmt.Println(err)
	}
	fmt.Printf("num test cases: %d.\n", T)
}

func Split() {
	var err error
	for i := 0; i < T; i++ {
		S.Scan()
		var n0 int
		n0, err = strconv.Atoi(S.Text())
		if err != nil {
			fmt.Println(err)
		}
		p0 := NewPerm(n0)
		S.Scan()
		n1 := strings.Split(S.Text(), " ")
		for j := range n1 {
			p0.V[j], err = strconv.Atoi(n1[j])
			if err != nil {
				fmt.Println(err)
			}
		}
		p0.Id = i + 1
		P[i] = p0
		WG.Add(1)
		go p0.Solve()
	}
}

func Finish() {
	defer I.Close()
	defer O.Close()
	for i := 0; i < T; i++ {
		s0 := fmt.Sprintf("Case #%d: %s\n", i+1, P[i].S)
		W.WriteString(s0)
	}
	W.Flush()
}

func main() {
	begin := time.Now()
	cpus := runtime.NumCPU()
	runtime.GOMAXPROCS(cpus)
	rand.Seed(time.Now().UnixNano())
	Load()
	NumCases()
	P = make([]*Perm, T)
	M = NewMC(800000, 1000)
	M.Run()
	Split()
	WG.Wait()
	Finish()
	end := time.Now()
	fmt.Printf("total running time: %v.\n", end.Sub(begin))
}

// classic cs problem
// ref: http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
// total run time: 3m30s
// thanks to wabe for fine sol'n
// http://www.go-hero.net/jam/14/name/wabe