part1 (4925B)
1--- Day 22: Mode Maze --- 2 3This is it, your final stop: the year -483. It's snowing and dark outside; the only light you can 4see is coming from a small cottage in the distance. You make your way there and knock on the door. 5 6A portly man with a large, white beard answers the door and invites you inside. For someone living 7near the North Pole in -483, he must not get many visitors, but he doesn't act surprised to see you. 8Instead, he offers you some milk and cookies. 9 10After talking for a while, he asks a favor of you. His friend hasn't come back in a few hours, and 11he's not sure where he is. Scanning the region briefly, you discover one life signal in a cave 12system nearby; his friend must have taken shelter there. The man asks if you can go there to 13retrieve his friend. 14 15The cave is divided into square [1m[97mregions[0m which are either dominantly [1m[97mrocky[0m, [1m[97mnarrow[0m, or 16[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 17integers and zero or greater. (Adjacent regions can be the same type.) 18 19The scan (your puzzle input) is not very detailed: it only reveals the [1m[97mdepth[0m of the cave system and 20the [1m[97mcoordinates of the target[0m. However, it does not reveal the type of each region. The mouth of the 21cave is at 0,0. 22 23The man explains that due to the unusual geology in the area, there is a method to determine any 24region's type based on its [1m[97merosion level[0m. The erosion level of a region can be determined from its 25[1m[97mgeologic index[0m. The geologic index can be determined using the first rule that applies from the list 26below: 27 28 29 - The region at 0,0 (the mouth of the cave) has a geologic index of 0. 30 31 - The region at the coordinates of the target has a geologic index of 0. 32 33 - If the region's Y coordinate is 0, the geologic index is its X coordinate times 16807. 34 35 - If the region's X coordinate is 0, the geologic index is its Y coordinate times 48271. 36 37 - Otherwise, the region's geologic index is the result of multiplying the erosion 38[1m[97mlevels[0m of the regions at X-1,Y and X,Y-1. 39 40 41A region's [1m[97merosion level[0m is its [1m[97mgeologic index[0m plus the cave system's [1m[97mdepth[0m, all modulo 20183. Then: 42 43 44 - If the [1m[97merosion level modulo 3[0m is 0, the region's type is [1m[97mrocky[0m. 45 46 - If the [1m[97merosion level modulo 3[0m is 1, the region's type is [1m[97mwet[0m. 47 48 - If the [1m[97merosion level modulo 3[0m is 2, the region's type is [1m[97mnarrow[0m. 49 50 51For example, suppose the cave system's depth is 510 and the target's coordinates are 10,10. Using % 52to represent the modulo operator, the cavern would look as follows: 53 54 55 - At 0,0, the geologic index is 0. The erosion level is (0 + 510) % 20183 = 510. The type is 510 % 563 = 0, [1m[97mrocky[0m. 57 58 - At 1,0, because the Y coordinate is 0, the geologic index is 1 * 16807 = 16807. The erosion level 59is (16807 + 510) % 20183 = 17317. The type is 17317 % 3 = 1, [1m[97mwet[0m. 60 61 - At 0,1, because the X coordinate is 0, the geologic index is 1 * 48271 = 48271. The erosion 62level is (48271 + 510) % 20183 = 8415. The type is 8415 % 3 = 0, [1m[97mrocky[0m. 63 64 - At 1,1, neither coordinate is 0 and it is not the coordinate of the target, so the geologic index 65is the erosion level of 0,1 (8415) times the erosion level of 1,0 (17317), 8415 * 17317 = 145722555. 66The erosion level is (145722555 + 510) % 20183 = 1805. The type is 1805 % 3 = 2, 67[1m[97mnarrow[0m. 68 69 - At 10,10, because they are the target's coordinates, the geologic index is 0. The erosion level 70is (0 + 510) % 20183 = 510. The type is 510 % 3 = 0, [1m[97mrocky[0m. 71 72 73Drawing this same cave system with rocky as ., wet as =, narrow as |, the mouth as M, the target as 74T, with 0,0 in the top-left corner, X increasing to the right, and Y increasing downward, the 75top-left corner of the map looks like this: 76 77[1m[97mM[0m=.|=.|.|=.|=|=. 78.|=|=|||..|.=... 79.==|....||=..|== 80=.|....|.==.|==. 81=|..==...=.|==.. 82=||.=.=||=|=..|= 83|.=.===|||..=..| 84|..==||=.|==|=== 85.=..===..=|.|||. 86.======|||=|=.|= 87.===|=|===[1m[97mT[0m===|| 88=|||...|==..|=.| 89=.=|=.=..=.||==| 90||=|=...|==.=|== 91|=.=||===.|||=== 92||.|==.|.|.||=|| 93 94Before you go in, you should determine the [1m[97mrisk level[0m of the area. For the rectangle that has a 95top-left corner of region 0,0 and a bottom-right corner of the region containing the target, add up 96the risk level of each individual region: 0 for rocky regions, 1 for wet regions, and 2 for narrow 97regions. 98 99In the cave system above, because the mouth is at 0,0 and the target is at 10,10, adding up the risk 100level of all regions with an X coordinate from 0 to 10 and a Y coordinate from 0 to 10, this total 101is [1m[97m114[0m. 102 103[1m[97mWhat is the total risk level for the smallest rectangle that includes 0,0 and the target's 104coordinates?[0m 105 106