advent2022/solutions/day16/day16.go

package day16

import (
	"bufio"
	"fmt"
	"os"
	"strings"
	"unicode"
)

type Valve struct {
	flowRate int
	leadsTo  []string
}

type SimulationPoint struct {
	time       int
	imAt       string
	elephantAt string
	opened     string
}

type MovePair struct {
	me       string
	elephant string
}

func newMovePair(useElephant bool, a string, b string) MovePair {
	if useElephant && a != "**" && b != "**" && b < a {
		return MovePair{b, a}
	} else {
		return MovePair{a, b}
	}
}

func addMovePair(pair MovePair, list *[]MovePair) {
	for _, existing := range *list {
		if existing.me == pair.me && existing.elephant == pair.elephant {
			return
		}
	}
	*list = append(*list, pair)
}

func alreadyVisited(place string, point SimulationPoint) bool {
	for i := 0; i < len(point.opened); i += 2 {
		if place[0] == point.opened[i] && place[1] == point.opened[i+1] {
			return true
		}
	}
	return false
}

func addPlace(place string, opened string) string {
	injectionPoint := 0

	for injectionPoint < len(opened) && (opened[injectionPoint] < place[0] || (opened[injectionPoint] == place[0] && opened[injectionPoint+1] < place[1])) {
		injectionPoint += 2
	}

	return opened[0:injectionPoint] + place + opened[injectionPoint:]
}

var everythingOpened string
var simulatedItems map[SimulationPoint]int

func runSimulations(useElephant bool, time int, myPlace string, elephantAt string, opened string, valves map[string]Valve) int {
	maxTime := 30
	if useElephant {
		maxTime = 26
	}

	if time == maxTime || everythingOpened == opened {
		return 0
	}

	point := SimulationPoint{time, myPlace, elephantAt, opened}

	if previousValue, ok := simulatedItems[point]; ok {
		return previousValue
	}

	bestResult := 0

	myMoves := []string{}
	if !alreadyVisited(myPlace, point) && valves[myPlace].flowRate != 0 {
		myMoves = append(myMoves, "**")
	}
	myMoves = append(myMoves, valves[myPlace].leadsTo...)

	elephantMoves := []string{"AA"}
	if useElephant {
		elephantMoves = []string{}
		if !alreadyVisited(elephantAt, point) && valves[elephantAt].flowRate != 0 && myPlace != elephantAt {
			elephantMoves = append(elephantMoves, "**")
		}
		elephantMoves = append(elephantMoves, valves[elephantAt].leadsTo...)
	}

	moves := []MovePair{}
	for _, myMove := range myMoves {
		for _, elephantMove := range elephantMoves {
			pair := newMovePair(useElephant, myMove, elephantMove)
			addMovePair(pair, &moves)
		}
	}

	for _, pair := range moves {
		myMove := pair.me
		elephantMove := pair.elephant
		openReleases := 0
		myNext := myPlace
		elephantNext := elephantAt
		nowOpen := opened

		if myMove == "**" {
			openReleases += valves[myPlace].flowRate * (maxTime - (time + 1))
			nowOpen = addPlace(myPlace, nowOpen)
		} else {
			myNext = myMove
		}

		if elephantMove == "**" {
			openReleases += valves[elephantAt].flowRate * (maxTime - (time + 1))
			nowOpen = addPlace(elephantAt, nowOpen)
		} else {
			elephantNext = elephantMove
		}

		candidate := openReleases + runSimulations(useElephant, time+1, myNext, elephantNext, nowOpen, valves)
		if candidate > bestResult {
			bestResult = candidate
		}
	}

	simulatedItems[point] = bestResult

	return bestResult
}

func Run(filename string) {
	file, err := os.Open(filename)

	if err != nil {
		fmt.Println("Error opening file:", err)
		return
	}

	scanner := bufio.NewScanner(file)
	scanner.Split(bufio.ScanLines)
	valveMap := map[string]Valve{}
	everythingOpened = ""

	for scanner.Scan() {
		line := scanner.Text()
		var valve string
		var rate int
		fmt.Sscanf(line, "Valve %s has flow rate=%d", &valve, &rate)
		_, after_semi, found_semi := strings.Cut(line, ";")
		if !found_semi {
			fmt.Println("PANIC: Couldn't find semi colon in line.")
			return
		}
		after_semi = strings.TrimLeftFunc(after_semi, func(r rune) bool {
			return !unicode.IsUpper(r)
		})
		targets := strings.Split(after_semi, ", ")

		if rate > 0 {
			everythingOpened = addPlace(valve, everythingOpened)
		}

		valveMap[valve] = Valve{rate, targets}
	}

	simulatedItems = map[SimulationPoint]int{}
	bestRelease1 := runSimulations(false, 0, "AA", "AA", "", valveMap)
	fmt.Println("Working on my own, best pressure release found is", bestRelease1)

	simulatedItems = map[SimulationPoint]int{}
	bestRelease2 := runSimulations(true, 0, "AA", "AA", "", valveMap)
	fmt.Println("Working with an elephant, best pressure release found is", bestRelease2)

	file.Close()
}