Google Code Jam 2016 * Qualification Round * Problem A. Counting Sheep

A.go

/*
 * Google Code Jam
 * 2016 Qualification Round
 * Problem A. Counting Sheep
 * AQ <[email protected]>
 */
package main

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

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

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

type Sheep struct {
	Id int      // case number
	N  int      // starting number
	C  int      // current count
	M  []string // accumulator
	S  int      // solution
}

func NewSheep() *Sheep {
	// return &Sheep{}
	// create new
	s := &Sheep{}
	s.C = 1
	s.M = make([]string, 10)
	copy(s.M, strings.Split("0123456789", ""))
	return s
}

func (s *Sheep) Solve() {
	// count
	if s.N == 0 {
		s.S = 0
		WG.Done()
		return
	}
	for {
		n0 := s.N * s.C
		// convert n to string
		n1 := strconv.Itoa(n0)
		n2 := strings.Split(n1, "")
		for i := 0; i < len(n2); i++ {
			b0, a0 := Remove(n2[i], s.M)
			// copy(s.M, a0)
			s.M = a0
			if b0 == true {
				// fmt.Println(s.Id, s.M, a0, b0)
				if len(s.M) == 0 {
					// done
					s.S = n0
					WG.Done()
					return
				}
			}
		}
		// remove from accumulator
		// check size
		s.C = s.C + 1
	}
	// s.S = 0
	// s.S = S.C * s.N
	// WG.Done()
}

func Remove(s string, a []string) (bool, []string) {
	// check if s in a
	// if so remove and return new and true
	// else return original and false
	for i := 0; i < len(a); i++ {
		if s == a[i] {
			b1 := true
			a1 := append(a[:i], a[i+1:]...)
			return b1, a1
		}
	}
	return false, a
}

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 Cases() {
	var err error
	S.Scan()
	T, err = strconv.Atoi(S.Text())
	if err != nil {
		fmt.Println(err)
	}
	fmt.Printf("%d test cases. \n", T)
}

func Split() {
	var err error
	Sh = make([]*Sheep, T)
	for i := 0; i < T; i++ {
		s := NewSheep()
		S.Scan()
		s.N, err = strconv.Atoi(S.Text())
		if err != nil {
			fmt.Println(err)
		}
		s.Id = i + 1
		// fmt.Println(s)
		Sh[i] = s
		WG.Add(1)
		go Sh[i].Solve()
	}
}

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

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

// naive simulation with string arrays
// total run time large data set: 2ms
// watch out for slice copy repeating values