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/07/input | 101 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/07/part1 | 65 +++++++++++++++++++++++++++++++++++ src/07/part2 | 54 +++++++++++++++++++++++++++++ src/07/solve.py | 105 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 325 insertions(+) create mode 100644 src/07/input create mode 100644 src/07/part1 create mode 100644 src/07/part2 create mode 100644 src/07/solve.py (limited to 'src/07') diff --git a/src/07/input b/src/07/input new file mode 100644 index 0000000..77b5f0c --- /dev/null +++ b/src/07/input @@ -0,0 +1,101 @@ +Step S must be finished before step V can begin. +Step J must be finished before step T can begin. +Step N must be finished before step Q can begin. +Step O must be finished before step H can begin. +Step I must be finished before step C can begin. +Step Y must be finished before step R can begin. +Step K must be finished before step B can begin. +Step A must be finished before step C can begin. +Step B must be finished before step D can begin. +Step W must be finished before step T can begin. +Step E must be finished before step V can begin. +Step Q must be finished before step L can begin. +Step U must be finished before step P can begin. +Step R must be finished before step C can begin. +Step V must be finished before step M can begin. +Step X must be finished before step P can begin. +Step G must be finished before step T can begin. +Step T must be finished before step Z can begin. +Step Z must be finished before step M can begin. +Step F must be finished before step C can begin. +Step M must be finished before step L can begin. +Step D must be finished before step C can begin. +Step H must be finished before step L can begin. +Step L must be finished before step P can begin. +Step P must be finished before step C can begin. +Step S must be finished before step Q can begin. +Step M must be finished before step P can begin. +Step S must be finished before step T can begin. +Step U must be finished before step T can begin. +Step X must be finished before step H can begin. +Step Q must be finished before step G can begin. +Step Y must be finished before step U can begin. +Step H must be finished before step C can begin. +Step O must be finished before step F can begin. +Step S must be finished before step P can begin. +Step B must be finished before step E can begin. +Step S must be finished before step D can begin. +Step R must be finished before step X can begin. +Step Z must be finished before step D can begin. +Step J must be finished before step C can begin. +Step Z must be finished before step F can begin. +Step K must be finished before step T can begin. +Step T must be finished before step H can begin. +Step E must be finished before step H can begin. +Step D must be finished before step L can begin. +Step O must be finished before step A can begin. +Step V must be finished before step T can begin. +Step V must be finished before step X can begin. +Step Q must be finished before step X can begin. +Step O must be finished before step K can begin. +Step L must be finished before step C can begin. +Step W must be finished before step H can begin. +Step I must be finished before step T can begin. +Step M must be finished before step H can begin. +Step V must be finished before step G can begin. +Step K must be finished before step P can begin. +Step E must be finished before step X can begin. +Step V must be finished before step C can begin. +Step Y must be finished before step W can begin. +Step J must be finished before step G can begin. +Step B must be finished before step C can begin. +Step B must be finished before step Z can begin. +Step K must be finished before step R can begin. +Step Y must be finished before step V can begin. +Step X must be finished before step G can begin. +Step J must be finished before step K can begin. +Step A must be finished before step M can begin. +Step T must be finished before step M can begin. +Step W must be finished before step D can begin. +Step G must be finished before step F can begin. +Step A must be finished before step B can begin. +Step W must be finished before step F can begin. +Step Y must be finished before step P can begin. +Step B must be finished before step V can begin. +Step N must be finished before step G can begin. +Step J must be finished before step H can begin. +Step S must be finished before step L can begin. +Step A must be finished before step R can begin. +Step X must be finished before step D can begin. +Step Y must be finished before step M can begin. +Step H must be finished before step P can begin. +Step F must be finished before step D can begin. +Step S must be finished before step G can begin. +Step K must be finished before step C can begin. +Step W must be finished before step Z can begin. +Step A must be finished before step Z can begin. +Step O must be finished before step Y can begin. +Step U must be finished before step C can begin. +Step X must be finished before step M can begin. +Step Y must be finished before step A can begin. +Step F must be finished before step P can begin. +Step J must be finished before step Y can begin. +Step R must be finished before step G can begin. +Step Y must be finished before step Q can begin. +Step D must be finished before step P can begin. +Step O must be finished before step U can begin. +Step O must be finished before step I can begin. +Step E must be finished before step L can begin. +Step G must be finished before step Z can begin. +Step T must be finished before step F can begin. +Step Q must be finished before step F can begin. diff --git a/src/07/part1 b/src/07/part1 new file mode 100644 index 0000000..2006578 --- /dev/null +++ b/src/07/part1 @@ -0,0 +1,65 @@ +--- Day 7: The Sum of Its Parts --- + +You find yourself standing on a snow-covered coastline; apparently, you landed a little off course. +The region is too hilly to see the North Pole from here, but you do spot some Elves that seem to be +trying to unpack something that washed ashore. It's quite cold out, so you decide to risk creating a +paradox by asking them for directions. + +"Oh, are you the search party?" Somehow, you can understand whatever Elves from the year 1018 speak; +you assume it's Ancient Nordic Elvish. Could the device on your wrist also be a translator? "Those +clothes don't look very warm; take this." They hand you a heavy coat. + +"We do need to find our way back to the North Pole, but we have higher priorities at the moment. You +see, believe it or not, this box contains something that will solve all of Santa's transportation +problems - at least, that's what it looks like from the pictures in the instructions." It doesn't +seem like they can read whatever language it's in, but you can: "Sleigh kit. Some assembly +required." + +"'Sleigh'? What a wonderful name! You must help us assemble this 'sleigh' at once!" They start +excitedly pulling more parts out of the box. + +The instructions specify a series of steps and requirements about which steps must be finished +before others can begin (your puzzle input). Each step is designated by a single letter. For +example, suppose you have the following instructions: + +Step C must be finished before step A can begin. +Step C must be finished before step F can begin. +Step A must be finished before step B can begin. +Step A must be finished before step D can begin. +Step B must be finished before step E can begin. +Step D must be finished before step E can begin. +Step F must be finished before step E can begin. + +Visually, these requirements look like this: + + -->A--->B-- + / \ \ +C -->D----->E + \ / + ---->F----- + +Your first goal is to determine the order in which the steps should be completed. If more than one +step is ready, choose the step which is first alphabetically. In this example, the steps would be +completed as follows: + + + - Only C is available, and so it is done first. + + - Next, both A and F are available. A is first alphabetically, so it is done next. + + - Then, even though F was available earlier, steps B and D are now also available, and +B is the first alphabetically of the three. + + - After that, only D and F are available. E is not available because only some of its prerequisites +are complete. Therefore, D is completed next. + + - F is the only choice, so it is done next. + + - Finally, E is completed. + + +So, in this example, the correct order is CABDFE. + +In what order should the steps in your instructions be completed? + + diff --git a/src/07/part2 b/src/07/part2 new file mode 100644 index 0000000..d79d8a1 --- /dev/null +++ b/src/07/part2 @@ -0,0 +1,54 @@ +--- Part Two --- + +It's no good - in this configuration, the amplifiers can't generate a large enough output signal to +produce the thrust you'll need. The Elves quickly talk you through rewiring the amplifiers into a +feedback loop: + + O-------O O-------O O-------O O-------O O-------O +0 -+->| Amp A |->| Amp B |->| Amp C |->| Amp D |->| Amp E |-. + | O-------O O-------O O-------O O-------O O-------O | + | | + '--------------------------------------------------------+ + | + v + (to thrusters) + +Most of the amplifiers are connected as they were before; amplifier A's output is connected to +amplifier B's input, and so on. However, the output from amplifier E is now connected into amplifier +A's input. This creates the feedback loop: the signal will be sent through the amplifiers +many times. + +In feedback loop mode, the amplifiers need totally different phase settings: integers from 5 to 9, +again each used exactly once. These settings will cause the Amplifier Controller Software to +repeatedly take input and produce output many times before halting. Provide each amplifier its phase +setting at its first input instruction; all further input/output instructions are for signals. + +Don't restart the Amplifier Controller Software on any amplifier during this process. Each one +should continue receiving and sending signals until it halts. + +All signals sent or received in this process will be between pairs of amplifiers except the very +first signal and the very last signal. To start the process, a 0 signal is sent to amplifier A's +input exactly once. + +Eventually, the software on the amplifiers will halt after they have processed the final loop. When +this happens, the last output signal from amplifier E is sent to the thrusters. Your job is to +find the largest output signal that can be sent to the thrusters using the new phase settings and +feedback loop arrangement. + +Here are some example programs: + + + - Max thruster signal 139629729 (from phase setting sequence 9,8,7,6,5): +3,26,1001,26,-4,26,3,27,1002,27,2,27,1,27,26, +27,4,27,1001,28,-1,28,1005,28,6,99,0,0,5 + + - Max thruster signal 18216 (from phase setting sequence 9,7,8,5,6): +3,52,1001,52,-5,52,3,53,1,52,56,54,1007,54,5,55,1005,55,26,1001,54, +-5,54,1105,1,12,1,53,54,53,1008,54,0,55,1001,55,1,55,2,53,55,53,4, +53,1001,56,-1,56,1005,56,6,99,0,0,0,0,10 + + +Try every combination of the new phase settings on the amplifier feedback loop. What is the highest +signal that can be sent to the thrusters? + + diff --git a/src/07/solve.py b/src/07/solve.py new file mode 100644 index 0000000..8d7c708 --- /dev/null +++ b/src/07/solve.py @@ -0,0 +1,105 @@ +import sys +sys.path.append("../common") +import aoc + +data = aoc.data.split("\n") + +def remove_reqs(req, insts): + for res in insts: + if req in insts[res]: + insts[res].remove(req) + +def parse_entry(l): + split = l.split(" ") + firstl = split[1] + nextl = split[-3] + return firstl, nextl + +def gen_insts(): + global data + data = [parse_entry(l) for l in data if len(l) != 0] + + insts = dict() + + for ins in data: + req = ins[0] + res = ins[1] + if res not in insts: + insts[res] = [ req ] + else: + insts[res].append(req) + + values = list(insts.values())[:] + for reslist in values: + for res in reslist: + if res not in insts: + insts[res] = [] + + return insts + +def overlap(arr1, arr2): + for a1 in arr1: + if a1 in arr2: + return True + return False + +def checkfail(workers): + done = True + for w in workers: + if w[2]: + done = False + break + return done + +def solve1(args): + insts = gen_insts() + + i = 0 + plan = list() + while i < len(insts): + res = sorted(insts.keys())[i] # alphabetically + if len(insts[res]) == 0: + plan.append(res) + insts.pop(res, None) + remove_reqs(res, insts) + i = 0 + else: + i += 1 + + return "".join(plan) + +def solve2(args): + insts = gen_insts() + + # worker: (task, time, done) + workers = [["", 0, False] for x in range(5)] + + time = -1 + stop = False + while not stop: + time += 1 + for i in range(len(workers)): + w = workers[i] + if time >= w[1]: + if w[2]: + remove_reqs(w[0], insts) + aoc.debug("end : " + str(i) + " - " + str((w[0], w[1]))) + w[2] = False + if len(insts) == 0 and checkfail(workers): + stop = True + break + + for i in range(len(workers)): + w = workers[i] + if time >= w[1]: + for res in sorted(insts.keys()): + if len(insts[res]) == 0: + wtime = time + ord(res)-65+1 + 60 + aoc.debug("start : " + str(i) + " - " + str((res, time))) + w[:] = (res, wtime, True) + insts.pop(res, None) + break + + return time + +aoc.run(solve1, solve2, sols=["JNOIKSYABEQRUVWXGTZFDMHLPC", 1099]) -- cgit v1.2.3-71-gd317