16
🧦 - 2025 DAY 11 SOLUTIONS - 🧦
(programming.dev)
Go
Yeeeaaay graphs! This one has been a pleasure to program and here comes my solution, with pruning of irrelevant branches (cursed nodes) and memoïzation for better performance.
day11.go
package main
import (
"aoc/utils"
"fmt"
"slices"
"strings"
)
type graph map[string][]string
func graphFromInput(input chan string) graph {
g := graph{}
for line := range input {
firstSplit := strings.Split(line, ":")
currentNode := firstSplit[0]
followers := strings.Fields(firstSplit[1])
g[currentNode] = followers
}
return g
}
var memo = make(map[string]map[string]int)
func (g *graph) dfsUntil(currentNode, targetNode string, cursedNodes map[string]any) int {
subMemo, ok := memo[currentNode]
if !ok {
memo[currentNode] = make(map[string]int)
} else {
sum, ok := subMemo[targetNode]
if ok {
return sum
}
}
followers, _ := (*g)[currentNode]
sum := 0
for _, follower := range followers {
if follower == targetNode {
memo[currentNode][targetNode] = 1
return 1
} else if _, ok := cursedNodes[follower]; ok {
continue
}
sum += g.dfsUntil(follower, targetNode, cursedNodes)
}
memo[currentNode][targetNode] = sum
return sum
}
func stepOne(input chan string) (int, error) {
g := graphFromInput(input)
return g.dfsUntil("you", "out", make(map[string]any)), nil
}
func (g *graph) dfsFromSvrToOut(
currentNode string, hasDac, hasFft bool, cursedNodes map[string]any) int {
if currentNode == "dac" && hasFft {
return g.dfsUntil("dac", "out", cursedNodes)
}
hasDac = hasDac || currentNode == "dac"
hasFft = hasFft || currentNode == "fft"
followers := (*g)[currentNode]
sum := 0
for _, follower := range followers {
switch follower {
case "out":
if hasDac && hasFft {
return 1
} else {
return 0
}
default:
sum += g.dfsFromSvrToOut(follower, hasDac, hasFft, cursedNodes)
}
}
return sum
}
func (g *graph) getCursedNodes() map[string]any {
cursedNodes := make(map[string]any)
for node := range *g {
if node == "dac" || node == "fft" || node == "svr" {
continue
}
fftToNode := g.dfsUntil("fft", node, cursedNodes)
dacToNode := g.dfsUntil("dac", node, cursedNodes)
nodeToFft := g.dfsUntil(node, "fft", cursedNodes)
nodeToDac := g.dfsUntil(node, "dac", cursedNodes)
if dacToNode > 0 {
continue
}
if fftToNode > 0 && nodeToDac > 0 {
continue
}
if nodeToFft == 0 {
cursedNodes[node] = nil
}
}
return cursedNodes
}
func stepTwo(input chan string) (int, error) {
g := graphFromInput(input)
cursedNodes := g.getCursedNodes()
for cursedKey := range cursedNodes {
delete(g, cursedKey)
for gkey := range g {
g[gkey] = slices.DeleteFunc(g[gkey], func(n string) bool {
return n == cursedKey
})
}
}
memo = make(map[string]map[string]int)
sum := g.dfsUntil("svr", "out", nil)
return sum, nil
}
func main() {
input, err := utils.DownloadTodaysInputFile()
if err != nil {
_ = fmt.Errorf("%v\n", err)
}
utils.RunStep(utils.ONE, input, stepOne)
utils.RunStep(utils.TWO, input, stepTwo)
}
I have also finally written a function to automatically download the input file (which will prove useful for... ehm... tomorrow):
download today's input file
func DownloadTodaysInputFile() (FilePath, error) {
today := time.Now().Day()
url := fmt.Sprintf("https://adventofcode.com/2025/day/%d/input", today)
client := &http.Client{}
req, err := http.NewRequest("GET", url, nil)
if err != nil {
return FilePath(""), err
}
// const sessionValue = 'hehehehehehe'
req.Header.Set("Cookie", fmt.Sprintf("session=%s", sessionValue))
resp, err := client.Do(req)
if err != nil {
return FilePath(""), err
}
data, err := io.ReadAll(resp.Body)
if err != nil {
return FilePath(""), err
}
path := fmt.Sprintf("day%d.txt", today)
f, err := os.Create(path)
if err != nil {
return FilePath(""), err
}
defer f.Close()
_, err = f.Write(data)
if err != nil {
return FilePath(""), err
}
return FilePath(path), nil
}