From 87ab487d59fa85dbe2afa55cc841b02805ae42ca Mon Sep 17 00:00:00 2001 From: Louis Burda Date: Fri, 7 Apr 2023 17:18:18 -0400 Subject: Reorder days into src --- src/22/input | 2 ++ src/22/part1 | 106 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/22/part2 | 22 ++++++++++++ src/22/solve.py | 93 +++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 223 insertions(+) create mode 100644 src/22/input create mode 100644 src/22/part1 create mode 100644 src/22/part2 create mode 100644 src/22/solve.py (limited to 'src/22') diff --git a/src/22/input b/src/22/input new file mode 100644 index 0000000..9b643c6 --- /dev/null +++ b/src/22/input @@ -0,0 +1,2 @@ +depth: 4848 +target: 15,700 diff --git a/src/22/part1 b/src/22/part1 new file mode 100644 index 0000000..bb29305 --- /dev/null +++ b/src/22/part1 @@ -0,0 +1,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 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 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? + + diff --git a/src/22/part2 b/src/22/part2 new file mode 100644 index 0000000..fbcfdd7 --- /dev/null +++ b/src/22/part2 @@ -0,0 +1,22 @@ +--- Part Two --- + +After a while, you realize your shuffling skill won't improve much more with merely a single deck of +cards. You ask every 3D printer on the ship to make you some more cards while you check on the ship +repairs. While reviewing the work the droids have finished so far, you think you see Halley's Comet +fly past! + +When you get back, you discover that the 3D printers have combined their power to create for you a +single, giant, brand new, factory order deck of 119315717514047 space cards. + +Finally, a deck of cards worthy of shuffling! + +You decide to apply your complete shuffle process (your puzzle input) to the deck +101741582076661 times in a row. + +You'll need to be careful, though - one wrong move with this many cards and you might +overflow your entire ship! + +After shuffling your new, giant, factory order deck that many times, what number is on the card that +ends up in position 2020? + + diff --git a/src/22/solve.py b/src/22/solve.py new file mode 100644 index 0000000..375ae23 --- /dev/null +++ b/src/22/solve.py @@ -0,0 +1,93 @@ +import sys +sys.path.append("../common") +import aoc +import networkx + +adjacent = [[-1, 0], [0, -1], [1, 0], [0, 1]] + +# create symbol definitions +symbols = [".", "=", "|"] +rocky, wet, narrow = 0, 1, 2 +torch, gear, neither = 0, 1, 2 + +tooloptions = dict() +tooloptions[rocky] = (torch, gear) +tooloptions[wet] = (gear, neither) +tooloptions[narrow] = (torch, neither) + +# parse input file +def parse_input(si): + s = si.split("\n") + depth = int(s[0].split(": ")[1]) + target = [int(v) for v in s[1].split(": ")[1].split(",")] + return depth, target + +# get erosion level from geological index +def get_erosion_level(n): + return (n + depth) % 20183 + +# generate map of erosion types +def gen_map(): + grid = [[0 for x in range(mrange[0])] for y in range(mrange[1])] + + # generate values on x side + grid[0] = [get_erosion_level(x * 16807) for x in range(mrange[0])] + + # generate values on y side + for y in range(mrange[1]): + grid[y][0] = get_erosion_level(y * 48271) + + # fill in other positions + for y in range(1, mrange[1]): + for x in range(1, mrange[0]): + grid[y][x] = get_erosion_level(grid[y-1][x] * grid[y][x-1]) + + # mod 3 for env type + grid = [[grid[y][x] % 3 for x in range(mrange[0])] for y in range(mrange[1])] + + # start position is rocky + grid[target[1]][target[0]] = 0 + + return grid + +# define constants from input file +depth, target = parse_input(aoc.data) +mrange = (target[0] + 100, target[1] + 100) # 100 block padding for potential hook-paths + +vmap = gen_map() + +def risk_level(width, height): + risk = 0 + for y in range(height + 1): + for x in range(width + 1): + risk += vmap[y][x] + return risk + +def adj(p): + return [[p[0] + di[0], p[1] + di[1]] for di in adjacent] + +def dijkstra(): + graph = networkx.Graph() + for y in range(mrange[1]): + for x in range(mrange[0]): + tools = tooloptions[vmap[y][x]] + # always takes 7 minutes to switch, 2 z-options for each tool + graph.add_edge((x, y, tools[0]), (x, y, tools[1]), weight = 7) + for (nx, ny) in adj((x, y)): + if 0 <= nx < mrange[0] and 0 <= ny < mrange[1]: + ntools = tooloptions[vmap[ny][nx]] + # if tool is usable in both environments + for tool in [t for t in tools if t in ntools]: + # then it only takes 1 minute + graph.add_edge((x, y, tool), (nx, ny, tool), weight = 1) + + return networkx.dijkstra_path_length(graph, + (0, 0, torch), (target[0], target[1], torch)) + +def solve1(args): + return risk_level(target[0], target[1]) + +def solve2(args): + return dijkstra() + +aoc.run(solve1, solve2, sols=[11359, 976]) -- cgit v1.2.3-71-gd317