Google Code Jam Round 1A * Problem A. Charging Chaos

A.go

/*
 *  Google Code Jam Round 1A
 *  Problem A. Charging Chaos
 *  execute with: go run A.go
 */
package main

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

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

var (
	// Number of test cases.
	T int
	// I/O
	I *os.File
	O *os.File
	S *bufio.Scanner
	W *bufio.Writer
	// Breakers list.
	B []*Breaker
	// Wait group for synchronization.
	WG sync.WaitGroup
)

// Circuit main
type Breaker struct {
	Id int
	// Number of outlets.
	N int
	// Length of flow.
	L int
	// Outlets.
	O []uint64
	// Devices.
	D []uint64
	// Mask.
	M []uint64
	// Solution
	S string
}

func (b *Breaker) Solve() {
	best := b.L + 1
	b.M = make([]uint64, b.N)
	for i := 0; i < b.N; i++ {
		mask := b.D[0] ^ b.O[i]
		for j := 0; j < b.N; j++ {
			b.M[j] = b.O[j] ^ mask
		}
		SortUint64s(b.M)
		ok := true
		for j := 0; j < b.N; j++ {
			if b.D[j] != b.M[j] {
				ok = false
				break
			}
		}
		if !ok {
			continue
		}
		bits := uint(0)
		for mask > 0 {
			if mask&1 != 0 {
				bits++
			}
			mask >>= 1
		}
		bits2 := int(bits)
		if bits2 < best {
			best = bits2
		}
	}
	var s0 string
	if best > b.L {
		s0 = "NOT POSSIBLE"
	} else {
		s0 = strconv.Itoa(best)
	}
	// s0 := fmt.Sprintf("%+v", b)
	b.S = s0
	// b.S = strconv.Itoa(b.Id)
	WG.Done()
}

// Breaker implements sort.Sort on Outlets only.
func (b *Breaker) Len() int {
	return len(b.O)
}

func (b *Breaker) Less(i, j int) bool {
	return b.O[i] < b.O[j]
}

func (b *Breaker) Swap(i, j int) {
	b.O[i], b.O[j] = b.O[j], b.O[i]
}

func (b *Breaker) Sort() {
	sort.Sort(b)
}

// Universal uint64 sort.
type Uint64Slice []uint64

func (u Uint64Slice) Len() int           { return len(u) }
func (u Uint64Slice) Less(i, j int) bool { return u[i] < u[j] }
func (u Uint64Slice) Swap(i, j int)      { u[i], u[j] = u[j], u[i] }
func SortUint64s(a []uint64)             { sort.Sort(Uint64Slice(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 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() {
	var err error
	for i := 0; i < T; i++ {
		c0 := new(Breaker)
		c0.Id = i + 1
		S.Scan()
		n0 := strings.Split(S.Text(), " ")
		// fmt.Printf("case: %d. n: %s. l: %s.\n", i+1, n0[0], n0[1])
		c0.N, err = strconv.Atoi(n0[0])
		if err != nil {
			fmt.Println(err)
		}
		c0.L, err = strconv.Atoi(n0[1])
		if err != nil {
			fmt.Println(err)
		}
		S.Scan()
		n1 := strings.Split(S.Text(), " ")
		S.Scan()
		n2 := strings.Split(S.Text(), " ")
		c0.O = make([]uint64, c0.N)
		c0.D = make([]uint64, c0.N)
		for j := 0; j < c0.N; j++ {
			var x0, x1 int64
			x0, err = strconv.ParseInt(n1[j], 2, 64)
			if err != nil {
				fmt.Println(err)
			}
			x1, err = strconv.ParseInt(n2[j], 2, 64)
			if err != nil {
				fmt.Println(err)
			}
			c0.O[j] = uint64(x0)
			c0.D[j] = uint64(x1)
		}
		// c0.Sort()
		SortUint64s(c0.O)
		SortUint64s(c0.D)
		B[i] = c0
		// fmt.Println(c0)
		WG.Add(1)
		go c0.Solve()
	}
}

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

func main() {
	begin := time.Now()
	fmt.Println("starting solver...")
	cpus := runtime.NumCPU()
	runtime.GOMAXPROCS(cpus)
	fmt.Printf("using %d cpus.\n", runtime.GOMAXPROCS(0))
	Load()
	NumCases()
	B = make([]*Breaker, T)
	Split()
	WG.Wait()
	Finish()
	end := time.Now()
	fmt.Printf("total running time: %v.\n", end.Sub(begin))
}

// thanks wabe for a fine sol'n
// total running time: 86.3ms