150 lines
2.9 KiB
Go
150 lines
2.9 KiB
Go
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
|
|
}
|