Optimizations and minor cleanups

Thanks to Go's profiling tools, I discovered that the memoization, while it was cutting down runtime significantly, was itself slow because it was using arrays. Swapping those arrays out for maps made a _massive_ difference (4s/14s part1/part2 to 1ms/2ms with no other changes). Lesson learned. Again.

The IntHeap rename was long overdue since I took the code originally from Go's sample docs for priority queues.

days/18.go

@@ -0,0 +1,345 @@
+package days
+
+import (
+	"container/heap"
+	"fmt"
+	"math"
+	"strings"
+
+	"github.com/edwingeng/deque/v2"
+	u "parnic.com/aoc2019/utilities"
+)
+
+type day18Cell int
+type day18Vec u.Vec2[int]
+type day18Graph map[rune][]u.Pair[rune, int]
+
+const (
+	day18CellWall day18Cell = iota
+	day18CellOpen
+)
+
+var (
+	day18AdjacentOffsets = []day18Vec{
+		{X: -1, Y: 0},
+		{X: 1, Y: 0},
+		{X: 0, Y: -1},
+		{X: 0, Y: 1},
+	}
+)
+
+type Day18 struct {
+	entrance day18Vec
+	grid     [][]day18Cell
+	doors    map[day18Vec]int
+	keys     map[day18Vec]int
+}
+
+func (d *Day18) Parse() {
+	d.doors = make(map[day18Vec]int)
+	d.keys = make(map[day18Vec]int)
+
+	lines := u.GetStringLines("18p")
+	d.grid = make([][]day18Cell, len(lines))
+	for i, line := range lines {
+		d.grid[i] = make([]day18Cell, len(line))
+		for j, char := range line {
+			if char == '#' {
+				d.grid[i][j] = day18CellWall
+			} else if char == '.' {
+				d.grid[i][j] = day18CellOpen
+			} else if char == '@' {
+				d.grid[i][j] = day18CellOpen
+				d.entrance = day18Vec{X: j, Y: i}
+			} else if char >= 'A' && char <= 'Z' {
+				d.grid[i][j] = day18CellOpen
+				d.doors[day18Vec{X: j, Y: i}] = int(char - 'A')
+			} else if char >= 'a' && char <= 'z' {
+				d.grid[i][j] = day18CellOpen
+				d.keys[day18Vec{X: j, Y: i}] = int(char - 'a')
+			}
+		}
+	}
+}
+
+func (d Day18) Num() int {
+	return 18
+}
+
+func (d Day18) Draw(grid [][]day18Cell, keys, doors map[day18Vec]int, entrances ...day18Vec) {
+	for y := range grid {
+		for x := range grid[y] {
+			switch grid[y][x] {
+			case day18CellWall:
+				fmt.Print("█")
+			case day18CellOpen:
+				posVec := day18Vec{X: x, Y: y}
+				if _, exists := doors[posVec]; exists {
+					fmt.Printf("%c", rune(doors[posVec]+'A'))
+				} else if _, exists := keys[posVec]; exists {
+					fmt.Printf("%c", rune(keys[posVec]+'a'))
+				} else if u.ArrayContains(entrances, posVec) {
+					fmt.Print("@")
+				} else {
+					fmt.Print(".")
+				}
+			}
+		}
+		fmt.Println()
+	}
+}
+
+func (d Day18) findAdjacentCells(inPos day18Vec, keys, doors map[day18Vec]int, grid [][]day18Cell) []u.Pair[rune, int] {
+	found := make([]u.Pair[rune, int], 0)
+
+	getAdjacent := func(pos day18Vec) []day18Vec {
+		retAdjacent := make([]day18Vec, 0, len(day18AdjacentOffsets))
+		for _, off := range day18AdjacentOffsets {
+			offVec := day18Vec{X: pos.X + off.X, Y: pos.Y + off.Y}
+			if grid[offVec.Y][offVec.X] == day18CellWall {
+				continue
+			}
+			retAdjacent = append(retAdjacent, offVec)
+		}
+
+		return retAdjacent
+	}
+
+	queue := deque.NewDeque[u.Pair[int, day18Vec]]()
+	visited := make(map[day18Vec]bool)
+	for _, adjacent := range getAdjacent(inPos) {
+		queue.PushBack(u.Pair[int, day18Vec]{First: 1, Second: adjacent})
+	}
+
+	for !queue.IsEmpty() {
+		next := queue.PopFront()
+
+		if _, exists := visited[next.Second]; !exists {
+			visited[next.Second] = true
+
+			key, adjacentIsKey := keys[next.Second]
+			door, adjacentIsDoor := doors[next.Second]
+			if adjacentIsKey || adjacentIsDoor {
+				var rVal rune
+				if adjacentIsKey {
+					rVal = rune('a' + key)
+				} else if adjacentIsDoor {
+					rVal = rune('A' + door)
+				}
+
+				alreadyFound := false
+				for _, p := range found {
+					if p.First == rVal {
+						alreadyFound = true
+						break
+					}
+				}
+				if !alreadyFound {
+					found = append(found, u.Pair[rune, int]{First: rVal, Second: next.First})
+					continue
+				}
+			}
+
+			for _, neighbor := range getAdjacent(next.Second) {
+				if _, exists := visited[neighbor]; !exists {
+					queue.PushBack(u.Pair[int, day18Vec]{First: next.First + 1, Second: neighbor})
+				}
+			}
+		}
+	}
+
+	return found
+}
+
+type day18PriorityQueue struct {
+	distance int
+	neighbor rune
+}
+type PriorityQueueHeap []day18PriorityQueue
+
+func (h PriorityQueueHeap) Len() int           { return len(h) }
+func (h PriorityQueueHeap) Less(i, j int) bool { return h[i].distance < h[j].distance }
+func (h PriorityQueueHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
+
+func (h *PriorityQueueHeap) Push(x any) {
+	*h = append(*h, x.(day18PriorityQueue))
+}
+
+func (h *PriorityQueueHeap) Pop() any {
+	old := *h
+	n := len(old)
+	x := old[n-1]
+	*h = old[0 : n-1]
+	return x
+}
+
+type reachableKeysMemo struct {
+	pos       rune
+	keysFound int
+}
+
+var knownReachableKeys = make(map[reachableKeysMemo][]u.Pair[rune, int])
+
+func (d Day18) reachableKeys(inPos rune, keysFound int, graph day18Graph) []u.Pair[rune, int] {
+	memo := reachableKeysMemo{
+		pos:       inPos,
+		keysFound: keysFound,
+	}
+	if v, exists := knownReachableKeys[memo]; exists {
+		return v
+	}
+
+	ret := make([]u.Pair[rune, int], 0)
+	distance := make(map[rune]int)
+
+	ih := make(PriorityQueueHeap, 0)
+
+	for _, p := range graph[inPos] {
+		ih = append(ih, day18PriorityQueue{
+			distance: p.Second,
+			neighbor: p.First,
+		})
+	}
+
+	heap.Init(&ih)
+
+	for ih.Len() > 0 {
+		node := heap.Pop(&ih).(day18PriorityQueue)
+
+		// it's a key and we haven't picked it up yet...
+		if node.neighbor >= 'a' && node.neighbor <= 'z' && (1<<int(node.neighbor-'a')&keysFound) == 0 {
+			ret = append(ret, u.Pair[rune, int]{First: node.neighbor, Second: node.distance})
+			continue
+		}
+
+		// it's a door but we don't have the key yet...
+		if node.neighbor >= 'A' && node.neighbor <= 'Z' && ((1<<int(node.neighbor-'A'))&keysFound) == 0 {
+			continue
+		}
+
+		for _, p := range graph[node.neighbor] {
+			newDistance := node.distance + p.Second
+			if dist, exists := distance[p.First]; !exists || newDistance < dist {
+				distance[p.First] = newDistance
+				heap.Push(&ih, day18PriorityQueue{
+					distance: newDistance,
+					neighbor: p.First,
+				})
+			}
+		}
+	}
+
+	knownReachableKeys[memo] = ret
+	return ret
+}
+
+type minStepsMemo struct {
+	pos        string
+	keysToFind int
+	keysFound  int
+}
+
+var knownMinimumSteps = make(map[minStepsMemo]int, 0)
+
+func (d Day18) minimumSteps(inPos string, keysToFind int, keysFound int, graph day18Graph) int {
+	memo := minStepsMemo{
+		pos:        inPos,
+		keysToFind: keysToFind,
+		keysFound:  keysFound,
+	}
+	if v, exists := knownMinimumSteps[memo]; exists {
+		return v
+	}
+
+	if keysToFind == 0 {
+		return 0
+	}
+
+	best := math.Inf(1)
+	for _, item := range inPos {
+		for _, p := range d.reachableKeys(item, keysFound, graph) {
+			sb := strings.Builder{}
+			oldIdx := strings.IndexRune(inPos, item)
+			for i := range inPos {
+				if i == oldIdx {
+					sb.WriteRune(p.First)
+				} else {
+					sb.WriteByte(inPos[i])
+				}
+			}
+			newKeys := keysFound + (1 << (p.First - 'a'))
+			dist := p.Second
+
+			dist += d.minimumSteps(sb.String(), keysToFind-1, newKeys, graph)
+
+			if float64(dist) < best {
+				best = float64(dist)
+			}
+		}
+	}
+
+	knownMinimumSteps[memo] = int(best)
+	return int(best)
+}
+
+func (d Day18) buildGraph(pos []day18Vec, keys map[day18Vec]int, doors map[day18Vec]int, grid [][]day18Cell) day18Graph {
+	graph := make(day18Graph)
+	for i, p := range pos {
+		adjacent := d.findAdjacentCells(p, keys, doors, grid)
+		graph[rune('1'+i)] = adjacent
+	}
+	for keyPos, keyType := range keys {
+		graph[rune('a'+keyType)] = d.findAdjacentCells(keyPos, keys, doors, grid)
+	}
+	for doorPos, doorType := range doors {
+		graph[rune('A'+doorType)] = d.findAdjacentCells(doorPos, keys, doors, grid)
+	}
+
+	return graph
+}
+
+func (d Day18) part2PatchMap(grid [][]day18Cell, entrance day18Vec) []day18Vec {
+	grid[entrance.Y-1][entrance.X] = day18CellWall
+	grid[entrance.Y][entrance.X-1] = day18CellWall
+	grid[entrance.Y][entrance.X] = day18CellWall
+	grid[entrance.Y][entrance.X+1] = day18CellWall
+	grid[entrance.Y+1][entrance.X] = day18CellWall
+
+	return []day18Vec{
+		{X: entrance.X - 1, Y: entrance.Y - 1},
+		{X: entrance.X + 1, Y: entrance.Y - 1},
+		{X: entrance.X - 1, Y: entrance.Y + 1},
+		{X: entrance.X + 1, Y: entrance.Y + 1},
+	}
+}
+
+func (d *Day18) Part1() string {
+	// fmt.Println("initial state:")
+	// d.Draw(d.grid, d.keys, d.doors, d.entrance)
+
+	graph := d.buildGraph([]day18Vec{d.entrance}, d.keys, d.doors, d.grid)
+	minSteps := d.minimumSteps("1", len(d.keys), 0, graph)
+
+	return fmt.Sprintf("Total distance traveled: %s%d%s", u.TextBold, minSteps, u.TextReset)
+}
+
+func (d *Day18) Part2() string {
+	// fmt.Println("initial state:")
+	grid := make([][]day18Cell, len(d.grid))
+	for i := range d.grid {
+		grid[i] = make([]day18Cell, len(d.grid[i]))
+		copy(grid[i], d.grid[i])
+	}
+
+	entrances := d.part2PatchMap(grid, d.entrance)
+	// d.Draw(grid, d.keys, d.doors, entrances...)
+
+	// clear memoized maps that (might have) came from part1
+	knownMinimumSteps = make(map[minStepsMemo]int)
+	knownReachableKeys = make(map[reachableKeysMemo][]u.Pair[rune, int])
+
+	graph := d.buildGraph(entrances, d.keys, d.doors, grid)
+	minSteps := d.minimumSteps("1234", len(d.keys), 0, graph)
+
+	return fmt.Sprintf("Total distance traveled: %s%d%s", u.TextBold, minSteps, u.TextReset)
+}

go.mod

@@ -1,3 +1,5 @@
 module parnic.com/aoc2019
 
 go 1.18
+
+require github.com/edwingeng/deque/v2 v2.0.1

go.sum

@@ -0,0 +1,2 @@
+github.com/edwingeng/deque/v2 v2.0.1 h1:yNEsA9tUImO0vyw2hmVGiK4nnkoxBQ8stMYpdVq2ZmQ=
+github.com/edwingeng/deque/v2 v2.0.1/go.mod h1:HukI8CQe9KDmZCcURPZRYVYjH79Zy2tIjTF9sN3Bgb0=

inputs/18p.txt

@@ -0,0 +1,81 @@
+#################################################################################
+#...#.........P...................#.....#.........#.......#.........#...........#
+#.###.#############.#.###########.#.#.###.#########.###.###.#######.#.###########
+#.#...#.#...V.....#.#..t..#.......#.#..a#...........#.#..c..#...#.#.#...........#
+#.#.###.#.#######.#####.#.#####.#######.#.###########.#######.#.#.#.###########.#
+#...#...#...#.#...#.J.#.#.....#.........#.......#.......#.....#.#.#.......#...#.#
+#Z###.#####.#.#.###.#.###.###.#################.#.###.#.#.#####.#.#######.#.#.#.#
+#.....#...#.#.......#...#...#.#...#.....#...#.#.#.#...#.#...#.....#.......#.#.#.#
+###.###.#.#.###########.###.#.#.#.#.###.#.#.#.#.#.#.###.###.#######.#######.#.#.#
+#.#.#...#..y#.........#...#.#...#...#...#.#...#.#.#.#.......#.......#.......#...#
+#.#.#.#######.#######.###.#######.###.###.###.#.###.#######.#.#######.#########.#
+#.#.#..q........#.....#.#...#.E.#...#...#.#...#...#.....#.#.#.#...........#...#.#
+#.#.#############.#####.###.#.#.#######.#.###.###.#.###.#.#.#.#####.#####.#.#.#.#
+#.#...F.......#...#...#.......#.........#...#.#...#.#...#.#.#.....#.#.....#.#...#
+#.#########.###.###.#S###################.#I###.#####.###.#.#####.#.#.#########.#
+#...#...#...#...#...#....u......#.#.....#.#...#.#...#.#...#.....#.#.#.#.......#.#
+#.###.#.#.###.###.#############.#.#.###.#####.#.#.#.#.#.#######.#.#.#.#.#####.#.#
+#.#...#.#.#.#.#s..#...#hG.#...#.#.#...#.#.....#...#...#.#.......#.#.#...#...#.#.#
+#.#.###.#.#.#O#.###.#.#.#.#.#.#.#.#.###.#.###.#########.#.#######.###.###.###.#.#
+#m..#.#...#.#.#.#...#...#...#g#.#.#.#...#.#.#.#.........#.#.#...#...#.....#...#.#
+#.###.#####.#.#.#H###########.#.#.#.#.###.#.#.###.#.#####.#.#.#.#.#.#.#####.###.#
+#.#.........#...#.....#...#...#.#...#...#.#...#...#.#...#.#.#.#.#.#.#.#..w#.#.#.#
+#.#.#####.#.#############.#.###U###.###.#.#.###.###.#.#.#.#.###.###.#.#.#.#.#.#.#
+#.#.....#.#.#.....#.......#.#.....#.#...#.#.....#...#.#.#.#...#...#.#.#.#...#...#
+#.#######.#.###.#.#####.###.#####.###.#.#.#######.###.#.#.#.#####.#.###.#####.###
+#.#.......#.....#.....#...#.#...#b#...#.#.#.#.....#...#.....#.....#...#.#.....#.#
+#.#.#################.#.#.#.#.#.#.#.###.#.#.#.#####.#########.#######.#.#.#####.#
+#.#.#.......#.......#.#.#.#.B.#...#.#.#.#.#.....#...#.....#...#.......#.#...#...#
+#.#.#.#######.###.###.#.#.#########.#.#.#.#######.###.#.###.#####.#.###N###.#.###
+#.#.#...#.....#...#...#.#...........#.#.#.......#.#...#.#...#...#.#.#...#...#...#
+#.#.#.#.#.#####.###.###.###########.#.#.#.#####.#.#.###.#.###.#.###.#.###.###.#.#
+#...#.#.#.#...#.....#.#.#...#.......#...#.#..r#...#.#...#.....#.....#.#.#...#.#.#
+#######.#.###.#######.#.###.#.#######.###.###.#######.#.#############.#.###.#.#.#
+#.......#...#.......#.#...#.#.#.....#.#.#.....#.......#.......#.......#...#.#.#.#
+###.###.###.#.#####.#.###.#.#.###.#.#.#.#####.#.#.###########.###.#####.#.#.###.#
+#...#...#...#...#.#.#.......#...#.#.#.#.#.#...#.#...#...#...#...#.#.....#.#...#.#
+#D###.###.###.#.#.#.###########.#.###.#.#.#.###.###.#.#.#.#.###.#.#.###.#####.#.#
+#...#...#.#...#.#.#...........#.#.#...#.#...#...#...#.#...#...#...#.#.#.......#.#
+#.#.#####.#####.#.###########.#.#.#.###.#.#######.###.#######.#####.#.#########.#
+#.#.............#...............#.................#.........#.................M.#
+#######################################.@.#######################################
+#.#...#.......#...............................#.........#.........#..d#...#.....#
+#.#.#.#.#####.#.#######################.###.#.#.#######.#.###.###.###.#.#.#.#.#K#
+#...#...#...#.#.#...#.................#.#...#.#.#.#.....#...#.#.#.....#.#...#.#.#
+#.#########.#.#.#.#.#.###############.#.#.###.#.#.#.#########.#.#####.#.#####.###
+#.....#...#.#.#.#.#.#.#...#.........#...#.#...#.#.#.......#...#.#.....#.....#...#
+#####.#.#.#.#.#.#.#.#.#.#.#.#####.#####.#.#.###.#.#######.#.###.#.#########.###.#
+#...#.#.#...#.....#.#.#.#.#...#...#...#.#.#.#...#...........#.....#.......#.#...#
+#.#.#.#.###.#########.#.#.###.#####.#.#.#.#.###.###.###########.###.###.###.#.#.#
+#.#.#...#.W...#.......#.#...#.......#.#.#.#...#...#.#...#.#...#.#...#l#.#...#.#.#
+#.###.#########.#######.###.#.#######.#.#.###.###.#.#.#.#.#.#.###.###.#.#.###.#.#
+#.....#.........#...#...#...#.......#...#.#...#...#...#...#.#.#.......#.#...#.#.#
+#.#####.#######.#.#.#.###.###.#####.#####.###.#.#####.#####.#.#.#######.###.#.###
+#.#...#.#.....#.#.#...#...#...#...#.....#...#.R.#...#.#.....#.....#...#...#x#...#
+#.#.#.#.###.###.#.#####.#######.#.#######.#.#####.#.###.###########.#.#.###.###.#
+#...#.#...#...#.#.#...#...#...#.#.#.....#.#.#.....#.#...#.#.........#.#.......#.#
+#####.###.###.#.#.###.###.#.#.#.#.#.###.#.#.#.#####.#.###.#.#########.#.#######.#
+#...#...#...#...#...#.......#...#.#...#.#.#...#.#...#.....#.#.......#.#.#.......#
+###.###.###.###.###.#############.###.#.#.#####.#.#######.#.#.#.#####Y###.#####.#
+#...#.....#...#...#.......#.#...#.....#.#.#..i..#.......#.#.#.#.......#...#.#...#
+#.###.#######.###.#######.#.#.#.#######.#.#.###.#####.###.#Q###.#######.###.#.###
+#...#.#.......#..n#.#.....#...#...#.....#.#.#...#...#.#...#.#.#.#...#...#.#...#.#
+#.#.#.#.###.#####.#.#######.#####.#.#####.#.#.###.###.#.###.#.#.#.#.#.###.#.###.#
+#.#...#.#...#...#.....#...#.#...#...#...#...#...#.#...#...#..o#...#.#.#.......#.#
+#.#####.#####.#.#######.#.#.#.#.#####.#.#######.#.#.###.###########.#.#######.#.#
+#.....#...#...#.#.......#.#.#.#.....#.#.#.....#.#.#.....#.........#.#.#...#.....#
+#####L###.#.###.#.#######.#.###.###.###.###.#.#.#.#######.#.#####.#.#.#.#.#######
+#...#.#...#.#...#...#...#.#...#.#.......#...#.#...#.....#.#.....#.#.#.#.#.......#
+#.#.#.#.###.#.#.###.#.#.#.###.#.#######.#.#######.#.#.###.#####.###.#.#.#######.#
+#.#.#.#.....#.#.#...#.#.....#.#.......#.#.......#...#.#...#..j..#..v#.........#.#
+#.#.#.#######.#.#.###.#.#####.###.###.###.#####.###.###.###.###.#.###.#########.#
+#.#.#.#...#...#.#...#.#.#...#...#...#...#...#.#.#...#...#.#.#...#.#.#.#.........#
+###.#.#.#.#.#######.#.###.#.###.#####.#.###.#.#.#.###.###.#.#####.#.#.#.#######.#
+#...#...#.#.........#.....#...#.....#f#.#.....#.....#e..#.#.......#.#.#.#.#...#.#
+#.#######.#################.#.#####.###.#.#############A#.#########.#.#.#.#.#.#.#
+#...#.....#.....#...#.....#.#.....#.....#...#...#.....#...#...#.......#.#.#.#..z#
+#.#.#.#####.###.###.#.###C#.###########.###.#.#T#.#.#####.#.###.#######.#.#.#####
+#.#.#.X.#k..#.#...#...#...#.....#.....#.#...#.#...#.......#.....#....p..#...#...#
+#.#.###.###.#.###.#####.#.#####.#.#.###.#.###.###################.#######.###.#.#
+#.#.........#...........#.....#...#.....#...#.....................#...........#.#
+#################################################################################

inputs/18s1.txt

@@ -0,0 +1,3 @@
+#########
+#b.A.@.a#
+#########

inputs/18s2.txt

@@ -0,0 +1,5 @@
+########################
+#f.D.E.e.C.b.A.@.a.B.c.#
+######################.#
+#d.....................#
+########################

inputs/18s3.txt

@@ -0,0 +1,5 @@
+########################
+#...............b.C.D.f#
+#.######################
+#.....@.a.B.c.d.A.e.F.g#
+########################

inputs/18s4.txt

@@ -0,0 +1,9 @@
+#################
+#i.G..c...e..H.p#
+########.########
+#j.A..b...f..D.o#
+########@########
+#k.E..a...g..B.n#
+########.########
+#l.F..d...h..C.m#
+#################

inputs/18s5.txt

@@ -0,0 +1,6 @@
+########################
+#@..............ac.GI.b#
+###d#e#f################
+###A#B#C################
+###g#h#i################
+########################

inputs/18s6.txt

@@ -0,0 +1,7 @@
+#######
+#a.#Cd#
+##...##
+##.@.##
+##...##
+#cB#Ab#
+#######

inputs/18s7.txt

@@ -0,0 +1,7 @@
+###############
+#d.ABC.#.....a#
+######...######
+######.@.######
+######...######
+#b.....#.....c#
+###############

inputs/18s8.txt

@@ -0,0 +1,7 @@
+#############
+#DcBa.#.GhKl#
+#.###...#I###
+#e#d#.@.#j#k#
+###C#...###J#
+#fEbA.#.FgHi#
+#############

inputs/18s9.txt

@@ -0,0 +1,9 @@
+#############
+#g#f.D#..h#l#
+#F###e#E###.#
+#dCba...BcIJ#
+#####.@.#####
+#nK.L...G...#
+#M###N#H###.#
+#o#m..#i#jk.#
+#############

main.go

@@ -48,6 +48,7 @@ var dayMap = []day{
 	&days.Day15{},
 	&days.Day16{},
 	&days.Day17{},
+	&days.Day18{},
 }
 
 func main() {

utilities/map.go

@@ -15,3 +15,13 @@ func MapValues[T comparable, U any](m map[T]U) []U {
 	}
 	return r
 }
+
+// CopyMap returns a copy of the passed-in map. Note: currently only works if [U]
+// is not a map or slice.
+func CopyMap[T comparable, U any](m map[T]U) map[T]U {
+	r := make(map[T]U)
+	for k, v := range m {
+		r[k] = v
+	}
+	return r
+}

utilities/vector.go

@@ -44,11 +44,16 @@ func (v Vec2[T]) Equals(other Vec2[T]) bool {
 		v.Y == other.Y
 }
 
+func (v Vec2[T]) ManhattanDistance(other Vec2[T]) T {
+	return T(math.Abs(float64(v.X-other.X)) + math.Abs(float64(v.Y-other.Y)))
+}
+
 func VecBetween[T Number](a, b Vec2[T]) Vec2[T] {
-	return Vec2[T]{
-		X: a.X - b.X,
-		Y: a.Y - b.Y,
-	}
+	return a.To(b)
+}
+
+func ManhattanDistance[T Number](a, b Vec2[T]) T {
+	return a.ManhattanDistance(b)
 }
 
 func (v Vec3[T]) Dot(other Vec3[T]) T {