Google Code Jam 2014 * Round 3 * Problem A. Magical, Marvelous Tour

A.go

/*
*
*  Google Code Jam
*  2014 Round 3
*  Problem A. Magical, Marvelous Tour
*
 */
package main

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

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

var (
	I  *os.File
	O  *os.File
	S  *bufio.Scanner
	W  *bufio.Writer
	T  int
	D  []*Device
	WG sync.WaitGroup
)

type Device struct {
	Id   int
	N    int
	p    int
	q    int
	r    int
	s    int
	t    []int
	sum  []int
	Prob float64
}

func NewDevice() *Device {
	return &Device{}
}

func (d *Device) Transistors(i int) int {
	return ((i*d.p+d.q)%d.r + d.s)
}

func (d *Device) SumArray() {
	d.sum = make([]int, d.N+1)
	d.sum[0] = 0
	for i := 1; i < d.N+1; i++ {
		d.sum[i] = d.t[i-1] + d.sum[i-1]
	}
}

func (d *Device) CalcProb(i, j int) float64 {
	p0 := make([]int, 3)
	p0[0] = d.sum[i]
	p0[1] = d.sum[j+1] - d.sum[i]
	p0[2] = d.sum[d.N] - d.sum[j+1]
	p1 := 0 // solveig chooses best
	i1 := 0
	for i := 0; i < len(p0); i++ {
		if p0[i] > p1 {
			p1 = p0[i]
			i1 = i
		}
	}
	p2 := 0 // amar gets the rest
	p3 := 0 // devices total
	for i := 0; i < len(p0); i++ {
		p3 = p3 + p0[i]
		if i != i1 {
			p2 = p2 + p0[i]
		}
	}
	p4 := float64(p2) / float64(p3)
	return p4
}

func (d *Device) Solve() {
	// binary search iteration of partitions
	// i < j < N
	// function that returns left, middle, right sum lookups
	// left = sum[i]
	// middle = sum[j+1] - sum[i]
	// right = sum[N] - sum[j+1]
	// d.Prob = 0.0
	p0 := float64(0.0)
	for i := 1; i < d.N; i++ {
		for j := i; j < d.N; j++ {
			p1 := d.CalcProb(i, j)
			if p1 > p0 {
				p0 = p1
			}
		}
	}
	d.Prob = p0
	WG.Done()
}

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

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

func Split() {
	D = make([]*Device, T)
	var err error
	for i := 0; i < T; i++ {
		d := NewDevice()
		d.Id = i
		S.Scan()
		n0 := strings.Split(S.Text(), " ")
		d.N, err = strconv.Atoi(n0[0])
		d.p, err = strconv.Atoi(n0[1])
		d.q, err = strconv.Atoi(n0[2])
		d.r, err = strconv.Atoi(n0[3])
		d.s, err = strconv.Atoi(n0[4])
		if err != nil {
			fmt.Println(err)
		}
		// loop transistors
		d.t = make([]int, d.N)
		for j := 0; j < d.N; j++ {
			d.t[j] = d.Transistors(j)
		}
		// create sum array
		d.SumArray()
		// refactor: scan line & input to Device constructor
		// then auto-compute transistors, sum -array
		// bonus: launch wait group and solver from constructor
		// also: buffered chan to pass solutions to devices list
		D[i] = d
		// add wg
		WG.Add(1)
		// solve
		go D[i].Solve()
	}
	// fmt.Println(len(D))
	// fmt.Println(D[1])
	// fmt.Println(D[1].Transistors(9))
	// fmt.Println(D[1].t)
}

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

func main() {
	begin := time.Now()
	Load()
	Cases()
	Split()
	WG.Wait()
	Finish()
	end := time.Now()
	fmt.Printf("total running time: %v. \n", end.Sub(begin))
}

// brute force solver
// small input total run time: 300ms