-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy path21.worksheet.sc
170 lines (146 loc) · 5.23 KB
/
21.worksheet.sc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
/*
--- Day 21: Step Counter ---
You manage to catch the airship right as it's dropping someone else off on their
all-expenses-paid trip to Desert Island! It even helpfully drops you off near
the gardener and his massive farm.
"You got the sand flowing again! Great work! Now we just need to wait until we
have enough sand to filter the water for Snow Island and we'll have snow again
in no time."
While you wait, one of the Elves that works with the gardener heard how good you
are at solving problems and would like your help. He needs to get his steps in
for the day, and so he'd like to know which garden plots he can reach with
exactly his remaining 64 steps.
He gives you an up-to-date map (your puzzle input) of his starting position (S),
garden plots (.), and rocks (#). For example:
...........
.....###.#.
.###.##..#.
..#.#...#..
....#.#....
.##..S####.
.##..#...#.
.......##..
.##.#.####.
.##..##.##.
...........
The Elf starts at the starting position (S) which also counts as a garden plot.
Then, he can take one step north, south, east, or west, but only onto tiles that
are garden plots. This would allow him to reach any of the tiles marked O:
...........
.....###.#.
.###.##..#.
..#.#...#..
....#O#....
.##.OS####.
.##..#...#.
.......##..
.##.#.####.
.##..##.##.
...........
Then, he takes a second step. Since at this point he could be at either tile
marked O, his second step would allow him to reach any garden plot that is one
step north, south, east, or west of any tile that he could have reached after
the first step:
...........
.....###.#.
.###.##..#.
..#.#O..#..
....#.#....
.##O.O####.
.##.O#...#.
.......##..
.##.#.####.
.##..##.##.
...........
After two steps, he could be at any of the tiles marked O above, including the
starting position (either by going north-then-south or by going west-then-east).
A single third step leads to even more possibilities:
...........
.....###.#.
.###.##..#.
..#.#.O.#..
...O#O#....
.##.OS####.
.##O.#...#.
....O..##..
.##.#.####.
.##..##.##.
...........
He will continue like this until his steps for the day have been exhausted.
After a total of 6 steps, he could reach any of the garden plots marked O:
...........
.....###.#.
.###.##.O#.
.O#O#O.O#..
O.O.#.#.O..
.##O.O####.
.##.O#O..#.
.O.O.O.##..
.##.#.####.
.##O.##.##.
...........
In this example, if the Elf's goal was to get exactly 6 more steps today, he
could use them to reach any of 16 garden plots.
However, the Elf actually needs to get 64 steps today, and the map he's handed
you is much larger than the example map.
Starting from the garden plot marked S on your map, how many garden plots could
the Elf reach in exactly 64 steps?
--- Part Two ---
The Elf seems confused by your answer until he realizes his mistake: he was
reading from a list of his favorite numbers that are both perfect squares and
perfect cubes, not his step counter.
The actual number of steps he needs to get today is exactly 26501365.
He also points out that the garden plots and rocks are set up so that the map
repeats infinitely in every direction.
So, if you were to look one additional map-width or map-height out from the edge
of the example map above, you would find that it keeps repeating:
.................................
.....###.#......###.#......###.#.
.###.##..#..###.##..#..###.##..#.
..#.#...#....#.#...#....#.#...#..
....#.#........#.#........#.#....
.##...####..##...####..##...####.
.##..#...#..##..#...#..##..#...#.
.......##.........##.........##..
.##.#.####..##.#.####..##.#.####.
.##..##.##..##..##.##..##..##.##.
.................................
.................................
.....###.#......###.#......###.#.
.###.##..#..###.##..#..###.##..#.
..#.#...#....#.#...#....#.#...#..
....#.#........#.#........#.#....
.##...####..##..S####..##...####.
.##..#...#..##..#...#..##..#...#.
.......##.........##.........##..
.##.#.####..##.#.####..##.#.####.
.##..##.##..##..##.##..##..##.##.
.................................
.................................
.....###.#......###.#......###.#.
.###.##..#..###.##..#..###.##..#.
..#.#...#....#.#...#....#.#...#..
....#.#........#.#........#.#....
.##...####..##...####..##...####.
.##..#...#..##..#...#..##..#...#.
.......##.........##.........##..
.##.#.####..##.#.####..##.#.####.
.##..##.##..##..##.##..##..##.##.
.................................
This is just a tiny three-map-by-three-map slice of the inexplicably-infinite
farm layout; garden plots and rocks repeat as far as you can see. The Elf still
starts on the one middle tile marked S, though - every other repeated S is
replaced with a normal garden plot (.).
Here are the number of reachable garden plots in this new infinite version of
the example map for different numbers of steps:
In exactly 6 steps, he can still reach 16 garden plots.
In exactly 10 steps, he can reach any of 50 garden plots.
In exactly 50 steps, he can reach 1594 garden plots.
In exactly 100 steps, he can reach 6536 garden plots.
In exactly 500 steps, he can reach 167004 garden plots.
In exactly 1000 steps, he can reach 668697 garden plots.
In exactly 5000 steps, he can reach 16733044 garden plots.
However, the step count the Elf needs is much larger! Starting from the garden
plot marked S on your infinite map, how many garden plots could the Elf reach in
exactly 26501365 steps?
*/