package main

import (
	"bufio"
	"log"
	"math"
	"os"
	"strconv"
	"strings"
)

type (
	Planet struct {
		Name    string
		Planets []*Planet
		Orbit   []*Planet
	}
)

func main() {
	file, err := os.Open("input.txt")
	if err != nil {
		log.Fatal(err)
	}
	defer file.Close()

	scanner := bufio.NewScanner(file)
	cmds := make([]string, 0)
	for scanner.Scan() {
		cmds = append(cmds, scanner.Text())
	}

	planets := ParseMap(cmds)

	log.Println("Part1: " + strconv.Itoa(SolvePzl1(planets)))
	log.Println("Part2: " + strconv.Itoa(SolvePzl2(planets)))
}

func SolvePzl1(planets []*Planet) int {
	sum := 0
	for i := 0; i < len(planets); i++ {
		sum += CountOrbits(planets[i])
	}
	return sum
}

func SolvePzl2(planets []*Planet) int {
	startPlanet := FindPlanet("YOU", planets)
	sum, _ := CountPath("SAN", startPlanet, make([]*Planet, 0))
	return sum - 2
}

func ParseMap(list []string) []*Planet {
	planets := make([]*Planet, 0)
	var orbitPlanet *Planet
	var inPlanet *Planet

	for _, cmd := range list {
		parts := strings.Split(cmd, ")")
		inPlanetName := parts[0]
		orbitName := parts[1]

		orbitPlanet, planets = GetOrInitialPlanet(orbitName, planets)
		inPlanet, planets = GetOrInitialPlanet(inPlanetName, planets)

		orbitPlanet.Planets = append(orbitPlanet.Planets, inPlanet)
		inPlanet.Orbit = append(inPlanet.Orbit, orbitPlanet)
	}
	return planets
}

func CountOrbits(planet *Planet) int {
	sum := len(planet.Planets)

	if sum == 0 {
		return 0
	}

	for i := 0; i < len(planet.Planets); i++ {
		sum += CountOrbits(planet.Planets[i])
	}
	return sum
}

func CountPath(destination string, currentPlanet *Planet, checkedPlanets []*Planet) (int, bool) {

	if currentPlanet.Name == destination {
		return 0, true
	}

	if FindPlanet(currentPlanet.Name, checkedPlanets) != nil {
		return -1, false
	}

	if len(currentPlanet.Planets) == 0 {
		return -1, false
	}
	checkedPlanets = append(checkedPlanets, currentPlanet)

	minimumCost := math.MaxInt32
	wasSuccess := false

	for i := 0; i < len(currentPlanet.Orbit); i++ {
		path, success := CountPath(destination, currentPlanet.Orbit[i], checkedPlanets)
		path += 1
		if success {
			wasSuccess = true
			if path <= minimumCost {
				minimumCost = path
			}
		}
	}

	for i := 0; i < len(currentPlanet.Planets); i++ {
		path, success := CountPath(destination, currentPlanet.Planets[i], checkedPlanets)
		path += 1
		if success {
			wasSuccess = true
			if path <= minimumCost {
				minimumCost = path
			}
		}
	}

	return minimumCost, wasSuccess
}

func FindPlanet(name string, planets []*Planet) *Planet {
	for i := 0; i < len(planets); i++ {
		if planets[i].Name == name {
			return planets[i]
		}
	}
	return nil
}

func GetOrInitialPlanet(name string, planets []*Planet) (*Planet, []*Planet) {
	planet := FindPlanet(name, planets)

	if planet == nil {
		planet = &Planet{
			Name:    name,
			Planets: make([]*Planet, 0),
			Orbit:   make([]*Planet, 0),
		}
		planets = append(planets, planet)
	}
	return planet, planets
}