10000 Add solution day 20 part 1 · terminalnode/adventofcode2024@49e4f16 · GitHub
[go: up one dir, main page]

Skip to content
This repository was archived by the owner on Dec 28, 2024. It is now read-only.

Commit 49e4f16

Browse files
committed
Add solution day 20 part 1
1 parent 27179eb commit 49e4f16

File tree

4 files changed

+175
-2
lines changed

4 files changed

+175
-2
lines changed

README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -52,7 +52,7 @@ automatically rebuilt and redeployed every time the `common` module or their own
5252
| 04 | ⭐ ⭐ | 17 | ⭐ ⭐ |
5353
| 05 | ⭐ ⭐ | 18 | ⭐ ⭐ |
5454
| 06 | ⭐ ⭐ | 19 | ⭐ ⭐ |
55-
| 07 | ⭐ ⭐ | 20 | |
55+
| 07 | ⭐ ⭐ | 20 | |
5656
| 08 | ⭐ ⭐ | 21 | |
5757
| 09 | ⭐ ⭐ | 22 | |
5858
| 10 | ⭐ ⭐ | 23 | |

common/util/coordinate.go

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,23 @@ func (c Coordinate) PositiveModulo(x int, y int) Coordinate {
5555
}
5656
}
5757

58+
func (c Coordinate) Adjacent4() []Coordinate {
59+
return []Coordinate{c.North(), c.East(), c.South(), c.West()}
60+
}
61+
62+
func (c Coordinate) Adjacent8() []Coordinate {
63+
return []Coordinate{
64+
c.North(),
65+
c.NorthEast(),
66+
c.NorthWest(),
67+
c.South(),
68+
c.SouthEast(),
69+
c.SouthWest(),
70+
c.East(),
71+
c.West(),
72+
}
73+
}
74+
5875
func (c Coordinate) North() Coordinate {
5976
return Coordinate{c.X, c.Y - 1}
6077
}

solutions/day20/main.go

Lines changed: 96 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,104 @@
11
package main
22

33
import (
4+
"fmt"
45
"github.com/terminalnode/adventofcode2024/common"
6+
"github.com/terminalnode/adventofcode2024/common/util"
7+
"slices"
58
)
69

710
func main() {
8-
common.Setup(20, nil, nil)
11+
common.Setup(20, part1, nil)
12+
}
13+
14+
func part1(
15+
input string,
16+
) string {
17+
p, err := parse(input)
18+
if err != nil {
19+
return fmt.Sprintf("Failed to parse input: %v", err)
20+
}
21+
22+
dm, path, err := p.createDistanceMap()
23+
if err != nil {
24+
return fmt.Sprintf("Failed to create distance map: %v", err)
25+
}
26+
27+
cheatCounts := make(map[int]int)
28+
for _, pos := range path {
29+
distance := dm[pos.Y][pos.X]
30+
next := []util.Coordinate{
31+
pos.North().North(),
32+
pos.South().South(),
33+
pos.East().East(),
34+
pos.West().West(),
35+
}
36+
37+
for _, nPos := range next {
38+
// Normally moving two steps should give us two less distance,
39+
// so these 2 are subtracted from the saved amount.
40+
nDistance := dm[nPos.Y][nPos.X]
41+
saved := nDistance - distance - 2
42+
if saved > 0 {
43+
cheatCounts[saved] += 1
44+
}
45+
}
46+
}
47+
48+
count := 0
49+
for k, v := range cheatCounts {
50+
if k >= 100 {
51+
count += v
52+
}
53+
fmt.Printf("There are %d cheats that save %d picoseconds.\n", v, k)
54+
}
55+
56+
return fmt.Sprintf("Number of cheats saving at least 100ps: %d", count)
57+
}
58+
59+
func (p parsedInput) createDistanceMap() (distanceMap, []util.Coordinate, error) {
60+
newM := make(distanceMap)
61+
path := make([]util.Coordinate, 0, p.length)
62+
for y, _ := range p.m {
63+
newM[y] = make(map[intX]int)
64+
}
65+
66+
distance := 0
67+
curr := util.Coordinate{X: p.e.X, Y: p.e.Y}
68+
newM[curr.Y][curr.X] = 0
69+
70+
visited := make(map[intY]map[intX]bool)
71+
for y := range p.m {
72+
visited[y] = make(map[intX]bool)
73+
}
74+
visited[curr.Y][curr.X] = true
75+
76+
for !curr.Equals(p.s) {
77+
distance++
78+
found := false
79+
for _, newP := range curr.Adjacent4() {
80+
isBlocked := !p.m[newP.Y][newP.X]
81+
isVisited := visited[newP.Y][newP.X]
82+
if isBlocked || isVisited {
83+
continue
84+
}
85+
86+
found = true
87+
newM[newP.Y][newP.X] = distance
88+
path = append(path, newP)
89+
visited[newP.Y][newP.X] = true
90+
curr = newP
91+
break
92+
}
93+
94+
if !found {
95+
return newM, path, fmt.Errorf("missing path from %v", curr)
96+
}
97+
}
98+
99+
// Skip end position and position next to end position,
100+
// because there's no point in cheating there.
101+
slices.Reverse(path[1:])
102+
103+
return newM, path, nil
9104
}

solutions/day20/parse.go

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package main
2+
3+
import (
4+
"errors"
5+
"github.com/terminalnode/adventofcode2024/common/util"
6+
"strings"
7+
)
8+
9+
type intX = int
10+
type intY = int
11+
type raceMap map[intY]map[intX]bool
12+
type distanceMap map[intY]map[intX]int
13+
14+
type parsedInput struct {
15+
m raceMap
16+
length int
17+
s util.Coordinate
18+
e util.Coordinate
19+
}
20+
21+
func parse(
22+
input string,
23+
) (parsedInput, error) {
24+
lines := strings.Split(input, "\n")
25+
m := make(raceMap)
26+
length := 0
27+
s := util.Coordinate{}
28+
e := util.Coordinate{}
29+
sFound := false
30+
eFound := false
31< E182 code class="diff-text syntax-highlighted-line addition">+
32+
for y, line := range lines {
33+
m[y] = make(map[intX]bool)
34+
for x, ch := range line {
35+
if ch == '#' {
36+
continue
37+
}
38+
length += 1
39+
40+
if ch == 'S' {
41+
sFound = true
42+
s = util.Coordinate{X: x, Y: y}
43+
} else if ch == 'E' {
44+
eFound = true
45+
e = util.Coordinate{X: x, Y: y}
46+
}
47+
m[y][x] = true
48+
}
49+
}
50+
out := parsedInput{m: m, s: s, e: e, length: length}
51+
52+
if !sFound && !eFound {
53+
return out, errors.New("neither start nor end found")
54+
} else if !sFound {
55+
return out, errors.New("no start found")
56+
} else if !eFound {
57+
return out, errors.New("no end found")
58+
}
59+
60+
return out, nil
61+
}

0 commit comments

Comments
 (0)
0