Advent of Code 2024 - Day 18 - Go

 --- Day 18: RAM Run ---

https://adventofcode.com/2024/day/18

Day 18 - Solution

	package main
	import (
	"fmt"
	"image"
	"os"
	"strings"
	)
	const gridSize = 70
	// Breadth-First Search (BFS)
	func main() {
	// Read and parse input
	obstaclePoints := parseInput("input.txt")
	// Create the grid
	grid := initializeGrid(gridSize)
	// Simulate the process
	for index, obstacle := range obstaclePoints {
	// Mark the obstacle on the grid
	grid[obstacle] = false
	// Check if the target is reachable
	if isTargetReachable(grid, gridSize) {
	if index == 1024 {
	fmt.Printf("Distance to target: %d\n", calculateShortestDistance(grid, gridSize))
	}
	continue
	}
	// Output the obstacle that blocked the target
	fmt.Printf("Blocked by obstacle at: %d,%d\n", obstacle.X, obstacle.Y)
	break
	}
	}
	// parseInput reads the input file and returns a slice of obstacle points
	func parseInput(filename string) []image.Point {
	data, err := os.ReadFile(filename)
	if err != nil {
	panic(fmt.Sprintf("Error reading file: %v", err))
	}
	var obstaclePoints []image.Point
	for _, pointStr := range strings.Fields(string(data)) {
	var x, y int
	fmt.Sscanf(pointStr, "%d,%d", &x, &y)
	obstaclePoints = append(obstaclePoints, image.Point{X: x, Y: y})
	}
	return obstaclePoints
	}
	// initializeGrid creates a grid of the given size, initializing all points as walkable
	func initializeGrid(size int) map[image.Point]bool {
	grid := make(map[image.Point]bool)
	for y := 0; y <= size; y++ {
	for x := 0; x <= size; x++ {
	grid[image.Point{X: x, Y: y}] = true
	}
	}
	return grid
	}
	// isTargetReachable checks if the target (gridSize, gridSize) is reachable
	func isTargetReachable(grid map[image.Point]bool, size int) bool {
	queue := []image.Point{{0, 0}}
	visited := map[image.Point]bool{{0, 0}: true}
	for len(queue) > 0 {
	currentPoint := queue[0]
	queue = queue[1:]
	if currentPoint == (image.Point{X: size, Y: size}) {
	return true
	}
	for _, neighbor := range getNeighbors(currentPoint) {
	if grid[neighbor] && !visited[neighbor] {
	visited[neighbor] = true
	queue = append(queue, neighbor)
	}
	}
	}
	return false
	}
	// calculateShortestDistance calculates the shortest distance to the target (gridSize, gridSize)
	func calculateShortestDistance(grid map[image.Point]bool, size int) int {
	queue := []image.Point{{0, 0}}
	distances := map[image.Point]int{{0, 0}: 0}
	for len(queue) > 0 {
	currentPoint := queue[0]
	queue = queue[1:]
	if currentPoint == (image.Point{X: size, Y: size}) {
	return distances[currentPoint]
	}
	for _, neighbor := range getNeighbors(currentPoint) {
	if grid[neighbor] {
	if _, visited := distances[neighbor]; !visited {
	distances[neighbor] = distances[currentPoint] + 1
	queue = append(queue, neighbor)
	}
	}
	}
	}
	return -1 // Return -1 if the target is unreachable
	}
	// getNeighbors returns the neighboring points of a given point
	func getNeighbors(point image.Point) []image.Point {
	return []image.Point{
	{X: point.X, Y: point.Y - 1}, // Up
	{X: point.X + 1, Y: point.Y}, // Right
	{X: point.X, Y: point.Y + 1}, // Down
	{X: point.X - 1, Y: point.Y}, // Left
	}
	}

view raw main.go hosted with ❤ by GitHub