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)
}