304 lines
9.7 KiB
Go
304 lines
9.7 KiB
Go
package main
|
|
|
|
import (
|
|
"bufio"
|
|
"fmt"
|
|
"os"
|
|
"time"
|
|
)
|
|
|
|
const FILE_PATH = "./input.txt"
|
|
|
|
//const FILE_PATH = "./sample.txt"
|
|
|
|
func LoadInput(filename string) ([]string, error) {
|
|
file, err := os.Open(filename)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
defer file.Close()
|
|
|
|
var lines []string
|
|
scanner := bufio.NewScanner(file)
|
|
for scanner.Scan() {
|
|
lines = append(lines, scanner.Text())
|
|
}
|
|
|
|
if err := scanner.Err(); err != nil {
|
|
return nil, err
|
|
}
|
|
|
|
return lines, nil
|
|
}
|
|
|
|
type Vector2 struct {
|
|
x int
|
|
y int
|
|
}
|
|
|
|
type Position struct {
|
|
cords Vector2
|
|
dir int
|
|
}
|
|
|
|
const (
|
|
EMPTY = iota
|
|
WALL = iota
|
|
)
|
|
|
|
const (
|
|
UP = iota
|
|
RIGHT = iota
|
|
DOWN = iota
|
|
LEFT = iota
|
|
)
|
|
|
|
var MOVEMENT = map[byte]Vector2{
|
|
UP: Vector2{0, -1},
|
|
DOWN: Vector2{0, 1},
|
|
LEFT: Vector2{-1, 0},
|
|
RIGHT: Vector2{1, 0},
|
|
}
|
|
|
|
type Maze struct {
|
|
field [][]int
|
|
width int
|
|
height int
|
|
start Vector2
|
|
end Vector2
|
|
}
|
|
|
|
type structuredInput = Maze
|
|
|
|
func TransformInput(lines []string) structuredInput {
|
|
var field = make([][]int, len(lines))
|
|
var start Vector2
|
|
var end Vector2
|
|
for y := 0; y < len(lines); y++ {
|
|
field[y] = make([]int, len(lines[y]))
|
|
for x := 0; x < len(lines[y]); x++ {
|
|
if lines[y][x] == '#' {
|
|
field[y][x] = WALL
|
|
} else {
|
|
field[y][x] = EMPTY
|
|
}
|
|
|
|
if lines[y][x] == 'S' {
|
|
start = Vector2{x, y}
|
|
} else if lines[y][x] == 'E' {
|
|
end = Vector2{x, y}
|
|
}
|
|
}
|
|
}
|
|
|
|
return Maze{field, len(lines[0]), len(lines), start, end}
|
|
}
|
|
|
|
func printScores(maze Maze, scores [][]int, positions []Position) {
|
|
var found = false
|
|
for y := 0; y < maze.height; y++ {
|
|
for x := 0; x < maze.width; x++ {
|
|
if maze.field[y][x] == WALL {
|
|
fmt.Print("#")
|
|
continue
|
|
}
|
|
|
|
found = false
|
|
|
|
for i := 0; i < len(positions); i++ {
|
|
if positions[i].cords.x == x && positions[i].cords.y == y {
|
|
fmt.Print("O")
|
|
found = true
|
|
break
|
|
}
|
|
}
|
|
if found {
|
|
continue
|
|
}
|
|
fmt.Print(".")
|
|
}
|
|
fmt.Println()
|
|
}
|
|
}
|
|
|
|
func Part1(input structuredInput) int {
|
|
var result int
|
|
var scores = make([][]int, 4)
|
|
var positions = make([]Position, 1)
|
|
var position Position
|
|
var lowestDistance int
|
|
var lowestPosition int
|
|
|
|
for i := 0; i < 4; i++ {
|
|
scores[i] = make([]int, input.width*input.height)
|
|
for j := 0; j < input.width*input.height; j++ {
|
|
scores[i][j] = -1
|
|
}
|
|
}
|
|
|
|
scores[RIGHT][input.start.x+input.start.y*input.width] = 0
|
|
positions[0] = Position{Vector2{input.start.x, input.start.y}, RIGHT}
|
|
|
|
for len(positions) > 0 {
|
|
lowestDistance = scores[positions[0].dir][positions[0].cords.x+positions[0].cords.y*input.width]
|
|
lowestPosition = 0
|
|
for i := 1; i < len(positions); i++ {
|
|
if scores[positions[i].dir][positions[i].cords.x+positions[i].cords.y*input.width] < lowestDistance {
|
|
lowestDistance = scores[positions[i].dir][positions[i].cords.x+positions[i].cords.y*input.width]
|
|
lowestPosition = i
|
|
}
|
|
}
|
|
position = positions[lowestPosition]
|
|
positions = append(positions[:lowestPosition], positions[lowestPosition+1:]...)
|
|
|
|
if position.cords.x == input.end.x && position.cords.y == input.end.y {
|
|
result = scores[position.dir][position.cords.x+position.cords.y*input.width]
|
|
break
|
|
}
|
|
|
|
if scores[(position.dir+1)%4][position.cords.x+position.cords.y*input.width] == -1 && input.field[position.cords.y+MOVEMENT[byte((position.dir+1)%4)].y][position.cords.x+MOVEMENT[byte((position.dir+1)%4)].x] != WALL {
|
|
scores[(position.dir+1)%4][position.cords.x+position.cords.y*input.width] = scores[position.dir][position.cords.x+position.cords.y*input.width] + 1000
|
|
positions = append(positions, Position{Vector2{position.cords.x, position.cords.y}, (position.dir + 1) % 4})
|
|
}
|
|
if scores[(position.dir-1+4)%4][position.cords.x+position.cords.y*input.width] == -1 && input.field[position.cords.y+MOVEMENT[byte((position.dir-1+4)%4)].y][position.cords.x+MOVEMENT[byte((position.dir-1+4)%4)].x] != WALL && scores[(position.dir-1+4)%4][position.cords.x+(position.cords.y+MOVEMENT[byte((position.dir-1+4)%4)].y)*input.width] != WALL {
|
|
scores[(position.dir-1+4)%4][position.cords.x+position.cords.y*input.width] = scores[position.dir][position.cords.x+position.cords.y*input.width] + 1000
|
|
positions = append(positions, Position{Vector2{position.cords.x, position.cords.y}, (position.dir - 1 + 4) % 4})
|
|
}
|
|
if input.field[position.cords.y+MOVEMENT[byte(position.dir)].y][position.cords.x+MOVEMENT[byte(position.dir)].x] == EMPTY && scores[position.dir][position.cords.x+MOVEMENT[byte(position.dir)].x+(position.cords.y+MOVEMENT[byte(position.dir)].y)*input.width] == -1 {
|
|
scores[position.dir][position.cords.x+MOVEMENT[byte(position.dir)].x+(position.cords.y+MOVEMENT[byte(position.dir)].y)*input.width] = scores[position.dir][position.cords.x+position.cords.y*input.width] + 1
|
|
positions = append(positions, Position{Vector2{position.cords.x + MOVEMENT[byte(position.dir)].x, position.cords.y + MOVEMENT[byte(position.dir)].y}, position.dir})
|
|
}
|
|
|
|
//printScores(input, scores, positions)
|
|
}
|
|
|
|
return result
|
|
}
|
|
|
|
func getLeftPosition(position Position) Position {
|
|
return Position{position.cords, (position.dir + 3) % 4}
|
|
}
|
|
|
|
func getRightPosition(position Position) Position {
|
|
return Position{position.cords, (position.dir + 1) % 4}
|
|
}
|
|
|
|
func getForwardPosition(position Position) Position {
|
|
return Position{Vector2{position.cords.x + MOVEMENT[byte(position.dir)].x, position.cords.y + MOVEMENT[byte(position.dir)].y}, position.dir}
|
|
}
|
|
|
|
func getBackwardPosition(position Position) Position {
|
|
return Position{Vector2{position.cords.x + MOVEMENT[byte(position.dir)].x*-1, position.cords.y + MOVEMENT[byte(position.dir)].y*-1}, position.dir}
|
|
}
|
|
|
|
func Part2(input structuredInput) int {
|
|
var result int
|
|
var scores = make([][][]int, 4)
|
|
var positions = make([]Position, 1)
|
|
var position Position
|
|
var lowestDistance int
|
|
var lowestPosition int
|
|
|
|
var bestScore = Part1(input)
|
|
|
|
for i := 0; i < 4; i++ {
|
|
scores[i] = make([][]int, input.height)
|
|
for j := 0; j < input.height; j++ {
|
|
scores[i][j] = make([]int, input.width)
|
|
for x := 0; x < input.width; x++ {
|
|
scores[i][j][x] = -1
|
|
}
|
|
}
|
|
}
|
|
|
|
scores[RIGHT][input.start.y][input.start.x] = 0
|
|
positions[0] = Position{Vector2{input.start.x, input.start.y}, RIGHT}
|
|
|
|
for len(positions) > 0 {
|
|
lowestDistance = scores[positions[0].dir][positions[0].cords.y][positions[0].cords.x]
|
|
lowestPosition = 0
|
|
for i := 1; i < len(positions); i++ {
|
|
if scores[positions[i].dir][positions[i].cords.y][positions[i].cords.x] < lowestDistance {
|
|
lowestDistance = scores[positions[i].dir][positions[i].cords.y][positions[i].cords.x]
|
|
lowestPosition = i
|
|
}
|
|
}
|
|
position = positions[lowestPosition]
|
|
positions = append(positions[:lowestPosition], positions[lowestPosition+1:]...)
|
|
|
|
if scores[(position.dir+1)%4][position.cords.y][position.cords.x] == -1 && input.field[position.cords.y+MOVEMENT[byte((position.dir+1)%4)].y][position.cords.x+MOVEMENT[byte((position.dir+1)%4)].x] != WALL {
|
|
scores[(position.dir+1)%4][position.cords.y][position.cords.x] = scores[position.dir][position.cords.y][position.cords.x] + 1000
|
|
positions = append(positions, Position{Vector2{position.cords.x, position.cords.y}, (position.dir + 1) % 4})
|
|
}
|
|
if scores[(position.dir-1+4)%4][position.cords.y][position.cords.x] == -1 && input.field[position.cords.y+MOVEMENT[byte((position.dir-1+4)%4)].y][position.cords.x+MOVEMENT[byte((position.dir-1+4)%4)].x] != WALL {
|
|
scores[(position.dir-1+4)%4][position.cords.y][position.cords.x] = scores[position.dir][position.cords.y][position.cords.x] + 1000
|
|
positions = append(positions, Position{Vector2{position.cords.x, position.cords.y}, (position.dir - 1 + 4) % 4})
|
|
}
|
|
if input.field[position.cords.y+MOVEMENT[byte(position.dir)].y][position.cords.x+MOVEMENT[byte(position.dir)].x] == EMPTY && scores[position.dir][position.cords.y+MOVEMENT[byte(position.dir)].y][position.cords.x+MOVEMENT[byte(position.dir)].x] == -1 {
|
|
scores[position.dir][position.cords.y+MOVEMENT[byte(position.dir)].y][position.cords.x+MOVEMENT[byte(position.dir)].x] = scores[position.dir][position.cords.y][position.cords.x] + 1
|
|
positions = append(positions, Position{Vector2{position.cords.x + MOVEMENT[byte(position.dir)].x, position.cords.y + MOVEMENT[byte(position.dir)].y}, position.dir})
|
|
}
|
|
}
|
|
|
|
var set = map[Vector2]bool{}
|
|
var score = 0
|
|
var leftRotation Position
|
|
var rightRotation Position
|
|
var backwardPosition Position
|
|
positions = make([]Position, 4)
|
|
for i := 0; i < 4; i++ {
|
|
positions[i] = Position{input.end, i}
|
|
}
|
|
|
|
for len(positions) > 0 {
|
|
var position = positions[0]
|
|
positions = positions[1:]
|
|
score = scores[position.dir][position.cords.y][position.cords.x]
|
|
|
|
if score > bestScore {
|
|
continue
|
|
}
|
|
|
|
set[position.cords] = true
|
|
|
|
leftRotation = getLeftPosition(position)
|
|
rightRotation = getRightPosition(position)
|
|
backwardPosition = getBackwardPosition(position)
|
|
|
|
if scores[leftRotation.dir][leftRotation.cords.y][leftRotation.cords.x] == score-1000 {
|
|
positions = append(positions, leftRotation)
|
|
}
|
|
if scores[rightRotation.dir][rightRotation.cords.y][rightRotation.cords.x] == score-1000 {
|
|
positions = append(positions, rightRotation)
|
|
}
|
|
if scores[backwardPosition.dir][backwardPosition.cords.y][backwardPosition.cords.x] != -1 && scores[backwardPosition.dir][backwardPosition.cords.y][backwardPosition.cords.x] == score-1 {
|
|
positions = append(positions, backwardPosition)
|
|
}
|
|
}
|
|
|
|
result = len(set)
|
|
return result
|
|
}
|
|
|
|
func main() {
|
|
var start time.Time
|
|
var elapsed time.Duration = 0
|
|
input, err := LoadInput(FILE_PATH)
|
|
if err != nil {
|
|
fmt.Println("Error loading input:", err)
|
|
return
|
|
}
|
|
|
|
structuredInput := TransformInput(input)
|
|
fmt.Println("Structured Input:", structuredInput)
|
|
|
|
start = time.Now()
|
|
fmt.Println("Solution Part 1: ", Part1(structuredInput))
|
|
elapsed = time.Since(start)
|
|
fmt.Printf("Part 1 took %s\n", elapsed)
|
|
|
|
start = time.Now()
|
|
fmt.Println("Solution Part 2: ", Part2(structuredInput))
|
|
elapsed = time.Since(start)
|
|
fmt.Printf("Part 2 took %s\n", elapsed)
|
|
}
|