Google Code Jam 2014 Qualification Round * Problem D. Deceitful War

D.go

/*
 *  Google Code Jam 2014 Qualification Round
 *  Problem D. Deceitful War
 *  execute with: go run D.go
 */
package main

import (
	"bufio"
	"fmt"
	"os"
	"runtime"
	"sort"
	"strconv"
	"strings"
	"sync"
	"time"
)

const (
	INPUT  = "D-large-practice.in"
	OUTPUT = "D-large-practice.out"
)

var (
	// Number of test cases.
	T int
	// I/O.
	In  *os.File
	Out *os.File
	S   *bufio.Scanner
	W   *bufio.Writer
	// Deceitful Wars list
	DW []*Deceit
	// Wait Group.
	WG sync.WaitGroup
)

type Deceit struct {
	// Number of blocks.
	N int
	// Masses of Naomi's blocks, in kg.
	Naomi []float64
	// Masses of Ken's blocks, in kg.
	Ken []float64
	// Case Id
	X int
	// Points for Deceitful War
	Y int
	// Points for Optimal War
	Z int
}

func (d *Deceit) Sort() {
	sort.Sort(sort.Reverse(sort.Float64Slice(d.Naomi)))
	sort.Sort(sort.Reverse(sort.Float64Slice(d.Ken)))
}

func (d *Deceit) Solve() {
	// make copies of original data
	on, ok := make([]float64, len(d.Naomi)), make([]float64, len(d.Ken))
	copy(on, d.Naomi)
	copy(ok, d.Ken)
	// optimal war
	tn, tk := 0, 0
	for i := 0; i < d.N; i++ {
		// naomi always picks her highest weight
		var wn, wk float64
		// pop
		// ref: https://code.google.com/p/go-wiki/wiki/SliceTricks
		wn, on = on[0], on[1:]
		// ken's optimal pick is marginally higher, if it exists
		// else pop from ken's lowest weight
		for j := len(ok) - 1; j >= 0; j-- {
			if ok[j] > wn {
				wk = ok[j]
				d0 := ok[:j]
				d1 := ok[j+1:]
				ok = d0
				ok = append(ok, d1...)
				break
			}
		}
		if wk == 0 {
			wk = ok[len(ok)-1]
			ok = ok[:len(ok)-1]
		}
		if wn > wk {
			tn++
		} else {
			tk++
		}
	}
	d.Z = tn
	// copies
	dn, dk := make([]float64, len(d.Naomi)), make([]float64, len(d.Ken))
	copy(dn, d.Naomi)
	copy(dk, d.Ken)
	// deceitful war
	tn, tk = 0, 0
	// naomi always picks her lowest weight
	// either she wins the round,
	// or pops ken's highest weight
	for i := d.N - 1; i >= 0; i-- {
		var wn float64
		// pop
		wn, dn = dn[i], dn[:i]
		if wn > dk[i] {
			dk = dk[:i]
			tn++
		} else {
			dk = dk[1:]
			tk++
		}
	}
	d.Y = tn
	WG.Done()
}

type Tree struct {
	// Left *Tree
	// Right *Tree
	Node   int
	Child  *Tree
	Parent *Tree
}

func Load() {
	var err error
	In, err = os.Open(INPUT)
	if err != nil {
		fmt.Println(err)
	}
	S = bufio.NewScanner(In)
	Out, err = os.Create(OUTPUT)
	if err != nil {
		fmt.Println(err)
	}
	W = bufio.NewWriter(Out)
}

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

func Split() {
	for i := 0; i < T; i++ {
		dw0 := new(Deceit)
		var err error
		// weights
		S.Scan()
		w0 := strings.Split(S.Text(), " ")
		dw0.N, err = strconv.Atoi(w0[0])
		if err != nil {
			fmt.Println(err)
		}
		// naomi
		S.Scan()
		n0 := strings.Split(S.Text(), " ")
		dw0.Naomi = make([]float64, len(n0))
		for k, _ := range n0 {
			var n1 float64
			n1, err = strconv.ParseFloat(n0[k], 64)
			if err != nil {
				fmt.Println(err)
			}
			dw0.Naomi[k] = n1
		}
		// ken
		S.Scan()
		n2 := strings.Split(S.Text(), " ")
		dw0.Ken = make([]float64, len(n2))
		for k, _ := range n2 {
			var n3 float64
			n3, err = strconv.ParseFloat(n2[k], 64)
			if err != nil {
				fmt.Println(err)
			}
			dw0.Ken[k] = n3
		}
		dw0.Sort()
		dw0.X = i + 1
		DW[i] = dw0
		// fmt.Println(dw0)
		WG.Add(1)
		go dw0.Solve()
	}
}

func Finish() {
	defer In.Close()
	defer Out.Close()
	for i := 0; i < T; i++ {
		s0 := fmt.Sprintf("Case #%d: %d %d\n", DW[i].X, DW[i].Y, DW[i].Z)
		W.WriteString(s0)
	}
	W.Flush()
}

func main() {
	begin := time.Now()
	cpus := runtime.NumCPU()
	runtime.GOMAXPROCS(cpus)
	Load()
	NumCases()
	DW = make([]*Deceit, T)
	Split()
	WG.Wait()
	Finish()
	end := time.Now()
	fmt.Printf("total running time: %v.\n", end.Sub(begin))
}

// no need for MDP or expectimax ;)
// total run time: 126.5ms