advent2022

commit 67647abfdee54462a6c10a4d61a1840d32f9cc06
parent 6bb3a066ed5fa1cde0df46219fd86379777d2d0e
Author: bsandro <email@bsandro.tech>
Date:   Tue, 13 Dec 2022 18:52:58 +0200

Day 12 optimization

Diffstat:
M
day12/main.go
 | 
44
++++++++++++++++++++++----------------------

1 file changed, 22 insertions(+), 22 deletions(-)
diff --git a/day12/main.go b/day12/main.go
@@ -39,6 +39,9 @@ type Area struct {
 	start, finish Cell
 }
 
+type IsFinishFn func(c Cell) bool
+type IsPathFn func(diff int) bool
+
 func main() {
 	if len(os.Args) > 1 {
 		day12(os.Args[1])
@@ -83,36 +86,34 @@ func day12(input_file string) {
 
 	area.height = line
 
-	fmt.Println("Part 1:", area.Astar(area.start))
+	fmt.Println("Part 1:", area.Astar(area.start, func(cur Cell) bool {
+		return cur.x == area.finish.x && cur.y == area.finish.y
+	}, func(diff int) bool {
+		return diff <= 1
+	}, false)[0])
 
-	var starts Cells
-	for y := 0; y < area.height; y++ {
-		for x := 0; x < area.width; x++ {
-			if area.grid[y][x] == 'a' {
-				starts = append(starts, Cell{x: x, y: y, v: 'a'})
-			}
-		}
-	}
-	var paths []int
-	for i, _ := range starts {
-		path := area.Astar(starts[i])
-		if path > 0 {
-			paths = append(paths, path)
-		}
-	}
+	paths := area.Astar(area.finish, func(cur Cell) bool {
+		return cur.v == 'a'
+	}, func(diff int) bool {
+		return diff >= -1
+	}, true)
 	sort.Ints(paths)
 	fmt.Println("Part 2:", paths[0])
 }
 
-func (area *Area) Astar(start Cell) int {
+func (area *Area) Astar(start Cell, isFinish IsFinishFn, isPath IsPathFn, isMulti bool) []int {
 	dirs := [4][2]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
 	var visited, upcoming Cells
+	var lengths []int
 	upcoming = append(upcoming, start)
 	for len(upcoming) > 0 {
 		sort.Sort(upcoming)
 		cur := upcoming[0]
-		if cur.x == area.finish.x && cur.y == area.finish.y {
-			return cur.f
+		if isFinish(cur) {
+			lengths = append(lengths, cur.f)
+			if !isMulti {
+				break
+			}
 		}
 		visited = append(visited, cur)
 		upcoming = upcoming[1:]
@@ -131,13 +132,12 @@ func (area *Area) Astar(start Cell) int {
 			}
 			child.v = int(area.grid[child.y][child.x])
 			diff := child.v - cur.v
-			if diff == 0 || diff == 1 || diff < 0 {
+			if isPath(diff) {
 				if !upcoming.Has(child) {
 					upcoming = append(upcoming, child)
 				}
 			}
 		}
 	}
-	//fmt.Println("astar error")
-	return 0
+	return lengths
 }