Advent of Code 2021 Day 15: Chiton

By Andreas Røssland

https://adventofcode.com/2021/day/15 https://github.com/roessland/advent-of-code

Today’s problem was to find the shortest path in a graph. A* or Dijkstra are the obvious solutions. I decided to just use my existing Dijkstra implementation for this.

I create a big graph of the extended graph, solve part 2, then delete edges going out from the first area and run Dijkstra again. So the answer for Part 2 is actually computed first. If I don’t delete those edges the answer is too low, since the optimal path to the corner of the initial area actually goes outside the initial area for my input.

I introduce the concept of I5 and I1 to avoid getting so confused. I5 is the width of the expanded cave, and I1 is the width of the initial cave.

Note the bijection between (i,j) and id, which is super useful for things like Advent of Code, graphics programming, scientific programming and so on. It encodes a 2-tuple into a single number, as long as the grid dimensions are known.

id = j*I + i

j = id / I = (j*I + i)/I = j
i = id % J = (j*I + i)%I = i

My solution:

package main

import (
	"bufio"
	"fmt"
	"github.com/pkg/errors"
	"github.com/roessland/gopkg/digraph"
	"log"
	"math"
	"os"
	"time"
)

func main() {
	t0 := time.Now()
	g, I1, J1 := ReadInput()
	I5, J5 := I1*5, J1*5

	dist, _ := digraph.Dijkstra(g, 0)
	fmt.Println("Part 2:", dist[(J5-1)*(I5)+(I5)-1]) // 3012

	// Remove edges going out from top left area so the part 1 doesn't go out of bounds.
	// j5*I5 + i5
	for id := 0; id < len(g.Nodes); id++ {
		if id / I5 >= J1 || id % I5 >= I1 {
			// We're outside top left area already.
			continue
		}
		for edgeNo, edge := range g.Nodes[id].Neighbors {
			if edge.To / I5 >= J1 || edge.To % J5 >= I1 {
				g.Nodes[id].Neighbors[edgeNo].Weight = math.MaxFloat64
			}
		}
	}
	dist, _ = digraph.Dijkstra(g, 0)
	fmt.Println("Part 1:", dist[(J1-1)*I5+I1-1]) // 811

	fmt.Println(time.Since(t0)) // 160 ms
}


func ReadInput() (graph digraph.Graph, I1, J1 int) {
	f, err := os.Open("input.txt")
	if err != nil {
		log.Fatal(err)
	}
	scanner := bufio.NewScanner(f)
	var cave [][]int
	for scanner.Scan() {
		var nums []int
		for _, c := range scanner.Text() {
			nums = append(nums, int(c-'0'))
		}
		cave = append(cave, nums)
	}

	J1, I1 = len(cave), len(cave[0])
	J5, I5 := J1*5, I1*5
	graph = digraph.Graph{Nodes: make([]digraph.Node, I5*J5)}

	getID := func(j5, i5 int) (int, error) {
		if j5 < 0 || j5 >= J5 || i5 < 0 || i5 >= I5 {
			return -1, errors.New("oob")
		}
		return j5*I5 + i5, nil
	}

	getWeight := func(j5, i5 int) float64 {
		j1, i1 := j5%J1, i5%I1
		return float64((cave[j1][i1] + j5/J1 + i5/I1 - 1) % 9 + 1)
	}

	for j := 0; j < J5; j++ {
		for i := 0; i < I5; i++ {
			id, _ := getID(j, i)
			if neighbor, err := getID(j-1, i); err == nil {
				graph.Nodes[id].Neighbors = append(graph.Nodes[id].Neighbors, digraph.Edge{
					To:     neighbor,
					Weight: getWeight(j-1, i),
				})
			}
			if neighbor, err := getID(j+1, i); err == nil {
				graph.Nodes[id].Neighbors = append(graph.Nodes[id].Neighbors, digraph.Edge{
					To:     neighbor,
					Weight: getWeight(j+1, i),
				})
			}
			if neighbor, err := getID(j, i-1); err == nil {
				graph.Nodes[id].Neighbors = append(graph.Nodes[id].Neighbors, digraph.Edge{
					To:     neighbor,
					Weight: getWeight(j, i-1),
				})
			}
			if neighbor, err := getID(j, i+1); err == nil {
				graph.Nodes[id].Neighbors = append(graph.Nodes[id].Neighbors, digraph.Edge{
					To:     neighbor,
					Weight: getWeight(j, i+1),
				})
			}

		}
	}
	return
}

Appendix: Dijkstra’s implementation

It’s not perfect, but it’s mine. In particular this package exports a bit too much, and there is probably no need to keep track of which index a heap item has.

Import:

import "github.com/roessland/gopkg/digraph"

Implementation:

package digraph

import (
	"math"
)
import "container/heap"

type Graph struct {
	Nodes []Node
}

type Node struct {
	Neighbors []Edge
}

type Edge struct {
	To     int
	Weight float64
}

type Item struct {
	value    int
	priority float64 // Distance from source to this node
	index    int     // Index of the item in the heap
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func Dijkstra(graph Graph, source int) ([]float64, []int) {
	numNodes := len(graph.Nodes)
	//numEdges := len(graph.Edges)

	// Initialize distances to infinity
	dist := make([]float64, numNodes)
	for i, _ := range dist {
		dist[i] = math.Inf(1)
	}
	dist[source] = 0

	// Initialize pointers to previous nodes.
	// -1 means undefined.
	prev := make([]int, numNodes)
	for i, _ := range prev {
		prev[i] = -1
	}

	Q := make(PriorityQueue, numNodes)
	for i, _ := range graph.Nodes {
		Q[i] = &Item{
			value:    i,
			priority: dist[i],
			index:    i,
		}
	}
	heap.Init(&Q)

	for len(Q) > 0 {
		u := heap.Pop(&Q).(*Item).value
		for _, uv := range graph.Nodes[u].Neighbors {
			v := uv.To
			alt := dist[u] + uv.Weight
			if alt < dist[v] {
				dist[v] = alt
				prev[v] = u
				// v could already be on the heap!
				// But that's OK.
				heap.Push(&Q, &Item{
					value:    v,
					priority: dist[v],
				})
			}
		}
	}
	return dist, prev
}