solve

My goal for 2024 is to be prolific not meticulous. To the summit we go! I may shift this to more system design posts later on, we will see.

As of right now, these posts will mainly be code snippets of coding problems with comments. Treat them as photos with captions. Some moment being captured to ascertain my daily check-in.

Below code for 2022 advent day 12. It's a fitting problem because it's about using bfs to get to the summit. Written in golang.

package problems

import (
	"github.com/gammazero/deque"
	"github.com/xxxxxxx/advent/internal"
)

type day12 struct {
	lines []string
}

func Day12(part int, file string) int {

	in := day12{
		lines: internal.Read(file),
	}

	switch part {
	case 1:
		return in.part_one()
	case 2:
		return in.part_two()
	default:
		return 0
	}

}

func read_graph(lines []string) [][]int {

	graph := make([][]int, len(lines))

	for i, line := range lines {
		graph[i] = []int{}
		for _, character := range line {
			height := int(character) - 97
			if height == -14 { // S
				height = 0
			}
			if height == -28 {
				height = 25
			}
			graph[i] = append(graph[i], height)
		}
	}

	return graph
}

func get_start_end(lines []string) ([2]int, [2]int) {

	start := [2]int{}
	end := [2]int{}

	for i, line := range lines {
		for j, char := range line {
			if char == 'S' {
				start = [2]int{i, j}
			}
			if char == 'E' {
				end = [2]int{i, j}
			}
		}
	}

	return start, end

}

func (input day12) part_one() int {
	graph := read_graph(input.lines)
	start, end := get_start_end(input.lines)
	rows := len(graph)
	columns := len(graph[0])
	directions := [4][2]int{
		{1, 0}, {-1, 0}, {0, 1}, {0, -1},
	}

	visited := make(map[[2]int]bool)
	visited[start] = true
	var q deque.Deque[[3]int]
	q.PushBack([3]int{start[0], start[1], 0})

	for q.Len() != 0 {
		curr := q.PopFront()
		if curr[0] == end[0] && curr[1] == end[1] {
			return curr[2]
		}

		for _, direction := range directions {
			next := [2]int{}
			next[0], next[1] = curr[0]+direction[0], curr[1]+direction[1]
			_, curr_visited := visited[next]

			if next[0] >= 0 && next[0] < rows &&
				next[1] >= 0 && next[1] < columns &&
				!curr_visited && graph[next[0]][next[1]] <= graph[curr[0]][curr[1]]+1 {
				q.PushBack([3]int{next[0], next[1], curr[2] + 1})
				visited[next] = true
			}
		}

	}

	return 0
}

func (input day12) part_two() int {
	graph := read_graph(input.lines)
	_, start := get_start_end(input.lines)
	rows := len(graph)
	columns := len(graph[0])
	directions := [4][2]int{
		{1, 0}, {-1, 0}, {0, 1}, {0, -1},
	}

	visited := make(map[[2]int]bool)
	visited[start] = true
	var q deque.Deque[[3]int]
	q.PushBack([3]int{start[0], start[1], 0})

	for q.Len() != 0 {
		curr := q.PopFront()
		if graph[curr[0]][curr[1]] == 0 {
			return curr[2]
		}

		for _, direction := range directions {
			next := [2]int{}
			next[0], next[1] = curr[0]+direction[0], curr[1]+direction[1]
			_, curr_visited := visited[next]

			if next[0] >= 0 && next[0] < rows &&
				next[1] >= 0 && next[1] < columns &&
				!curr_visited &&
				graph[next[0]][next[1]] >= graph[curr[0]][curr[1]]-1 {
				q.PushBack([3]int{next[0], next[1], curr[2] + 1})
				visited[next] = true
			}
		}

	}

	return 0
}