-
Notifications
You must be signed in to change notification settings - Fork 0
/
advent17.go
103 lines (77 loc) · 2.57 KB
/
advent17.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package main
import("fmt";"bufio";"os";"strings";"strconv")
type point struct{
x, y int
}
func main(){
fmt.Println("Input coordinates:")
reader:= bufio.NewReader(os.Stdin)
var m [][]int
row:=0
//valoss
for{
s,_ := reader.ReadString('\n')
s=strings.TrimSpace(s)
if(s=="end"){break}
m = append(m,make([]int,len(s)))
for i,c := range s{
m[row][i],_ = strconv.Atoi(string(c))
}
row++
}
start, end := point{0, 0}, point{len(m[0]) - 1, len(m) - 1}
heatLoss := countHeatLoss(m,start,end,1,3)
fmt.Println("Min Heat loss with max distance 3 is:",heatLoss)
heatLoss = countHeatLoss(m,start,end,4,10)
fmt.Println("Min Heat loss with min distance 4 and max distance 10 is:",heatLoss)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
type HeatState struct {
p, dir point
streak int
}
func countHeatLoss(m [][]int, start point, end point, minS int, maxS int) int{
pointsToCheck := []HeatState{{p:start, dir:point{1, 0}, streak:0}, {p:start, dir:point{0, 1}, streak:0}}
visited := map[HeatState]int{{p:start, dir:point{0, 0}, streak:0}: 0}
minHeatLoss := 999999999
for len(pointsToCheck) > 0 {
current := pointsToCheck[0]
pointsToCheck = pointsToCheck[1:]
if current.p == end && current.streak >= minS {
minHeatLoss = min(minHeatLoss, visited[current])
}
for _,dir := range [3]point{current.dir, dirLeft(current.dir), dirRight(current.dir)}{
nextP := point{current.p.x + dir.x, current.p.y + dir.y}
if !(nextP.x>=0&&nextP.x<=end.x&&nextP.y>=0&&nextP.y<=end.y){
continue
}
totalHeatLoss := visited[current] + getHeatLoss(m,nextP)
nextStreak := 1
if dir == current.dir{
nextStreak = current.streak + 1
}
if(dir==current.dir && current.streak < maxS)||(dir!=current.dir && current.streak>= minS){
nextState := HeatState{nextP,dir,nextStreak}
if val, found := visited[nextState]; !found||val > totalHeatLoss{
visited[nextState] = totalHeatLoss
pointsToCheck = append(pointsToCheck, nextState)
}
}
}
}
return minHeatLoss
}
func getHeatLoss(grid [][]int, p point) int {
return int(grid[p.y][p.x])
}
func dirLeft(p point) point {
return point{p.y, -p.x}
}
func dirRight(p point) point {
return point{-p.y, p.x}
}