Day 10

4 files changed, 165 insertions, 0 deletions

diff --git a/day10/data.txt b/day10/data.txt
new file mode 100644
index 0000000..3d5716b
--- /dev/null
+++ b/day10/data.txt
@@ -0,0 +1,52 @@
+5654348767654328943210568976534369910789674323105678

+8701239458901217658121477687623478823658789410234089

+9687012344567806789054389598510562734569876501870123

+7896543569478910690343201423421051650121965432965434

+3234512478321001541252102310436710543230892396566985

+0105601309010192432567010121045827652340181087654876

+3238711210520983401478121012310938981653276321049965

+4589100345601276512389652983429845670787345438038734

+7671018986798345601456743876536762103894421589125621

+8562327019887016512567895805445653214545430677894100

+9443456523456325434898656914560344367656528912763210

+2356932108701236721019847823271255698767817603454323

+1047823019854349832478739854180766789678906541065410

+2154014323769858210567026765099850176543215432878929

+3763005458958765523450110623458901289012103898945678

+7892176767567894654543210210567110378650112367630567

+4567989853018723743210321671003025496743203456721656

+3298789914329610894987434582312136789867654109876545

+0107678801458543043406535495443249834578943218103430

+1014565432367232112312345456954956725669867823212321

+0123054545850187601432196307867875218754756984654321

+1232123456987696566545087212987890109843405498789210

+8741876567896501487656996501256765210762112301230101

+9650985401223432398747887450345034369854013010149877

+8967812370314671054321076365432123456343401323456778

+7874901987404589969965431256501432369265692454987569

+2965543256563217878872120387124501078104783467873456

+1234630159870101767013098591037612156943476550012347

+0323701068965432656523107652348765747872105621891298

+3410892454321140545432112543659877831030323436760101

+6598543265210061236789093456701436921121410345603456

+5677610178901176678768186569892345430236587107812367

+0189825679543285789451076654385454321947496236901098

+1670134389056994874342345789276542100858905145610329

+2765245212167823965218763210167033103767814098783410

+3874396103456710454109454109098124912980123045696598

+4983087023469832310087345678567865843832652136787867

+5672171110578761101296218778410976756741743421691958

+9876780987645670814385609569328985401650898330540349

+6565491234532189985674212432310670332798567891231210

+5430303456541023476543203421211591243897678780010676

+6321212187650116567800134560101487654016549654321985

+7890341098565207656912129870122371210323434545401014

+6088780879876348745923038565430110326546783256910123

+2109691965665489632874567678321065487235490127823434

+1234532234786543211065212589832966599104381030198569

+0398940123894678707845103492123877678567210943217678

+1787654014783289698934598783034568943498219854006010

+5671013005654194567827647695693210012382108760125421

+0542562196678003430918034506784345894563456978934438

+1233478787549112321209123215410256723874567834983549

+2012989101238103012213230123322105012965450125676678

diff --git a/day10/example.txt b/day10/example.txt
new file mode 100644
index 0000000..2390837
--- /dev/null
+++ b/day10/example.txt
@@ -0,0 +1,8 @@
+89010123

+78121874

+87430965

+96549874

+45678903

+32019012

+01329801

+10456732

diff --git a/day10/go.mod b/day10/go.mod
new file mode 100644
index 0000000..2940193
--- /dev/null
+++ b/day10/go.mod
@@ -0,0 +1,3 @@
+module stevenlr.com/aoc2024/day10
+
+go 1.23.3
diff --git a/day10/main.go b/day10/main.go
new file mode 100644
index 0000000..e122082
--- /dev/null
+++ b/day10/main.go
@@ -0,0 +1,102 @@
+package main
+
+import (
+	"bufio"
+	"fmt"
+	"os"
+	"strings"
+)
+
+func main() {
+	fmt.Println(find(readData("example.txt")))
+	fmt.Println(36, 81)
+	fmt.Println(find(readData("data.txt")))
+}
+
+type Candidate struct {
+	X, Y int
+	Alt  byte
+	Head *TrailHead
+}
+
+func (c Candidate) Identity() int {
+	return (c.X << 16) | c.Y
+}
+
+type TrailHead struct {
+	Reaches map[int]bool
+}
+
+func findNextCandidates(x, y int, targetAlt byte, head *TrailHead, topo [][]byte) (result []Candidate) {
+	if x > 0 && topo[y][x-1] == targetAlt {
+		result = append(result, Candidate{x - 1, y, targetAlt, head})
+	}
+	if x < len(topo[y])-1 && topo[y][x+1] == targetAlt {
+		result = append(result, Candidate{x + 1, y, targetAlt, head})
+	}
+	if y > 0 && topo[y-1][x] == targetAlt {
+		result = append(result, Candidate{x, y - 1, targetAlt, head})
+	}
+	if y < len(topo)-1 && topo[y+1][x] == targetAlt {
+		result = append(result, Candidate{x, y + 1, targetAlt, head})
+	}
+	return
+}
+
+func find(topo [][]byte) (resultPart1, resultPart2 int) {
+	candidates := make([]Candidate, 0)
+	for y, line := range topo {
+		for x, alt := range line {
+			if alt == 0 {
+				trailhead := &TrailHead{make(map[int]bool)}
+				candidate := Candidate{x, y, alt, trailhead}
+				candidates = append(candidates, candidate)
+			}
+		}
+	}
+
+	for len(candidates) > 0 {
+		current := candidates[len(candidates)-1]
+		candidates = candidates[:len(candidates)-1]
+
+		nextCandidates := findNextCandidates(current.X, current.Y, current.Alt+1, current.Head, topo)
+		if current.Alt == 8 {
+			for _, summit := range nextCandidates {
+				id := summit.Identity()
+				_, alreadyIn := summit.Head.Reaches[id]
+				if !alreadyIn {
+					summit.Head.Reaches[id] = true
+					resultPart1++
+				}
+			}
+			resultPart2 += len(nextCandidates)
+		} else {
+			candidates = append(candidates, nextCandidates...)
+		}
+	}
+
+	return
+}
+
+func readData(fileName string) (topo [][]byte) {
+	fp, err := os.Open(fileName)
+	if err != nil {
+		panic(err)
+	}
+
+	scanner := bufio.NewScanner(fp)
+	for scanner.Scan() {
+		line := []byte(strings.TrimSpace(scanner.Text()))
+		if len(line) == 0 {
+			continue
+		}
+
+		for i := range line {
+			line[i] = line[i] - '0'
+		}
+
+		topo = append(topo, line)
+	}
+
+	return
+}