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
|
--- Day 22: Mode Maze ---
This is it, your final stop: the year -483. It's snowing and dark outside; the only light you can
see is coming from a small cottage in the distance. You make your way there and knock on the door.
A portly man with a large, white beard answers the door and invites you inside. For someone living
near the North Pole in -483, he must not get many visitors, but he doesn't act surprised to see you.
Instead, he offers you some milk and cookies.
After talking for a while, he asks a favor of you. His friend hasn't come back in a few hours, and
he's not sure where he is. Scanning the region briefly, you discover one life signal in a cave
system nearby; his friend must have taken shelter there. The man asks if you can go there to
retrieve his friend.
The cave is divided into square [1m[97mregions[0m which are either dominantly [1m[97mrocky[0m, [1m[97mnarrow[0m, or
[1m[97mwet[0m (called its [1m[97mtype[0m). Each region occupies exactly one [1m[97mcoordinate[0m in X,Y format where X and Y are
integers and zero or greater. (Adjacent regions can be the same type.)
The scan (your puzzle input) is not very detailed: it only reveals the [1m[97mdepth[0m of the cave system and
the [1m[97mcoordinates of the target[0m. However, it does not reveal the type of each region. The mouth of the
cave is at 0,0.
The man explains that due to the unusual geology in the area, there is a method to determine any
region's type based on its [1m[97merosion level[0m. The erosion level of a region can be determined from its
[1m[97mgeologic index[0m. The geologic index can be determined using the first rule that applies from the list
below:
- The region at 0,0 (the mouth of the cave) has a geologic index of 0.
- The region at the coordinates of the target has a geologic index of 0.
- If the region's Y coordinate is 0, the geologic index is its X coordinate times 16807.
- If the region's X coordinate is 0, the geologic index is its Y coordinate times 48271.
- Otherwise, the region's geologic index is the result of multiplying the erosion
[1m[97mlevels[0m of the regions at X-1,Y and X,Y-1.
A region's [1m[97merosion level[0m is its [1m[97mgeologic index[0m plus the cave system's [1m[97mdepth[0m, all modulo 20183. Then:
- If the [1m[97merosion level modulo 3[0m is 0, the region's type is [1m[97mrocky[0m.
- If the [1m[97merosion level modulo 3[0m is 1, the region's type is [1m[97mwet[0m.
- If the [1m[97merosion level modulo 3[0m is 2, the region's type is [1m[97mnarrow[0m.
For example, suppose the cave system's depth is 510 and the target's coordinates are 10,10. Using %
to represent the modulo operator, the cavern would look as follows:
- At 0,0, the geologic index is 0. The erosion level is (0 + 510) % 20183 = 510. The type is 510 %
3 = 0, [1m[97mrocky[0m.
- At 1,0, because the Y coordinate is 0, the geologic index is 1 * 16807 = 16807. The erosion level
is (16807 + 510) % 20183 = 17317. The type is 17317 % 3 = 1, [1m[97mwet[0m.
- At 0,1, because the X coordinate is 0, the geologic index is 1 * 48271 = 48271. The erosion
level is (48271 + 510) % 20183 = 8415. The type is 8415 % 3 = 0, [1m[97mrocky[0m.
- At 1,1, neither coordinate is 0 and it is not the coordinate of the target, so the geologic index
is the erosion level of 0,1 (8415) times the erosion level of 1,0 (17317), 8415 * 17317 = 145722555.
The erosion level is (145722555 + 510) % 20183 = 1805. The type is 1805 % 3 = 2,
[1m[97mnarrow[0m.
- At 10,10, because they are the target's coordinates, the geologic index is 0. The erosion level
is (0 + 510) % 20183 = 510. The type is 510 % 3 = 0, [1m[97mrocky[0m.
Drawing this same cave system with rocky as ., wet as =, narrow as |, the mouth as M, the target as
T, with 0,0 in the top-left corner, X increasing to the right, and Y increasing downward, the
top-left corner of the map looks like this:
[1m[97mM[0m=.|=.|.|=.|=|=.
.|=|=|||..|.=...
.==|....||=..|==
=.|....|.==.|==.
=|..==...=.|==..
=||.=.=||=|=..|=
|.=.===|||..=..|
|..==||=.|==|===
.=..===..=|.|||.
.======|||=|=.|=
.===|=|===[1m[97mT[0m===||
=|||...|==..|=.|
=.=|=.=..=.||==|
||=|=...|==.=|==
|=.=||===.|||===
||.|==.|.|.||=||
Before you go in, you should determine the [1m[97mrisk level[0m of the area. For the rectangle that has a
top-left corner of region 0,0 and a bottom-right corner of the region containing the target, add up
the risk level of each individual region: 0 for rocky regions, 1 for wet regions, and 2 for narrow
regions.
In the cave system above, because the mouth is at 0,0 and the target is at 10,10, adding up the risk
level of all regions with an X coordinate from 0 to 10 and a Y coordinate from 0 to 10, this total
is [1m[97m114[0m.
[1m[97mWhat is the total risk level for the smallest rectangle that includes 0,0 and the target's
coordinates?[0m
|
