Skip to content

Instantly share code, notes, and snippets.

@almendar
Created December 15, 2021 11:53
Show Gist options
  • Save almendar/e47e5e625e682f05cd7a4c46a485013e to your computer and use it in GitHub Desktop.
Save almendar/e47e5e625e682f05cd7a4c46a485013e to your computer and use it in GitHub Desktop.
package main
import (
"fmt"
"io/ioutil"
"log"
"math"
"strconv"
"strings"
)
func prettyPrint(val [][]int) {
for y := range val {
for x := range val[y] {
fmt.Print(val[y][x])
}
fmt.Println()
}
}
func readInput(input string) [][]int {
bytes, err := ioutil.ReadFile(input)
if err != nil {
log.Fatal(err)
}
lines := strings.Split(string(bytes), "\n")
cave := make([][]int, 0)
for _, line := range lines {
row := make([]int, 0, 16)
for _, rune := range line {
height, err := strconv.Atoi(string(rune))
if err != nil {
log.Fatal(err)
}
row = append(row, height)
}
cave = append(cave, row)
}
return cave
}
type coord struct {
x, y int
}
func shortestPath(data [][]int) int {
weights := make(map[coord]int)
queue := make([]coord, 0, 512)
for y := range data {
for x := range data[y] {
weights[coord{x, y}] = math.MaxInt
}
}
weights[coord{0, 0}] = 0
queue = append(queue, coord{0, 0})
for len(queue) > 0 {
pop := queue[0]
queue = queue[1:]
for _, neighbourCoord := range []coord{
{pop.x + 1, pop.y},
{pop.x, pop.y + 1},
{pop.x - 1, pop.y},
{pop.x, pop.y - 1},
} {
_, ok := weights[neighbourCoord]
if !ok {
continue
}
if newCost := weights[pop] + data[neighbourCoord.y][neighbourCoord.x]; newCost < weights[neighbourCoord] {
weights[neighbourCoord] = newCost
queue = append(queue, neighbourCoord)
}
}
}
totalCost := weights[coord{len(data[0]) - 1, len(data) - 1}]
return totalCost
}
func task1(input string) {
data := readInput(input)
cost := shortestPath(data)
fmt.Printf("Day15 task1 %s - %d\n", input, cost)
}
func task2(input string) {
data := readInput(input)
small_y := len(data)
small_x := len(data[0])
globalMap := make([][]int, small_y*5)
for i := 0; i < small_y*5; i++ {
globalMap[i] = make([]int, 5*small_x)
}
for y, row := range data {
for x, item := range row {
for i := 0; i < 5; i++ {
for j := 0; j < 5; j++ {
newVal := (item + i + j)
if newVal > 9 {
newVal = newVal % 9
}
globalMap[y+(i*small_y)][x+(j*small_x)] = newVal
}
}
}
}
// prettyPrint(globalMap)
cost := shortestPath(globalMap)
fmt.Printf("Day15 task1 %s - %d\n", input, cost)
}
func main() {
task1("example.txt")
task1("input.txt")
task2("example.txt")
task2("input.txt")
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment