diff options
| -rw-r--r-- | day10/data.txt | 52 | ||||
| -rw-r--r-- | day10/example.txt | 8 | ||||
| -rw-r--r-- | day10/go.mod | 3 | ||||
| -rw-r--r-- | day10/main.go | 102 | ||||
| -rw-r--r-- | go.work | 3 |
5 files changed, 167 insertions, 1 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 +} @@ -1,7 +1,8 @@ -go 1.22.2 +go 1.23.3 use ( ./day1 + ./day10 ./day2 ./day3 ./day4 |