package main
import (
"bufio"
"log"
"math"
"os"
"strconv"
"strings"
)
var directions = [][2]int{
{-1, 0},
{1, 0},
{0, -1},
{0, 1},
}
type point [2]int
type distance [][]int
type seen map[point]bool
func main() {
if err := myMain(); err != nil {
log.Println(err)
}
}
func myMain() error {
d, err := parseInput("haver.txt")
if err != nil {
return err
}
log.Println(solveFirst(d))
big := genBig(d)
log.Println(solveFirst(big))
return nil
}
func solveFirst(d distance) int {
road := make(distance, len(d))
for row := 0; row < len(road); row++ {
road[row] = make([]int, len(d[0]))
for col := 0; col < len(road[0]); col++ {
road[row][col] = int(math.Inf(1))
}
}
road[0][0] = 0
opts := seen{point{0, 1}: true, point{1, 0}: true}
for len(opts) > 0 {
next := road.getLowest(opts)
road.update(d, next, opts)
}
return road[len(road)-1][len(road[0])-1]
}
func (r distance) update(dist distance, p point, opts seen) {
delete(opts, p)
for _, d := range directions {
diffrow := p[0] + d[0]
diffcol := p[1] + d[1]
if diffrow >= 0 && diffrow < len(r) &&
diffcol >= 0 && diffcol < len(r[0]) {
distance := r[p[0]][p[1]] + dist[diffrow][diffcol]
if distance < r[diffrow][diffcol] {
r[diffrow][diffcol] = distance
opts[point{diffrow, diffcol}] = true
}
}
}
}
func (r distance) getLowest(opts seen) point {
var ret point
min := int(math.Inf(1))
for o := range opts {
if r[o[0]][o[1]] < min {
ret = o
min = r[o[0]][o[1]]
}
}
return ret
}
func genBig(d distance) distance {
const expansion = 5
bigd := make(distance, expansion*len(d))
for i := range bigd {
bigd[i] = make([]int, expansion*len(d[0]))
}
for y := range d {
for x := range d[y] {
for j := 0; j < expansion; j++ {
for i := 0; i < expansion; i++ {
bigd[y+j*len(d)][x+i*len(d[0])] = (d[y][x]+i+j)%10 + (d[y][x]+i+j)/10
}
}
}
}
return bigd
}
func (d distance) String() string {
ret := strings.Builder{}
ret.WriteByte('\n')
for _, row := range d {
for _, ch := range row {
ret.WriteString(strconv.Itoa(ch))
}
ret.WriteByte('\n')
}
return ret.String()
}
func parseInput(fileName string) (distance, error) {
var ret = distance{}
fd, err := os.Open(fileName)
if err != nil {
return ret, err
}
defer fd.Close()
buf := bufio.NewScanner(fd)
for line := 0; buf.Scan(); line++ {
l := []int{}
for _, ch := range buf.Text() {
tmp, err := strconv.Atoi(string(ch))
if err != nil {
return ret, err
}
l = append(l, tmp)
}
ret = append(ret, l)
}
return ret, nil
}