diff options
Diffstat (limited to 'src/12')
| -rw-r--r-- | src/12/input | 34 | ||||
| -rw-r--r-- | src/12/part1 | 99 | ||||
| -rw-r--r-- | src/12/part2 | 49 | ||||
| -rw-r--r-- | src/12/solve.py | 53 |
4 files changed, 235 insertions, 0 deletions
diff --git a/src/12/input b/src/12/input new file mode 100644 index 0000000..6dcf208 --- /dev/null +++ b/src/12/input @@ -0,0 +1,34 @@ +initial state: ##..#.#.#..##..#..##..##..#.#....#.....##.#########...#.#..#..#....#.###.###....#..........###.#.#.. + +..##. => . +..... => . +##..# => . +...#. => . +#.... => . +...## => # +.#.#. => . +#..#. => # +##.#. => . +#..## => . +..#.. => . +#.#.# => . +###.# => . +###.. => . +.#... => # +.##.# => . +##... => # +..### => . +####. => . +#...# => # +.#..# => # +##### => # +..#.# => # +.#.## => # +#.### => . +....# => . +.###. => . +.#### => # +.##.. => . +##.## => # +#.##. => # +#.#.. => # diff --git a/src/12/part1 b/src/12/part1 new file mode 100644 index 0000000..ad06d34 --- /dev/null +++ b/src/12/part1 @@ -0,0 +1,99 @@ +--- Day 12: Subterranean Sustainability --- + +The year 518 is significantly more underground than your history books implied. Either that, or +you've arrived in a vast cavern network under the North Pole. + +After exploring a little, you discover a long tunnel that contains a row of small pots as far as you +can see to your left and right. A few of them contain plants - someone is trying to grow things in +these geothermally-heated caves. + +The pots are numbered, with 0 in front of you. To the left, the pots are numbered -1, -2, -3, and +so on; to the right, 1, 2, 3.... Your puzzle input contains a list of pots from 0 to the right and +whether they do (#) or do not (.) currently contain a plant, the [1m[97minitial state[0m. (No other pots +currently contain plants.) For example, an initial state of #..##.... indicates that pots 0, 3, and +4 currently contain plants. + +Your puzzle input also contains some notes you find on a nearby table: someone has been trying to +figure out how these plants [1m[97mspread[0m to nearby pots. Based on the notes, for each generation of +plants, a given pot has or does not have a plant based on whether that pot (and the two pots on +either side of it) had a plant in the last generation. These are written as LLCRR => N, where L are +pots to the left, C is the current pot being considered, R are the pots to the right, and N is +whether the current pot will have a plant in the next generation. For example: + + + - A note like ..#.. => . means that a pot that contains a plant but with no plants within two pots +of it will not have a plant in it during the next generation. + + - A note like ##.## => . means that an empty pot with two plants on each side of it will remain +empty in the next generation. + + - A note like .##.# => # means that a pot has a plant in a given generation if, in the previous +generation, there were plants in that pot, the one immediately to the left, and the one two pots to +the right, but not in the ones immediately to the right and two to the left. + + +It's not clear what these plants are for, but you're sure it's important, so you'd like to make sure +the current configuration of plants is sustainable by determining what will happen after [1m[97m20 +generations[0m. + +For example, given the following input: + +initial state: #..#.#..##......###...### + +...## => # +..#.. => # +.#... => # +.#.#. => # +.#.## => # +.##.. => # +.#### => # +#.#.# => # +#.### => # +##.#. => # +##.## => # +###.. => # +###.# => # +####. => # + +For brevity, in this example, only the combinations which do produce a plant are listed. (Your input +includes all possible combinations.) Then, the next 20 generations will look like this: + + 1 2 3 + 0 0 0 0 + 0: ...#..#.#..##......###...###........... + 1: ...#...#....#.....#..#..#..#........... + 2: ...##..##...##....#..#..#..##.......... + 3: ..#.#...#..#.#....#..#..#...#.......... + 4: ...#.#..#...#.#...#..#..##..##......... + 5: ....#...##...#.#..#..#...#...#......... + 6: ....##.#.#....#...#..##..##..##........ + 7: ...#..###.#...##..#...#...#...#........ + 8: ...#....##.#.#.#..##..##..##..##....... + 9: ...##..#..#####....#...#...#...#....... +10: ..#.#..#...#.##....##..##..##..##...... +11: ...#...##...#.#...#.#...#...#...#...... +12: ...##.#.#....#.#...#.#..##..##..##..... +13: ..#..###.#....#.#...#....#...#...#..... +14: ..#....##.#....#.#..##...##..##..##.... +15: ..##..#..#.#....#....#..#.#...#...#.... +16: .#.#..#...#.#...##...#...#.#..##..##... +17: ..#...##...#.#.#.#...##...#....#...#... +18: ..##.#.#....#####.#.#.#...##...##..##.. +19: .#..###.#..#.#.#######.#.#.#..#.#...#.. +20: .#....##....#####...#######....#.#..##. + +The generation is shown along the left, where 0 is the initial state. The pot numbers are shown +along the top, where 0 labels the center pot, negative-numbered pots extend to the left, and +positive pots extend toward the right. Remember, the initial state begins at pot 0, which is not the +leftmost pot used in this example. + +After one generation, only seven plants remain. The one in pot 0 matched the rule looking for +..#.., the one in pot 4 matched the rule looking for .#.#., pot 9 matched .##.., and so on. + +In this example, after 20 generations, the pots shown as # contain plants, the furthest left of +which is pot -2, and the furthest right of which is pot 34. Adding up all the numbers of +plant-containing pots after the 20th generation produces [1m[97m325[0m. + +[1m[97mAfter 20 generations, what is the sum of the numbers of all pots which contain a plant?[0m + + diff --git a/src/12/part2 b/src/12/part2 new file mode 100644 index 0000000..1fec84f --- /dev/null +++ b/src/12/part2 @@ -0,0 +1,49 @@ +--- Part Two --- + +All this drifting around in space makes you wonder about the nature of the universe. Does history +really repeat itself? You're curious whether the moons will ever return to a previous state. + +Determine [1m[97mthe number of steps[0m that must occur before all of the moons' [1m[97mpositions and velocities[0m +exactly match a previous point in time. + +For example, the first example above takes 2772 steps before they exactly match a previous point in +time; it eventually returns to the initial state: + +After 0 steps: +pos=<x= -1, y= 0, z= 2>, vel=<x= 0, y= 0, z= 0> +pos=<x= 2, y=-10, z= -7>, vel=<x= 0, y= 0, z= 0> +pos=<x= 4, y= -8, z= 8>, vel=<x= 0, y= 0, z= 0> +pos=<x= 3, y= 5, z= -1>, vel=<x= 0, y= 0, z= 0> + +After 2770 steps: +pos=<x= 2, y= -1, z= 1>, vel=<x= -3, y= 2, z= 2> +pos=<x= 3, y= -7, z= -4>, vel=<x= 2, y= -5, z= -6> +pos=<x= 1, y= -7, z= 5>, vel=<x= 0, y= -3, z= 6> +pos=<x= 2, y= 2, z= 0>, vel=<x= 1, y= 6, z= -2> + +After 2771 steps: +pos=<x= -1, y= 0, z= 2>, vel=<x= -3, y= 1, z= 1> +pos=<x= 2, y=-10, z= -7>, vel=<x= -1, y= -3, z= -3> +pos=<x= 4, y= -8, z= 8>, vel=<x= 3, y= -1, z= 3> +pos=<x= 3, y= 5, z= -1>, vel=<x= 1, y= 3, z= -1> + +After 2772 steps: +pos=<x= -1, y= 0, z= 2>, vel=<x= 0, y= 0, z= 0> +pos=<x= 2, y=-10, z= -7>, vel=<x= 0, y= 0, z= 0> +pos=<x= 4, y= -8, z= 8>, vel=<x= 0, y= 0, z= 0> +pos=<x= 3, y= 5, z= -1>, vel=<x= 0, y= 0, z= 0> + +Of course, the universe might last for a [1m[97mvery long time[0m before repeating. Here's a copy of the +second example from above: + +<x=-8, y=-10, z=0> +<x=5, y=5, z=10> +<x=2, y=-7, z=3> +<x=9, y=-8, z=-3> + +This set of initial positions takes 4686774924 steps before it repeats a previous state! Clearly, +you might need to [1m[97mfind a more efficient way to simulate the universe[0m. + +[1m[97mHow many steps does it take[0m to reach the first state that exactly matches a previous state? + + diff --git a/src/12/solve.py b/src/12/solve.py new file mode 100644 index 0000000..a688376 --- /dev/null +++ b/src/12/solve.py @@ -0,0 +1,53 @@ +import sys
+sys.path.append("../common")
+import aoc
+
+lines = aoc.data.split("\n")
+istate = lines[0].split(": ")[1]
+rules = [l.split(" => ") for l in lines[2:] if l != ""]
+rules = [r[0] for r in rules if r[1] == "#"]
+
+def next_gen(pots):
+ pmin = min(pots)
+ pmax = max(pots)
+ npots = list()
+ for i in range(pmin-4, pmax+1):
+ for r in rules:
+ match = True
+ for j in range(5):
+ if (r[j] == "#") != ((i+j) in pots):
+ match = False
+ break
+ if match:
+ npots.append(i+2)
+ break
+ return npots
+
+def get_pots():
+ pots = list()
+ for i in range(len(istate)):
+ if istate[i] == "#":
+ pots.append(i)
+ return pots
+
+def solve1(args):
+ pots = get_pots()
+ for i in range(20):
+ pots = next_gen(pots)
+ return sum(pots)
+
+def solve2(args):
+ pots = get_pots()
+ psum = sum(pots)
+ pdif = None
+ i = 0
+ while (True):
+ pots = next_gen(pots)
+ i += 1
+ csum = sum(pots)
+ if pdif == csum - psum:
+ return csum + pdif * (50000000000 - 164)
+ pdif = csum - psum
+ psum = csum
+
+aoc.run(solve1, solve2, sols=[1987, 1150000000358])
|