Google Code Jam 2014 Qualification Round * Problem C. Minesweeper Master

C.go

/*
 *  Google Code Jam 2014 Qualification Round
 *  Problem C. Minesweeper Master
 *  execute with: go run C.go
 */
package main

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

const (
	INPUT  = "C-small-practice.in"
	OUTPUT = "C-small-practice.out"
)

var (
	// Number of test cases.
	T int
	// I/O.
	In  *os.File
	Out *os.File
	S   *bufio.Scanner
	W   *bufio.Writer
	// Mines list.
	Mines []*Mine
	// Wait group.
	WG sync.WaitGroup
)

type Mine struct {
	// Rows.
	R int
	// Columns.
	C int
	// Mines.
	M int
	// Test case number.
	Id int
	// Linear representation.
	L []int
	// Solution.
	S string
}

// Linear array encoding for a minesweeper board.
// 0 = empty, 1 = mine, 2 = click
// 3+ = number of NN mines
func (m *Mine) Linear() {
	tot := m.R * m.C
	m.L = make([]int, tot)
	empty := tot - m.M
	for i := 0; i < tot; i++ {
		if i < empty {
			m.L[i] = 0
		} else {
			m.L[i] = 1
		}
		m.L[0] = 2
	}
}

func (m *Mine) Solve() {
	// total grid size
	tot := m.R * m.C
	empty := tot - m.M
	if empty == 1 || m.R == 1 || m.C == 1 {
		goto POS
	} else if (empty%2 == 0) && empty >= 4 {
		goto POS
	} else if (empty%2 != 0) && empty >= 9 {
		if m.R >= 3 && m.C >= 3 {
			goto POS
		} else {
			goto IMPOS
		}
	} else {
		goto IMPOS
	}
POS:
	m.Render()
	WG.Done()
	return
IMPOS:
	m.S = "Impossible\n"
	WG.Done()
	return
}

func (m *Mine) Render() {
	m.Pretty()
	m.Single()
	var s0 []string
	for row := 0; row < m.R; row++ {
		for col := 0; col < m.C; col++ {
			i := row*m.C + col
			v := m.L[i]
			s1 := ""
			switch v {
			case 0:
				s1 = "."
			case 1:
				s1 = "*"
			case 2:
				s1 = "c"
			}
			s0 = append(s0, s1)
		}
		s0 = append(s0, "\n")
	}
	m.S = strings.Join(s0, "")
}

func (m *Mine) Pretty() {
	tot := m.R * m.C
	empty := tot - m.M
	if ((empty % 2) == 0) && (empty < (2 * m.C)) && (m.R > 1) {
		half := empty / 2
		for row := 0; row < m.R; row++ {
			for col := 0; col < m.C; col++ {
				i0 := (row * m.C) + col
				if i0 == 0 {
					m.L[i0] = 2
					continue
				}
				if row < 2 {
					if col < half {
						m.L[i0] = 0
						continue
					} else {
						m.L[i0] = 1
						continue
					}
				}
				m.L[i0] = 1
			}
		}
	}
	if ((empty % 2) == 1) && (empty < (2*m.C + 3)) && m.R > 2 && m.C > 2 {
		third := (empty - 3) / 2
		for row := 0; row < m.R; row++ {
			for col := 0; col < m.C; col++ {
				i0 := (row * m.C) + col
				if i0 == 0 {
					m.L[i0] = 2
					continue
				}
				if row < 2 {
					if col < third {
						m.L[i0] = 0
						continue
					} else {
						m.L[i0] = 1
						continue
					}
				}
				if row == 2 {
					if col < 3 {
						m.L[i0] = 0
						continue
					} else {
						m.L[i0] = 1
						continue
					}
				}
				m.L[i0] = 1

			}
		}
	}
}

func (m *Mine) Single() {
	tot := m.R * m.C
	empty := tot - m.M
	if (empty % m.C == 1) && (empty > m.C*2) && m.R > 2 && m.C > 2 {
		m.Switch(empty-2, empty)
	}
}

func (m *Mine) Switch(l, f int) {
	t0 := m.L[l]
	m.L[l] = m.L[f]
	m.L[f] = t0
}

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(), " ")
		m := new(Mine)
		var err error
		m.R, err = strconv.Atoi(p[0])
		if err != nil {
			fmt.Println(err)
		}
		m.C, err = strconv.Atoi(p[1])
		if err != nil {
			fmt.Println(err)
		}
		m.M, err = strconv.Atoi(p[2])
		if err != nil {
			fmt.Println(err)
		}
		m.Id = i + 1
		m.Linear()
		Mines[i] = m
		WG.Add(1)
		go m.Solve()
	}
}

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

}

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

// run time: 3.5ms
// O(1) rules based solution
// reference: http://stackoverflow.com/a/23042705