"Optimized" Cellular Tower solution.

tower2.go

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"log"
	"math/rand"
	"os"
	"runtime/pprof"
	"strconv"
	"strings"
)

var debug = false

func doTower(input io.Reader) {
	scanner := bufio.NewScanner(input) // was os.Stdin
	scanner.Scan()

	line := scanner.Text()
	if debug {
		fmt.Println("[", line, "]")
	}
	words := strings.Split(line, " ")

	width, _ := strconv.Atoi(words[0])
	distance, _ := strconv.Atoi(words[1])

	region := make([][]int16, width)

	for i := 0; i < width; i++ {
		scanner.Scan()
		line := scanner.Text()
		if debug {
			fmt.Println(line)
		}
		region[i] = make([]int16, width)
		words := strings.Split(line, " ")

		for k, word := range words {
			bigint, _ := strconv.Atoi(word)
			region[i][k] = int16(bigint)
		}
	}

	best := 0
	cache := make([][]int16, width)

	// Yeah, we can probably optimize some of this to skip
	// the cells on the edges, because we *know* the best
	// i, j is going to be within distance < i < width-distance
	// anyway. *shrug*
	for i := 0; i < width; i++ {
		cache[i] = make([]int16, width)

		sum := int16(0)
		for j := 0; j <= distance; j++ {
			sum += region[i][j]
		}
		cache[i][0] = sum
		for j, k := distance+1, 1; j < width+distance; j, k = j+1, k+1 {
			if j < width {
				sum += region[i][j]
			}
			if j-distance-distance-1 >= 0 {
				sum -= region[i][j-distance-distance-1]
			}
			cache[i][k] = sum
		}
	}

	for i := 0; i < width; i++ {
		sum := 0
		for j := 0; j <= distance; j++ {
			sum += int(cache[j][i])
		}
		if sum > best {
			best = sum
		}
		for j, k := distance+1, 1; j < width+distance; j, k = j+1, k+1 {
			if j < width {
				sum += int(cache[j][i])
			}
			if j-distance-distance-1 >= 0 {
				sum -= int(cache[j-distance-distance-1][i])
			}
			if sum > best {
				best = sum
			}
		}
	}
	fmt.Println(best)
}

func newTowerGenerator(width int, distance int) io.Reader {
	s := ""
	r := rand.New(rand.NewSource(4))
	s = fmt.Sprintf("%d %d\n", width, distance)
	for i := 0; i < width; i++ {
		row := make([]int, width)
		for k, _ := range row {
			row[k] = r.Intn(501)
		}
		k := fmt.Sprintln(row)
		s += k[1:len(k)-2] + "\n"
	}

	return bytes.NewBufferString(s)
}

func main() {
	cpuprofile := "cpu.pprof"
	f, err := os.Create(cpuprofile)
	if err != nil {
		log.Fatal(err)
	}
	pprof.StartCPUProfile(f)
	defer pprof.StopCPUProfile()

	memprofile := "mem.pprof"
	f2, err := os.Create(memprofile)
	if err != nil {
		log.Fatal(err)
	}
	defer pprof.WriteHeapProfile(f2)

	doTower(bytes.NewBufferString(`4 1
0 1 2 0
0 0 0 0
0 0 0 0
1 0 0 0
`))
	doTower(newTowerGenerator(5, 1)) // 2730

	doTower(newTowerGenerator(10, 5))

	doTower(newTowerGenerator(50, 10))   // 114068
	doTower(newTowerGenerator(500, 50))  // 2605317 6 seconds
	doTower(newTowerGenerator(1000, 50)) // 2619815 13 seconds
	doTower(newTowerGenerator(2000, 50)) // 2607329 was 0m56.408s now 5.407s
}