Skip to content

Instantly share code, notes, and snippets.

@okaq
Created April 20, 2012 13:24
Show Gist options
  • Save okaq/2428538 to your computer and use it in GitHub Desktop.
Save okaq/2428538 to your computer and use it in GitHub Desktop.
Solution: Recycled Numbers (Google Code Jam 2012 Qualification Round Problem C)
/*
* Google Code Jam 2012 Qualification Round
* Problem C. Recycled Numbers
*/
package main
import (
"bufio"
"bytes"
"flag"
"fmt"
"os"
"strconv"
"time"
)
var (
inpath *string
outpath *string
infile *os.File
outfile *os.File
reader *bufio.Reader
writer *bufio.Writer
tests int
Pairs []Pair
recycle []int
)
type Pair struct {
A []byte
B []byte
}
func flags() {
inpath = flag.String("i", "C-small-practice.in", "Input filepath for the problem.")
outpath = flag.String("o", "C-small-practice.out", "Output filepath for the problem.")
flag.Parse()
}
func files() {
var err error
infile, err = os.Open(*inpath)
if err != nil {
fmt.Println(err)
}
outfile, err = os.Create(*outpath)
if err != nil {
fmt.Println(err)
}
reader = bufio.NewReader(infile)
writer = bufio.NewWriter(outfile)
}
func cleanup() {
var err error
err = infile.Close()
if err != nil {
fmt.Println(err)
}
err = outfile.Close()
if err != nil {
fmt.Println(err)
}
}
func parse() {
l0, p0, e0 := reader.ReadLine()
if e0 != nil {
fmt.Println(e0, p0)
}
tests, _ = strconv.Atoi(string(l0))
Pairs = make([]Pair, tests)
recycle = make([]int, tests)
for i := 0; i < tests; i++ {
l0, p0, e0 = reader.ReadLine()
if e0 != nil {
fmt.Println(e0, p0)
}
// fmt.Println(l0) // l0 is ascii byte array
// [49 49 56 32 57 57 54] == "118 996"
// space char is 32
// digits are 48-57
// s0 := strings.Split(string(l0), " ")
r0 := new(Pair)
sep := make([]byte, 1)
sep[0] = 32
r0.A = l0[0:bytes.Index(l0, sep)]
r0.B = l0[bytes.Index(l0, sep)+1:]
Pairs[i] = *r0
}
}
func Btoi(b []byte) int {
s0, _ := strconv.Atoi(string(b))
return s0
}
func Itob(i int) []byte {
return []byte(strconv.Itoa(i))
}
func perm(n int) []int {
b0 := Itob(n)
r0 := make([]int, len(b0))
r0[0] = n
if len(b0) == 1 {
return r0
}
for i := (len(b0) - 1); i >= 1; i-- {
if b0[i] == 48 {
r0[i] = -1
continue
}
b1 := make([]byte, len(b0))
copy(b1[:len(b0)-i], b0[i:])
copy(b1[len(b0)-i:], b0[:i])
r0[i] = Btoi(b1)
}
return r0
}
func solve() {
var d0 int64
d0 = 0
for i := 0; i < len(Pairs); i++ {
t0 := time.Now()
t := 0
a := Btoi(Pairs[i].A)
b := Btoi(Pairs[i].B)
for n := a; n < b; n++ {
for j, c := range perm(n) {
if c == n && j != 0 {
break
}
if c > n && c <= b && c > 0 {
t = t + 1
}
}
}
recycle[i] = t
t1 := time.Now().Sub(t0)
d0 = d0 + t1.Nanoseconds()
fmt.Println(i, t1.String())
}
fmt.Println(d0)
}
func output() {
for i := 0; i < len(recycle); i++ {
s0 := fmt.Sprintf("Case #%d: %d\n", i+1, recycle[i])
writer.WriteString(s0)
}
writer.Flush()
}
func main() {
flags()
files()
defer cleanup()
parse()
solve()
output()
}
/*
total run time for C-large: 109s
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment