main.go (2931B)
1 package main 2 3 import ( 4 "bufio" 5 "fmt" 6 "log" 7 "os" 8 "sort" 9 ) 10 11 type Cell struct { 12 x, y int 13 px, py int // parent 14 f int // steps 15 v int 16 } 17 18 type Cells []Cell 19 20 func (cs Cells) Len() int { return len(cs) } 21 func (cs Cells) Swap(i, j int) { 22 cs[i], cs[j] = cs[j], cs[i] 23 } 24 func (cs Cells) Less(i, j int) bool { 25 return cs[i].f < cs[j].f 26 } 27 func (cs Cells) Has(c Cell) bool { 28 for _, cell := range cs { 29 if cell.x == c.x && cell.y == c.y { 30 return true 31 } 32 } 33 return false 34 } 35 36 type Area struct { 37 width, height int 38 grid [][]byte 39 start, finish Cell 40 } 41 42 type IsFinishFn func(c Cell) bool 43 type IsPathFn func(diff int) bool 44 45 func main() { 46 if len(os.Args) > 1 { 47 day12(os.Args[1]) 48 } else if len(os.Args) == 1 { 49 fmt.Printf("usage: %s inputfile.txt\n", os.Args[0]) 50 } else { 51 fmt.Println("No input data") 52 } 53 } 54 55 func day12(input_file string) { 56 fmt.Printf("day 12 input filename: %s\n", input_file) 57 input, err := os.Open(input_file) 58 if err != nil { 59 log.Fatal(err) 60 } 61 defer input.Close() 62 scanner := bufio.NewScanner(input) 63 var area Area 64 line := 0 65 for scanner.Scan() { 66 in := scanner.Text() 67 area.grid = append(area.grid, make([]byte, len(in))) 68 for i := 0; i < len(in); i++ { 69 s := in[i] 70 if s == 'S' { // start 71 area.grid[line][i] = 'a' 72 area.start = Cell{x: i, y: line, v: 'a'} 73 } else if s == 'E' { 74 area.grid[line][i] = 'z' 75 area.finish = Cell{x: i, y: line, v: 'z'} 76 } else { 77 area.grid[line][i] = s 78 } 79 area.width = len(in) 80 } 81 line++ 82 } 83 if err = scanner.Err(); err != nil { 84 log.Fatal(err) 85 } 86 87 area.height = line 88 89 fmt.Println("Part 1:", area.Astar(area.start, func(cur Cell) bool { 90 return cur.x == area.finish.x && cur.y == area.finish.y 91 }, func(diff int) bool { 92 return diff <= 1 93 }, false)[0]) 94 95 paths := area.Astar(area.finish, func(cur Cell) bool { 96 return cur.v == 'a' 97 }, func(diff int) bool { 98 return diff >= -1 99 }, true) 100 sort.Ints(paths) 101 fmt.Println("Part 2:", paths[0]) 102 } 103 104 func (area *Area) Astar(start Cell, isFinish IsFinishFn, isPath IsPathFn, isMulti bool) []int { 105 dirs := [4][2]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}} 106 var visited, upcoming Cells 107 var lengths []int 108 upcoming = append(upcoming, start) 109 for len(upcoming) > 0 { 110 sort.Sort(upcoming) 111 cur := upcoming[0] 112 if isFinish(cur) { 113 lengths = append(lengths, cur.f) 114 if !isMulti { 115 break 116 } 117 } 118 visited = append(visited, cur) 119 upcoming = upcoming[1:] 120 for i := 0; i < 4; i++ { 121 var child Cell 122 child.x = cur.x + dirs[i][0] 123 child.y = cur.y + dirs[i][1] 124 child.px = cur.x 125 child.py = cur.y 126 child.f = cur.f + 1 127 if child.x < 0 || child.y < 0 || child.x >= area.width || child.y >= area.height { 128 continue 129 } 130 if visited.Has(child) { 131 continue 132 } 133 child.v = int(area.grid[child.y][child.x]) 134 diff := child.v - cur.v 135 if isPath(diff) { 136 if !upcoming.Has(child) { 137 upcoming = append(upcoming, child) 138 } 139 } 140 } 141 } 142 return lengths 143 }