advent2022

commit 1b7d93f0429debca3fd06f36737cb6172c80a4a8
parent 38f2af58ffede9ab6e6de2198797703ec5a2f758
Author: bsandro <email@bsandro.tech>
Date:   Mon, 12 Dec 2022 08:19:22 +0000

Day 12 part 2 + go fmt

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

1 file changed, 40 insertions(+), 22 deletions(-)
diff --git a/day12/main.go b/day12/main.go
@@ -9,13 +9,14 @@ import (
 )
 
 type Cell struct {
-	x, y int
+	x, y   int
 	px, py int // parent
-	f int // steps
-	v int
+	f      int // steps
+	v      int
 }
 
 type Cells []Cell
+
 func (cs Cells) Len() int { return len(cs) }
 func (cs Cells) Swap(i, j int) {
 	cs[i], cs[j] = cs[j], cs[i]
@@ -34,7 +35,7 @@ func (cs Cells) Has(c Cell) bool {
 
 type Area struct {
 	width, height int
-	grid [][]byte
+	grid          [][]byte
 	start, finish Cell
 }
 
@@ -61,14 +62,14 @@ func day12(input_file string) {
 	for scanner.Scan() {
 		in := scanner.Text()
 		area.grid = append(area.grid, make([]byte, len(in)))
-		for i:=0;i<len(in);i++{
+		for i := 0; i < len(in); i++ {
 			s := in[i]
 			if s == 'S' { // start
 				area.grid[line][i] = 'a'
-				area.start = Cell{x:i,y:line,v:'a'}
+				area.start = Cell{x: i, y: line, v: 'a'}
 			} else if s == 'E' {
 				area.grid[line][i] = 'z'
-				area.finish = Cell{x:i, y:line,v:'z'}
+				area.finish = Cell{x: i, y: line, v: 'z'}
 			} else {
 				area.grid[line][i] = s
 			}
@@ -76,50 +77,67 @@ func day12(input_file string) {
 		}
 		line++
 	}
-	area.height = line
 	if err = scanner.Err(); err != nil {
 		log.Fatal(err)
 	}
 
-	fmt.Println("Part 1:", area.Astar())
+	area.height = line
+
+	fmt.Println("Part 1:", area.Astar(area.start))
+
+	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)
+		}
+	}
+	sort.Ints(paths)
+	fmt.Println("Part 2:", paths[0])
 }
 
-func (area *Area) Astar() int {
-	dirs := [4][2]int{{-1,0},{0,-1},{1,0},{0,1}}
+func (area *Area) Astar(start Cell) int {
+	dirs := [4][2]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
 	var visited, upcoming Cells
-	upcoming = append(upcoming, area.start)
+	upcoming = append(upcoming, start)
 	for len(upcoming) > 0 {
 		sort.Sort(upcoming)
 		cur := upcoming[0]
-		//fmt.Println("processing", cur.x, cur.y)
 		if cur.x == area.finish.x && cur.y == area.finish.y {
 			return cur.f
 		}
 		visited = append(visited, cur)
 		upcoming = upcoming[1:]
-		for i:=0;i<4;i++{
+		for i := 0; i < 4; i++ {
 			var child Cell
-			child.x =cur.x+dirs[i][0]
-			child.y =cur.y+dirs[i][1]
+			child.x = cur.x + dirs[i][0]
+			child.y = cur.y + dirs[i][1]
 			child.px = cur.x
 			child.py = cur.y
-			child.f = cur.f+1
-			if child.x<0 || child.y < 0 || child.x >= area.width || child.y >= area.height {
+			child.f = cur.f + 1
+			if child.x < 0 || child.y < 0 || child.x >= area.width || child.y >= area.height {
 				continue
 			}
 			if visited.Has(child) {
 				continue
 			}
 			child.v = int(area.grid[child.y][child.x])
-			diff := child.v-cur.v
-			//fmt.Printf("diff %d, %c -> %c, %v\n",diff, cur.v, child.v, child)
-			if diff==0 || diff==1 || diff <0 {
+			diff := child.v - cur.v
+			if diff == 0 || diff == 1 || diff < 0 {
 				if !upcoming.Has(child) {
 					upcoming = append(upcoming, child)
 				}
 			}
 		}
 	}
-	fmt.Println("astar error")
+	//fmt.Println("astar error")
 	return 0
 }