Google Code Jam 2014 Qualification Round * Problem B. Cookie Clicker Alpha

B.go

/*
 *  Google Code Jam 2014 Qualification Round
 *  Problem B. Cookie Clicker Alpha
 *  execute with: go run B.go
 */
package main

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

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

var (
	// Number of test cases.
	T int
	// Input file desc
	In *os.File
	// Outpue file desc
	Out *os.File
	// Input scanner
	S *bufio.Scanner
	// Output writer
	W *bufio.Writer
	// Answer map
	A map[int]float64
	// Wait group to synchronize
	WG sync.WaitGroup
)

type Cutter struct {
	// Initial production rate.
	V float64
	// Cookies farm price.
	C float64
	// Cookie gain rate.
	F float64
	// Goal
	X float64
	// Case ID
	Id int
}

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("num cases: %d\n", T)
}

func Split() {
	for i := 0; i < T; i++ {
		S.Scan()
		p := strings.Split(S.Text(), " ")
		Cut := new(Cutter)
		Cut.V = 2.0
		var err error
		Cut.C, err = strconv.ParseFloat(p[0], 64)
		if err != nil {
			fmt.Println(err)
		}
		Cut.F, err = strconv.ParseFloat(p[1], 64)
		if err != nil {
			fmt.Println(err)
		}
		Cut.X, err = strconv.ParseFloat(p[2], 64)
		if err != nil {
			fmt.Println(err)
		}
		Cut.Id = i + 1
		WG.Add(1)
		// launching a new goroutine per instance
		// introduces zero values for some Cut fields
		// sleep a bit to protect memory
		// but in future, use buffered chan
		go Solve(Cut)
		time.Sleep(time.Millisecond)
	}
}

func Solve(c *Cutter) {
	defer WG.Done()
	// time to reach goal
	t0 := make([]float64, 1)
	// accumulated time
	t1 := make([]float64, 1)
	t1[0] = float64(0.0)
	// cookie generation rates
	v0 := make([]float64, 1)
	v0[0] = c.V
	t0[0] = c.X / v0[0]
	// index
	n0 := 0
	for {
		// time to obtain new farm
		t2 := c.C / v0[n0]
		// new rate
		v1 := v0[n0] + c.F
		// new goal time
		t3 := c.X / v1
		// new total time
		t4 := t1[n0] + t2 + t3
		if t4 > t0[n0] {
			break
		} else {
			// update vals
			n0 = n0 + 1
			t0 = append(t0, t4)
			t1 = append(t1, t1[n0-1]+t2)
			v0 = append(v0, v1)
		}
	}
	A[c.Id] = t0[n0]
}

func Finish() {
	defer In.Close()
	defer Out.Close()
	for i := 0; i < T; i++ {
		s := fmt.Sprintf("Case #%d: %v\n", i+1, A[i+1])
		W.WriteString(s)
	}
	W.Flush()
}

func main() {
	begin := time.Now()
	Load()
	NumCases()
	A = make(map[int]float64)
	Split()
	WG.Wait()
	Finish()
	end := time.Now()
	fmt.Printf("total running time: %v.\n", end.Sub(begin))
}
// running time: 190ms