351 lines
11 KiB
Text
351 lines
11 KiB
Text
|
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 *regions* which are either dominantly *rocky*, *narrow*, or *wet* (called its *type*). Each region occupies exactly one *coordinate* 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 *depth* of the cave system and the *coordinates of the target*. 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 *erosion level*. The erosion level of a region can be determined from its *geologic index*. 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 *levels* of the regions at `X-1,Y` and `X,Y-1`.
|
||
|
|
|
||
|
|
A region's *erosion level* is its *geologic index* plus the cave system's *depth*, all [modulo](https://en.wikipedia.org/wiki/Modulo_operation) `20183`. Then:
|
||
|
|
|
||
|
|
* If the *erosion level modulo `3`* is `0`, the region's type is *rocky*.
|
||
|
|
* If the *erosion level modulo `3`* is `1`, the region's type is *wet*.
|
||
|
|
* If the *erosion level modulo `3`* is `2`, the region's type is *narrow*.
|
||
|
|
|
||
|
|
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`, *rocky*.
|
||
|
|
* 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`, *wet*.
|
||
|
|
* 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`, *rocky*.
|
||
|
|
* 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`, *narrow*.
|
||
|
|
* 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`, *rocky*.
|
||
|
|
|
||
|
|
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:
|
||
|
|
|
||
|
|
```
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
.|=|=|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..===..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===T===||
|
||
|
|
=|||...|==..|=.|
|
||
|
|
=.=|=.=..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
```
|
||
|
|
|
||
|
|
Before you go in, you should determine the *risk level* 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 `*114*`.
|
||
|
|
|
||
|
|
*What is the total risk level for the smallest rectangle that includes `0,0` and the target's coordinates?*
|
||
|
|
|
||
|
|
Your puzzle answer was `11810`.
|
||
|
|
|
||
|
|
\--- Part Two ---
|
||
|
|
----------
|
||
|
|
|
||
|
|
Okay, it's time to go rescue the man's friend.
|
||
|
|
|
||
|
|
As you leave, he hands you some tools: a *torch* and some *climbing gear*. You can't equip both tools at once, but you can choose to use *neither*.
|
||
|
|
|
||
|
|
Tools can only be used in certain regions:
|
||
|
|
|
||
|
|
* In *rocky* regions, you can use the *climbing gear* or the *torch*. You cannot use *neither* (you'll likely slip and fall).
|
||
|
|
* In *wet* regions, you can use the *climbing gear* or *neither* tool. You cannot use the *torch* (if it gets wet, you won't have a light source).
|
||
|
|
* In *narrow* regions, you can use the *torch* or *neither* tool. You cannot use the *climbing gear* (it's too bulky to fit).
|
||
|
|
|
||
|
|
You start at `0,0` (the mouth of the cave) with *the torch equipped* and must reach the target coordinates as quickly as possible. The regions with negative `X` or `Y` are solid rock and cannot be traversed. The fastest route might involve entering regions beyond the `X` or `Y` coordinate of the target.
|
||
|
|
|
||
|
|
You can *move to an adjacent region* (up, down, left, or right; never diagonally) if your currently equipped tool allows you to enter that region. Moving to an adjacent region takes *one minute*. (For example, if you have the *torch* equipped, you can move between *rocky* and *narrow* regions, but cannot enter *wet* regions.)
|
||
|
|
|
||
|
|
You can *change your currently equipped tool or put both away* if your new equipment would be valid for your current region. Switching to using the *climbing gear*, *torch*, or *neither* always takes *seven minutes*, regardless of which tools you start with. (For example, if you are in a *rocky* region, you can switch from the *torch* to the *climbing gear*, but you cannot switch to *neither*.)
|
||
|
|
|
||
|
|
Finally, once you reach the target, you need the *torch* equipped before you can find him in the dark. The target is always in a *rocky* region, so if you arrive there with *climbing gear* equipped, you will need to spend seven minutes switching to your torch.
|
||
|
|
|
||
|
|
For example, using the same cave system as above, starting in the top left corner (`0,0`) and moving to the bottom right corner (the target, `10,10`) as quickly as possible, one possible route is as follows, with your current position marked `X`:
|
||
|
|
|
||
|
|
```
|
||
|
|
Initially:
|
||
|
|
X=.|=.|.|=.|=|=.
|
||
|
|
.|=|=|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..===..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===T===||
|
||
|
|
=|||...|==..|=.|
|
||
|
|
=.=|=.=..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
Down:
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
X|=|=|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..===..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===T===||
|
||
|
|
=|||...|==..|=.|
|
||
|
|
=.=|=.=..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
Right:
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
.X=|=|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..===..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===T===||
|
||
|
|
=|||...|==..|=.|
|
||
|
|
=.=|=.=..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
Switch from using the torch to neither tool:
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
.X=|=|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..===..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===T===||
|
||
|
|
=|||...|==..|=.|
|
||
|
|
=.=|=.=..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
Right 3:
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
.|=|X|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..===..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===T===||
|
||
|
|
=|||...|==..|=.|
|
||
|
|
=.=|=.=..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
Switch from using neither tool to the climbing gear:
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
.|=|X|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..===..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===T===||
|
||
|
|
=|||...|==..|=.|
|
||
|
|
=.=|=.=..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
Down 7:
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
.|=|=|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..X==..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===T===||
|
||
|
|
=|||...|==..|=.|
|
||
|
|
=.=|=.=..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
Right:
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
.|=|=|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..=X=..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===T===||
|
||
|
|
=|||...|==..|=.|
|
||
|
|
=.=|=.=..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
Down 3:
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
.|=|=|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..===..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===T===||
|
||
|
|
=|||.X.|==..|=.|
|
||
|
|
=.=|=.=..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
Right:
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
.|=|=|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..===..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===T===||
|
||
|
|
=|||..X|==..|=.|
|
||
|
|
=.=|=.=..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
Down:
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
.|=|=|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..===..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===T===||
|
||
|
|
=|||...|==..|=.|
|
||
|
|
=.=|=.X..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
Right 4:
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
.|=|=|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..===..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===T===||
|
||
|
|
=|||...|==..|=.|
|
||
|
|
=.=|=.=..=X||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
Up 2:
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
.|=|=|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..===..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===X===||
|
||
|
|
=|||...|==..|=.|
|
||
|
|
=.=|=.=..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
Switch from using the climbing gear to the torch:
|
||
|
|
M=.|=.|.|=.|=|=.
|
||
|
|
.|=|=|||..|.=...
|
||
|
|
.==|....||=..|==
|
||
|
|
=.|....|.==.|==.
|
||
|
|
=|..==...=.|==..
|
||
|
|
=||.=.=||=|=..|=
|
||
|
|
|.=.===|||..=..|
|
||
|
|
|..==||=.|==|===
|
||
|
|
.=..===..=|.|||.
|
||
|
|
.======|||=|=.|=
|
||
|
|
.===|=|===X===||
|
||
|
|
=|||...|==..|=.|
|
||
|
|
=.=|=.=..=.||==|
|
||
|
|
||=|=...|==.=|==
|
||
|
|
|=.=||===.|||===
|
||
|
|
||.|==.|.|.||=||
|
||
|
|
|
||
|
|
```
|
||
|
|
|
||
|
|
This is tied with other routes as the *fastest way to reach the target*: `*45*` minutes. In it, `21` minutes are spent switching tools (three times, seven minutes each) and the remaining `24` minutes are spent moving.
|
||
|
|
|
||
|
|
*What is the fewest number of minutes you can take to reach the target?*
|
||
|
|
|
||
|
|
Your puzzle answer was `1015`.
|
||
|
|
|
||
|
|
Both parts of this puzzle are complete! They provide two gold stars: \*\*
|
||
|
|
|
||
|
|
At this point, you should [return to your Advent calendar](/2018) and try another puzzle.
|
||
|
|
|
||
|
|
If you still want to see it, you can [get your puzzle input](22/input).
|