diff options
| -rw-r--r-- | 01/input (renamed from src/1/input.txt) | 0 | ||||
| -rw-r--r-- | 01/part1 | 55 | ||||
| -rw-r--r-- | 01/part2 | 42 | ||||
| -rw-r--r-- | 01/solve.py (renamed from src/1/solve.py) | 35 | ||||
| -rw-r--r-- | 02/input (renamed from src/2/input.txt) | 0 | ||||
| -rw-r--r-- | 02/part1 | 50 | ||||
| -rw-r--r-- | 02/part2 | 24 | ||||
| -rw-r--r-- | 02/solve.py (renamed from src/2/solve.py) | 29 | ||||
| -rw-r--r-- | 03/input (renamed from src/3/input.txt) | 0 | ||||
| -rw-r--r-- | 03/part1 | 63 | ||||
| -rw-r--r-- | 03/part2 | 11 | ||||
| -rw-r--r-- | 03/solve.py (renamed from src/3/solve.py) | 37 | ||||
| -rw-r--r-- | 04/input (renamed from src/4/input.txt) | 0 | ||||
| -rw-r--r-- | 04/part1 | 76 | ||||
| -rw-r--r-- | 04/part2 | 11 | ||||
| -rw-r--r-- | 04/solve.py (renamed from src/4/solve.py) | 49 | ||||
| -rw-r--r-- | 05/input (renamed from src/5/input.txt) | 0 | ||||
| -rw-r--r-- | 05/part1 | 40 | ||||
| -rw-r--r-- | 05/part2 | 30 | ||||
| -rw-r--r-- | 05/solve.py | 30 | ||||
| -rw-r--r-- | 06/input (renamed from src/6/input.txt) | 0 | ||||
| -rw-r--r-- | 06/part1 | 65 | ||||
| -rw-r--r-- | 06/part2 | 52 | ||||
| -rw-r--r-- | 06/solve.py | 76 | ||||
| -rw-r--r-- | 07/input (renamed from src/7/input.txt) | 0 | ||||
| -rw-r--r-- | 07/part1 | 65 | ||||
| -rw-r--r-- | 07/part2 | 46 | ||||
| -rw-r--r-- | 07/solve.py | 105 | ||||
| -rw-r--r-- | 08/input (renamed from src/8/input.txt) | 0 | ||||
| -rw-r--r-- | 08/part1 | 58 | ||||
| -rw-r--r-- | 08/part2 | 33 | ||||
| -rw-r--r-- | 08/solve.py | 43 | ||||
| -rw-r--r-- | 09/input (renamed from src/9/input.txt) | 0 | ||||
| -rw-r--r-- | 09/part1 | 78 | ||||
| -rw-r--r-- | 09/part2 | 7 | ||||
| -rw-r--r-- | 09/solve.py (renamed from src/9/solve.py) | 29 | ||||
| -rw-r--r-- | 10/input (renamed from src/10/input.txt) | 0 | ||||
| -rw-r--r-- | 10/part1 | 160 | ||||
| -rw-r--r-- | 10/part2 | 9 | ||||
| -rw-r--r-- | 10/solve.py | 105 | ||||
| -rw-r--r-- | 10/test-input.txt (renamed from src/10/test-input.txt) | 0 | ||||
| -rw-r--r-- | 11/input (renamed from src/11/input.txt) | 0 | ||||
| -rw-r--r-- | 11/part1 | 87 | ||||
| -rw-r--r-- | 11/part2 | 22 | ||||
| -rw-r--r-- | 11/solve.py (renamed from src/11/solve.py) | 36 | ||||
| -rw-r--r-- | 12/input (renamed from src/12/input.txt) | 0 | ||||
| -rw-r--r-- | 12/part1 | 99 | ||||
| -rw-r--r-- | 12/part2 | 9 | ||||
| -rw-r--r-- | 12/solve.py (renamed from src/12/solve.py) | 38 | ||||
| -rw-r--r-- | 13/input (renamed from src/13/input.txt) | 0 | ||||
| -rw-r--r-- | 13/part1 | 187 | ||||
| -rw-r--r-- | 13/part2 | 49 | ||||
| -rw-r--r-- | 13/solve.py (renamed from src/13/solve.py) | 67 | ||||
| -rw-r--r-- | 13/test1 | 7 | ||||
| -rw-r--r-- | 14/input (renamed from src/14/input.txt) | 0 | ||||
| -rw-r--r-- | 14/part1 | 69 | ||||
| -rw-r--r-- | 14/part2 | 19 | ||||
| -rw-r--r-- | 14/solve.py (renamed from src/14/solve.py) | 37 | ||||
| -rw-r--r-- | 15/input (renamed from src/15/input.txt) | 0 | ||||
| -rw-r--r-- | 15/part1 | 343 | ||||
| -rw-r--r-- | 15/part2 | 91 | ||||
| -rw-r--r-- | 15/solve.py (renamed from src/15/solve.py) | 172 | ||||
| -rw-r--r-- | 15/test1 | 7 | ||||
| -rw-r--r-- | 15/test2 | 7 | ||||
| -rw-r--r-- | 15/test3 | 7 | ||||
| -rw-r--r-- | 15/test4 | 7 | ||||
| -rw-r--r-- | 15/test5 | 9 | ||||
| -rw-r--r-- | 15/test6 | 7 | ||||
| -rw-r--r-- | 16/input (renamed from src/16/input.txt) | 0 | ||||
| -rw-r--r-- | 16/part1 | 136 | ||||
| -rw-r--r-- | 16/part2 | 8 | ||||
| -rw-r--r-- | 16/solve.py (renamed from src/16/solve.py) | 52 | ||||
| -rw-r--r-- | 17/.gitignore (renamed from src/17/.gitignore) | 0 | ||||
| -rw-r--r-- | 17/input (renamed from src/17/input.txt) | 0 | ||||
| -rw-r--r-- | 17/part1 | 177 | ||||
| -rw-r--r-- | 17/part2 | 10 | ||||
| -rw-r--r-- | 17/solve.py (renamed from src/17/solve.py) | 85 | ||||
| -rw-r--r-- | 17/test1 | 8 | ||||
| -rw-r--r-- | 18/input (renamed from src/18/input.txt) | 0 | ||||
| -rw-r--r-- | 18/part1 | 174 | ||||
| -rw-r--r-- | 18/part2 | 8 | ||||
| -rw-r--r-- | 18/solve.py (renamed from src/18/solve.py) | 63 | ||||
| -rw-r--r-- | 18/test1 | 10 | ||||
| -rw-r--r-- | 19/input (renamed from src/19/input.txt) | 0 | ||||
| -rw-r--r-- | 19/part1 | 92 | ||||
| -rw-r--r-- | 19/part2 | 8 | ||||
| -rw-r--r-- | 19/solve.py (renamed from src/19/solve.py) | 82 | ||||
| -rw-r--r-- | 19/test1 | 8 | ||||
| -rw-r--r-- | 20/.gitignore (renamed from src/20/.gitignore) | 0 | ||||
| -rw-r--r-- | 20/input (renamed from src/20/input.txt) | 0 | ||||
| -rw-r--r-- | 20/part1 | 187 | ||||
| -rw-r--r-- | 20/part2 | 8 | ||||
| -rw-r--r-- | 20/solve.py (renamed from src/20/solve.py) | 85 | ||||
| -rw-r--r-- | 20/test1 | 1 | ||||
| -rw-r--r-- | 21/input (renamed from src/21/input.txt) | 0 | ||||
| -rw-r--r-- | 21/part1 | 41 | ||||
| -rw-r--r-- | 21/part2 | 9 | ||||
| -rw-r--r-- | 21/solve.py (renamed from src/21/solve.py) | 73 | ||||
| -rw-r--r-- | 21/test1 | 8 | ||||
| -rw-r--r-- | 22/input (renamed from src/22/input.txt) | 0 | ||||
| -rw-r--r-- | 22/part1 | 105 | ||||
| -rw-r--r-- | 22/part2 | 302 | ||||
| -rw-r--r-- | 22/solve.py (renamed from src/22/solve.py) | 69 | ||||
| -rw-r--r-- | 23/input (renamed from src/23/input.txt) | 0 | ||||
| -rw-r--r-- | 23/part1 | 64 | ||||
| -rw-r--r-- | 23/part2 | 27 | ||||
| -rw-r--r-- | 23/solve.py (renamed from src/23/solve.py) | 52 | ||||
| -rw-r--r-- | 24/input (renamed from src/24/input.txt) | 0 | ||||
| -rw-r--r-- | 24/part1 | 199 | ||||
| -rw-r--r-- | 24/part2 | 150 | ||||
| -rw-r--r-- | 24/solve.py (renamed from src/24/solve.py) | 58 | ||||
| -rw-r--r-- | 25/input (renamed from src/25/input.txt) | 0 | ||||
| -rw-r--r-- | 25/part1 | 108 | ||||
| -rw-r--r-- | 25/part2 | 15 | ||||
| -rw-r--r-- | 25/solve.py | 50 | ||||
| -rw-r--r-- | 25/test1 | 10 | ||||
| -rw-r--r-- | 25/test2 | 10 | ||||
| -rw-r--r-- | 25/test3 | 8 | ||||
| -rw-r--r-- | 25/test4 | 10 | ||||
| -rw-r--r-- | Makefile | 15 | ||||
| -rw-r--r-- | README.md | 2 | ||||
| -rw-r--r-- | common/aoc.py | 35 | ||||
| -rw-r--r-- | data/template.py | 25 | ||||
| -rw-r--r-- | src/10/solve.py | 81 | ||||
| -rw-r--r-- | src/13/solve.py~ | 158 | ||||
| -rw-r--r-- | src/16/notes.txt | 47 | ||||
| -rw-r--r-- | src/24/notes.txt | 26 | ||||
| -rw-r--r-- | src/25/solve.py | 100 | ||||
| -rw-r--r-- | src/5/solve.py | 46 | ||||
| -rw-r--r-- | src/6/solve.py | 103 | ||||
| -rw-r--r-- | src/7/solve.py | 131 | ||||
| -rw-r--r-- | src/8/solve.py | 52 |
132 files changed, 4785 insertions, 1495 deletions
diff --git a/src/1/input.txt b/01/input index 419087f..419087f 100644 --- a/src/1/input.txt +++ b/01/input diff --git a/01/part1 b/01/part1 new file mode 100644 index 0000000..1675638 --- /dev/null +++ b/01/part1 @@ -0,0 +1,55 @@ +--- Day 1: Chronal Calibration --- + +"We've detected some temporal anomalies," one of Santa's Elves at the Temporal Anomaly Research and +Detection Instrument Station tells you. She sounded pretty worried when she called you down here. +"At 500-year intervals into the past, someone has been changing Santa's history!" + +"The good news is that the changes won't propagate to our time stream for another 25 days, and we +have a device" - she attaches something to your wrist - "that will let you fix the changes with no +such propagation delay. It's configured to send you 500 years further into the past every few days; +that was the best we could do on such short notice." + +"The bad news is that we are detecting roughly fifty anomalies throughout time; the device will +indicate fixed anomalies with stars. The other bad news is that we only have one device and you're +the best person for the job! Good lu--" She taps a button on the device and you suddenly feel like +you're falling. To save Christmas, you need to get all fifty stars by December 25th. + +Collect stars by solving puzzles. Two puzzles will be made available on each day in the Advent +calendar; the second puzzle is unlocked when you complete the first. Each puzzle grants one star. +Good luck! + +After feeling like you've been falling for a few minutes, you look at the device's tiny screen. +"Error: Device must be calibrated before first use. Frequency drift detected. Cannot maintain +destination lock." Below the message, the device shows a sequence of changes in frequency (your +puzzle input). A value like +6 means the current frequency increases by 6; a value like -3 means the +current frequency decreases by 3. + +For example, if the device displays frequency changes of +1, -2, +3, +1, then starting from a +frequency of zero, the following changes would occur: + + + - Current frequency 0, change of +1; resulting frequency 1. + + - Current frequency 1, change of -2; resulting frequency -1. + + - Current frequency -1, change of +3; resulting frequency 2. + + - Current frequency 2, change of +1; resulting frequency 3. + + +In this example, the resulting frequency is 3. + +Here are other example situations: + + + - +1, +1, +1 results in 3 + + - +1, +1, -2 results in 0 + + - -1, -2, -3 results in -6 + + +Starting with a frequency of zero, what is the resulting frequency after all of the changes in +frequency have been applied? + + diff --git a/01/part2 b/01/part2 new file mode 100644 index 0000000..d595eb7 --- /dev/null +++ b/01/part2 @@ -0,0 +1,42 @@ +--- Part Two --- + +You notice that the device repeats the same frequency change list over and over. To calibrate the +device, you need to find the first frequency it reaches twice. + +For example, using the same list of changes above, the device would loop as follows: + + + - Current frequency 0, change of +1; resulting frequency 1. + + - Current frequency 1, change of -2; resulting frequency -1. + + - Current frequency -1, change of +3; resulting frequency 2. + + - Current frequency 2, change of +1; resulting frequency 3. + + - (At this point, the device continues from the start of the list.) + + - Current frequency 3, change of +1; resulting frequency 4. + + - Current frequency 4, change of -2; resulting frequency 2, which has already been seen. + + +In this example, the first frequency reached twice is 2. Note that your device might need to repeat +its list of frequency changes many times before a duplicate frequency is found, and that duplicates +might be found while in the middle of processing the list. + +Here are other examples: + + + - +1, -1 first reaches 0 twice. + + - +3, +3, +4, -2, -4 first reaches 10 twice. + + - -6, +3, +8, +5, -6 first reaches 5 twice. + + - +7, +7, -2, -7, -4 first reaches 14 twice. + + +What is the first frequency your device reaches twice? + + diff --git a/src/1/solve.py b/01/solve.py index f02651d..d23d8d5 100644 --- a/src/1/solve.py +++ b/01/solve.py @@ -1,19 +1,19 @@ -from sys import argv as args
+import sys
+sys.path.append("../common")
+import aoc
-file = open("input.txt")
-data = [int(x) for x in file.readlines()]
-file.close()
+data = [int(l) for l in aoc.data.split("\n")]
-def solve1(): # answer: 411
- print(sum(data))
+def solve1(args):
+ return sum(data)
-def solve2(): # answer: 56360
+def solve2(args):
totshift = 0
fvals = list()
for c in data:
fvals.append(totshift)
totshift += c
- print("total shift: " + str(totshift))
+ aoc.debug("total shift: " + str(totshift))
doubles = list()
@@ -41,21 +41,8 @@ def solve2(): # answer: 56360 doubles.append([pos, fvals[inds[1]]])
i += 1
- if len(doubles) == 0: #fail
- return
+ assert(len(doubles) != 0)
- min = doubles[0]
- for d in doubles:
- if d[0] < min[0]:
- min = d
+ return min(doubles, key = lambda x: x[0])[1]
- print(min[1])
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
+aoc.run(solve1, solve2, sols=[411, 56360])
diff --git a/src/2/input.txt b/02/input index 0bb005f..0bb005f 100644 --- a/src/2/input.txt +++ b/02/input diff --git a/02/part1 b/02/part1 new file mode 100644 index 0000000..13365fe --- /dev/null +++ b/02/part1 @@ -0,0 +1,50 @@ +--- Day 2: Inventory Management System --- + +You stop falling through time, catch your breath, and check the screen on the device. "Destination +reached. Current Year: 1518. Current Location: North Pole Utility Closet 83N10." You made it! Now, +to find those anomalies. + +Outside the utility closet, you hear footsteps and a voice. "...I'm not sure either. But now that so +many people have chimneys, maybe he could sneak in that way?" Another voice responds, "Actually, +we've been working on a new kind of suit that would let him fit through tight spaces like that. But, +I heard that a few days ago, they lost the prototype fabric, the design plans, everything! Nobody on +the team can even seem to remember important details of the project!" + +"Wouldn't they have had enough fabric to fill several boxes in the warehouse? They'd be stored +together, so the box IDs should be similar. Too bad it would take forever to search the warehouse +for two similar box IDs..." They walk too far away to hear any more. + +Late at night, you sneak to the warehouse - who knows what kinds of paradoxes you could cause if you +were discovered - and use your fancy wrist device to quickly scan every box and produce a list of +the likely candidates (your puzzle input). + +To make sure you didn't miss any, you scan the likely candidate boxes again, counting the number +that have an ID containing exactly two of any letter and then separately counting those with exactly +three of any letter. You can multiply those two counts together to get a rudimentary checksum and +compare it to what your device predicts. + +For example, if you see the following box IDs: + + + - abcdef contains no letters that appear exactly two or three times. + + - bababc contains two a and three b, so it counts for both. + + - abbcde contains two b, but no letter appears exactly three times. + + - abcccd contains three c, but no letter appears exactly two times. + + - aabcdd contains two a and two d, but it only counts once. + + - abcdee contains two e. + + - ababab contains three a and three b, but it only counts once. + + +Of these box IDs, four of them contain a letter which appears exactly twice, and three of them +contain a letter which appears exactly three times. Multiplying these together produces a checksum +of 4 * 3 = 12. + +What is the checksum for your list of box IDs? + + diff --git a/02/part2 b/02/part2 new file mode 100644 index 0000000..ce0901a --- /dev/null +++ b/02/part2 @@ -0,0 +1,24 @@ +--- Part Two --- + +Confident that your list of box IDs is complete, you're ready to find the boxes full of prototype +fabric. + +The boxes will have IDs which differ by exactly one character at the same position in both strings. +For example, given the following box IDs: + +abcde +fghij +klmno +pqrst +fguij +axcye +wvxyz + +The IDs abcde and axcye are close, but they differ by two characters (the second and fourth). +However, the IDs fghij and fguij differ by exactly one character, the third (h and u). Those must be +the correct boxes. + +What letters are common between the two correct box IDs? (In the example above, this is found by +removing the differing character from either ID, producing fgij.) + + diff --git a/src/2/solve.py b/02/solve.py index 79e60e7..6b3594f 100644 --- a/src/2/solve.py +++ b/02/solve.py @@ -1,21 +1,21 @@ -from sys import argv as args
+import sys
+sys.path.append("../common")
+import aoc
-file = open("input.txt")
-data = [x.replace("\n","") for x in file.readlines()]
-file.close()
+data = aoc.data.split("\n")
-def solve1():
+def solve1(args):
doubles = 0
triples = 0
for s in data:
- counts = list((0,) * 26) # characters
+ counts = list((0,) * 26)
for c in s:
counts[ord(c[0])-97] += 1
if 2 in counts:
doubles += 1
if 3 in counts:
triples += 1
- print(doubles * triples)
+ return doubles * triples
def compare(s1, s2):
dif = 0
@@ -25,23 +25,16 @@ def compare(s1, s2): dif += 1
else:
same.append(s1[i])
- return(dif, same)
+ return (dif, same)
-def solve2():
+def solve2(args):
for i in range(len(data)):
for j in range(i, len(data)):
if i == j:
continue
res = compare(data[i], data[j])
if res[0] == 1:
- print("".join(res[1]))
- return
+ return "".join(res[1])
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-main()
+aoc.run(solve1, solve2, sols=[3952, "vtnikorkulbfejvyznqgdxpaw"])
diff --git a/src/3/input.txt b/03/input index 2947617..2947617 100644 --- a/src/3/input.txt +++ b/03/input diff --git a/03/part1 b/03/part1 new file mode 100644 index 0000000..fa86a57 --- /dev/null +++ b/03/part1 @@ -0,0 +1,63 @@ +--- Day 3: No Matter How You Slice It --- + +The Elves managed to locate the chimney-squeeze prototype fabric for Santa's suit (thanks to someone +who helpfully wrote its box IDs on the wall of the warehouse in the middle of the night). +Unfortunately, anomalies are still affecting them - nobody can even agree on how to cut the fabric. + +The whole piece of fabric they're working on is a very large square - at least 1000 inches on each +side. + +Each Elf has made a claim about which area of fabric would be ideal for Santa's suit. All claims +have an ID and consist of a single rectangle with edges parallel to the edges of the fabric. Each +claim's rectangle is defined as follows: + + + - The number of inches between the left edge of the fabric and the left edge of the rectangle. + + - The number of inches between the top edge of the fabric and the top edge of the rectangle. + + - The width of the rectangle in inches. + + - The height of the rectangle in inches. + + +A claim like #123 @ 3,2: 5x4 means that claim ID 123 specifies a rectangle 3 inches from the left +edge, 2 inches from the top edge, 5 inches wide, and 4 inches tall. Visually, it claims the square +inches of fabric represented by # (and ignores the square inches of fabric represented by .) in the +diagram below: + +........... +........... +...#####... +...#####... +...#####... +...#####... +........... +........... +........... + +The problem is that many of the claims overlap, causing two or more claims to cover part of the same +areas. For example, consider the following claims: + +#1 @ 1,3: 4x4 +#2 @ 3,1: 4x4 +#3 @ 5,5: 2x2 + +Visually, these claim the following areas: + +........ +...2222. +...2222. +.11XX22. +.11XX22. +.111133. +.111133. +........ + +The four square inches marked with X are claimed by both 1 and 2. (Claim 3, while adjacent to the +others, does not overlap either of them.) + +If the Elves all proceed with their own plans, none of them will have enough fabric. How many square +inches of fabric are within two or more claims? + + diff --git a/03/part2 b/03/part2 new file mode 100644 index 0000000..514ee56 --- /dev/null +++ b/03/part2 @@ -0,0 +1,11 @@ +--- Part Two --- + +Amidst the chaos, you notice that exactly one claim doesn't overlap by even a single square inch of +fabric with any other claim. If you can somehow draw attention to it, maybe the Elves will be able +to make Santa's suit after all! + +For example, in the claims above, only claim 3 is intact after all claims are made. + +What is the ID of the only claim that doesn't overlap? + + diff --git a/src/3/solve.py b/03/solve.py index 53dd245..766b00e 100644 --- a/src/3/solve.py +++ b/03/solve.py @@ -1,12 +1,12 @@ -from sys import argv as args
+import sys
+sys.path.append("../common")
+import aoc
-file = open("input.txt")
-data = [x for x in file.readlines()]
-file.close()
+data = aoc.data.split("\n")
#data = "#1 @ 1,3: 4x4","#2 @ 3,1: 4x4","#3 @ 5,5: 2x2"
-def parserect(l):
+def parse_rect(l):
split = l.split("@")
id = int(split[0].replace("#",""))
split = split[1].split(":")
@@ -14,9 +14,9 @@ def parserect(l): size = [int(x) for x in split[1].split("x")]
return pos, size, id
-def createMap():
+def create_map():
global rectdata
- rectdata = [parserect(l) for l in data]
+ rectdata = [parse_rect(l) for l in data]
msize = list([0,0])
for i in range(len(rectdata)):
r = rectdata[i]
@@ -37,8 +37,8 @@ def createMap(): return map
-def solve1(): # answer: 114946
- map = createMap()
+def solve1(args):
+ map = create_map()
overlap = 0
for x in range(len(map)):
@@ -46,10 +46,10 @@ def solve1(): # answer: 114946 if len(map[x][y]) > 1:
overlap += 1
- print(overlap)
+ return overlap
-def solve2(): # answer: 877
- map = createMap()
+def solve2(args):
+ map = create_map()
overlap = set()
for x in range(len(map)):
@@ -58,17 +58,8 @@ def solve2(): # answer: 877 for id in map[x][y]:
overlap.add(id)
- # print(overlap)
-
for i in range(1, len(rectdata)):
if i not in overlap:
- print(i)
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
+ return i
-main()
+aoc.run(solve1, solve2, sols=[114946, 877])
diff --git a/src/4/input.txt b/04/input index c92ca08..c92ca08 100644 --- a/src/4/input.txt +++ b/04/input diff --git a/04/part1 b/04/part1 new file mode 100644 index 0000000..fa93645 --- /dev/null +++ b/04/part1 @@ -0,0 +1,76 @@ +--- Day 4: Repose Record --- + +You've sneaked into another supply closet - this time, it's across from the prototype suit +manufacturing lab. You need to sneak inside and fix the issues with the suit, but there's a guard +stationed outside the lab, so this is as close as you can safely get. + +As you search the closet for anything that might help, you discover that you're not the first person +to want to sneak in. Covering the walls, someone has spent an hour starting every midnight for the +past few months secretly observing this guard post! They've been writing down the ID of the one +guard on duty that night - the Elves seem to have decided that one guard was enough for the +overnight shift - as well as when they fall asleep or wake up while at their post (your puzzle +input). + +For example, consider the following records, which have already been organized into chronological +order: + +[1518-11-01 00:00] Guard #10 begins shift +[1518-11-01 00:05] falls asleep +[1518-11-01 00:25] wakes up +[1518-11-01 00:30] falls asleep +[1518-11-01 00:55] wakes up +[1518-11-01 23:58] Guard #99 begins shift +[1518-11-02 00:40] falls asleep +[1518-11-02 00:50] wakes up +[1518-11-03 00:05] Guard #10 begins shift +[1518-11-03 00:24] falls asleep +[1518-11-03 00:29] wakes up +[1518-11-04 00:02] Guard #99 begins shift +[1518-11-04 00:36] falls asleep +[1518-11-04 00:46] wakes up +[1518-11-05 00:03] Guard #99 begins shift +[1518-11-05 00:45] falls asleep +[1518-11-05 00:55] wakes up + +Timestamps are written using year-month-day hour:minute format. The guard falling asleep or waking +up is always the one whose shift most recently started. Because all asleep/awake times are during +the midnight hour (00:00 - 00:59), only the minute portion (00 - 59) is relevant for those events. + +Visually, these records show that the guards are asleep at these times: + +Date ID Minute + 000000000011111111112222222222333333333344444444445555555555 + 012345678901234567890123456789012345678901234567890123456789 +11-01 #10 .....####################.....#########################..... +11-02 #99 ........................................##########.......... +11-03 #10 ........................#####............................... +11-04 #99 ....................................##########.............. +11-05 #99 .............................................##########..... + +The columns are Date, which shows the month-day portion of the relevant day; ID, which shows the +guard on duty that day; and Minute, which shows the minutes during which the guard was asleep within +the midnight hour. (The Minute column's header shows the minute's ten's digit in the first row and +the one's digit in the second row.) Awake is shown as ., and asleep is shown as #. + +Note that guards count as asleep on the minute they fall asleep, and they count as awake on the +minute they wake up. For example, because Guard #10 wakes up at 00:25 on 1518-11-01, minute 25 is +marked as awake. + +If you can figure out the guard most likely to be asleep at a specific time, you might be able to +trick that guard into working tonight so you can have the best chance of sneaking in. You have two +strategies for choosing the best guard/minute combination. + +Strategy 1: Find the guard that has the most minutes asleep. What minute does that guard spend +asleep the most? + +In the example above, Guard #10 spent the most minutes asleep, a total of 50 minutes (20+25+5), +while Guard #99 only slept for a total of 30 minutes (10+10+10). Guard #10 was asleep most during +minute 24 (on two days, whereas any other minute the guard was asleep was only seen on one day). + +While this example listed the entries in chronological order, your entries are in the order you +found them. You'll need to organize them before they can be analyzed. + +What is the ID of the guard you chose multiplied by the minute you chose? (In the above example, the +answer would be 10 * 24 = 240.) + + diff --git a/04/part2 b/04/part2 new file mode 100644 index 0000000..a61bf95 --- /dev/null +++ b/04/part2 @@ -0,0 +1,11 @@ +--- Part Two --- + +Strategy 2: Of all guards, which guard is most frequently asleep on the same minute? + +In the example above, Guard #99 spent minute 45 asleep more than any other guard or minute - three +times in total. (In all other cases, any guard spent any minute asleep at most twice.) + +What is the ID of the guard you chose multiplied by the minute you chose? (In the above example, the +answer would be 99 * 45 = 4455.) + + diff --git a/src/4/solve.py b/04/solve.py index 72c595a..0783b9b 100644 --- a/src/4/solve.py +++ b/04/solve.py @@ -1,8 +1,8 @@ -from sys import argv as args
+import sys
+sys.path.append("../common")
+import aoc
-file = open("input.txt")
-data = [x for x in file.readlines()]
-file.close()
+data = aoc.data.split("\n")
def parse_entry(l):
split = l.split(" ")
@@ -24,7 +24,7 @@ class guard: def gen_shiftmap():
shiftdata = [parse_entry(l) for l in data]
- shiftdata = sorted(shiftdata, key=lambda x: x[3]) #sort by date
+ shiftdata = sorted(shiftdata, key=lambda x: x[3]) # sort by date
shiftmap = dict()
ltime = shiftdata[0][0]
@@ -35,12 +35,9 @@ def gen_shiftmap(): gid = entry[1]
cawake = entry[2]
- if gid != 0: # new shift
+ if gid != 0:
if gid not in shiftmap:
shiftmap[gid] = guard(gid)
- #if i != 0 and not shiftmap[cgid].awake: # not first
- # shiftmap[cgid].shifts.append((ltime, timedif(ctime, ltime), None))
- #ltime = ctime
cgid = gid
else:
g = shiftmap[cgid]
@@ -53,7 +50,7 @@ def gen_shiftmap(): return shiftmap
-def solve1():
+def solve1(args):
shiftmap = gen_shiftmap()
maxsleep = None
@@ -74,9 +71,10 @@ def solve1(): timel[(i-1)%60] += 1
minute = timel.index(max(timel))+1
- print(minute * mg.id)
-def solve2():
+ return minute * mg.id
+
+def solve2(args):
shiftmap = gen_shiftmap()
timetables = dict()
@@ -86,24 +84,9 @@ def solve2(): for i in range(t[0], t[0] + t[1]):
timetables[g.id][i] += 1
- max = None
- mmin = None
- mgid = None
- for i in range(60):
- for gid in timetables:
- t = timetables[gid]
- if max is None or t[i] > max:
- max = t[i]
- mmin = i
- mgid = gid
-
- print(mgid * mmin)
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
+ mgid, mmin = max(((gid, i) for gid in timetables for i in range(60)),
+ key = lambda x: timetables[x[0]][x[1]])
+
+ return mgid * mmin
+
+aoc.run(solve1, solve2, sols=[87681, 136461])
diff --git a/src/5/input.txt b/05/input index 1b4b16c..1b4b16c 100644 --- a/src/5/input.txt +++ b/05/input diff --git a/05/part1 b/05/part1 new file mode 100644 index 0000000..bfc8bfa --- /dev/null +++ b/05/part1 @@ -0,0 +1,40 @@ +--- Day 5: Alchemical Reduction --- + +You've managed to sneak in to the prototype suit manufacturing lab. The Elves are making decent +progress, but are still struggling with the suit's size reduction capabilities. + +While the very latest in 1518 alchemical technology might have solved their problem eventually, you +can do better. You scan the chemical composition of the suit's material and discover that it is +formed by extremely long polymers (one of which is available as your puzzle input). + +The polymer is formed by smaller units which, when triggered, react with each other such that two +adjacent units of the same type and opposite polarity are destroyed. Units' types are represented by +letters; units' polarity is represented by capitalization. For instance, r and R are units with the +same type but opposite polarity, whereas r and s are entirely different types and do not react. + +For example: + + + - In aA, a and A react, leaving nothing behind. + + - In abBA, bB destroys itself, leaving aA. As above, this then destroys itself, leaving nothing. + + - In abAB, no two adjacent units are of the same type, and so nothing happens. + + - In aabAAB, even though aa and AA are of the same type, their polarities match, and so nothing +happens. + + +Now, consider a larger example, dabAcCaCBAcCcaDA: + +dabAcCaCBAcCcaDA The first 'cC' is removed. +dabAaCBAcCcaDA This creates 'Aa', which is removed. +dabCBAcCcaDA Either 'cC' or 'Cc' are removed (the result is the same). +dabCBAcaDA No further actions can be taken. + +After all possible reactions, the resulting polymer contains 10 units. + +How many units remain after fully reacting the polymer you scanned? (Note: in this puzzle and +others, the input is large; if you copy/paste your input, make sure you get the whole thing.) + + diff --git a/05/part2 b/05/part2 new file mode 100644 index 0000000..043e78e --- /dev/null +++ b/05/part2 @@ -0,0 +1,30 @@ +--- Part Two --- + +Time to improve the polymer. + +One of the unit types is causing problems; it's preventing the polymer from collapsing as much as it +should. Your goal is to figure out which unit type is causing the most problems, remove all +instances of it (regardless of polarity), fully react the remaining polymer, and measure its length. + +For example, again using the polymer dabAcCaCBAcCcaDA from above: + + + - Removing all A/a units produces dbcCCBcCcD. Fully reacting this polymer produces dbCBcD, which +has length 6. + + - Removing all B/b units produces daAcCaCAcCcaDA. Fully reacting this polymer produces daCAcaDA, +which has length 8. + + - Removing all C/c units produces dabAaBAaDA. Fully reacting this polymer produces daDA, which has +length 4. + + - Removing all D/d units produces abAcCaCBAcCcaA. Fully reacting this polymer produces abCBAc, +which has length 6. + + +In this example, removing all C/c units was best, producing the answer 4. + +What is the length of the shortest polymer you can produce by removing all units of exactly one type +and fully reacting the result? + + diff --git a/05/solve.py b/05/solve.py new file mode 100644 index 0000000..263f9fd --- /dev/null +++ b/05/solve.py @@ -0,0 +1,30 @@ +import sys
+sys.path.append("../common")
+import aoc
+
+data = aoc.data
+
+def react(s):
+ i = 0
+ while i < len(s)-1:
+ cs = "".join(s[i:i+2])
+ csl = cs.lower()
+ if csl[0] == csl[1] and cs[0] != cs[1]:
+ s.pop(i)
+ s.pop(i)
+ if i > 0:
+ i -= 1
+ else:
+ i += 1
+
+ return len(s)
+
+def solve1(args):
+ return react(list(data))
+
+def solve2(args):
+ react_wo = lambda x : react(list(data.replace(x, "").replace(x.upper(), "")))
+ alph = "abcdefghijklmnopqrstuvwxyz"
+ return min((react_wo(c) for c in alph))
+
+aoc.run(solve1, solve2, sols=[11364, 4212])
diff --git a/src/6/input.txt b/06/input index 233e279..233e279 100644 --- a/src/6/input.txt +++ b/06/input diff --git a/06/part1 b/06/part1 new file mode 100644 index 0000000..4c1cc60 --- /dev/null +++ b/06/part1 @@ -0,0 +1,65 @@ +--- Day 6: Chronal Coordinates --- + +The device on your wrist beeps several times, and once again you feel like you're falling. + +"Situation critical," the device announces. "Destination indeterminate. Chronal interference +detected. Please specify new target coordinates." + +The device then produces a list of coordinates (your puzzle input). Are they places it thinks are +safe or dangerous? It recommends you check manual page 729. The Elves did not give you a manual. + +If they're dangerous, maybe you can minimize the danger by finding the coordinate that gives the +largest distance from the other points. + +Using only the Manhattan distance, determine the area around each coordinate by counting the number +of integer X,Y locations that are closest to that coordinate (and aren't tied in distance to any +other coordinate). + +Your goal is to find the size of the largest area that isn't infinite. For example, consider the +following list of coordinates: + +1, 1 +1, 6 +8, 3 +3, 4 +5, 5 +8, 9 + +If we name these coordinates A through F, we can draw them on a grid, putting 0,0 at the top left: + +.......... +.A........ +.......... +........C. +...D...... +.....E.... +.B........ +.......... +.......... +........F. + +This view is partial - the actual grid extends infinitely in all directions. Using the Manhattan +distance, each location's closest coordinate can be determined, shown here in lowercase: + +aaaaa.cccc +aAaaa.cccc +aaaddecccc +aadddeccCc +..dDdeeccc +bb.deEeecc +bBb.eeee.. +bbb.eeefff +bbb.eeffff +bbb.ffffFf + +Locations shown as . are equally far from two or more coordinates, and so they don't count as being +closest to any. + +In this example, the areas of coordinates A, B, C, and F are infinite - while not shown here, their +areas extend forever outside the visible grid. However, the areas of coordinates D and E are finite: +D is closest to 9 locations, and E is closest to 17 (both including the coordinate's location +itself). Therefore, in this example, the size of the largest area is 17. + +What is the size of the largest area that isn't infinite? + + diff --git a/06/part2 b/06/part2 new file mode 100644 index 0000000..cc942a7 --- /dev/null +++ b/06/part2 @@ -0,0 +1,52 @@ +--- Part Two --- + +On the other hand, if the coordinates are safe, maybe the best you can do is try to find a region +near as many coordinates as possible. + +For example, suppose you want the sum of the Manhattan distance to all of the coordinates to be less +than 32. For each location, add up the distances to all of the given coordinates; if the total of +those distances is less than 32, that location is within the desired region. Using the same +coordinates as above, the resulting region looks like this: + +.......... +.A........ +.......... +...###..C. +..#D###... +..###E#... +.B.###.... +.......... +.......... +........F. + +In particular, consider the highlighted location 4,3 located at the top middle of the region. Its +calculation is as follows, where abs() is the absolute value function: + + + - Distance to coordinate A: abs(4-1) + abs(3-1) = 5 + + - Distance to coordinate B: abs(4-1) + abs(3-6) = 6 + + - Distance to coordinate C: abs(4-8) + abs(3-3) = 4 + + - Distance to coordinate D: abs(4-3) + abs(3-4) = 2 + + - Distance to coordinate E: abs(4-5) + abs(3-5) = 3 + + - Distance to coordinate F: abs(4-8) + abs(3-9) = 10 + + - Total distance: 5 + 6 + 4 + 2 + 3 + 10 = 30 + + +Because the total distance to all coordinates (30) is less than 32, the location is within the +region. + +This region, which also includes coordinates D and E, has a total size of 16. + +Your actual region will need to be much larger than this example, though, instead including all +locations with a total distance of less than 10000. + +What is the size of the region containing all locations which have a total distance to all given +coordinates of less than 10000? + + diff --git a/06/solve.py b/06/solve.py new file mode 100644 index 0000000..f0627fe --- /dev/null +++ b/06/solve.py @@ -0,0 +1,76 @@ +import sys
+sys.path.append("../common")
+import aoc
+
+data = [[int(v) for v in l.split(",")] for l in aoc.data.split("\n")]
+
+minx = min(data, key = lambda x: x[0])[0]
+maxx = max(data, key = lambda x: x[0])[0]
+miny = min(data, key = lambda x: x[1])[1]
+maxy = max(data, key = lambda x: x[1])[1]
+
+def closest(x, y):
+ mc = None
+ md = None
+ ad = None
+ for i in range(len(data)):
+ c = data[i]
+ dist = abs(c[0] - x) + abs(c[1] - y)
+ if md == None or dist < md:
+ md = dist
+ mc = i
+ ad = None
+ elif dist == md:
+ ad = dist
+ return mc, ad
+
+def combined_dist(x, y):
+ dist = 0
+ for i in range(len(data)):
+ c = data[i]
+ dist += abs(c[0] - x) + abs(c[1] - y)
+ return dist
+
+def solve1(args):
+ areas = dict()
+ for x in range(minx, maxx):
+ for y in range(miny, maxy):
+ mc, ad = closest(x, y)
+ if ad == None:
+ if mc not in areas:
+ areas[mc] = 1
+ else:
+ areas[mc] += 1
+
+ # remove outside points
+ for i in range(len(data)):
+ c = data[i]
+ mc, ac = closest(minx, c[1])
+ if mc == i:
+ areas.pop(i)
+ continue
+ mc, ac = closest(maxx, c[1])
+ if mc == i:
+ areas.pop(i)
+ continue
+ mc, ac = closest(c[0], miny)
+ if mc == i:
+ areas.pop(i)
+ continue
+ mc, ac = closest(c[0], maxy)
+ if mc == i:
+ areas.pop(i)
+ continue
+
+ return max(areas.values())
+
+def solve2(args):
+ safezone = 0
+ for x in range(minx, maxx):
+ for y in range(miny, maxy):
+ dist = combined_dist(x,y)
+ if dist < 10000:
+ safezone += 1
+ return safezone
+
+aoc.run(solve1, solve2, sols=[3276, 38380])
diff --git a/src/7/input.txt b/07/input index 77b5f0c..77b5f0c 100644 --- a/src/7/input.txt +++ b/07/input diff --git a/07/part1 b/07/part1 new file mode 100644 index 0000000..b559869 --- /dev/null +++ b/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/07/part2 b/07/part2 new file mode 100644 index 0000000..f5d6d25 --- /dev/null +++ b/07/part2 @@ -0,0 +1,46 @@ +--- Part Two --- + +As you're about to begin construction, four of the Elves offer to help. "The sun will set soon; +it'll go faster if we work together." Now, you need to account for multiple people working on steps +simultaneously. If multiple steps are available, workers should still begin them in alphabetical +order. + +Each step takes 60 seconds plus an amount corresponding to its letter: A=1, B=2, C=3, and so on. So, +step A takes 60+1=61 seconds, while step Z takes 60+26=86 seconds. No time is required between +steps. + +To simplify things for the example, however, suppose you only have help from one Elf (a total of two +workers) and that each step takes 60 fewer seconds (so that step A takes 1 second and step Z takes +26 seconds). Then, using the same instructions as above, this is how each second would be spent: + +Second Worker 1 Worker 2 Done + 0 C . + 1 C . + 2 C . + 3 A F C + 4 B F CA + 5 B F CA + 6 D F CAB + 7 D F CAB + 8 D F CAB + 9 D . CABF + 10 E . CABFD + 11 E . CABFD + 12 E . CABFD + 13 E . CABFD + 14 E . CABFD + 15 . . CABFDE + +Each row represents one second of time. The Second column identifies how many seconds have passed +as of the beginning of that second. Each worker column shows the step that worker is currently +doing (or . if they are idle). The Done column shows completed steps. + +Note that the order of the steps has changed; this is because steps now take time to finish and +multiple workers can begin multiple steps simultaneously. + +In this example, it would take 15 seconds for two workers to complete these steps. + +With 5 workers and the 60+ second step durations described above, how long will it take to complete +all of the steps? + + diff --git a/07/solve.py b/07/solve.py new file mode 100644 index 0000000..8d7c708 --- /dev/null +++ b/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])
diff --git a/src/8/input.txt b/08/input index bbf272c..bbf272c 100644 --- a/src/8/input.txt +++ b/08/input diff --git a/08/part1 b/08/part1 new file mode 100644 index 0000000..1a723f4 --- /dev/null +++ b/08/part1 @@ -0,0 +1,58 @@ +--- Day 8: Memory Maneuver --- + +The sleigh is much easier to pull than you'd expect for something its weight. Unfortunately, neither +you nor the Elves know which way the North Pole is from here. + +You check your wrist device for anything that might help. It seems to have some kind of navigation +system! Activating the navigation system produces more bad news: "Failed to start navigation +system. Could not read software license file." + +The navigation system's license file consists of a list of numbers (your puzzle input). The numbers +define a data structure which, when processed, produces some kind of tree that can be used to +calculate the license number. + +The tree is made up of nodes; a single, outermost node forms the tree's root, and it contains all +other nodes in the tree (or contains nodes that contain nodes, and so on). + +Specifically, a node consists of: + + + - A header, which is always exactly two numbers: + + - The quantity of child nodes. + + - The quantity of metadata entries. + + + - Zero or more child nodes (as specified in the header). + + - One or more metadata entries (as specified in the header). + + + +Each child node is itself a node that has its own header, child nodes, and metadata. For example: + +2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2 +A---------------------------------- + B----------- C----------- + D----- + +In this example, each node of the tree is also marked with an underline starting with a letter for +easier identification. In it, there are four nodes: + + + - A, which has 2 child nodes (B, C) and 3 metadata entries (1, 1, 2). + + - B, which has 0 child nodes and 3 metadata entries (10, 11, 12). + + - C, which has 1 child node (D) and 1 metadata entry (2). + + - D, which has 0 child nodes and 1 metadata entry (99). + + +The first check done on the license file is to simply add up all of the metadata entries. In this +example, that sum is 1+1+2+10+11+12+2+99=138. + +What is the sum of all metadata entries? + + diff --git a/08/part2 b/08/part2 new file mode 100644 index 0000000..1ab6296 --- /dev/null +++ b/08/part2 @@ -0,0 +1,33 @@ +--- Part Two --- + +The second check is slightly more complicated: you need to find the value of the root node (A in the +example above). + +The value of a node depends on whether it has child nodes. + +If a node has no child nodes, its value is the sum of its metadata entries. So, the value of node B +is 10+11+12=33, and the value of node D is 99. + +However, if a node does have child nodes, the metadata entries become indexes which refer to those +child nodes. A metadata entry of 1 refers to the first child node, 2 to the second, 3 to the third, +and so on. The value of this node is the sum of the values of the child nodes referenced by the +metadata entries. If a referenced child node does not exist, that reference is skipped. A child node +can be referenced multiple time and counts each time it is referenced. A metadata entry of 0 does +not refer to any child node. + +For example, again using the above nodes: + + + - Node C has one metadata entry, 2. Because node C has only one child node, 2 references a child +node which does not exist, and so the value of node C is 0. + + - Node A has three metadata entries: 1, 1, and 2. The 1 references node A's first child node, B, +and the 2 references node A's second child node, C. Because node B has a value of 33 and node C has +a value of 0, the value of node A is 33+33+0=66. + + +So, in this example, the value of the root node is 66. + +What is the value of the root node? + + diff --git a/08/solve.py b/08/solve.py new file mode 100644 index 0000000..bc999d8 --- /dev/null +++ b/08/solve.py @@ -0,0 +1,43 @@ +import sys
+sys.path.append("../common")
+import aoc
+
+data = [int(v) for v in aoc.data.split(" ")]
+
+def get_nodes(nsize, index):
+ nodes = list()
+ for i in range(nsize):
+ cnsize = data[index + 0]
+ mdsize = data[index + 1]
+ cnodes, index = get_nodes(cnsize, index + 2)
+ metadata = data[index:index + mdsize]
+ nodes.append([cnodes, metadata])
+ index = index + mdsize
+ return nodes, index
+
+def node_sum(nodes):
+ metadata = 0
+ for n in nodes:
+ metadata += sum(n[1]) + node_sum(n[0])
+ return metadata
+
+def nodeValue(n):
+ if len(n[0]) == 0:
+ return sum(n[1])
+ else:
+ value = 0
+ for i in range(len(n[1])):
+ ni = n[1][i]-1
+ if ni < len(n[0]):
+ value += nodeValue(n[0][ni])
+ return value
+
+def solve1(args):
+ nodes, index = get_nodes(1, 0)
+ return node_sum(nodes)
+
+def solve2(args):
+ nodes, index = get_nodes(1, 0)
+ return nodeValue(nodes[0])
+
+aoc.run(solve1, solve2, sols=[36307, 25154])
diff --git a/src/9/input.txt b/09/input index 29b93ef..29b93ef 100644 --- a/src/9/input.txt +++ b/09/input diff --git a/09/part1 b/09/part1 new file mode 100644 index 0000000..b25ac3c --- /dev/null +++ b/09/part1 @@ -0,0 +1,78 @@ +--- Day 9: Marble Mania --- + +You talk to the Elves while you wait for your navigation system to initialize. To pass the time, +they introduce you to their favorite marble game. + +The Elves play this game by taking turns arranging the marbles in a circle according to very +particular rules. The marbles are numbered starting with 0 and increasing by 1 until every marble +has a number. + +First, the marble numbered 0 is placed in the circle. At this point, while it contains only a single +marble, it is still a circle: the marble is both clockwise from itself and counter-clockwise from +itself. This marble is designated the current marble. + +Then, each Elf takes a turn placing the lowest-numbered remaining marble into the circle between the +marbles that are 1 and 2 marbles clockwise of the current marble. (When the circle is large enough, +this means that there is one marble between the marble that was just placed and the current marble.) +The marble that was just placed then becomes the current marble. + +However, if the marble that is about to be placed has a number which is a multiple of 23, something +entirely different happens. First, the current player keeps the marble they would have placed, +adding it to their score. In addition, the marble 7 marbles counter-clockwise from the current +marble is removed from the circle and also added to the current player's score. The marble located +immediately clockwise of the marble that was removed becomes the new current marble. + +For example, suppose there are 9 players. After the marble with value 0 is placed in the middle, +each player (shown in square brackets) takes a turn. The result of each of those turns would produce +circles of marbles like this, where clockwise is to the right and the resulting current marble is in +parentheses: + +[-] (0) +[1] 0 (1) +[2] 0 (2) 1 +[3] 0 2 1 (3) +[4] 0 (4) 2 1 3 +[5] 0 4 2 (5) 1 3 +[6] 0 4 2 5 1 (6) 3 +[7] 0 4 2 5 1 6 3 (7) +[8] 0 (8) 4 2 5 1 6 3 7 +[9] 0 8 4 (9) 2 5 1 6 3 7 +[1] 0 8 4 9 2(10) 5 1 6 3 7 +[2] 0 8 4 9 2 10 5(11) 1 6 3 7 +[3] 0 8 4 9 2 10 5 11 1(12) 6 3 7 +[4] 0 8 4 9 2 10 5 11 1 12 6(13) 3 7 +[5] 0 8 4 9 2 10 5 11 1 12 6 13 3(14) 7 +[6] 0 8 4 9 2 10 5 11 1 12 6 13 3 14 7(15) +[7] 0(16) 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15 +[8] 0 16 8(17) 4 9 2 10 5 11 1 12 6 13 3 14 7 15 +[9] 0 16 8 17 4(18) 9 2 10 5 11 1 12 6 13 3 14 7 15 +[1] 0 16 8 17 4 18 9(19) 2 10 5 11 1 12 6 13 3 14 7 15 +[2] 0 16 8 17 4 18 9 19 2(20)10 5 11 1 12 6 13 3 14 7 15 +[3] 0 16 8 17 4 18 9 19 2 20 10(21) 5 11 1 12 6 13 3 14 7 15 +[4] 0 16 8 17 4 18 9 19 2 20 10 21 5(22)11 1 12 6 13 3 14 7 15 +[5] 0 16 8 17 4 18(19) 2 20 10 21 5 22 11 1 12 6 13 3 14 7 15 +[6] 0 16 8 17 4 18 19 2(24)20 10 21 5 22 11 1 12 6 13 3 14 7 15 +[7] 0 16 8 17 4 18 19 2 24 20(25)10 21 5 22 11 1 12 6 13 3 14 7 15 + +The goal is to be the player with the highest score after the last marble is used up. Assuming the +example above ends after the marble numbered 25, the winning score is 23+9=32 (because player 5 kept +marble 23 and removed marble 9, while no other player got any points in this very short example +game). + +Here are a few more examples: + + + - 10 players; last marble is worth 1618 points: high score is 8317 + + - 13 players; last marble is worth 7999 points: high score is 146373 + + - 17 players; last marble is worth 1104 points: high score is 2764 + + - 21 players; last marble is worth 6111 points: high score is 54718 + + - 30 players; last marble is worth 5807 points: high score is 37305 + + +What is the winning Elf's score? + + diff --git a/09/part2 b/09/part2 new file mode 100644 index 0000000..eca750c --- /dev/null +++ b/09/part2 @@ -0,0 +1,7 @@ +--- Part Two --- + +Amused by the speed of your answer, the Elves are curious: + +What would the new winning Elf's score be if the number of the last marble were 100 times larger? + + diff --git a/src/9/solve.py b/09/solve.py index 99a84f0..f0aa4bf 100644 --- a/src/9/solve.py +++ b/09/solve.py @@ -1,11 +1,14 @@ +import sys
+sys.path.append("../common")
+import aoc
+
from collections import deque
-from sys import argv as args
-words = open("input.txt").read().split(" ")
+words = aoc.data.split(" ")
playercount = int(words[0])
lastworth = int(words[6])
-def getHighScore(playercount, lastworth): #optimized with deque
+def highscore(playercount, lastworth):
lastworth = lastworth - lastworth % 23
players = [0 for x in range(playercount)]
@@ -27,22 +30,14 @@ def getHighScore(playercount, lastworth): #optimized with deque marbles.rotate((len(marbles)- 1 -pos) - 1)
marbles.append(i)
pos = len(marbles)-1
- #print(pos,marbles)
-
- print(max(players))
+ return max(players)
-def solve1():
- getHighScore(playercount, lastworth)
-def solve2():
- getHighScore(playercount, lastworth * 100)
+def solve1(args):
+ return highscore(playercount, lastworth)
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
+def solve2(args):
+ return highscore(playercount, lastworth * 100)
-main()
+aoc.run(solve1, solve2, sols=[412127, 3482394794])
diff --git a/src/10/input.txt b/10/input index 2b803f1..2b803f1 100644 --- a/src/10/input.txt +++ b/10/input diff --git a/10/part1 b/10/part1 new file mode 100644 index 0000000..98612ac --- /dev/null +++ b/10/part1 @@ -0,0 +1,160 @@ +--- Day 10: The Stars Align --- + +It's no use; your navigation system simply isn't capable of providing walking directions in the +arctic circle, and certainly not in 1018. + +The Elves suggest an alternative. In times like these, North Pole rescue operations will arrange +points of light in the sky to guide missing Elves back to base. Unfortunately, the message is easy +to miss: the points move slowly enough that it takes hours to align them, but have so much momentum +that they only stay aligned for a second. If you blink at the wrong time, it might be hours before +another message appears. + +You can see these points of light floating in the distance, and record their position in the sky and +their velocity, the relative change in position per second (your puzzle input). The coordinates are +all given from your perspective; given enough time, those positions and velocities will move the +points into a cohesive message! + +Rather than wait, you decide to fast-forward the process and calculate what the points will +eventually spell. + +For example, suppose you note the following points: + +position=< 9, 1> velocity=< 0, 2> +position=< 7, 0> velocity=<-1, 0> +position=< 3, -2> velocity=<-1, 1> +position=< 6, 10> velocity=<-2, -1> +position=< 2, -4> velocity=< 2, 2> +position=<-6, 10> velocity=< 2, -2> +position=< 1, 8> velocity=< 1, -1> +position=< 1, 7> velocity=< 1, 0> +position=<-3, 11> velocity=< 1, -2> +position=< 7, 6> velocity=<-1, -1> +position=<-2, 3> velocity=< 1, 0> +position=<-4, 3> velocity=< 2, 0> +position=<10, -3> velocity=<-1, 1> +position=< 5, 11> velocity=< 1, -2> +position=< 4, 7> velocity=< 0, -1> +position=< 8, -2> velocity=< 0, 1> +position=<15, 0> velocity=<-2, 0> +position=< 1, 6> velocity=< 1, 0> +position=< 8, 9> velocity=< 0, -1> +position=< 3, 3> velocity=<-1, 1> +position=< 0, 5> velocity=< 0, -1> +position=<-2, 2> velocity=< 2, 0> +position=< 5, -2> velocity=< 1, 2> +position=< 1, 4> velocity=< 2, 1> +position=<-2, 7> velocity=< 2, -2> +position=< 3, 6> velocity=<-1, -1> +position=< 5, 0> velocity=< 1, 0> +position=<-6, 0> velocity=< 2, 0> +position=< 5, 9> velocity=< 1, -2> +position=<14, 7> velocity=<-2, 0> +position=<-3, 6> velocity=< 2, -1> + +Each line represents one point. Positions are given as <X, Y> pairs: X represents how far left +(negative) or right (positive) the point appears, while Y represents how far up (negative) or down +(positive) the point appears. + +At 0 seconds, each point has the position given. Each second, each point's velocity is added to its +position. So, a point with velocity <1, -2> is moving to the right, but is moving upward twice as +quickly. If this point's initial position were <3, 9>, after 3 seconds, its position would become +<6, 3>. + +Over time, the points listed above would move like this: + +Initially: +........#............. +................#..... +.........#.#..#....... +...................... +#..........#.#.......# +...............#...... +....#................. +..#.#....#............ +.......#.............. +......#............... +...#...#.#...#........ +....#..#..#.........#. +.......#.............. +...........#..#....... +#...........#......... +...#.......#.......... + +After 1 second: +...................... +...................... +..........#....#...... +........#.....#....... +..#.........#......#.. +...................... +......#............... +....##.........#...... +......#.#............. +.....##.##..#......... +........#.#........... +........#...#.....#... +..#...........#....... +....#.....#.#......... +...................... +...................... + +After 2 seconds: +...................... +...................... +...................... +..............#....... +....#..#...####..#.... +...................... +........#....#........ +......#.#............. +.......#...#.......... +.......#..#..#.#...... +....#....#.#.......... +.....#...#...##.#..... +........#............. +...................... +...................... +...................... + +After 3 seconds: +...................... +...................... +...................... +...................... +......#...#..###...... +......#...#...#....... +......#...#...#....... +......#####...#....... +......#...#...#....... +......#...#...#....... +......#...#...#....... +......#...#..###...... +...................... +...................... +...................... +...................... + +After 4 seconds: +...................... +...................... +...................... +............#......... +........##...#.#...... +......#.....#..#...... +.....#..##.##.#....... +.......##.#....#...... +...........#....#..... +..............#....... +....#......#...#...... +.....#.....##......... +...............#...... +...............#...... +...................... +...................... + +After 3 seconds, the message appeared briefly: HI. Of course, your message will be much longer and +will take many more seconds to appear. + +What message will eventually appear in the sky? + + diff --git a/10/part2 b/10/part2 new file mode 100644 index 0000000..5bbc610 --- /dev/null +++ b/10/part2 @@ -0,0 +1,9 @@ +--- Part Two --- + +Good thing you didn't have to wait, because that would have taken a long time - much longer than the +3 seconds in the example above. + +Impressed by your sub-hour communication capabilities, the Elves are curious: exactly how many +seconds would they have needed to wait for that message to appear? + + diff --git a/10/solve.py b/10/solve.py new file mode 100644 index 0000000..7800379 --- /dev/null +++ b/10/solve.py @@ -0,0 +1,105 @@ +import sys
+sys.path.append("../common")
+import aoc
+
+def parse_line(l):
+ s = l.split(">")
+ vals = list()
+ for ss in s:
+ if len(ss) == 0:
+ continue
+ ss = ss.split("<",1)[1]
+ vals.append([int(x) for x in ss.split(",")])
+ return vals
+
+data = [parse_line(l) for l in aoc.data.split("\n") if len(l) != 0]
+posdata = [x[0] for x in data]
+veldata = [x[1] for x in data]
+
+def check_adj(pi):
+ for p in posdata:
+ if abs(p[0] - pi[0]) + abs(p[1] - pi[1]) == 1:
+ return True
+ return False
+
+def check_data():
+ for p in posdata:
+ if not check_adj(p):
+ return False
+ return True
+
+def bounds():
+ minx = None
+ maxx = None
+ miny = None
+ maxy = None
+ for p in posdata:
+ if minx is None or p[0] < minx:
+ minx = p[0]
+ if maxx is None or p[0] > maxx:
+ maxx = p[0]
+ if miny is None or p[1] < miny:
+ miny = p[1]
+ if maxy is None or p[1] > maxy:
+ maxy = p[1]
+ return minx, maxx, miny, maxy
+
+def solve(part, args):
+ count = 0
+ distx = None
+ disty = None
+ while True:
+ for i in range(len(data)):
+ posdata[i][0] += veldata[i][0]
+ posdata[i][1] += veldata[i][1]
+ count += 1
+
+ minx, maxx, miny, maxy = bounds()
+ if distx == None:
+ distx = maxx - minx
+ disty = maxy - miny
+ else:
+ cdistx = maxx - minx
+ cdisty = maxy - miny
+ if cdistx > distx or cdisty > disty:
+ for i in range(len(data)):
+ posdata[i][0] -= veldata[i][0]
+ posdata[i][1] -= veldata[i][1]
+ count -= 1
+ break
+ else:
+ distx = cdistx
+ disty = cdisty
+
+ if count % 100 == 0:
+ aoc.debug("\r" + " " * 50, end="")
+ aoc.debug(f"\rcluster size: {distx}, {disty}", end="")
+
+ if part == 1:
+ return count
+ elif part == 2:
+ answer = ""
+ minx, maxx, miny, maxy = bounds()
+ for y in range(maxy - miny + 1):
+ f = lambda x: "#" if list([x + minx, y + miny]) in posdata else " "
+ answer += "".join([f(x) for x in range(maxx - minx + 1)]) + "\n"
+ print(repr(answer))
+ print(repr(sol2))
+ return answer
+ else:
+ assert(False)
+
+sol2 = """\
+# # ###### # ##### # # # # #### # #
+# # # # # # # # # # # # # #
+# # # # # # # # # # # # #
+# # # # # # # # # # # # #
+## ##### # ##### ###### ## # ##
+## # # # # # # ## # ### ##
+# # # # # # # # # # # # # #
+# # # # # # # # # # # # # #
+# # # # # # # # # # # ## # #
+# # # ###### ##### # # # # ### # # #
+"""
+
+aoc.run(lambda args: solve(1, args), lambda args: solve(2, args), sols=[10659, sol2])
diff --git a/src/10/test-input.txt b/10/test-input.txt index e499c03..e499c03 100644 --- a/src/10/test-input.txt +++ b/10/test-input.txt diff --git a/src/11/input.txt b/11/input index 141d29f..141d29f 100644 --- a/src/11/input.txt +++ b/11/input diff --git a/11/part1 b/11/part1 new file mode 100644 index 0000000..28c13a3 --- /dev/null +++ b/11/part1 @@ -0,0 +1,87 @@ +--- Day 11: Chronal Charge --- + +You watch the Elves and their sleigh fade into the distance as they head toward the North Pole. + +Actually, you're the one fading. The falling sensation returns. + +The low fuel warning light is illuminated on your wrist-mounted device. Tapping it once causes it to +project a hologram of the situation: a 300x300 grid of fuel cells and their current power levels, +some negative. You're not sure what negative power means in the context of time travel, but it can't +be good. + +Each fuel cell has a coordinate ranging from 1 to 300 in both the X (horizontal) and Y (vertical) +direction. In X,Y notation, the top-left cell is 1,1, and the top-right cell is 300,1. + +The interface lets you select any 3x3 square of fuel cells. To increase your chances of getting to +your destination, you decide to choose the 3x3 square with the largest total power. + +The power level in a given fuel cell can be found through the following process: + + + - Find the fuel cell's rack ID, which is its X coordinate plus 10. + + - Begin with a power level of the rack ID times the Y coordinate. + + - Increase the power level by the value of the grid serial number (your puzzle input). + + - Set the power level to itself multiplied by the rack ID. + + - Keep only the hundreds digit of the power level (so 12345 becomes 3; numbers with no hundreds +digit become 0). + + - Subtract 5 from the power level. + + +For example, to find the power level of the fuel cell at 3,5 in a grid with serial number 8: + + + - The rack ID is 3 + 10 = 13. + + - The power level starts at 13 * 5 = 65. + + - Adding the serial number produces 65 + 8 = 73. + + - Multiplying by the rack ID produces 73 * 13 = 949. + + - The hundreds digit of 949 is 9. + + - Subtracting 5 produces 9 - 5 = 4. + + +So, the power level of this fuel cell is 4. + +Here are some more example power levels: + + + - Fuel cell at 122,79, grid serial number 57: power level -5. + + - Fuel cell at 217,196, grid serial number 39: power level 0. + + - Fuel cell at 101,153, grid serial number 71: power level 4. + + +Your goal is to find the 3x3 square which has the largest total power. The square must be entirely +within the 300x300 grid. Identify this square using the X,Y coordinate of its top-left fuel cell. +For example: + +For grid serial number 18, the largest total 3x3 square has a top-left corner of 33,45 (with a total +power of 29); these fuel cells appear in the middle of this 5x5 region: + +-2 -4 4 4 4 +-4 4 4 4 -5 + 4 3 3 4 -4 + 1 1 2 4 -3 +-1 0 2 -5 -2 + +For grid serial number 42, the largest 3x3 square's top-left is 21,61 (with a total power of 30); +they are in the middle of this region: + +-3 4 2 2 2 +-4 4 3 3 4 +-5 3 3 4 -4 + 4 3 3 4 -3 + 3 3 3 -5 -1 + +What is the X,Y coordinate of the top-left fuel cell of the 3x3 square with the largest total power? + + diff --git a/11/part2 b/11/part2 new file mode 100644 index 0000000..fa135d7 --- /dev/null +++ b/11/part2 @@ -0,0 +1,22 @@ +--- Part Two --- + +You discover a dial on the side of the device; it seems to let you select a square of any size, not +just 3x3. Sizes from 1x1 to 300x300 are supported. + +Realizing this, you now must find the square of any size with the largest total power. Identify this +square by including its size as a third parameter after the top-left coordinate: a 9x9 square with a +top-left corner of 3,5 is identified as 3,5,9. + +For example: + + + - For grid serial number 18, the largest total square (with a total power of 113) is 16x16 and has +a top-left corner of 90,269, so its identifier is 90,269,16. + + - For grid serial number 42, the largest total square (with a total power of 119) is 12x12 and has +a top-left corner of 232,251, so its identifier is 232,251,12. + + +What is the X,Y,size identifier of the square with the largest total power? + + diff --git a/src/11/solve.py b/11/solve.py index c2f20a8..66fc956 100644 --- a/src/11/solve.py +++ b/11/solve.py @@ -1,7 +1,8 @@ import sys
-args = sys.argv
+sys.path.append("../common")
+import aoc
-gridserial = int(open("input.txt").read())
+gridserial = int(aoc.data)
# rack ID = x + 10
# intial power = rackID * y
@@ -10,7 +11,7 @@ gridserial = int(open("input.txt").read()) # power = str(power)[2]
# power -= 5
-def getPower(x,y):
+def get_power(x,y):
id = x + 10
power = id * y
power += gridserial
@@ -23,7 +24,7 @@ def getPower(x,y): power -= 5
return power
-def solve1():
+def solve1(args):
maxpower = None
coords = None
for x in range(300-2):
@@ -31,26 +32,27 @@ def solve1(): power = 0;
for i in range(3):
for j in range(3):
- power += getPower(x+i,y+j)
+ power += get_power(x+i,y+j)
if maxpower == None or power > maxpower:
maxpower = power
coords = (x, y)
- print(f"{coords[0]},{coords[1]}")
-def genMap():
+ return f"{coords[0]},{coords[1]}"
+
+def gen_map():
vmap = [[0 for y in range(300)] for x in range(300)]
for x in range(300):
for y in range(300):
- vmap[x][y] = getPower(x,y)
+ vmap[x][y] = get_power(x,y)
return vmap
-def solve2():
+def solve2(args):
maxpower = None
res = None
- pmap = genMap()
+ pmap = gen_map()
vmap = [[list() for y in range(300)] for x in range(300)]
for s in range(1, 301):
- print(f"\rTrying: {s}", end="")
+ aoc.debug(f"\rTrying: {s}", end="")
cmaxpower = None
cres = None
for x in range(300-(s-1)):
@@ -67,14 +69,8 @@ def solve2(): elif cmaxpower < maxpower:
break
- print("\r" + " " * 50 + "\r", end="")
- print(f"{res[0]},{res[1]},{res[2]}")
+ aoc.debug("\r" + " " * 50 + "\r", end="")
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
+ return f"{res[0]},{res[1]},{res[2]}"
-main()
+aoc.run(solve1, solve2, sols=["21,93", "231,108,14"])
diff --git a/src/12/input.txt b/12/input index 6dcf208..6dcf208 100644 --- a/src/12/input.txt +++ b/12/input diff --git a/12/part1 b/12/part1 new file mode 100644 index 0000000..34c246e --- /dev/null +++ b/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 initial state. (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 spread 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 20 +generations. + +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 325. + +After 20 generations, what is the sum of the numbers of all pots which contain a plant? + + diff --git a/12/part2 b/12/part2 new file mode 100644 index 0000000..ac78a25 --- /dev/null +++ b/12/part2 @@ -0,0 +1,9 @@ +--- Part Two --- + +You realize that 20 generations aren't enough. After all, these plants will need to last another +1500 years to even reach your timeline, not to mention your future. + +After fifty billion (50000000000) generations, what is the sum of the numbers of all pots which +contain a plant? + + diff --git a/src/12/solve.py b/12/solve.py index 8c4784c..a688376 100644 --- a/src/12/solve.py +++ b/12/solve.py @@ -1,11 +1,13 @@ -from sys import argv as args
+import sys
+sys.path.append("../common")
+import aoc
-lines = open("input.txt").read().split("\n")
+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 nextGen(pots):
+def next_gen(pots):
pmin = min(pots)
pmax = max(pots)
npots = list()
@@ -21,41 +23,31 @@ def nextGen(pots): break
return npots
-def getPots():
+def get_pots():
pots = list()
for i in range(len(istate)):
if istate[i] == "#":
pots.append(i)
return pots
-def solve1():
- pots = getPots()
+def solve1(args):
+ pots = get_pots()
for i in range(20):
- pots = nextGen(pots)
- print(sum(pots))
- return
+ pots = next_gen(pots)
+ return sum(pots)
-def solve2():
- pots = getPots()
+def solve2(args):
+ pots = get_pots()
psum = sum(pots)
pdif = None
i = 0
while (True):
- pots = nextGen(pots)
+ pots = next_gen(pots)
i += 1
csum = sum(pots)
if pdif == csum - psum:
- print(csum + pdif * (50000000000 - 164))
- break
+ return csum + pdif * (50000000000 - 164)
pdif = csum - psum
psum = csum
- return
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
+aoc.run(solve1, solve2, sols=[1987, 1150000000358])
diff --git a/src/13/input.txt b/13/input index f970d12..f970d12 100644 --- a/src/13/input.txt +++ b/13/input diff --git a/13/part1 b/13/part1 new file mode 100644 index 0000000..99d03c1 --- /dev/null +++ b/13/part1 @@ -0,0 +1,187 @@ +--- Day 13: Mine Cart Madness --- + +A crop of this size requires significant logistics to transport produce, soil, fertilizer, and so +on. The Elves are very busy pushing things around in carts on some kind of rudimentary system of +tracks they've come up with. + +Seeing as how cart-and-track systems don't appear in recorded history for another 1000 years, the +Elves seem to be making this up as they go along. They haven't even figured out how to avoid +collisions yet. + +You map out the tracks (your puzzle input) and see where you can help. + +Tracks consist of straight paths (| and -), curves (/ and \), and intersections (+). Curves connect +exactly two perpendicular pieces of track; for example, this is a closed loop: + +/----\ +| | +| | +\----/ + +Intersections occur when two perpendicular paths cross. At an intersection, a cart is capable of +turning left, turning right, or continuing straight. Here are two loops connected by two +intersections: + +/-----\ +| | +| /--+--\ +| | | | +\--+--/ | + | | + \-----/ + +Several carts are also on the tracks. Carts always face either up (^), down (v), left (<), or right +(>). (On your initial map, the track under each cart is a straight path matching the direction the +cart is facing.) + +Each time a cart has the option to turn (by arriving at any intersection), it turns left the first +time, goes straight the second time, turns right the third time, and then repeats those directions +starting again with left the fourth time, straight the fifth time, and so on. This process is +independent of the particular intersection at which the cart has arrived - that is, the cart has no +per-intersection memory. + +Carts all move at the same speed; they take turns moving a single step at a time. They do this based +on their current location: carts on the top row move first (acting from left to right), then carts +on the second row move (again from left to right), then carts on the third row, and so on. Once +each cart has moved one step, the process repeats; each of these loops is called a tick. + +For example, suppose there are two carts on a straight track: + +| | | | | +v | | | | +| v v | | +| | | v X +| | ^ ^ | +^ ^ | | | +| | | | | + +First, the top cart moves. It is facing down (v), so it moves down one square. Second, the bottom +cart moves. It is facing up (^), so it moves up one square. Because all carts have moved, the first +tick ends. Then, the process repeats, starting with the first cart. The first cart moves down, +then the second cart moves up - right into the first cart, colliding with it! (The location of the +crash is marked with an X.) This ends the second and last tick. +Here is a longer example: + +/->-\ +| | /----\ +| /-+--+-\ | +| | | | v | +\-+-/ \-+--/ + \------/ + +/-->\ +| | /----\ +| /-+--+-\ | +| | | | | | +\-+-/ \->--/ + \------/ + +/---v +| | /----\ +| /-+--+-\ | +| | | | | | +\-+-/ \-+>-/ + \------/ + +/---\ +| v /----\ +| /-+--+-\ | +| | | | | | +\-+-/ \-+->/ + \------/ + +/---\ +| | /----\ +| /->--+-\ | +| | | | | | +\-+-/ \-+--^ + \------/ + +/---\ +| | /----\ +| /-+>-+-\ | +| | | | | ^ +\-+-/ \-+--/ + \------/ + +/---\ +| | /----\ +| /-+->+-\ ^ +| | | | | | +\-+-/ \-+--/ + \------/ + +/---\ +| | /----< +| /-+-->-\ | +| | | | | | +\-+-/ \-+--/ + \------/ + +/---\ +| | /---<\ +| /-+--+>\ | +| | | | | | +\-+-/ \-+--/ + \------/ + +/---\ +| | /--<-\ +| /-+--+-v | +| | | | | | +\-+-/ \-+--/ + \------/ + +/---\ +| | /-<--\ +| /-+--+-\ | +| | | | v | +\-+-/ \-+--/ + \------/ + +/---\ +| | /<---\ +| /-+--+-\ | +| | | | | | +\-+-/ \-<--/ + \------/ + +/---\ +| | v----\ +| /-+--+-\ | +| | | | | | +\-+-/ \<+--/ + \------/ + +/---\ +| | /----\ +| /-+--v-\ | +| | | | | | +\-+-/ ^-+--/ + \------/ + +/---\ +| | /----\ +| /-+--+-\ | +| | | X | | +\-+-/ \-+--/ + \------/ + +After following their respective paths for a while, the carts eventually crash. To help prevent +crashes, you'd like to know the location of the first crash. Locations are given in X,Y coordinates, +where the furthest left column is X=0 and the furthest top row is Y=0: + + 111 + 0123456789012 +0/---\ +1| | /----\ +2| /-+--+-\ | +3| | | X | | +4\-+-/ \-+--/ +5 \------/ + +In this example, the location of the first crash is 7,3. + + + + diff --git a/13/part2 b/13/part2 new file mode 100644 index 0000000..96a0ea6 --- /dev/null +++ b/13/part2 @@ -0,0 +1,49 @@ +--- Part Two --- + +There isn't much you can do to prevent crashes in this ridiculous system. However, by predicting the +crashes, the Elves know where to be in advance and instantly remove the two crashing carts the +moment any crash occurs. + +They can proceed like this for a while, but eventually, they're going to run out of carts. It could +be useful to figure out where the last cart that hasn't crashed will end up. + +For example: + +/>-<\ +| | +| /<+-\ +| | | v +\>+</ | + | ^ + \<->/ + +/---\ +| | +| v-+-\ +| | | | +\-+-/ | + | | + ^---^ + +/---\ +| | +| /-+-\ +| v | | +\-+-/ | + ^ ^ + \---/ + +/---\ +| | +| /-+-\ +| | | | +\-+-/ ^ + | | + \---/ + +After four very expensive crashes, a tick ends with only one cart remaining; its final location is +6,4. + +What is the location of the last cart at the end of the first tick where it is the only cart left? + + diff --git a/src/13/solve.py b/13/solve.py index f8a4ac3..e89466c 100644 --- a/src/13/solve.py +++ b/13/solve.py @@ -1,21 +1,9 @@ -from sys import argv as args
-
-f = open("input.txt")
-contents = f.read()
-test_contents = """
-/>-<\\
-| |
-| /<+-\\
-| | | v
-\\>+</ |
- | ^
- \\<->/
-"""
-
-tmap = [list(l) for l in contents.split("\n") if len(l) != 0]
-xlen = len(tmap[0])
-ylen = len(tmap)
-f.close()
+import sys
+sys.path.append("../common")
+import aoc
+
+tmap = [list(l) for l in aoc.data.split("\n") if len(l) != 0]
+xlen, ylen = len(tmap[0]), len(tmap)
arrows = dict()
arrows["<"] = (-1, 0)
@@ -25,16 +13,16 @@ arrows["v"] = (0, 1) directions = [(-1,0), (0,-1), (1, 0), (0, 1)] # l - u - r - d
-def checkPos(x,y):
+def check_pos(x, y):
if x < xlen and x >= 0 and y < ylen and y >= 0:
return tmap[y][x]
return " "
def correct(x, y):
- cr = checkPos(x+1, y)
- cl = checkPos(x-1, y)
- cu = checkPos(x, y-1)
- cd = checkPos(x, y+1)
+ cr = check_pos(x+1, y)
+ cl = check_pos(x-1, y)
+ cu = check_pos(x, y-1)
+ cd = check_pos(x, y+1)
if cr == "|": cr = " "
if cl == "|": cl = " "
@@ -46,9 +34,8 @@ def correct(x, y): u = cu != " "
d = cd != " "
- sum = r + l + u + d
-
- if sum > 2:
+ vsum = r + l + u + d
+ if vsum > 2:
return "+"
# 2 around
@@ -74,7 +61,7 @@ for y in range(ylen): carts.append([x, y, arrows[tmap[y][x]], 0, 0])
tmap[y][x] = correct(x,y)
-def cartAt(x, y):
+def cart_at(x, y):
global carts
for i in range(len(carts)):
c = carts[i]
@@ -82,15 +69,16 @@ def cartAt(x, y): return i
return None
-def drawMap():
+def draw_map():
for y in range(ylen):
- print("".join(["#" if cartAt(x,y) != None else tmap[y][x] for x in range(len(tmap[y]))]))
+ f = lambda x : "".join(["#" if cart_at(x,y) != None else tmap[y][x]])
+ aoc.debug([f(x) for x in range(len(tmap[y]))])
def advance(cart):
ncart = [0 for x in range(5)]
ncart[0] = cart[0]+cart[2][0]
ncart[1] = cart[1]+cart[2][1]
- col = cartAt(ncart[0], ncart[1])
+ col = cart_at(ncart[0], ncart[1])
if col != None:
return ncart[0], ncart[1], col
@@ -101,7 +89,7 @@ def advance(cart): d = (d + len(directions)-1 + cart[3]) % len(directions)
ncart[2] = directions[d]
ncart[3] = (cart[3] + 1) % 3
- else: #dont need to change direction for '-' and '|'
+ else: # dont need to change direction for '-' and '|'
if c == "/":
ncart[2] = directions[3-d]
elif c == "\\":
@@ -119,7 +107,7 @@ def advance(cart): return ncart
-def solve1():
+def solve1(args):
global carts
crash = None
@@ -133,9 +121,9 @@ def solve1(): else:
carts[c] = nc
- print(f"{crash[0]},{crash[1]}")
+ return f"{crash[0]},{crash[1]}"
-def solve2():
+def solve2(args):
global carts
while len(carts) > 1:
@@ -155,13 +143,6 @@ def solve2(): if c in carts: # prevent doubles
carts.remove(c)
- print(f"{carts[0][0]},{carts[0][1]}")
-
-def main():
- if len(args) == 2:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
+ return f"{carts[0][0]},{carts[0][1]}"
-main()
+aoc.run(solve1, solve2)
diff --git a/13/test1 b/13/test1 new file mode 100644 index 0000000..30bc010 --- /dev/null +++ b/13/test1 @@ -0,0 +1,7 @@ +/>-<\ +| | +| /<+-\ +| | | v +\>+</ | + | ^ + \<->/ diff --git a/src/14/input.txt b/14/input index 1c93252..1c93252 100644 --- a/src/14/input.txt +++ b/14/input diff --git a/14/part1 b/14/part1 new file mode 100644 index 0000000..277863d --- /dev/null +++ b/14/part1 @@ -0,0 +1,69 @@ +--- Day 14: Chocolate Charts --- + +You finally have a chance to look at all of the produce moving around. Chocolate, cinnamon, mint, +chili peppers, nutmeg, vanilla... the Elves must be growing these plants to make hot chocolate! As +you realize this, you hear a conversation in the distance. When you go to investigate, you discover +two Elves in what appears to be a makeshift underground kitchen/laboratory. + +The Elves are trying to come up with the ultimate hot chocolate recipe; they're even maintaining a +scoreboard which tracks the quality score (0-9) of each recipe. + +Only two recipes are on the board: the first recipe got a score of 3, the second, 7. Each of the two +Elves has a current recipe: the first Elf starts with the first recipe, and the second Elf starts +with the second recipe. + +To create new recipes, the two Elves combine their current recipes. This creates new recipes from +the digits of the sum of the current recipes' scores. With the current recipes' scores of 3 and 7, +their sum is 10, and so two new recipes would be created: the first with score 1 and the second with +score 0. If the current recipes' scores were 2 and 3, the sum, 5, would only create one recipe (with +a score of 5) with its single digit. + +The new recipes are added to the end of the scoreboard in the order they are created. So, after the +first round, the scoreboard is 3, 7, 1, 0. + +After all new recipes are added to the scoreboard, each Elf picks a new current recipe. To do this, +the Elf steps forward through the scoreboard a number of recipes equal to 1 plus the score of their +current recipe. So, after the first round, the first Elf moves forward 1 + 3 = 4 times, while the +second Elf moves forward 1 + 7 = 8 times. If they run out of recipes, they loop back around to the +beginning. After the first round, both Elves happen to loop around until they land on the same +recipe that they had in the beginning; in general, they will move to different recipes. + +Drawing the first Elf as parentheses and the second Elf as square brackets, they continue this +process: + +(3)[7] +(3)[7] 1 0 + 3 7 1 [0](1) 0 + 3 7 1 0 [1] 0 (1) +(3) 7 1 0 1 0 [1] 2 + 3 7 1 0 (1) 0 1 2 [4] + 3 7 1 [0] 1 0 (1) 2 4 5 + 3 7 1 0 [1] 0 1 2 (4) 5 1 + 3 (7) 1 0 1 0 [1] 2 4 5 1 5 + 3 7 1 0 1 0 1 2 [4](5) 1 5 8 + 3 (7) 1 0 1 0 1 2 4 5 1 5 8 [9] + 3 7 1 0 1 0 1 [2] 4 (5) 1 5 8 9 1 6 + 3 7 1 0 1 0 1 2 4 5 [1] 5 8 9 1 (6) 7 + 3 7 1 0 (1) 0 1 2 4 5 1 5 [8] 9 1 6 7 7 + 3 7 [1] 0 1 0 (1) 2 4 5 1 5 8 9 1 6 7 7 9 + 3 7 1 0 [1] 0 1 2 (4) 5 1 5 8 9 1 6 7 7 9 2 + +The Elves think their skill will improve after making a few recipes (your puzzle input). However, +that could take ages; you can speed this up considerably by identifying the scores of the ten +recipes after that. For example: + + + - If the Elves think their skill will improve after making 9 recipes, the scores of the ten recipes +after the first nine on the scoreboard would be 5158916779 (highlighted in the last line of the +diagram). + + - After 5 recipes, the scores of the next ten would be 0124515891. + + - After 18 recipes, the scores of the next ten would be 9251071085. + + - After 2018 recipes, the scores of the next ten would be 5941429882. + + +What are the scores of the ten recipes immediately after the number of recipes in your puzzle input? + + diff --git a/14/part2 b/14/part2 new file mode 100644 index 0000000..ffea6cf --- /dev/null +++ b/14/part2 @@ -0,0 +1,19 @@ +--- Part Two --- + +As it turns out, you got the Elves' plan backwards. They actually want to know how many recipes +appear on the scoreboard to the left of the first recipes whose scores are the digits from your +puzzle input. + + + - 51589 first appears after 9 recipes. + + - 01245 first appears after 5 recipes. + + - 92510 first appears after 18 recipes. + + - 59414 first appears after 2018 recipes. + + +How many recipes appear on the scoreboard to the left of the score sequence in your puzzle input? + + diff --git a/src/14/solve.py b/14/solve.py index fd6488c..a6c63a3 100644 --- a/src/14/solve.py +++ b/14/solve.py @@ -1,42 +1,37 @@ -from sys import argv as args
+import sys
+sys.path.append("../common")
+import aoc
-inputstr = open("input.txt").read().replace("\n","")
-recipes = [3,7]
+data = aoc.data
+recipes = [3, 7]
-def solve1():
- global recipes, inputstr
+def solve1(args):
+ global recipes, data
- end = int(inputstr)
+ end = int(data)
workers = [i for i in range(2)]
while len(recipes) < end + 10:
recipes += [int(c) for c in str(sum(recipes[workers[i]] for i in range(len(workers))))]
for i in range(len(workers)):
workers[i] = (workers[i] + recipes[workers[i]]+1) % len(recipes)
- print("".join([str(x) for x in recipes[end:]]))
+ return "".join([str(x) for x in recipes[end:]])
-def solve2():
- global recipes, inputstr
+def solve2(args):
+ global recipes, data
- ilen = len(inputstr)
- inputstr = [int(c) for c in inputstr]
+ ilen = len(data)
+ data = [int(c) for c in data]
workers = [i for i in range(2)]
stop = False
counter = 0
while not stop:
for v in [int(c) for c in str(sum(recipes[workers[i]] for i in range(len(workers))))]:
- if recipes[-ilen:] == inputstr:
+ if recipes[-ilen:] == data:
stop = True
break
recipes.append(v)
for i in range(len(workers)):
workers[i] = (workers[i] + recipes[workers[i]]+1) % len(recipes)
- print(len(recipes)-ilen)
+ return len(recipes) - ilen
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
+aoc.run(solve1, solve2, sols=["6107101544", 20291131])
diff --git a/src/15/input.txt b/15/input index c6ec342..c6ec342 100644 --- a/src/15/input.txt +++ b/15/input diff --git a/15/part1 b/15/part1 new file mode 100644 index 0000000..6820770 --- /dev/null +++ b/15/part1 @@ -0,0 +1,343 @@ +--- Day 15: Beverage Bandits --- + +Having perfected their hot chocolate, the Elves have a new problem: the Goblins that live in these +caves will do anything to steal it. Looks like they're here for a fight. + +You scan the area, generating a map of the walls (#), open cavern (.), and starting position of +every Goblin (G) and Elf (E) (your puzzle input). + +Combat proceeds in rounds; in each round, each unit that is still alive takes a turn, resolving all +of its actions before the next unit's turn begins. On each unit's turn, it tries to move into range +of an enemy (if it isn't already) and then attack (if it is in range). + +All units are very disciplined and always follow very strict combat rules. Units never move or +attack diagonally, as doing so would be dishonorable. When multiple choices are equally valid, ties +are broken in reading order: top-to-bottom, then left-to-right. For instance, the order in which +units take their turns within a round is the reading order of their starting positions in that +round, regardless of the type of unit or whether other units have moved after the round started. +For example: + + would take their +These units: turns in this order: + ####### ####### + #.G.E.# #.1.2.# + #E.G.E# #3.4.5# + #.G.E.# #.6.7.# + ####### ####### + +Each unit begins its turn by identifying all possible targets (enemy units). If no targets remain, +combat ends. + +Then, the unit identifies all of the open squares (.) that are in range of each target; these are +the squares which are adjacent (immediately up, down, left, or right) to any target and which aren't +already occupied by a wall or another unit. Alternatively, the unit might already be in range of a +target. If the unit is not already in range of a target, and there are no open squares which are in +range of a target, the unit ends its turn. + +If the unit is already in range of a target, it does not move, but continues its turn with an +attack. Otherwise, since it is not in range of a target, it moves. + +To move, the unit first considers the squares that are in range and determines which of those +squares it could reach in the fewest steps. A step is a single movement to any adjacent (immediately +up, down, left, or right) open (.) square. Units cannot move into walls or other units. The unit +does this while considering the current positions of units and does not do any prediction about +where units will be later. If the unit cannot reach (find an open path to) any of the squares that +are in range, it ends its turn. If multiple squares are in range and tied for being reachable in the +fewest steps, the square which is first in reading order is chosen. For example: + +Targets: In range: Reachable: Nearest: Chosen: +####### ####### ####### ####### ####### +#E..G.# #E.?G?# #E.@G.# #E.!G.# #E.+G.# +#...#.# --> #.?.#?# --> #.@.#.# --> #.!.#.# --> #...#.# +#.G.#G# #?G?#G# #@G@#G# #!G.#G# #.G.#G# +####### ####### ####### ####### ####### + +In the above scenario, the Elf has three targets (the three Goblins): + + + - Each of the Goblins has open, adjacent squares which are in range (marked with a ? on the map). + + - Of those squares, four are reachable (marked @); the other two (on the right) would require +moving through a wall or unit to reach. + + - Three of these reachable squares are nearest, requiring the fewest steps (only 2) to reach +(marked !). + + - Of those, the square which is first in reading order is chosen (+). + + +The unit then takes a single step toward the chosen square along the shortest path to that square. +If multiple steps would put the unit equally closer to its destination, the unit chooses the step +which is first in reading order. (This requires knowing when there is more than one shortest path so +that you can consider the first step of each such path.) For example: + +In range: Nearest: Chosen: Distance: Step: +####### ####### ####### ####### ####### +#.E...# #.E...# #.E...# #4E212# #..E..# +#...?.# --> #...!.# --> #...+.# --> #32101# --> #.....# +#..?G?# #..!G.# #...G.# #432G2# #...G.# +####### ####### ####### ####### ####### + +The Elf sees three squares in range of a target (?), two of which are nearest (!), and so the first +in reading order is chosen (+). Under "Distance", each open square is marked with its distance from +the destination square; the two squares to which the Elf could move on this turn (down and to the +right) are both equally good moves and would leave the Elf 2 steps from being in range of the +Goblin. Because the step which is first in reading order is chosen, the Elf moves right one square. + +Here's a larger example of movement: + +Initially: +######### +#G..G..G# +#.......# +#.......# +#G..E..G# +#.......# +#.......# +#G..G..G# +######### + +After 1 round: +######### +#.G...G.# +#...G...# +#...E..G# +#.G.....# +#.......# +#G..G..G# +#.......# +######### + +After 2 rounds: +######### +#..G.G..# +#...G...# +#.G.E.G.# +#.......# +#G..G..G# +#.......# +#.......# +######### + +After 3 rounds: +######### +#.......# +#..GGG..# +#..GEG..# +#G..G...# +#......G# +#.......# +#.......# +######### + +Once the Goblins and Elf reach the positions above, they all are either in range of a target or +cannot find any square in range of a target, and so none of the units can move until a unit dies. + +After moving (or if the unit began its turn in range of a target), the unit attacks. + +To attack, the unit first determines all of the targets that are in range of it by being immediately +adjacent to it. If there are no such targets, the unit ends its turn. Otherwise, the adjacent target +with the fewest hit points is selected; in a tie, the adjacent target with the fewest hit points +which is first in reading order is selected. + +The unit deals damage equal to its attack power to the selected target, reducing its hit points by +that amount. If this reduces its hit points to 0 or fewer, the selected target dies: its square +becomes . and it takes no further turns. + +Each unit, either Goblin or Elf, has 3 attack power and starts with 200 hit points. + +For example, suppose the only Elf is about to attack: + + HP: HP: +G.... 9 G.... 9 +..G.. 4 ..G.. 4 +..EG. 2 --> ..E.. +..G.. 2 ..G.. 2 +...G. 1 ...G. 1 + +The "HP" column shows the hit points of the Goblin to the left in the corresponding row. The Elf is +in range of three targets: the Goblin above it (with 4 hit points), the Goblin to its right (with 2 +hit points), and the Goblin below it (also with 2 hit points). Because three targets are in range, +the ones with the lowest hit points are selected: the two Goblins with 2 hit points each (one to the +right of the Elf and one below the Elf). Of those, the Goblin first in reading order (the one to the +right of the Elf) is selected. The selected Goblin's hit points (2) are reduced by the Elf's attack +power (3), reducing its hit points to -1, killing it. + +After attacking, the unit's turn ends. Regardless of how the unit's turn ends, the next unit in the +round takes its turn. If all units have taken turns in this round, the round ends, and a new round +begins. + +The Elves look quite outnumbered. You need to determine the outcome of the battle: the number of +full rounds that were completed (not counting the round in which combat ends) multiplied by the sum +of the hit points of all remaining units at the moment combat ends. (Combat only ends when a unit +finds no targets during its turn.) + +Below is an entire sample combat. Next to each map, each row's units' hit points are listed from +left to right. + +Initially: +####### +#.G...# G(200) +#...EG# E(200), G(200) +#.#.#G# G(200) +#..G#E# G(200), E(200) +#.....# +####### + +After 1 round: +####### +#..G..# G(200) +#...EG# E(197), G(197) +#.#G#G# G(200), G(197) +#...#E# E(197) +#.....# +####### + +After 2 rounds: +####### +#...G.# G(200) +#..GEG# G(200), E(188), G(194) +#.#.#G# G(194) +#...#E# E(194) +#.....# +####### + +Combat ensues; eventually, the top Elf dies: + +After 23 rounds: +####### +#...G.# G(200) +#..G.G# G(200), G(131) +#.#.#G# G(131) +#...#E# E(131) +#.....# +####### + +After 24 rounds: +####### +#..G..# G(200) +#...G.# G(131) +#.#G#G# G(200), G(128) +#...#E# E(128) +#.....# +####### + +After 25 rounds: +####### +#.G...# G(200) +#..G..# G(131) +#.#.#G# G(125) +#..G#E# G(200), E(125) +#.....# +####### + +After 26 rounds: +####### +#G....# G(200) +#.G...# G(131) +#.#.#G# G(122) +#...#E# E(122) +#..G..# G(200) +####### + +After 27 rounds: +####### +#G....# G(200) +#.G...# G(131) +#.#.#G# G(119) +#...#E# E(119) +#...G.# G(200) +####### + +After 28 rounds: +####### +#G....# G(200) +#.G...# G(131) +#.#.#G# G(116) +#...#E# E(113) +#....G# G(200) +####### + +More combat ensues; eventually, the bottom Elf dies: + +After 47 rounds: +####### +#G....# G(200) +#.G...# G(131) +#.#.#G# G(59) +#...#.# +#....G# G(200) +####### + +Before the 48th round can finish, the top-left Goblin finds that there are no targets remaining, and +so combat ends. So, the number of full rounds that were completed is 47, and the sum of the hit +points of all remaining units is 200+131+59+200 = 590. From these, the outcome of the battle is 47 * +590 = 27730. + +Here are a few example summarized combats: + +####### ####### +#G..#E# #...#E# E(200) +#E#E.E# #E#...# E(197) +#G.##.# --> #.E##.# E(185) +#...#E# #E..#E# E(200), E(200) +#...E.# #.....# +####### ####### + +Combat ends after 37 full rounds +Elves win with 982 total hit points left +Outcome: 37 * 982 = 36334 + +####### ####### +#E..EG# #.E.E.# E(164), E(197) +#.#G.E# #.#E..# E(200) +#E.##E# --> #E.##.# E(98) +#G..#.# #.E.#.# E(200) +#..E#.# #...#.# +####### ####### + +Combat ends after 46 full rounds +Elves win with 859 total hit points left +Outcome: 46 * 859 = 39514 + +####### ####### +#E.G#.# #G.G#.# G(200), G(98) +#.#G..# #.#G..# G(200) +#G.#.G# --> #..#..# +#G..#.# #...#G# G(95) +#...E.# #...G.# G(200) +####### ####### + +Combat ends after 35 full rounds +Goblins win with 793 total hit points left +Outcome: 35 * 793 = 27755 + +####### ####### +#.E...# #.....# +#.#..G# #.#G..# G(200) +#.###.# --> #.###.# +#E#G#G# #.#.#.# +#...#G# #G.G#G# G(98), G(38), G(200) +####### ####### + +Combat ends after 54 full rounds +Goblins win with 536 total hit points left +Outcome: 54 * 536 = 28944 + +######### ######### +#G......# #.G.....# G(137) +#.E.#...# #G.G#...# G(200), G(200) +#..##..G# #.G##...# G(200) +#...##..# --> #...##..# +#...#...# #.G.#...# G(200) +#.G...G.# #.......# +#.....G.# #.......# +######### ######### + +Combat ends after 20 full rounds +Goblins win with 937 total hit points left +Outcome: 20 * 937 = 18740 + +What is the outcome of the combat described in your puzzle input? + + diff --git a/15/part2 b/15/part2 new file mode 100644 index 0000000..ff17535 --- /dev/null +++ b/15/part2 @@ -0,0 +1,91 @@ +--- Part Two --- + +According to your calculations, the Elves are going to lose badly. Surely, you won't mess up the +timeline too much if you give them just a little advanced technology, right? + +You need to make sure the Elves not only win, but also suffer no losses: even the death of a single +Elf is unacceptable. + +However, you can't go too far: larger changes will be more likely to permanently alter spacetime. + +So, you need to find the outcome of the battle in which the Elves have the lowest integer attack +power (at least 4) that allows them to win without a single death. The Goblins always have an attack +power of 3. + +In the first summarized example above, the lowest attack power the Elves need to win without losses +is 15: + +####### ####### +#.G...# #..E..# E(158) +#...EG# #...E.# E(14) +#.#.#G# --> #.#.#.# +#..G#E# #...#.# +#.....# #.....# +####### ####### + +Combat ends after 29 full rounds +Elves win with 172 total hit points left +Outcome: 29 * 172 = 4988 + +In the second example above, the Elves need only 4 attack power: + +####### ####### +#E..EG# #.E.E.# E(200), E(23) +#.#G.E# #.#E..# E(200) +#E.##E# --> #E.##E# E(125), E(200) +#G..#.# #.E.#.# E(200) +#..E#.# #...#.# +####### ####### + +Combat ends after 33 full rounds +Elves win with 948 total hit points left +Outcome: 33 * 948 = 31284 + +In the third example above, the Elves need 15 attack power: + +####### ####### +#E.G#.# #.E.#.# E(8) +#.#G..# #.#E..# E(86) +#G.#.G# --> #..#..# +#G..#.# #...#.# +#...E.# #.....# +####### ####### + +Combat ends after 37 full rounds +Elves win with 94 total hit points left +Outcome: 37 * 94 = 3478 + +In the fourth example above, the Elves need 12 attack power: + +####### ####### +#.E...# #...E.# E(14) +#.#..G# #.#..E# E(152) +#.###.# --> #.###.# +#E#G#G# #.#.#.# +#...#G# #...#.# +####### ####### + +Combat ends after 39 full rounds +Elves win with 166 total hit points left +Outcome: 39 * 166 = 6474 + +In the last example above, the lone Elf needs 34 attack power: + +######### ######### +#G......# #.......# +#.E.#...# #.E.#...# E(38) +#..##..G# #..##...# +#...##..# --> #...##..# +#...#...# #...#...# +#.G...G.# #.......# +#.....G.# #.......# +######### ######### + +Combat ends after 30 full rounds +Elves win with 38 total hit points left +Outcome: 30 * 38 = 1140 + +After increasing the Elves' attack power until it is just barely enough for them to win without any +Elves dying, what is the outcome of the combat described in your puzzle input? + + diff --git a/src/15/solve.py b/15/solve.py index fa08fdb..cc16c9d 100644 --- a/src/15/solve.py +++ b/15/solve.py @@ -1,75 +1,13 @@ -from sys import argv as args
-
-debug = False
-
-file = open("input.txt")
-input = file.readlines()
-file.close()
-
-#sample 1 - (works!)
-ainput = """#######
-#G..#E#
-#E#E.E#
-#G.##.#
-#...#E#
-#...E.#
-#######""".split("\n")
-
-#sample 2 - (works!)
-binput = """#######
-#E..EG#
-#.#G.E#
-#E.##E#
-#G..#.#
-#..E#.#
-#######""".split("\n")
-
-#sample 3 - (works!)
-cinput = """#######
-#E.G#.#
-#.#G..#
-#G.#.G#
-#G..#.#
-#...E.#
-#######""".split("\n")
-
-#sample 4 - (works!)
-dinput = """#######
-#.E...#
-#.#..G#
-#.###.#
-#E#G#G#
-#...#G#
-#######""".split("\n")
-
-#sample 5 - (works!)
-einput = """#########
-#G......#
-#.E.#...#
-#..##..G#
-#...##..#
-#...#...#
-#.G...G.#
-#.....G.#
-#########""".split("\n")
-
-#sample 6 - (works!)
-finput = """#######
-#.G...#
-#...EG#
-#.#.#G#
-#..G#E#
-#.....#
-#######""".split("\n")
-
-sinput = dinput
+import sys
+sys.path.append("../common")
+import aoc
+data = aoc.data.split("\n")
actors = list()
-input = [l.replace("\n","") for l in input]
-def parseEntity(x, y):
+def parse_entity(x, y):
global actors
- c = input[y][x]
+ c = data[y][x]
if c == "#":
return 1
else:
@@ -79,16 +17,16 @@ def parseEntity(x, y): actors.append([x, y, 200, 0, len(actors), 3])
return 0
-ylen = len(input)
-xlen = len(input[0])
+ylen = len(data)
+xlen = len(data[0])
adjacent = [[0, -1], [-1, 0], [1, 0], [0, 1]] # first in reading order
vmap = list()
-def setGame():
+def set_game():
global vmap, actors
actors = list()
- vmap = [[parseEntity(x, y) for x in range(xlen)] for y in range(ylen)]
+ vmap = [[parse_entity(x, y) for x in range(xlen)] for y in range(ylen)]
def inmap(cmap, cx, cy):
@@ -121,11 +59,13 @@ def flatten(l): def drawMap():
global actors
+
for y in range(ylen):
for x in range(xlen):
ind = inmap(actors, x, y)
- print(("G" if actors[ind][3] == 1 else "E") if ind != None else ("." if vmap[y][x] == 0 else "#"), end="")
- print()
+ aoc.debug(("G" if actors[ind][3] == 1 else "E") \
+ if ind != None else ("." if vmap[y][x] == 0 else "#"), end="")
+ aoc.debug()
def getSteps(cmap, a1):
# adjacent squares
@@ -163,6 +103,7 @@ def closestStep(a1, a2): def move(a):
global actors
+
# best steps from enemies
steps = [[na[0], na[1]] + closestStep(a, na) for na in actors if na[3] != a[3]]
@@ -180,6 +121,7 @@ def move(a): def getInrange(a):
global actors
+
inrange = list()
for dir in adjacent:
nx = a[0] + dir[0]
@@ -189,8 +131,9 @@ def getInrange(a): inrange.append(ind)
return inrange
-def nextTick(tick):
+def next_tick(tick):
global actors
+
actors = sorted(actors, key=lambda x: (x[1], x[0]), reverse=True)
i = len(actors)-1
@@ -211,81 +154,76 @@ def nextTick(tick): actors[cai][2] -= a[5] # attack
if actors[cai][2] <= 0:
actors.pop(cai) # dead
- print("death -",cai)
- if minalive() == 0 and i != 0: # incomplete round
+ aoc.debug("death -",cai)
+ if min_alive() == 0 and i != 0: # incomplete round
return False
if cai < i: i -= 1
- if debug and False:
- print()
- print("small step -",a[4])
+ if aoc.debug_lvl and False:
+ aoc.debug()
+ aoc.debug("small step -",a[4])
drawMap()
- statusReport()
+ status_report()
i -= 1
- if debug:
- print()
- print("tick:", tick)
+ if aoc.debug_lvl:
+ aoc.debug()
+ aoc.debug("tick:", tick)
drawMap()
- statusReport()
+ status_report()
else:
- print(tick)
+ aoc.debug(tick)
+
return True
-def minalive():
+def min_alive():
alive = [0,0]
for a in actors:
alive[1 * (a[3] == 0)] += 1
return min(alive)
-def sumHP():
+def sum_hp():
return sum(a[2] for a in actors)
-def statusReport():
+def status_report():
global actors
- #drawMap()
+
sactors = sorted(actors, key = lambda x:x[4])
for a in sactors:
- print("HP:", a[2])
- print()
+ aoc.debug("HP:", a[2])
+ aoc.debug()
-def elvesAlive():
+def elves_alive():
return len([a for a in actors if a[3] == 0])
-def startBattle(eap):
+def start_battle(eap):
global actors
- setGame() # reset
+
+ set_game()
for a in actors:
if a[3] == 0:
a[5] = eap
- elfcount = elvesAlive()
+ elfcount = elves_alive()
ticks = 0
- while minalive() > 0:
- if nextTick(ticks):
+ while min_alive() > 0:
+ if next_tick(ticks):
ticks += 1
- statusReport()
- return ((sumHP() * ticks), (elfcount - elvesAlive())) # res and casualties
+ status_report()
-def solve1():
- res = startBattle(3)
- print("answer:", res[0]);
+ return ((sum_hp() * ticks), (elfcount - elves_alive()))
-def solve2():
+def solve1(args):
+ res = start_battle(3)
+ return res[0]
+
+def solve2(args):
eap = 4
- res = startBattle(eap)
+ res = start_battle(eap)
while res[1] != 0:
eap += 1
- res = startBattle(eap)
- #print(eap)
- print("answer:",res[0])
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
+ res = start_battle(eap)
+ return res[0]
+
+aoc.run(solve1, solve2, sols=[229798, 52972])
diff --git a/15/test1 b/15/test1 new file mode 100644 index 0000000..ac399d6 --- /dev/null +++ b/15/test1 @@ -0,0 +1,7 @@ +####### +#G..#E# +#E#E.E# +#G.##.# +#...#E# +#...E.# +####### diff --git a/15/test2 b/15/test2 new file mode 100644 index 0000000..58f778d --- /dev/null +++ b/15/test2 @@ -0,0 +1,7 @@ +####### +#E..EG# +#.#G.E# +#E.##E# +#G..#.# +#..E#.# +####### diff --git a/15/test3 b/15/test3 new file mode 100644 index 0000000..6dc1c08 --- /dev/null +++ b/15/test3 @@ -0,0 +1,7 @@ +####### +#E.G#.# +#.#G..# +#G.#.G# +#G..#.# +#...E.# +####### diff --git a/15/test4 b/15/test4 new file mode 100644 index 0000000..2343d7b --- /dev/null +++ b/15/test4 @@ -0,0 +1,7 @@ +####### +#.E...# +#.#..G# +#.###.# +#E#G#G# +#...#G# +####### diff --git a/15/test5 b/15/test5 new file mode 100644 index 0000000..95882b2 --- /dev/null +++ b/15/test5 @@ -0,0 +1,9 @@ +######### +#G......# +#.E.#...# +#..##..G# +#...##..# +#...#...# +#.G...G.# +#.....G.# +######### diff --git a/15/test6 b/15/test6 new file mode 100644 index 0000000..291d351 --- /dev/null +++ b/15/test6 @@ -0,0 +1,7 @@ +####### +#.G...# +#...EG# +#.#.#G# +#..G#E# +#.....# +####### diff --git a/src/16/input.txt b/16/input index 71f3ecd..71f3ecd 100644 --- a/src/16/input.txt +++ b/16/input diff --git a/16/part1 b/16/part1 new file mode 100644 index 0000000..48a9cba --- /dev/null +++ b/16/part1 @@ -0,0 +1,136 @@ +--- Day 16: Chronal Classification --- + +As you see the Elves defend their hot chocolate successfully, you go back to falling through time. +This is going to become a problem. + +If you're ever going to return to your own time, you need to understand how this device on your +wrist works. You have a little while before you reach your next destination, and with a bit of trial +and error, you manage to pull up a programming manual on the device's tiny screen. + +According to the manual, the device has four registers (numbered 0 through 3) that can be +manipulated by instructions containing one of 16 opcodes. The registers start with the value 0. + +Every instruction consists of four values: an opcode, two inputs (named A and B), and an output +(named C), in that order. The opcode specifies the behavior of the instruction and how the inputs +are interpreted. The output, C, is always treated as a register. + +In the opcode descriptions below, if something says "value A", it means to take the number given as +A literally. (This is also called an "immediate" value.) If something says "register A", it means to +use the number given as A to read from (or write to) the register with that number. So, if the +opcode addi adds register A and value B, storing the result in register C, and the instruction addi +0 7 3 is encountered, it would add 7 to the value contained by register 0 and store the sum in +register 3, never modifying registers 0, 1, or 2 in the process. + +Many opcodes are similar except for how they interpret their arguments. The opcodes fall into seven +general categories: + +Addition: + + + - addr (add register) stores into register C the result of adding register A and register B. + + - addi (add immediate) stores into register C the result of adding register A and value B. + + +Multiplication: + + + - mulr (multiply register) stores into register C the result of multiplying register A and register +B. + + - muli (multiply immediate) stores into register C the result of multiplying register A and value +B. + + +Bitwise AND: + + + - banr (bitwise AND register) stores into register C the result of the bitwise AND of register A +and register B. + + - bani (bitwise AND immediate) stores into register C the result of the bitwise AND of register A +and value B. + + +Bitwise OR: + + + - borr (bitwise OR register) stores into register C the result of the bitwise OR of register A and +register B. + + - bori (bitwise OR immediate) stores into register C the result of the bitwise OR of register A and +value B. + + +Assignment: + + + - setr (set register) copies the contents of register A into register C. (Input B is ignored.) + + - seti (set immediate) stores value A into register C. (Input B is ignored.) + + +Greater-than testing: + + + - gtir (greater-than immediate/register) sets register C to 1 if value A is greater than register +B. Otherwise, register C is set to 0. + + - gtri (greater-than register/immediate) sets register C to 1 if register A is greater than value +B. Otherwise, register C is set to 0. + + - gtrr (greater-than register/register) sets register C to 1 if register A is greater than register +B. Otherwise, register C is set to 0. + + +Equality testing: + + + - eqir (equal immediate/register) sets register C to 1 if value A is equal to register B. +Otherwise, register C is set to 0. + + - eqri (equal register/immediate) sets register C to 1 if register A is equal to value B. +Otherwise, register C is set to 0. + + - eqrr (equal register/register) sets register C to 1 if register A is equal to register B. +Otherwise, register C is set to 0. + + +Unfortunately, while the manual gives the name of each opcode, it doesn't seem to indicate the +number. However, you can monitor the CPU to see the contents of the registers before and after +instructions are executed to try to work them out. Each opcode has a number from 0 through 15, but +the manual doesn't say which is which. For example, suppose you capture the following sample: + +Before: [3, 2, 1, 1] +9 2 1 2 +After: [3, 2, 2, 1] + +This sample shows the effect of the instruction 9 2 1 2 on the registers. Before the instruction is +executed, register 0 has value 3, register 1 has value 2, and registers 2 and 3 have value 1. After +the instruction is executed, register 2's value becomes 2. + +The instruction itself, 9 2 1 2, means that opcode 9 was executed with A=2, B=1, and C=2. Opcode 9 +could be any of the 16 opcodes listed above, but only three of them behave in a way that would cause +the result shown in the sample: + + + - Opcode 9 could be mulr: register 2 (which has a value of 1) times register 1 (which has a value +of 2) produces 2, which matches the value stored in the output register, register 2. + + - Opcode 9 could be addi: register 2 (which has a value of 1) plus value 1 produces 2, which +matches the value stored in the output register, register 2. + + - Opcode 9 could be seti: value 2 matches the value stored in the output register, register 2; the +number given for B is irrelevant. + + +None of the other opcodes produce the result captured in the sample. Because of this, the sample +above behaves like three opcodes. + +You collect many of these samples (the first section of your puzzle input). The manual also includes +a small test program (the second section of your puzzle input) - you can ignore it for now. + +Ignoring the opcode numbers, how many samples in your puzzle input behave like three or more +opcodes? + + diff --git a/16/part2 b/16/part2 new file mode 100644 index 0000000..fc8d343 --- /dev/null +++ b/16/part2 @@ -0,0 +1,8 @@ +--- Part Two --- + +Using the samples you collected, work out the number of each opcode and execute the test program +(the second section of your puzzle input). + +What value is contained in register 0 after executing the test program? + + diff --git a/src/16/solve.py b/16/solve.py index e2098e3..f9a11b6 100644 --- a/src/16/solve.py +++ b/16/solve.py @@ -1,25 +1,22 @@ -from sys import argv as args
+import sys
+sys.path.append("../common")
+import aoc
-
-def parseLog(ls):
+def parse_log(ls):
data = list()
before = [int(v) for v in ls[0].split("[")[1].split("]")[0].split(",")]
ins = [int(v) for v in ls[1].split(" ")]
after = [int(v) for v in ls[2].split("[")[1].split("]")[0].split(",")]
return (before, ins, after)
-file = open("input.txt")
-inslog = list()
-input = file.readlines()
-file.close()
+inslog = []
+data = aoc.data.split("\n")
progsec = None
-
-for i in range(0, len(input), 4):
- if input[i] == "\n":
+for i in range(0, len(data), 4):
+ if data[i] == "\n":
progsec = i
break
- inslog.append(parseLog(input[i:i+4]))
-
+ inslog.append(parse_log(data[i:i+4]))
register = list()
@@ -41,7 +38,7 @@ opmap["eqir"] = lambda a, b : 1 * (a == register[b]) opmap["eqri"] = lambda a, b : 1 * (register[a] == b)
opmap["eqrr"] = lambda a, b : 1 * (register[a] == register[b])
-def getPossible(ins):
+def get_possible(ins):
global register
sregister = register[:]
before = ins[0]
@@ -64,23 +61,22 @@ def getPossible(ins): register = sregister
return possibles
-def solve1():
+def solve1(args):
global register
uncertain = 0
for ins in inslog:
- if len(getPossible(ins)) >= 3:
+ if len(get_possible(ins)) >= 3:
uncertain += 1
- print(uncertain)
- return
+ return uncertain
-def solve2():
+def solve2(args):
possible = dict()
for ins in inslog:
o = ins[1][0]
if o in possible:
- possible[o] = [op for op in getPossible(ins) if op in possible[o]]
+ possible[o] = [op for op in get_possible(ins) if op in possible[o]]
else:
- possible[o] = getPossible(ins)
+ possible[o] = get_possible(ins)
certain = False
while not certain:
@@ -99,8 +95,8 @@ def solve2(): for p in possible: # flatten
ntrans[p] = possible[p][0]
- for i in range(progsec, len(input)): # execute program
- l = input[i]
+ for i in range(progsec, len(data)): # execute program
+ l = data[i]
if l == "\n": continue
cmd = [int(v) for v in l.split(" ")]
while len(register)-1 < cmd[3]:
@@ -108,14 +104,6 @@ def solve2(): register[cmd[3]] = list(opmap.values())[ntrans[cmd[0]]](cmd[1], cmd[2])
+ return register[0]
- print(register[0])
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
+aoc.run(solve1, solve2, sols=[531, 649])
diff --git a/src/17/.gitignore b/17/.gitignore index 53752db..53752db 100644 --- a/src/17/.gitignore +++ b/17/.gitignore diff --git a/src/17/input.txt b/17/input index c383645..c383645 100644 --- a/src/17/input.txt +++ b/17/input diff --git a/17/part1 b/17/part1 new file mode 100644 index 0000000..01f4820 --- /dev/null +++ b/17/part1 @@ -0,0 +1,177 @@ +--- Day 17: Reservoir Research --- + +You arrive in the year 18. If it weren't for the coat you got in 1018, you would be very cold: the +North Pole base hasn't even been constructed. + +Rather, it hasn't been constructed yet. The Elves are making a little progress, but there's not a +lot of liquid water in this climate, so they're getting very dehydrated. Maybe there's more +underground? + +You scan a two-dimensional vertical slice of the ground nearby and discover that it is mostly sand +with veins of clay. The scan only provides data with a granularity of square meters, but it should +be good enough to determine how much water is trapped there. In the scan, x represents the distance +to the right, and y represents the distance down. There is also a spring of water near the surface +at x=500, y=0. The scan identifies which square meters are clay (your puzzle input). + +For example, suppose your scan shows the following veins of clay: + +x=495, y=2..7 +y=7, x=495..501 +x=501, y=3..7 +x=498, y=2..4 +x=506, y=1..2 +x=498, y=10..13 +x=504, y=10..13 +y=13, x=498..504 + +Rendering clay as #, sand as ., and the water spring as +, and with x increasing to the right and y +increasing downward, this becomes: + + 44444455555555 + 99999900000000 + 45678901234567 + 0 ......+....... + 1 ............#. + 2 .#..#.......#. + 3 .#..#..#...... + 4 .#..#..#...... + 5 .#.....#...... + 6 .#.....#...... + 7 .#######...... + 8 .............. + 9 .............. +10 ....#.....#... +11 ....#.....#... +12 ....#.....#... +13 ....#######... + +The spring of water will produce water forever. Water can move through sand, but is blocked by clay. +Water always moves down when possible, and spreads to the left and right otherwise, filling space +that has clay on both sides and falling out otherwise. + +For example, if five squares of water are created, they will flow downward until they reach the clay +and settle there. Water that has come to rest is shown here as ~, while sand through which water has +passed (but which is now dry again) is shown as |: + +......+....... +......|.....#. +.#..#.|.....#. +.#..#.|#...... +.#..#.|#...... +.#....|#...... +.#~~~~~#...... +.#######...... +.............. +.............. +....#.....#... +....#.....#... +....#.....#... +....#######... + +Two squares of water can't occupy the same location. If another five squares of water are created, +they will settle on the first five, filling the clay reservoir a little more: + +......+....... +......|.....#. +.#..#.|.....#. +.#..#.|#...... +.#..#.|#...... +.#~~~~~#...... +.#~~~~~#...... +.#######...... +.............. +.............. +....#.....#... +....#.....#... +....#.....#... +....#######... + +Water pressure does not apply in this scenario. If another four squares of water are created, they +will stay on the right side of the barrier, and no water will reach the left side: + +......+....... +......|.....#. +.#..#.|.....#. +.#..#~~#...... +.#..#~~#...... +.#~~~~~#...... +.#~~~~~#...... +.#######...... +.............. +.............. +....#.....#... +....#.....#... +....#.....#... +....#######... + +At this point, the top reservoir overflows. While water can reach the tiles above the surface of the +water, it cannot settle there, and so the next five squares of water settle like this: + +......+....... +......|.....#. +.#..#||||...#. +.#..#~~#|..... +.#..#~~#|..... +.#~~~~~#|..... +.#~~~~~#|..... +.#######|..... +........|..... +........|..... +....#...|.#... +....#...|.#... +....#~~~~~#... +....#######... + +Note especially the leftmost |: the new squares of water can reach this tile, but cannot stop there. + Instead, eventually, they all fall to the right and settle in the reservoir below. + +After 10 more squares of water, the bottom reservoir is also full: + +......+....... +......|.....#. +.#..#||||...#. +.#..#~~#|..... +.#..#~~#|..... +.#~~~~~#|..... +.#~~~~~#|..... +.#######|..... +........|..... +........|..... +....#~~~~~#... +....#~~~~~#... +....#~~~~~#... +....#######... + +Finally, while there is nowhere left for the water to settle, it can reach a few more tiles before +overflowing beyond the bottom of the scanned data: + +......+....... (line not counted: above minimum y value) +......|.....#. +.#..#||||...#. +.#..#~~#|..... +.#..#~~#|..... +.#~~~~~#|..... +.#~~~~~#|..... +.#######|..... +........|..... +...|||||||||.. +...|#~~~~~#|.. +...|#~~~~~#|.. +...|#~~~~~#|.. +...|#######|.. +...|.......|.. (line not counted: below maximum y value) +...|.......|.. (line not counted: below maximum y value) +...|.......|.. (line not counted: below maximum y value) + +How many tiles can be reached by the water? To prevent counting forever, ignore tiles with a y +coordinate smaller than the smallest y coordinate in your scan data or larger than the largest one. +Any x coordinate is valid. In this example, the lowest y coordinate given is 1, and the highest is +13, causing the water spring (in row 0) and the water falling off the bottom of the render (in rows +14 through infinity) to be ignored. + +So, in the example above, counting both water at rest (~) and other sand tiles the water can +hypothetically reach (|), the total number of tiles the water can reach is 57. + +How many tiles can the water reach within the range of y values in your scan? + + diff --git a/17/part2 b/17/part2 new file mode 100644 index 0000000..6a3dfb2 --- /dev/null +++ b/17/part2 @@ -0,0 +1,10 @@ +--- Part Two --- + +After a very long time, the water spring will run dry. How much water will be retained? + +In the example above, water that won't eventually drain out is shown as ~, a total of 29 tiles. + +How many water tiles are left after the water spring stops producing water and all remaining water +not at rest has drained? + + diff --git a/src/17/solve.py b/17/solve.py index 95f0bc4..c6454f3 100644 --- a/src/17/solve.py +++ b/17/solve.py @@ -1,8 +1,8 @@ -from sys import argv as args
+import sys
+sys.path.append("../common")
+import aoc
-debug = False
-
-def parseLine(l):
+def parse_line(l):
s = l.split(", ")
if s[0].startswith("y="):
s = s[::-1]
@@ -10,22 +10,7 @@ def parseLine(l): res = [[int(x) for x in v.split("=")[1].split("..")] for v in s]
return res
-file = open("input.txt")
-sinput = file.read()
-file.close()
-
-ainput = """x=495, y=2..7
-y=7, x=495..501
-x=501, y=3..7
-x=498, y=2..4
-x=506, y=1..2
-x=498, y=10..13
-x=504, y=10..13
-y=13, x=498..504"""
-
-sinput = [l for l in sinput.split("\n") if len(l) != 0]
-
-constraints = [parseLine(l) for l in sinput]
+constraints = [parse_line(l) for l in aoc.data.split("\n")]
xmin = min(c[0][0] for c in constraints)-1
xmax = max(c[0][-1] for c in constraints)+1
@@ -34,18 +19,15 @@ ymax = max(c[1][-1] for c in constraints) xdif = xmax - xmin + 1
ydif = ymax - ymin + 1
-#print(xmin, xmax)
-#print(ymin, ymax)
-
vmap = [[0 for x in range(xdif)] for y in range(ydif)]
-def setMap(x, y, v):
+def set_map(x, y, v):
global vmap
if y < ymin or y > ymax or x < xmin or x > xmax:
return
vmap[y-ymin][x-xmin] = v
-def getMap(x, y):
+def get_map(x, y):
global vmap
if x > xmax or x < xmin:
return 1
@@ -56,10 +38,10 @@ def getMap(x, y): def drawWall(c):
if len(c[0]) == 1:
for y in range(c[1][0], c[1][1] + 1):
- setMap(c[0][0], y, 1)
+ set_map(c[0][0], y, 1)
else:
for x in range(c[0][0], c[0][1] + 1):
- setMap(x, c[1][0], 1)
+ set_map(x, c[1][0], 1)
for c in constraints:
drawWall(c)
@@ -76,7 +58,7 @@ def interpretChar(v): def drawMap():
for y in range(ydif):
- print("".join([interpretChar(v) for v in vmap[y]]))
+ aoc.debug("".join([interpretChar(v) for v in vmap[y]]))
def fwriteMap():
f = open("output","w+")
@@ -85,10 +67,10 @@ def fwriteMap(): f.close()
def isstatic(p):
- return getMap(p[0], p[1]) in (1, 3)
+ return get_map(p[0], p[1]) in (1, 3)
def isfree(p):
- return getMap(p[0], p[1]) == 0
+ return get_map(p[0], p[1]) == 0
def move(p):
x = p[0]
@@ -131,19 +113,19 @@ def fillfloor(p): return [(i, p[1]) for i in range(lx, rx+1)]
-def countWFlowing():
+def count_w_flowing():
water = 0
for y in range(ymin, ymax+1):
for x in range(xmin, xmax+1):
- if getMap(x,y) == 2:
+ if get_map(x,y) == 2:
water += 1
return water
-def countWStatic():
+def count_w_static():
water = 0
for y in range(ymin, ymax+1):
for x in range(xmin, xmax+1):
- if getMap(x,y) == 3:
+ if get_map(x,y) == 3:
water += 1
return water
@@ -156,11 +138,11 @@ def simulate(): res = fillfloor(cp)
if res:
for p in res:
- setMap(p[0], p[1], 3)
+ set_map(p[0], p[1], 3)
nhead = None
for x in range(res[0][0], res[-1][0]+1):
np = (x, res[0][1]-1)
- if getMap(np[0], np[1]) == 2:
+ if get_map(np[0], np[1]) == 2:
nhead = np
break
if nhead == None: # head got trapped
@@ -174,39 +156,28 @@ def simulate(): heads.pop()
heads += res
for p in res:
- setMap(p[0], p[1], 2)
+ set_map(p[0], p[1], 2)
else:
if res != cp:
if res[1] <= ymax:
- setMap(res[0], res[1], 2)
+ set_map(res[0], res[1], 2)
heads[-1] = res
else:
heads.pop()
else:
heads.pop()
- if debug:
- print(heads)
+ if aoc.debug_lvl:
+ aoc.debug(heads)
input()
fwriteMap()
-def solve1():
+def solve1(args):
simulate()
- #fwriteMap()
- print(countWFlowing() + countWStatic())
- return
+ return count_w_flowing() + count_w_static()
-def solve2():
+def solve2(args):
simulate()
- #fwriteMap()
- print(countWStatic())
- return
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
+ return count_w_static()
+
+aoc.run(solve1, solve2, sols=[39557, 32984])
diff --git a/17/test1 b/17/test1 new file mode 100644 index 0000000..293b5af --- /dev/null +++ b/17/test1 @@ -0,0 +1,8 @@ +x=495, y=2..7 +y=7, x=495..501 +x=501, y=3..7 +x=498, y=2..4 +x=506, y=1..2 +x=498, y=10..13 +x=504, y=10..13 +y=13, x=498..504 diff --git a/src/18/input.txt b/18/input index 0f62ca5..0f62ca5 100644 --- a/src/18/input.txt +++ b/18/input diff --git a/18/part1 b/18/part1 new file mode 100644 index 0000000..a4ea0ac --- /dev/null +++ b/18/part1 @@ -0,0 +1,174 @@ +--- Day 18: Settlers of The North Pole --- + +On the outskirts of the North Pole base construction project, many Elves are collecting lumber. + +The lumber collection area is 50 acres by 50 acres; each acre can be either open ground (.), trees +(|), or a lumberyard (#). You take a scan of the area (your puzzle input). + +Strange magic is at work here: each minute, the landscape looks entirely different. In exactly one +minute, an open acre can fill with trees, a wooded acre can be converted to a lumberyard, or a +lumberyard can be cleared to open ground (the lumber having been sent to other projects). + +The change to each acre is based entirely on the contents of that acre as well as the number of +open, wooded, or lumberyard acres adjacent to it at the start of each minute. Here, "adjacent" means +any of the eight acres surrounding that acre. (Acres on the edges of the lumber collection area +might have fewer than eight adjacent acres; the missing acres aren't counted.) + +In particular: + + + - An open acre will become filled with trees if three or more adjacent acres contained trees. +Otherwise, nothing happens. + + - An acre filled with trees will become a lumberyard if three or more adjacent acres were +lumberyards. Otherwise, nothing happens. + + - An acre containing a lumberyard will remain a lumberyard if it was adjacent to at least one other +lumberyard and at least one acre containing trees. Otherwise, it becomes open. + + +These changes happen across all acres simultaneously, each of them using the state of all acres at +the beginning of the minute and changing to their new form by the end of that same minute. Changes +that happen during the minute don't affect each other. + +For example, suppose the lumber collection area is instead only 10 by 10 acres with this initial +configuration: + +Initial state: +.#.#...|#. +.....#|##| +.|..|...#. +..|#.....# +#.#|||#|#| +...#.||... +.|....|... +||...#|.#| +|.||||..|. +...#.|..|. + +After 1 minute: +.......##. +......|### +.|..|...#. +..|#||...# +..##||.|#| +...#||||.. +||...|||.. +|||||.||.| +|||||||||| +....||..|. + +After 2 minutes: +.......#.. +......|#.. +.|.|||.... +..##|||..# +..###|||#| +...#|||||. +|||||||||. +|||||||||| +|||||||||| +.||||||||| + +After 3 minutes: +.......#.. +....|||#.. +.|.||||... +..###|||.# +...##|||#| +.||##||||| +|||||||||| +|||||||||| +|||||||||| +|||||||||| + +After 4 minutes: +.....|.#.. +...||||#.. +.|.#||||.. +..###||||# +...###||#| +|||##||||| +|||||||||| +|||||||||| +|||||||||| +|||||||||| + +After 5 minutes: +....|||#.. +...||||#.. +.|.##||||. +..####|||# +.|.###||#| +|||###|||| +|||||||||| +|||||||||| +|||||||||| +|||||||||| + +After 6 minutes: +...||||#.. +...||||#.. +.|.###|||. +..#.##|||# +|||#.##|#| +|||###|||| +||||#||||| +|||||||||| +|||||||||| +|||||||||| + +After 7 minutes: +...||||#.. +..||#|##.. +.|.####||. +||#..##||# +||##.##|#| +|||####||| +|||###|||| +|||||||||| +|||||||||| +|||||||||| + +After 8 minutes: +..||||##.. +..|#####.. +|||#####|. +||#...##|# +||##..###| +||##.###|| +|||####||| +||||#||||| +|||||||||| +|||||||||| + +After 9 minutes: +..||###... +.||#####.. +||##...##. +||#....### +|##....##| +||##..###| +||######|| +|||###|||| +|||||||||| +|||||||||| + +After 10 minutes: +.||##..... +||###..... +||##...... +|##.....## +|##.....## +|##....##| +||##.####| +||#####||| +||||#||||| +|||||||||| + +After 10 minutes, there are 37 wooded acres and 31 lumberyards. Multiplying the number of wooded +acres by the number of lumberyards gives the total resource value after ten minutes: 37 * 31 = 1147. + +What will the total resource value of the lumber collection area be after 10 minutes? + + diff --git a/18/part2 b/18/part2 new file mode 100644 index 0000000..aea233d --- /dev/null +++ b/18/part2 @@ -0,0 +1,8 @@ +--- Part Two --- + +This important natural resource will need to last for at least thousands of years. Are the Elves +collecting this lumber sustainably? + +What will the total resource value of the lumber collection area be after 1000000000 minutes? + + diff --git a/src/18/solve.py b/18/solve.py index 270ace1..f209429 100644 --- a/src/18/solve.py +++ b/18/solve.py @@ -1,4 +1,6 @@ -from sys import argv as args
+import sys
+sys.path.append("../common")
+import aoc
from copy import deepcopy
from collections import deque
@@ -9,27 +11,13 @@ ivals["#"] = 0 ivals["."] = 0
ivals["|"] = 0
-def parseLine(l):
+def pasrse_line(l):
return tuple([states.index(c) for c in l])
-inputstr = open("input.txt").read()
+vmap = [pasrse_line(l) for l in aoc.data.split("\n")]
+xlen, ylen = len(vmap[0]), len(vmap)
-sinputstr = """.#.#...|#.
-.....#|##|
-.|..|...#.
-..|#.....#
-#.#|||#|#|
-...#.||...
-.|....|...
-||...#|.#|
-|.||||..|.
-...#.|..|."""
-
-vmap = [parseLine(l) for l in inputstr.split("\n") if len(l) != 0]
-ylen = len(vmap)
-xlen = len(vmap[0])
-
-def getAt(x, y):
+def get_at(x, y):
if y < 0 or y >= ylen or x < 0 or x >= xlen:
return None
return vmap[y][x]
@@ -37,7 +25,7 @@ def getAt(x, y): def next(x, y):
v = vmap[y][x]
around = list()
- [[around.append(getAt(x+i-1, y+j-1)) for j in range(3) if not (i == 1 and j == 1)] for i in range(3)]
+ [[around.append(get_at(x+i-1, y+j-1)) for j in range(3) if not (i == 1 and j == 1)] for i in range(3)]
if v == 0:
if len([v for v in around if v == 1]) >= 3:
return 1
@@ -49,16 +37,16 @@ def next(x, y): return 0
return v
-def getVals():
+def get_vals():
vals = [0 for x in range(3)]
for y in range(ylen):
for x in range(xlen):
vals[vmap[y][x]] += 1
return vals
-def drawMap(cmap):
+def draw_map(cmap):
for y in range(ylen):
- print("".join([str(c) for c in cmap[y]]))
+ aoc.debug("".join([str(c) for c in cmap[y]]))
def iterate(n):
global vmap
@@ -69,19 +57,16 @@ def iterate(n): omap[y].append(next(x, y))
vmap = omap
-def getRes():
- vals = getVals()
+def get_res():
+ vals = get_vals()
return (vals[1] * vals[2])
-def solve1():
- #drawMap(vmap)
+def solve1(args):
iterate(10)
- vals = getVals()
- #drawMap(vmap)
- print(vals[1] * vals[2])
- return
+ vals = get_vals()
+ return vals[1] * vals[2]
-def solve2():
+def solve2(args):
iterate(1000)
omap = deepcopy(vmap)
counter = 0
@@ -91,16 +76,6 @@ def solve2(): if vmap == omap:
break
- #print(counter)
- print(getRes())
- #drawMap(vmap)
- return
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
+ return get_res()
-main()
+aoc.run(solve1, solve2, sols=[574590, 183787])
diff --git a/18/test1 b/18/test1 new file mode 100644 index 0000000..13d299d --- /dev/null +++ b/18/test1 @@ -0,0 +1,10 @@ +.#.#...|#. +.....#|##| +.|..|...#. +..|#.....# +#.#|||#|#| +...#.||... +.|....|... +||...#|.#| +|.||||..|. +...#.|..|. diff --git a/src/19/input.txt b/19/input index 0392b90..0392b90 100644 --- a/src/19/input.txt +++ b/19/input diff --git a/19/part1 b/19/part1 new file mode 100644 index 0000000..3e58fd1 --- /dev/null +++ b/19/part1 @@ -0,0 +1,92 @@ +--- Day 19: Go With The Flow --- + +With the Elves well on their way constructing the North Pole base, you turn your attention back to +understanding the inner workings of programming the device. + +You can't help but notice that the device's opcodes don't contain any flow control like jump +instructions. The device's manual goes on to explain: + +"In programs where flow control is required, the instruction pointer can be bound to a register so +that it can be manipulated directly. This way, setr/seti can function as absolute jumps, addr/addi +can function as relative jumps, and other opcodes can cause truly fascinating effects." + +This mechanism is achieved through a declaration like #ip 1, which would modify register 1 so that +accesses to it let the program indirectly access the instruction pointer itself. To compensate for +this kind of binding, there are now six registers (numbered 0 through 5); the five not bound to the +instruction pointer behave as normal. Otherwise, the same rules apply as the last time you worked +with this device. + +When the instruction pointer is bound to a register, its value is written to that register just +before each instruction is executed, and the value of that register is written back to the +instruction pointer immediately after each instruction finishes execution. Afterward, move to the +next instruction by adding one to the instruction pointer, even if the value in the instruction +pointer was just updated by an instruction. (Because of this, instructions must effectively set the +instruction pointer to the instruction before the one they want executed next.) + +The instruction pointer is 0 during the first instruction, 1 during the second, and so on. If the +instruction pointer ever causes the device to attempt to load an instruction outside the +instructions defined in the program, the program instead immediately halts. The instruction pointer +starts at 0. + +It turns out that this new information is already proving useful: the CPU in the device is not very +powerful, and a background process is occupying most of its time. You dump the background process' +declarations and instructions to a file (your puzzle input), making sure to use the names of the +opcodes rather than the numbers. + +For example, suppose you have the following program: + +#ip 0 +seti 5 0 1 +seti 6 0 2 +addi 0 1 0 +addr 1 2 3 +setr 1 0 0 +seti 8 0 4 +seti 9 0 5 + +When executed, the following instructions are executed. Each line contains the value of the +instruction pointer at the time the instruction started, the values of the six registers before +executing the instructions (in square brackets), the instruction itself, and the values of the six +registers after executing the instruction (also in square brackets). + +ip=0 [0, 0, 0, 0, 0, 0] seti 5 0 1 [0, 5, 0, 0, 0, 0] +ip=1 [1, 5, 0, 0, 0, 0] seti 6 0 2 [1, 5, 6, 0, 0, 0] +ip=2 [2, 5, 6, 0, 0, 0] addi 0 1 0 [3, 5, 6, 0, 0, 0] +ip=4 [4, 5, 6, 0, 0, 0] setr 1 0 0 [5, 5, 6, 0, 0, 0] +ip=6 [6, 5, 6, 0, 0, 0] seti 9 0 5 [6, 5, 6, 0, 0, 9] + +In detail, when running this program, the following events occur: + + + - The first line (#ip 0) indicates that the instruction pointer should be bound to register 0 in +this program. This is not an instruction, and so the value of the instruction pointer does not +change during the processing of this line. + + - The instruction pointer contains 0, and so the first instruction is executed (seti 5 0 1). It +updates register 0 to the current instruction pointer value (0), sets register 1 to 5, sets the +instruction pointer to the value of register 0 (which has no effect, as the instruction did not +modify register 0), and then adds one to the instruction pointer. + + - The instruction pointer contains 1, and so the second instruction, seti 6 0 2, is executed. This +is very similar to the instruction before it: 6 is stored in register 2, and the instruction pointer +is left with the value 2. + + - The instruction pointer is 2, which points at the instruction addi 0 1 0. This is like a +relative jump: the value of the instruction pointer, 2, is loaded into register 0. Then, addi finds +the result of adding the value in register 0 and the value 1, storing the result, 3, back in +register 0. Register 0 is then copied back to the instruction pointer, which will cause it to end up +1 larger than it would have otherwise and skip the next instruction (addr 1 2 3) entirely. Finally, +1 is added to the instruction pointer. + + - The instruction pointer is 4, so the instruction setr 1 0 0 is run. This is like an absolute +jump: it copies the value contained in register 1, 5, into register 0, which causes it to end up in +the instruction pointer. The instruction pointer is then incremented, leaving it at 6. + + - The instruction pointer is 6, so the instruction seti 9 0 5 stores 9 into register 5. The +instruction pointer is incremented, causing it to point outside the program, and so the program +ends. + + +What value is left in register 0 when the background process halts? + + diff --git a/19/part2 b/19/part2 new file mode 100644 index 0000000..873eecb --- /dev/null +++ b/19/part2 @@ -0,0 +1,8 @@ +--- Part Two --- + +A new background process immediately spins up in its place. It appears identical, but on closer +inspection, you notice that this time, register 0 started with the value 1. + +What value is left in register 0 when this new background process halts? + + diff --git a/src/19/solve.py b/19/solve.py index f764a99..c0c41eb 100644 --- a/src/19/solve.py +++ b/19/solve.py @@ -1,30 +1,18 @@ -from sys import argv as args
+import sys
+sys.path.append("../common")
+import aoc
from math import sqrt
-def parseCommand(l):
+def parse_command(l):
s = l.split(" ")
args = [s[0]]
args = args + [int(v) for v in s[1:]]
return args
-file = open("input.txt")
-input = file.read()
-file.close()
+data = aoc.data.split("\n")
-sinput = """#ip 0
-seti 5 0 1
-seti 6 0 2
-addi 0 1 0
-addr 1 2 3
-setr 1 0 0
-seti 8 0 4
-seti 9 0 5"""
-
-input = input.split("\n")
-
-inspaddr = int(input[0][4:])
-
-instructs = [parseCommand(l) for l in input[1:] if len(l) != 0]
+inspaddr = int(data[0][4:])
+instructs = [parse_command(l) for l in data[1:] if len(l) != 0]
register = [0 for x in range(inspaddr+1)]
@@ -47,12 +35,12 @@ opmap["eqri"] = lambda a, b : 1 * (register[a] == b) opmap["eqrr"] = lambda a, b : 1 * (register[a] == register[b])
-def solve1():
+def solve1(args):
global register, insptr
while register[inspaddr] < len(instructs):
insptr = register[inspaddr]
ins = instructs[insptr]
- #print(register)
+ #aoc.debug(register)
# execute command
if len(register) <= ins[3]:
@@ -62,7 +50,7 @@ def solve1(): # increment instruction pointer
register[inspaddr] += 1
- print(register[0])
+ return register[0]
alpha = [chr(c + ord('a')) for c in range(26)]
@@ -88,13 +76,23 @@ dismap["eqrr"] = lambda a, b : "(%s == %s)" % (alpha[a], alpha[b]) def disassemble():
for i in range(len(instructs)):
ins = instructs[i]
- print(i ,":",alpha[ins[3]],"=", dismap[ins[0]](ins[1], ins[2]))
- print()
-
-def solve2(): # disassembled and reverse engineered to solve
- #disassemble()
- #return
-
+ aoc.debug(i ,":",alpha[ins[3]],"=", dismap[ins[0]](ins[1], ins[2]))
+ aoc.debug()
+
+""" divisor sum algo disassembled
+c = 1
+b = 1
+a = 0
+while b <= f:
+ c = 1
+ while c <= f:
+ if b * c == f:
+ a += b
+ c += 1
+ b += 1
+"""
+
+def solve2(args):
f = 10551276 # found by running
res = 0
@@ -106,26 +104,6 @@ def solve2(): # disassembled and reverse engineered to solve if int(sqrtf) % f == 0:
res += sqrtf
- print(int(res))
- """ divisor sum algo disassembled
- c = 1
- b = 1
- a = 0
- while b <= f:
- c = 1
- while c <= f:
- if b * c == f:
- a += b
- c += 1
- print(".")
- b += 1
- """
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
+ return int(res)
+
+aoc.run(solve1, solve2, sols=[2072, 27578880])
diff --git a/19/test1 b/19/test1 new file mode 100644 index 0000000..d7d2a21 --- /dev/null +++ b/19/test1 @@ -0,0 +1,8 @@ +#ip 0 +seti 5 0 1 +seti 6 0 2 +addi 0 1 0 +addr 1 2 3 +setr 1 0 0 +seti 8 0 4 +seti 9 0 5 diff --git a/src/20/.gitignore b/20/.gitignore index 53752db..53752db 100644 --- a/src/20/.gitignore +++ b/20/.gitignore diff --git a/src/20/input.txt b/20/input index 9c6c2aa..9c6c2aa 100644 --- a/src/20/input.txt +++ b/20/input diff --git a/20/part1 b/20/part1 new file mode 100644 index 0000000..8216e43 --- /dev/null +++ b/20/part1 @@ -0,0 +1,187 @@ +--- Day 20: A Regular Map --- + +While you were learning about instruction pointers, the Elves made considerable progress. When you +look up, you discover that the North Pole base construction project has completely surrounded you. + +The area you are in is made up entirely of rooms and doors. The rooms are arranged in a grid, and +rooms only connect to adjacent rooms when a door is present between them. + +For example, drawing rooms as ., walls as #, doors as | or -, your current position as X, and where +north is up, the area you're in might look like this: + +##### +#.|.# +#-### +#.|X# +##### + +You get the attention of a passing construction Elf and ask for a map. "I don't have time to draw +out a map of this place - it's huge. Instead, I can give you directions to every room in the +facility!" He writes down some directions on a piece of parchment and runs off. In the example +above, the instructions might have been ^WNE$, a regular expression or "regex" (your puzzle input). + +The regex matches routes (like WNE for "west, north, east") that will take you from your current +room through various doors in the facility. In aggregate, the routes will take you through every +door in the facility at least once; mapping out all of these routes will let you build a proper map +and find your way around. + +^ and $ are at the beginning and end of your regex; these just mean that the regex doesn't match +anything outside the routes it describes. (Specifically, ^ matches the start of the route, and $ +matches the end of it.) These characters will not appear elsewhere in the regex. + +The rest of the regex matches various sequences of the characters N (north), S (south), E (east), +and W (west). In the example above, ^WNE$ matches only one route, WNE, which means you can move +west, then north, then east from your current position. Sequences of letters like this always match +that exact route in the same order. + +Sometimes, the route can branch. A branch is given by a list of options separated by pipes (|) and +wrapped in parentheses. So, ^N(E|W)N$ contains a branch: after going north, you must choose to go +either east or west before finishing your route by going north again. By tracing out the possible +routes after branching, you can determine where the doors are and, therefore, where the rooms are in +the facility. + +For example, consider this regex: ^ENWWW(NEEE|SSE(EE|N))$ + +This regex begins with ENWWW, which means that from your current position, all routes must begin by +moving east, north, and then west three times, in that order. After this, there is a branch. Before +you consider the branch, this is what you know about the map so far, with doors you aren't sure +about marked with a ?: + +#?#?#?#?# +?.|.|.|.? +#?#?#?#-# + ?X|.? + #?#?# + +After this point, there is (NEEE|SSE(EE|N)). This gives you exactly two options: NEEE and SSE(EE|N). +By following NEEE, the map now looks like this: + +#?#?#?#?# +?.|.|.|.? +#-#?#?#?# +?.|.|.|.? +#?#?#?#-# + ?X|.? + #?#?# + +Now, only SSE(EE|N) remains. Because it is in the same parenthesized group as NEEE, it starts from +the same room NEEE started in. It states that starting from that point, there exist doors which will +allow you to move south twice, then east; this ends up at another branch. After that, you can either +move east twice or north once. This information fills in the rest of the doors: + +#?#?#?#?# +?.|.|.|.? +#-#?#?#?# +?.|.|.|.? +#-#?#?#-# +?.?.?X|.? +#-#-#?#?# +?.|.|.|.? +#?#?#?#?# + +Once you've followed all possible routes, you know the remaining unknown parts are all walls, +producing a finished map of the facility: + +######### +#.|.|.|.# +#-####### +#.|.|.|.# +#-#####-# +#.#.#X|.# +#-#-##### +#.|.|.|.# +######### + +Sometimes, a list of options can have an empty option, like (NEWS|WNSE|). This means that routes at +this point could effectively skip the options in parentheses and move on immediately. For example, +consider this regex and the corresponding map: + +^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$ + +########### +#.|.#.|.#.# +#-###-#-#-# +#.|.|.#.#.# +#-#####-#-# +#.#.#X|.#.# +#-#-#####-# +#.#.|.|.|.# +#-###-###-# +#.|.|.#.|.# +########### + +This regex has one main route which, at three locations, can optionally include additional detours +and be valid: (NEWS|), (WNSE|), and (SWEN|). Regardless of which option is taken, the route +continues from the position it is left at after taking those steps. So, for example, this regex +matches all of the following routes (and more that aren't listed here): + + + - ENNWSWWSSSEENEENNN + + - ENNWSWWNEWSSSSEENEENNN + + - ENNWSWWNEWSSSSEENEESWENNNN + + - ENNWSWWSSSEENWNSEEENNN + + +By following the various routes the regex matches, a full map of all of the doors and rooms in the +facility can be assembled. + +To get a sense for the size of this facility, you'd like to determine which room is furthest from +you: specifically, you would like to find the room for which the shortest path to that room would +require passing through the most doors. + + + - In the first example (^WNE$), this would be the north-east corner 3 doors away. + + - In the second example (^ENWWW(NEEE|SSE(EE|N))$), this would be the south-east corner 10 doors +away. + + - In the third example (^ENNWSWW(NEWS|)SSSEEN(WNSE|)EE(SWEN|)NNN$), this would be the north-east +corner 18 doors away. + + +Here are a few more examples: + +Regex: ^ESSWWN(E|NNENN(EESS(WNSE|)SSS|WWWSSSSE(SW|NNNE)))$ +Furthest room requires passing 23 doors + +############# +#.|.|.|.|.|.# +#-#####-###-# +#.#.|.#.#.#.# +#-#-###-#-#-# +#.#.#.|.#.|.# +#-#-#-#####-# +#.#.#.#X|.#.# +#-#-#-###-#-# +#.|.#.|.#.#.# +###-#-###-#-# +#.|.#.|.|.#.# +############# + +Regex: ^WSSEESWWWNW(S|NENNEEEENN(ESSSSW(NWSW|SSEN)|WSWWN(E|WWS(E|SS))))$ +Furthest room requires passing 31 doors + +############### +#.|.|.|.#.|.|.# +#-###-###-#-#-# +#.|.#.|.|.#.#.# +#-#########-#-# +#.#.|.|.|.|.#.# +#-#-#########-# +#.#.#.|X#.|.#.# +###-#-###-#-#-# +#.|.#.#.|.#.|.# +#-###-#####-### +#.|.#.|.|.#.#.# +#-#-#####-#-#-# +#.#.|.|.|.#.|.# +############### + +What is the largest number of doors you would be required to pass through to reach a room? That is, +find the room for which the shortest path from your starting location to that room would require +passing through the most doors; what is the fewest doors you can pass through to reach it? + + diff --git a/20/part2 b/20/part2 new file mode 100644 index 0000000..9d9f481 --- /dev/null +++ b/20/part2 @@ -0,0 +1,8 @@ +--- Part Two --- + +Okay, so the facility is big. + +How many rooms have a shortest path from your current location that pass through at least 1000 +doors? + + diff --git a/src/20/solve.py b/20/solve.py index e978e91..63695b7 100644 --- a/src/20/solve.py +++ b/20/solve.py @@ -1,18 +1,18 @@ -from sys import argv as args
+import sys
+sys.path.append("../common")
+import aoc
from copy import deepcopy
-sinput = list(open("input.txt").read().strip())
+data = list(aoc.data)
-ainput = "^ENWWW(NEEE|SSE(EE|N))$"
-
-def getMap(p):
+def get_map(p):
return vmap[p[1] + spos[1]][p[0] + spos[0]]
-def setMap(p, c):
+def set_map(p, c):
global vmap, spos
vmap[p[1] + spos[1]][p[0] + spos[0]] = c
-def newpos(p, c):
+def new_pos(p, c):
p = p[:]
if c == "N":
p[1] -= 2
@@ -24,10 +24,10 @@ def newpos(p, c): p[0] += 2
return p
-def calcpos(stack):
+def calc_pos(stack):
p = [0,0]
for c in stack:
- p = newpos(p, c)
+ p = new_pos(p, c)
return p
xmin = 0
@@ -35,9 +35,10 @@ xmax = 0 ymin = 0
ymax = 0
-def checkSize(stack):
+def check_size(stack):
global xmin, xmax, ymin, ymax
- p = calcpos(stack)
+
+ p = calc_pos(stack)
if p[0] < xmin:
xmin = p[0]
if p[0] > xmax:
@@ -47,20 +48,20 @@ def checkSize(stack): if p[1] > ymax:
ymax = p[1]
-def drawRoute(stack):
- p = calcpos(stack)
- setMap(p, ".")
- np = newpos(p, stack[-1])
+def draw_route(stack):
+ p = calc_pos(stack)
+ set_map(p, ".")
+ np = new_pos(p, stack[-1])
cp = [0,0]
cp[0] = p[0] + int((p[0] - np[0])/2)
cp[1] = p[1] + int((p[1] - np[1])/2)
- setMap(cp, "+")
+ set_map(cp, "+")
-def iterRegex(func):
+def iter_regex(func):
stacklens = [0]
stack = []
- for i in range(1, len(sinput)-1):
- c = sinput[i]
+ for i in range(1, len(data)-1):
+ c = data[i]
if c == "(":
stacklens.append(0)
elif c == "|":
@@ -88,7 +89,8 @@ vmap = None def genMap():
global vmap, mshape, spos
- iterRegex(checkSize)
+
+ iter_regex(check_size)
xdif = xmax - xmin + 2
ydif = ymax - ymin + 2
@@ -98,12 +100,12 @@ def genMap(): vmap = [["#" for x in range(xdif+1)] for y in range(ydif+1)]
vmap[spos[1]][spos[0]] = "X"
- iterRegex(drawRoute)
+ iter_regex(draw_route)
adjacent = ((-1, 0), (0, -1), (1, 0), (0, 1))
-def genCountmap(sp):
+def gen_countmap(sp):
countmap = dict()
next = dict()
next[(sp[0], sp[1])] = 0
@@ -117,12 +119,12 @@ def genCountmap(sp): for dir in adjacent:
nx = n[0]+dir[0]
ny = n[1]+dir[1]
- if getMap((nx, ny)) != "#" and (nx, ny) not in countmap and (nx, ny) not in temp:
+ if get_map((nx, ny)) != "#" and (nx, ny) not in countmap and (nx, ny) not in temp:
temp[(nx,ny)] = counter
next = temp
return countmap
-def nextStep(cmap, p):
+def next_step(cmap, p):
# adjacent squares
npos = [[p[0] + dir[0], p[1] + dir[1]] for dir in adjacent]
@@ -134,31 +136,16 @@ def nextStep(cmap, p): else:
return sorted(steps, key = lambda x: x[2])[0] #closest
-### SETUP
-
genMap()
-#print("finished generating..")
-### PROBLEM CODE
-
-def solve1():
- cmap = genCountmap((0,0))
+def solve1(args):
+ cmap = gen_countmap((0,0))
ipos = sorted(cmap, key = lambda x : cmap[x])[-1]
- print(int(cmap[ipos]/2))
- #fwriteMap()
- return
-
-def solve2():
- cmap = genCountmap((0,0))
- count = len([v for v in cmap if int(cmap[v]/2) >= 1000 and getMap(v) == "."])
- print(count)
- return
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
+ return int(cmap[ipos]/2)
+
+def solve2(args):
+ cmap = gen_countmap((0,0))
+ count = len([v for v in cmap if int(cmap[v]/2) >= 1000 and get_map(v) == "."])
+ return count
+
+aoc.run(solve1, solve2, sols=[4121, 8636])
diff --git a/20/test1 b/20/test1 new file mode 100644 index 0000000..25ab237 --- /dev/null +++ b/20/test1 @@ -0,0 +1 @@ +^ENWWW(NEEE|SSE(EE|N))$ diff --git a/src/21/input.txt b/21/input index d60c037..d60c037 100644 --- a/src/21/input.txt +++ b/21/input diff --git a/21/part1 b/21/part1 new file mode 100644 index 0000000..0a15881 --- /dev/null +++ b/21/part1 @@ -0,0 +1,41 @@ +--- Day 21: Chronal Conversion --- + +You should have been watching where you were going, because as you wander the new North Pole base, +you trip and fall into a very deep hole! + +Just kidding. You're falling through time again. + +If you keep up your current pace, you should have resolved all of the temporal anomalies by the next +time the device activates. Since you have very little interest in browsing history in 500-year +increments for the rest of your life, you need to find a way to get back to your present time. + +After a little research, you discover two important facts about the behavior of the device: + +First, you discover that the device is hard-wired to always send you back in time in 500-year +increments. Changing this is probably not feasible. + +Second, you discover the activation system (your puzzle input) for the time travel module. +Currently, it appears to run forever without halting. + +If you can cause the activation system to halt at a specific moment, maybe you can make the device +send you so far back in time that you cause an integer underflow in time itself and wrap around back +to your current time! + +The device executes the program as specified in manual section one and manual section two. + +Your goal is to figure out how the program works and cause it to halt. You can only control +register 0; every other register begins at 0 as usual. + +Because time travel is a dangerous activity, the activation system begins with a few instructions +which verify that bitwise AND (via bani) does a numeric operation and not an operation as if the +inputs were interpreted as strings. If the test fails, it enters an infinite loop re-running the +test instead of allowing the program to execute normally. If the test passes, the program +continues, and assumes that all other bitwise operations (banr, bori, and borr) also interpret their +inputs as numbers. (Clearly, the Elves who wrote this system were worried that someone might +introduce a bug while trying to emulate this system with a scripting language.) + +What is the lowest non-negative integer value for register 0 that causes the program to halt after +executing the fewest instructions? (Executing the same instruction multiple times counts as multiple +instructions executed.) + + diff --git a/21/part2 b/21/part2 new file mode 100644 index 0000000..f2435cb --- /dev/null +++ b/21/part2 @@ -0,0 +1,9 @@ +--- Part Two --- + +In order to determine the timing window for your underflow exploit, you also need an upper bound: + +What is the lowest non-negative integer value for register 0 that causes the program to halt after +executing the most instructions? (The program must actually halt; running forever does not count as +halting.) + + diff --git a/src/21/solve.py b/21/solve.py index 1261009..e2b8fce 100644 --- a/src/21/solve.py +++ b/21/solve.py @@ -1,30 +1,18 @@ -from sys import argv as args
+import sys
+sys.path.append("../common")
+import aoc
from math import sqrt
-def parseCommand(l):
+def parse_command(l):
s = l.split(" ")
args = [s[0]]
args = args + [int(v) for v in s[1:]]
return args
-file = open("input.txt")
-sinput = file.read()
-file.close()
+data = aoc.data.split("\n")
-ainput = """#ip 0
-seti 5 0 1
-seti 6 0 2
-addi 0 1 0
-addr 1 2 3
-setr 1 0 0
-seti 8 0 4
-seti 9 0 5"""
-
-sinput = sinput.split("\n")
-
-inspaddr = int(sinput[0][4:])
-
-instructs = [parseCommand(l) for l in sinput[1:] if len(l) != 0]
+inspaddr = int(data[0][4:])
+instructs = [parse_command(l) for l in data[1:] if len(l) != 0]
register = [0 for x in range(inspaddr+1)]
@@ -70,11 +58,12 @@ dismap["eqrr"] = lambda a, b : "(%s == %s)" % (varname(a), varname(b)) def disassemble(s, e):
for i in range(s, e):
ins = instructs[i]
- print(i ,":",varname(ins[3]),"=", dismap[ins[0]](ins[1], ins[2]))
- print()
+ aoc.debug(i ,":",varname(ins[3]),"=", dismap[ins[0]](ins[1], ins[2]))
+ aoc.debug()
-def executeProgram():
+def execute():
global register, insptr
+
while register[inspaddr] < len(instructs):
insptr = register[inspaddr]
ins = instructs[insptr]
@@ -86,30 +75,23 @@ def executeProgram(): # part 1
#if insptr == 13 and register[4] == 1:
- # print(register)
+ # aoc.debug(register)
# return
# increment instruction pointer
register[inspaddr] += 1
-### SETUP
-
-
-### PROGRAM CODE
-
-
-def solve1():
+def solve1(args):
r0 = 1797184 # (first opportunity for comparison r1 and r0)
#disassemble(0, len(instructs))
- #executeProgram()
+ #execute()
- print(r0)
- return
+ return r0
-def solve2():
+def solve2(args):
r1 = 0
- possibles = list()
+ candidates = list()
while True:
r4 = r1 | 65536 # flip 9th bit
r1 = 3798839
@@ -122,18 +104,9 @@ def solve2(): if r4 < 256:
break
r4 = int(r4/256) # bit shift 8 to the right
- if r1 not in possibles:
- possibles.append(r1)
- #print("=>",r1)
- elif r1 == possibles[-1]:
- print(possibles[-1])
- break
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
+ if r1 not in candidates:
+ candidates.append(r1)
+ elif r1 == candidates[-1]:
+ return candidates[-1]
+
+aoc.run(solve1, solve2, sols=[1797184, 11011493])
diff --git a/21/test1 b/21/test1 new file mode 100644 index 0000000..d7d2a21 --- /dev/null +++ b/21/test1 @@ -0,0 +1,8 @@ +#ip 0 +seti 5 0 1 +seti 6 0 2 +addi 0 1 0 +addr 1 2 3 +setr 1 0 0 +seti 8 0 4 +seti 9 0 5 diff --git a/src/22/input.txt b/22/input index 9b643c6..9b643c6 100644 --- a/src/22/input.txt +++ b/22/input diff --git a/22/part1 b/22/part1 new file mode 100644 index 0000000..2b50fba --- /dev/null +++ b/22/part1 @@ -0,0 +1,105 @@ +--- 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/22/part2 b/22/part2 new file mode 100644 index 0000000..bd37d9a --- /dev/null +++ b/22/part2 @@ -0,0 +1,302 @@ +--- 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? + + diff --git a/src/22/solve.py b/22/solve.py index 29db6d7..375ae23 100644 --- a/src/22/solve.py +++ b/22/solve.py @@ -1,15 +1,10 @@ -# second part was solved with help from subreddit
-
-from sys import argv as args
+import sys
+sys.path.append("../common")
+import aoc
import networkx
adjacent = [[-1, 0], [0, -1], [1, 0], [0, 1]]
-# load file
-file = open("input.txt")
-sinput = file.read()
-file.close()
-
# create symbol definitions
symbols = [".", "=", "|"]
rocky, wet, narrow = 0, 1, 2
@@ -21,31 +16,31 @@ tooloptions[wet] = (gear, neither) tooloptions[narrow] = (torch, neither)
# parse input file
-def parseInput(si):
+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 getErosionLevel(n):
+def get_erosion_level(n):
return (n + depth) % 20183
# generate map of erosion types
-def genMap():
+def gen_map():
grid = [[0 for x in range(mrange[0])] for y in range(mrange[1])]
# generate values on x side
- grid[0] = [getErosionLevel(x * 16807) for x in range(mrange[0])]
+ 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] = getErosionLevel(y * 48271)
+ 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] = getErosionLevel(grid[y-1][x] * grid[y][x-1])
+ 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])]
@@ -56,53 +51,43 @@ def genMap(): return grid
# define constants from input file
-depth, target = parseInput(sinput)
+depth, target = parse_input(aoc.data)
mrange = (target[0] + 100, target[1] + 100) # 100 block padding for potential hook-paths
-vmap = genMap()
+vmap = gen_map()
-# risk level of area is sum of risk levels
-def getRiskLevel(width, height):
+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
-
-# indices of blocks around pos p
-def getAround(p):
+def adj(p):
return [[p[0] + di[0], p[1] + di[1]] for di in adjacent]
-# traverse grid using dijkstra's algorithm (3d)
def dijkstra():
graph = networkx.Graph()
for y in range(mrange[1]):
for x in range(mrange[0]):
tools = tooloptions[vmap[y][x]]
- graph.add_edge((x, y, tools[0]), (x, y, tools[1]), weight = 7) # always takes 7 minutes to switch, 2 z-options for each tool
- for (nx, ny) in getAround((x, y)): # for all surrounding positions
+ # 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]]
- for tool in [t for t in tools if t in ntools]: # if tool is usable in both environments
- graph.add_edge((x, y, tool), (nx, ny, tool), weight = 1) # then it only takes 1 minute
- return networkx.dijkstra_path_length(graph, (0, 0, torch), (target[0], target[1], torch))
-
-#print("setup done..")
-
-### PROGRAM CODE
+ # 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)
-def solve1():
- print(getRiskLevel(target[0], target[1]))
+ return networkx.dijkstra_path_length(graph,
+ (0, 0, torch), (target[0], target[1], torch))
-def solve2():
- print(dijkstra())
+def solve1(args):
+ return risk_level(target[0], target[1])
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
+def solve2(args):
+ return dijkstra()
-main()
+aoc.run(solve1, solve2, sols=[11359, 976])
diff --git a/src/23/input.txt b/23/input index 907fba5..907fba5 100644 --- a/src/23/input.txt +++ b/23/input diff --git a/23/part1 b/23/part1 new file mode 100644 index 0000000..1ae65b5 --- /dev/null +++ b/23/part1 @@ -0,0 +1,64 @@ +--- Day 23: Experimental Emergency Teleportation --- + +Using your torch to search the darkness of the rocky cavern, you finally locate the man's friend: a +small reindeer. + +You're not sure how it got so far in this cave. It looks sick - too sick to walk - and too heavy +for you to carry all the way back. Sleighs won't be invented for another 1500 years, of course. + +The only option is experimental emergency teleportation. + +You hit the "experimental emergency teleportation" button on the device and push I accept the risk +on no fewer than 18 different warning messages. Immediately, the device deploys hundreds of tiny +nanobots which fly around the cavern, apparently assembling themselves into a very specific +formation. The device lists the X,Y,Z position (pos) for each nanobot as well as its signal radius +(r) on its tiny screen (your puzzle input). + +Each nanobot can transmit signals to any integer coordinate which is a distance away from it less +than or equal to its signal radius (as measured by Manhattan distance). Coordinates a distance away +of less than or equal to a nanobot's signal radius are said to be in range of that nanobot. + +Before you start the teleportation process, you should determine which nanobot is the strongest +(that is, which has the largest signal radius) and then, for that nanobot, the total number of +nanobots that are in range of it, including itself. + +For example, given the following nanobots: + +pos=<0,0,0>, r=4 +pos=<1,0,0>, r=1 +pos=<4,0,0>, r=3 +pos=<0,2,0>, r=1 +pos=<0,5,0>, r=3 +pos=<0,0,3>, r=1 +pos=<1,1,1>, r=1 +pos=<1,1,2>, r=1 +pos=<1,3,1>, r=1 + +The strongest nanobot is the first one (position 0,0,0) because its signal radius, 4 is the largest. +Using that nanobot's location and signal radius, the following nanobots are in or out of range: + + + - The nanobot at 0,0,0 is distance 0 away, and so it is in range. + + - The nanobot at 1,0,0 is distance 1 away, and so it is in range. + + - The nanobot at 4,0,0 is distance 4 away, and so it is in range. + + - The nanobot at 0,2,0 is distance 2 away, and so it is in range. + + - The nanobot at 0,5,0 is distance 5 away, and so it is not in range. + + - The nanobot at 0,0,3 is distance 3 away, and so it is in range. + + - The nanobot at 1,1,1 is distance 3 away, and so it is in range. + + - The nanobot at 1,1,2 is distance 4 away, and so it is in range. + + - The nanobot at 1,3,1 is distance 5 away, and so it is not in range. + + +In this example, in total, 7 nanobots are in range of the nanobot with the largest signal radius. + +Find the nanobot with the largest signal radius. How many nanobots are in range of its signals? + + diff --git a/23/part2 b/23/part2 new file mode 100644 index 0000000..ace2cbb --- /dev/null +++ b/23/part2 @@ -0,0 +1,27 @@ +--- Part Two --- + +Now, you just need to figure out where to position yourself so that you're actually teleported when +the nanobots activate. + +To increase the probability of success, you need to find the coordinate which puts you in range of +the largest number of nanobots. If there are multiple, choose one closest to your position (0,0,0, +measured by manhattan distance). + +For example, given the following nanobot formation: + +pos=<10,12,12>, r=2 +pos=<12,14,12>, r=2 +pos=<16,12,12>, r=4 +pos=<14,14,14>, r=6 +pos=<50,50,50>, r=200 +pos=<10,10,10>, r=5 + +Many coordinates are in range of some of the nanobots in this formation. However, only the +coordinate 12,12,12 is in range of the most nanobots: it is in range of the first five, but is not +in range of the nanobot at 10,10,10. (All other coordinates are in range of fewer than five +nanobots.) This coordinate's distance from 0,0,0 is 36. + +Find the coordinates that are in range of the largest number of nanobots. What is the shortest +manhattan distance between any of those points and 0,0,0? + + diff --git a/src/23/solve.py b/23/solve.py index dc029af..f78dd94 100644 --- a/src/23/solve.py +++ b/23/solve.py @@ -1,25 +1,19 @@ -# 2nd part solved with the help of subreddit - -from sys import argv as args +import sys +sys.path.append("../common") +import aoc import math -# read input file -file = open("input.txt") -sinput = file.read() -file.close() - # nanobots consist of tuples containing: (position, radius) nanobots = list() # parse a line of input file -def parseLine(l): +def parse_entry(l): s = l.split(">, ") pos = [int(v) for v in s[0].split("=<")[1].split(",")] radius = int(s[1].split("=")[1]) nanobots.append((pos, radius)) -# parse input file -sinput = [parseLine(l) for l in sinput.split("\n") if len(l) != 0] +data = [parse_entry(l) for l in aoc.data.split("\n") if len(l) != 0] # manhattan distance def dist(p1, p2): @@ -29,15 +23,15 @@ def dist(p1, p2): return xd + yd + zd # two nanobots range overlap -def isoverlap(nb1, nb2): +def is_overlap(nb1, nb2): return nb1[1] + nb2[1] >= dist(nb1[0], nb2[0]) # nanobots range completely inside anothers range -def isinside(nb1, nb2): +def is_inside(nb1, nb2): return dist(nb1[0], nb2[0]) <= nb2[1] - nb1[1] # check if range of nanobot is inside grid -def tileinrange(tile, nb, gridsize): +def tile_in_range(tile, nb, gridsize): hgridsize = math.floor(gridsize / 2) # case gridsize = 1 => squares should have 0 width nbp = nb[0] ds = [abs(nbp[i] - tile[i]) for i in range(3)] @@ -47,18 +41,17 @@ def tileinrange(tile, nb, gridsize): ds = [d * hgridsize / md for d in ds] # get distance along squares sides return dist(nbp, tile) - sum(ds) <= nb[1] -### PROGRAM CODE - -def solve1(): +def solve1(args): maxr = max(nanobots, key = lambda x : x[1]) inrange = 0 for nb in nanobots: if dist(nb[0], maxr[0]) <= maxr[1]: inrange += 1 - print(inrange) + return inrange -def solve2(): +def solve2(args): global nanobots + # use smaller getting grid like binary search to find position in range of most nanobots minpx = min(nanobots, key = lambda x : x[0][0])[0][0] minpy = min(nanobots, key = lambda x : x[0][1])[0][1] @@ -88,29 +81,28 @@ def solve2(): z = minp[2] + nz * gridsize intile = 0 for nb in nanobots: - if tileinrange((x, y, z), nb, gridsize): # check if nanobots range intersects with tile + # check if nanobots range intersects with tile + if tile_in_range((x, y, z), nb, gridsize): intile += 1 if maxintile < intile: maxintile = intile bestpos = (x, y, z) elif maxintile == intile: - if maxintile == 0 or sum([abs(v) for v in (x, y, z)]) < sum([abs(v) for v in bestpos]): # if two gridtiles have the same count, choose the one closest to the origin + dist = sum([abs(v) for v in (x, y, z)]) + bestdist = sum([abs(v) for v in bestpos]) + # if two gridtiles have the same count, + # choose the one closest to the origin + if maxintile == 0 or dist < bestdist: bestpos = (x, y, z) if gridsize == 1: break + gridsize = math.floor(gridsize / 2) minp = [v - gridsize for v in bestpos] maxp = [v + gridsize for v in bestpos] - print(sum(bestpos)) - -def main(): - if len(args) > 1: - if args[1] == "1": - solve1() - elif args[1] == "2": - solve2() + return sum(bestpos) -main() +aoc.run(solve1, solve2, sols=[573, 107279292]) diff --git a/src/24/input.txt b/24/input index 969be90..969be90 100644 --- a/src/24/input.txt +++ b/24/input diff --git a/24/part1 b/24/part1 new file mode 100644 index 0000000..636d62b --- /dev/null +++ b/24/part1 @@ -0,0 +1,199 @@ +--- Day 24: Immune System Simulator 20XX --- + +After a weird buzzing noise, you appear back at the man's cottage. He seems relieved to see his +friend, but quickly notices that the little reindeer caught some kind of cold while out exploring. + +The portly man explains that this reindeer's immune system isn't similar to regular reindeer immune +systems: + +The immune system and the infection each have an army made up of several groups; each group consists +of one or more identical units. The armies repeatedly fight until only one army has units +remaining. + +Units within a group all have the same hit points (amount of damage a unit can take before it is +destroyed), attack damage (the amount of damage each unit deals), an attack type, an initiative +(higher initiative units attack first and win ties), and sometimes weaknesses or immunities. Here is +an example group: + +18 units each with 729 hit points (weak to fire; immune to cold, slashing) + with an attack that does 8 radiation damage at initiative 10 + +Each group also has an effective power: the number of units in that group multiplied by their attack +damage. The above group has an effective power of 18 * 8 = 144. Groups never have zero or negative +units; instead, the group is removed from combat. + +Each fight consists of two phases: target selection and attacking. + +During the target selection phase, each group attempts to choose one target. In decreasing order of +effective power, groups choose their targets; in a tie, the group with the higher initiative chooses +first. The attacking group chooses to target the group in the enemy army to which it would deal the +most damage (after accounting for weaknesses and immunities, but not accounting for whether the +defending group has enough units to actually receive all of that damage). + +If an attacking group is considering two defending groups to which it would deal equal damage, it +chooses to target the defending group with the largest effective power; if there is still a tie, it +chooses the defending group with the highest initiative. If it cannot deal any defending groups +damage, it does not choose a target. Defending groups can only be chosen as a target by one +attacking group. + +At the end of the target selection phase, each group has selected zero or one groups to attack, and +each group is being attacked by zero or one groups. + +During the attacking phase, each group deals damage to the target it selected, if any. Groups attack +in decreasing order of initiative, regardless of whether they are part of the infection or the +immune system. (If a group contains no units, it cannot attack.) + +The damage an attacking group deals to a defending group depends on the attacking group's attack +type and the defending group's immunities and weaknesses. By default, an attacking group would deal +damage equal to its effective power to the defending group. However, if the defending group is +immune to the attacking group's attack type, the defending group instead takes no damage; if the +defending group is weak to the attacking group's attack type, the defending group instead takes +double damage. + +The defending group only loses whole units from damage; damage is always dealt in such a way that it +kills the most units possible, and any remaining damage to a unit that does not immediately kill it +is ignored. For example, if a defending group contains 10 units with 10 hit points each and receives +75 damage, it loses exactly 7 units and is left with 3 units at full health. + +After the fight is over, if both armies still contain units, a new fight begins; combat only ends +once one army has lost all of its units. + +For example, consider the following armies: + +Immune System: +17 units each with 5390 hit points (weak to radiation, bludgeoning) with + an attack that does 4507 fire damage at initiative 2 +989 units each with 1274 hit points (immune to fire; weak to bludgeoning, + slashing) with an attack that does 25 slashing damage at initiative 3 + +Infection: +801 units each with 4706 hit points (weak to radiation) with an attack + that does 116 bludgeoning damage at initiative 1 +4485 units each with 2961 hit points (immune to radiation; weak to fire, + cold) with an attack that does 12 slashing damage at initiative 4 + +If these armies were to enter combat, the following fights, including details during the target +selection and attacking phases, would take place: + +Immune System: +Group 1 contains 17 units +Group 2 contains 989 units +Infection: +Group 1 contains 801 units +Group 2 contains 4485 units + +Infection group 1 would deal defending group 1 185832 damage +Infection group 1 would deal defending group 2 185832 damage +Infection group 2 would deal defending group 2 107640 damage +Immune System group 1 would deal defending group 1 76619 damage +Immune System group 1 would deal defending group 2 153238 damage +Immune System group 2 would deal defending group 1 24725 damage + +Infection group 2 attacks defending group 2, killing 84 units +Immune System group 2 attacks defending group 1, killing 4 units +Immune System group 1 attacks defending group 2, killing 51 units +Infection group 1 attacks defending group 1, killing 17 units + +Immune System: +Group 2 contains 905 units +Infection: +Group 1 contains 797 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 184904 damage +Immune System group 2 would deal defending group 1 22625 damage +Immune System group 2 would deal defending group 2 22625 damage + +Immune System group 2 attacks defending group 1, killing 4 units +Infection group 1 attacks defending group 2, killing 144 units + +Immune System: +Group 2 contains 761 units +Infection: +Group 1 contains 793 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 183976 damage +Immune System group 2 would deal defending group 1 19025 damage +Immune System group 2 would deal defending group 2 19025 damage + +Immune System group 2 attacks defending group 1, killing 4 units +Infection group 1 attacks defending group 2, killing 143 units + +Immune System: +Group 2 contains 618 units +Infection: +Group 1 contains 789 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 183048 damage +Immune System group 2 would deal defending group 1 15450 damage +Immune System group 2 would deal defending group 2 15450 damage + +Immune System group 2 attacks defending group 1, killing 3 units +Infection group 1 attacks defending group 2, killing 143 units + +Immune System: +Group 2 contains 475 units +Infection: +Group 1 contains 786 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 182352 damage +Immune System group 2 would deal defending group 1 11875 damage +Immune System group 2 would deal defending group 2 11875 damage + +Immune System group 2 attacks defending group 1, killing 2 units +Infection group 1 attacks defending group 2, killing 142 units + +Immune System: +Group 2 contains 333 units +Infection: +Group 1 contains 784 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 181888 damage +Immune System group 2 would deal defending group 1 8325 damage +Immune System group 2 would deal defending group 2 8325 damage + +Immune System group 2 attacks defending group 1, killing 1 unit +Infection group 1 attacks defending group 2, killing 142 units + +Immune System: +Group 2 contains 191 units +Infection: +Group 1 contains 783 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 181656 damage +Immune System group 2 would deal defending group 1 4775 damage +Immune System group 2 would deal defending group 2 4775 damage + +Immune System group 2 attacks defending group 1, killing 1 unit +Infection group 1 attacks defending group 2, killing 142 units + +Immune System: +Group 2 contains 49 units +Infection: +Group 1 contains 782 units +Group 2 contains 4434 units + +Infection group 1 would deal defending group 2 181424 damage +Immune System group 2 would deal defending group 1 1225 damage +Immune System group 2 would deal defending group 2 1225 damage + +Immune System group 2 attacks defending group 1, killing 0 units +Infection group 1 attacks defending group 2, killing 49 units + +Immune System: +No groups remain. +Infection: +Group 1 contains 782 units +Group 2 contains 4434 units + +In the example above, the winning army ends up with 782 + 4434 = 5216 units. + +You scan the reindeer's condition (your puzzle input); the white-bearded man looks nervous. As it +stands now, how many units would the winning army have? + + diff --git a/24/part2 b/24/part2 new file mode 100644 index 0000000..1b03a02 --- /dev/null +++ b/24/part2 @@ -0,0 +1,150 @@ +--- Part Two --- + +Things aren't looking good for the reindeer. The man asks whether more milk and cookies would help +you think. + +If only you could give the reindeer's immune system a boost, you might be able to change the outcome +of the combat. + +A boost is an integer increase in immune system units' attack damage. For example, if you were to +boost the above example's immune system's units by 1570, the armies would instead look like this: + +Immune System: +17 units each with 5390 hit points (weak to radiation, bludgeoning) with + an attack that does 6077 fire damage at initiative 2 +989 units each with 1274 hit points (immune to fire; weak to bludgeoning, + slashing) with an attack that does 1595 slashing damage at initiative 3 + +Infection: +801 units each with 4706 hit points (weak to radiation) with an attack + that does 116 bludgeoning damage at initiative 1 +4485 units each with 2961 hit points (immune to radiation; weak to fire, + cold) with an attack that does 12 slashing damage at initiative 4 + +With this boost, the combat proceeds differently: + +Immune System: +Group 2 contains 989 units +Group 1 contains 17 units +Infection: +Group 1 contains 801 units +Group 2 contains 4485 units + +Infection group 1 would deal defending group 2 185832 damage +Infection group 1 would deal defending group 1 185832 damage +Infection group 2 would deal defending group 1 53820 damage +Immune System group 2 would deal defending group 1 1577455 damage +Immune System group 2 would deal defending group 2 1577455 damage +Immune System group 1 would deal defending group 2 206618 damage + +Infection group 2 attacks defending group 1, killing 9 units +Immune System group 2 attacks defending group 1, killing 335 units +Immune System group 1 attacks defending group 2, killing 32 units +Infection group 1 attacks defending group 2, killing 84 units + +Immune System: +Group 2 contains 905 units +Group 1 contains 8 units +Infection: +Group 1 contains 466 units +Group 2 contains 4453 units + +Infection group 1 would deal defending group 2 108112 damage +Infection group 1 would deal defending group 1 108112 damage +Infection group 2 would deal defending group 1 53436 damage +Immune System group 2 would deal defending group 1 1443475 damage +Immune System group 2 would deal defending group 2 1443475 damage +Immune System group 1 would deal defending group 2 97232 damage + +Infection group 2 attacks defending group 1, killing 8 units +Immune System group 2 attacks defending group 1, killing 306 units +Infection group 1 attacks defending group 2, killing 29 units + +Immune System: +Group 2 contains 876 units +Infection: +Group 2 contains 4453 units +Group 1 contains 160 units + +Infection group 2 would deal defending group 2 106872 damage +Immune System group 2 would deal defending group 2 1397220 damage +Immune System group 2 would deal defending group 1 1397220 damage + +Infection group 2 attacks defending group 2, killing 83 units +Immune System group 2 attacks defending group 2, killing 427 units + +After a few fights... + +Immune System: +Group 2 contains 64 units +Infection: +Group 2 contains 214 units +Group 1 contains 19 units + +Infection group 2 would deal defending group 2 5136 damage +Immune System group 2 would deal defending group 2 102080 damage +Immune System group 2 would deal defending group 1 102080 damage + +Infection group 2 attacks defending group 2, killing 4 units +Immune System group 2 attacks defending group 2, killing 32 units + +Immune System: +Group 2 contains 60 units +Infection: +Group 1 contains 19 units +Group 2 contains 182 units + +Infection group 1 would deal defending group 2 4408 damage +Immune System group 2 would deal defending group 1 95700 damage +Immune System group 2 would deal defending group 2 95700 damage + +Immune System group 2 attacks defending group 1, killing 19 units + +Immune System: +Group 2 contains 60 units +Infection: +Group 2 contains 182 units + +Infection group 2 would deal defending group 2 4368 damage +Immune System group 2 would deal defending group 2 95700 damage + +Infection group 2 attacks defending group 2, killing 3 units +Immune System group 2 attacks defending group 2, killing 30 units + +After a few more fights... + +Immune System: +Group 2 contains 51 units +Infection: +Group 2 contains 40 units + +Infection group 2 would deal defending group 2 960 damage +Immune System group 2 would deal defending group 2 81345 damage + +Infection group 2 attacks defending group 2, killing 0 units +Immune System group 2 attacks defending group 2, killing 27 units + +Immune System: +Group 2 contains 51 units +Infection: +Group 2 contains 13 units + +Infection group 2 would deal defending group 2 312 damage +Immune System group 2 would deal defending group 2 81345 damage + +Infection group 2 attacks defending group 2, killing 0 units +Immune System group 2 attacks defending group 2, killing 13 units + +Immune System: +Group 2 contains 51 units +Infection: +No groups remain. + +This boost would allow the immune system's armies to win! It would be left with 51 units. + +You don't even know how you could boost the reindeer's immune system or what effect it might have, +so you need to be cautious and find the smallest boost that would allow the immune system to win. + +How many units does the immune system have left after getting the smallest boost it needs to win? + + diff --git a/src/24/solve.py b/24/solve.py index 020af79..fc89c84 100644 --- a/src/24/solve.py +++ b/24/solve.py @@ -1,22 +1,22 @@ -from sys import argv as args
-
-sinput = open("input.txt").read()
+import sys
+sys.path.append("../common")
+import aoc
immunesys = 0
infection = 1
ctype = 0
# parse input from file
-def parseInput():
+def parse_input():
groups = list()
- for l in sinput.split("\n"):
- pl = parseLine(l)
+ for l in aoc.data.split("\n"):
+ pl = parse_entry(l)
if pl != None:
groups.append(pl)
return groups
# parse line of input
-def parseLine(line):
+def parse_entry(line):
global ctype
group = None
if "Immune" in line:
@@ -43,16 +43,16 @@ def parseLine(line): group["dmgtype"] = dmginfo[1]
return group
-def getEffectivePower(g):
+def effective_power(g):
return g["units"] * g["dmg"]
-def getDamage(attacker, defender):
- dmg = getEffectivePower(attacker)
+def damage(attacker, defender):
+ dmg = effective_power(attacker)
dmg *= (0 if attacker["dmgtype"] in defender["immune"] else 1)
dmg *= (2 if attacker["dmgtype"] in defender["weak"] else 1)
return dmg
-groups = parseInput()
+groups = parse_input()
def fight():
global groups
@@ -66,14 +66,15 @@ def fight(): # target selection
attacked = list()
attackpairs = list()
- groups = sorted(groups, key = lambda x : (getEffectivePower(x), x["initiative"]), reverse = True)
+ groups = sorted(groups, key = lambda x : (effective_power(x), x["initiative"]), reverse = True)
for group in groups:
# choose group of other army, which is not already being attacked and sort appropriately
enemies = [g for g in groups if g["type"] != group["type"] and g not in attacked]
if len(enemies) == 0:
continue
- target = max(enemies, key = lambda x : (getDamage(group, x), getEffectivePower(x), x["initiative"]))
- if getDamage(group, target) != 0: # enemies which arent immune
+ target = max(enemies, key = lambda x : \
+ (damage(group, x), effective_power(x), x["initiative"]))
+ if damage(group, target) != 0: # enemies which arent immune
attacked.append(target)
attackpairs.append((groups.index(group), groups.index(target)))
@@ -83,9 +84,11 @@ def fight(): for ap in attackpairs:
attacker = groups[ap[0]]
attacked = groups[ap[1]]
- if attacker["units"] > 0 and attacked["units"] > 0: # if attacker or defender is dead, no need to attack
- dmg = getDamage(attacker, attacked)
- attacked["units"] = max(0, attacked["units"] - dmg // attacked["unithp"]) # remove whole numbers of units
+ # if attacker or defender is dead, no need to attack
+ if attacker["units"] > 0 and attacked["units"] > 0:
+ dmg = damage(attacker, attacked)
+ # remove whole numbers of units
+ attacked["units"] = max(0, attacked["units"] - dmg // attacked["unithp"])
groups = [g for g in groups if g["units"] > 0]
immalive = sum([g["units"] for g in groups if g["type"] == immunesys])
@@ -94,18 +97,19 @@ def fight(): if units == lunits:
return units
lunits = units
+
return units
-def solve1():
- print(fight())
+def solve1(args):
+ return fight()
-def solve2():
+def solve2(args):
global groups
immunewin = False
boost = 1
while not immunewin:
- groups = parseInput()
+ groups = parse_input()
for g in groups:
if g["type"] == immunesys:
g["dmg"] += boost
@@ -116,14 +120,8 @@ def solve2(): boost += 1
- #print("boost:", boost)
- print("units:", sum([v["units"] for v in groups]))
+ aoc.debug("boost:", boost)
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
+ return sum([v["units"] for v in groups])
-main()
+aoc.run(solve1, solve2, sols=[10538, 9174])
diff --git a/src/25/input.txt b/25/input index dfdbb5b..dfdbb5b 100644 --- a/src/25/input.txt +++ b/25/input diff --git a/25/part1 b/25/part1 new file mode 100644 index 0000000..d1230c0 --- /dev/null +++ b/25/part1 @@ -0,0 +1,108 @@ +--- Day 25: Four-Dimensional Adventure --- + +The reindeer's symptoms are getting worse, and neither you nor the white-bearded man have a +solution. At least the reindeer has a warm place to rest: a small bed near where you're sitting. + +As you reach down, the reindeer looks up at you, accidentally bumping a button on your wrist-mounted +device with its nose in the process - a button labeled "help". + +"Hello, and welcome to the Time Travel Support Hotline! If you are lost in time and space, press 1. +If you are trapped in a time paradox, press 2. If you need help caring for a sick reindeer, press 3. +If you--" + +Beep. + +A few seconds later, you hear a new voice. "Hello; please state the nature of your reindeer." You +try to describe the situation. + +"Just a moment, I think I can remotely run a diagnostic scan." A beam of light projects from the +device and sweeps over the reindeer a few times. + +"Okay, it looks like your reindeer is very low on magical energy; it should fully recover if we can +fix that. Let me check your timeline for a source.... Got one. There's actually a powerful source +of magical energy about 1000 years forward from you, and at roughly your position, too! It looks +like... hot chocolate? Anyway, you should be able to travel there to pick some up; just don't +forget a mug! Is there anything else I can help you with today?" + +You explain that your device isn't capable of going forward in time. "I... see. That's tricky. +Well, according to this information, your device should have the necessary hardware to open a small +portal and send some hot chocolate back to you. You'll need a list of fixed points in spacetime; I'm +transmitting it to you now." + +"You just need to align your device to the constellations of fixed points so that it can lock on to +the destination and open the portal. Let me look up how much hot chocolate that breed of reindeer +needs." + +"It says here that your particular reindeer is-- this can't be right, it says there's only one like +that in the universe! But THAT means that you're--" You disconnect the call. + +The list of fixed points in spacetime (your puzzle input) is a set of four-dimensional coordinates. +To align your device, acquire the hot chocolate, and save the reindeer, you just need to find the +number of constellations of points in the list. + +Two points are in the same constellation if their manhattan distance apart is no more than 3 or if +they can form a chain of points, each a manhattan distance no more than 3 from the last, between the +two of them. (That is, if a point is close enough to a constellation, it "joins" that +constellation.) For example: + + 0,0,0,0 + 3,0,0,0 + 0,3,0,0 + 0,0,3,0 + 0,0,0,3 + 0,0,0,6 + 9,0,0,0 +12,0,0,0 + +In the above list, the first six points form a single constellation: 0,0,0,0 is exactly distance 3 +from the next four, and the point at 0,0,0,6 is connected to the others by being 3 away from +0,0,0,3, which is already in the constellation. The bottom two points, 9,0,0,0 and 12,0,0,0 are in a +separate constellation because no point is close enough to connect them to the first constellation. +So, in the above list, the number of constellations is 2. (If a point at 6,0,0,0 were present, it +would connect 3,0,0,0 and 9,0,0,0, merging all of the points into a single giant constellation +instead.) + +In this example, the number of constellations is 4: + +-1,2,2,0 +0,0,2,-2 +0,0,0,-2 +-1,2,0,0 +-2,-2,-2,2 +3,0,2,-1 +-1,3,2,2 +-1,0,-1,0 +0,2,1,-2 +3,0,0,0 + +In this one, it's 3: + +1,-1,0,1 +2,0,-1,0 +3,2,-1,0 +0,0,3,1 +0,0,-1,-1 +2,3,-2,0 +-2,2,0,0 +2,-2,0,-1 +1,-1,0,-1 +3,2,0,2 + +Finally, in this one, it's 8: + +1,-1,-1,-2 +-2,-2,0,1 +0,2,1,3 +-2,3,-2,1 +0,2,3,-2 +-1,-1,1,-2 +0,-2,-1,0 +-2,2,3,-1 +1,2,2,0 +-1,-2,0,-2 + +The portly man nervously strokes his white beard. It's time to get that hot chocolate. + +How many constellations are formed by the fixed points in spacetime? + + diff --git a/25/part2 b/25/part2 new file mode 100644 index 0000000..5b55d88 --- /dev/null +++ b/25/part2 @@ -0,0 +1,15 @@ +--- Part Two --- + +A small glowing portal opens above the mug you prepared and just enough hot chocolate streams in to +fill it. You suspect the reindeer has never encountered hot chocolate before, but seems to enjoy it +anyway. You hope it works. + +It's time to start worrying about that integer underflow in time itself you set up a few days ago. +You check the status of the device: "Insufficient chronal energy for activation. Energy required: 50 +stars." + +The reindeer bumps the device with its nose. + +"Energy required: 49 stars." + + diff --git a/25/solve.py b/25/solve.py new file mode 100644 index 0000000..973885a --- /dev/null +++ b/25/solve.py @@ -0,0 +1,50 @@ +import sys
+sys.path.append("../common")
+import aoc
+
+def parse_entry(l):
+ return [int(v) for v in l.split(",")]
+
+coordinates = [parse_entry(l) for l in aoc.data.split("\n") if len(l) != 0]
+
+def dist(c1, c2):
+ return sum([abs(c1[i] - c2[i]) for i in range(4)])
+
+def get_close(coords, c):
+ match = list()
+ j = 0
+ while j in range(len(coords)):
+ if dist(c, coords[j]) <= 3:
+ match.append(coords[j])
+ coords.pop(j)
+ else:
+ j += 1
+ return match
+
+"""
+sum = 0
+for cons in constellations:
+ sum += len(cons)
+print(sum)
+"""
+
+def solve1(args):
+ constellations = list()
+ available = coordinates[:]
+
+ while len(available) != 0:
+ match = get_close(available, available[0])
+
+ j = 0
+ while j < len(match):
+ match += get_close(available, match[j])
+ j += 1
+
+ constellations.append(match)
+
+ return len(constellations)
+
+def solve2(args):
+ return ""
+
+aoc.run(solve1, solve2, sols=[386, ""])
diff --git a/25/test1 b/25/test1 new file mode 100644 index 0000000..1147af7 --- /dev/null +++ b/25/test1 @@ -0,0 +1,10 @@ +1,-1,-1,-2 +-2,-2,0,1 +0,2,1,3 +-2,3,-2,1 +0,2,3,-2 +-1,-1,1,-2 +0,-2,-1,0 +-2,2,3,-1 +1,2,2,0 +-1,-2,0,-2 diff --git a/25/test2 b/25/test2 new file mode 100644 index 0000000..bf5c2b9 --- /dev/null +++ b/25/test2 @@ -0,0 +1,10 @@ +1,-1,0,1 +2,0,-1,0 +3,2,-1,0 +0,0,3,1 +0,0,-1,-1 +2,3,-2,0 +-2,2,0,0 +2,-2,0,-1 +1,-1,0,-1 +3,2,0,2 diff --git a/25/test3 b/25/test3 new file mode 100644 index 0000000..3089dd5 --- /dev/null +++ b/25/test3 @@ -0,0 +1,8 @@ +0,0,0,0 +3,0,0,0 +0,3,0,0 +0,0,3,0 +0,0,0,3 +0,0,0,6 +9,0,0,0 +12,0,0,0 diff --git a/25/test4 b/25/test4 new file mode 100644 index 0000000..3a97e16 --- /dev/null +++ b/25/test4 @@ -0,0 +1,10 @@ +-1,2,2,0 +0,0,2,-2 +0,0,0,-2 +-1,2,0,0 +-2,-2,-2,2 +3,0,2,-1 +-1,3,2,2 +-1,0,-1,0 +0,2,1,-2 +3,0,0,0 diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..d564047 --- /dev/null +++ b/Makefile @@ -0,0 +1,15 @@ +DAYS = $(shell seq 1 25 | xargs printf "%02i\n") + +.PHONY: all +all:: + +define make-day +all:: $1/run +.PHONY: $1/run +$1/run: + @echo "== day $1 ==" + @echo -en "\npart 1: " && cd $1 && time python3 solve.py 1 + @echo -en "\npart 2: " && cd $1 && time python3 solve.py 2 + @echo "" +endef +$(foreach day,$(DAYS),$(eval $(call make-day,$(day)))) @@ -1,3 +1,3 @@ # Advent Of Code 2018 -All 25 solutions written in Python3 +Solutions to the annual [coding advent calendar](https://adventofcode.com) written in Python 3. diff --git a/common/aoc.py b/common/aoc.py new file mode 100644 index 0000000..0d8d802 --- /dev/null +++ b/common/aoc.py @@ -0,0 +1,35 @@ +import sys, os + +debug_lvl = os.getenv("AOC_DEBUG") +debug_lvl = int(debug_lvl) if debug_lvl is not None else 0 + +input_name = os.getenv("AOC_INPUT") +input_name = input_name if input_name is not None else "input" + +data = open(input_name).read().strip("\n") + +def debug(*args, **kwargs): + if debug_lvl: + print(*args, **kwargs, file=sys.stderr) + +def run(solve1, solve2, sols=[None, None]): + if len(sys.argv) <= 1: + sys.exit(0) + part = int(sys.argv[1]) + if part == 1: + answer = solve1(sys.argv[2:]) + print(answer) + if sols[part - 1] is not None: + assert(answer == sols[part - 1]) + else: + print("warn: no solution available", file=sys.stderr) + elif part == 2: + answer = solve2(sys.argv[2:]) + print(answer) + if sols[part - 1] is not None: + assert(answer == sols[part - 1]) + else: + print("warn: no solution available", file=sys.stderr) + else: + assert(False) # bad part + diff --git a/data/template.py b/data/template.py deleted file mode 100644 index 93b6e58..0000000 --- a/data/template.py +++ /dev/null @@ -1,25 +0,0 @@ -from sys import argv as args
-
-file = open("input.txt")
-sinput = file.read()
-file.close()
-
-def parseLine():
- return
-
-sinput = [parseLine(l) for l in sinput.split("\n")]
-
-def solve1():
- return
-
-def solve2():
- return
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
diff --git a/src/10/solve.py b/src/10/solve.py deleted file mode 100644 index 2ad1bfe..0000000 --- a/src/10/solve.py +++ /dev/null @@ -1,81 +0,0 @@ -def parseLine(l):
- s = l.split(">")
- vals = list()
- for ss in s:
- if len(ss) == 0:
- continue
- ss = ss.split("<",1)[1]
- vals.append([int(x) for x in ss.split(",")])
- return vals
-
-data = [parseLine(l) for l in open("input.txt").read().split("\n") if len(l) != 0]
-posdata = [x[0] for x in data]
-veldata = [x[1] for x in data]
-
-def checkAdjacent(pi):
- for p in posdata:
- if abs(p[0] - pi[0]) + abs(p[1] - pi[1]) == 1:
- return True
- return False
-
-def checkData():
- for p in posdata:
- if not checkAdjacent(p):
- return False
- return True
-
-def calcMax():
- minx = None
- maxx = None
- miny = None
- maxy = None
- for p in posdata:
- if minx is None or p[0] < minx:
- minx = p[0]
- if maxx is None or p[0] > maxx:
- maxx = p[0]
- if miny is None or p[1] < miny:
- miny = p[1]
- if maxy is None or p[1] > maxy:
- maxy = p[1]
- return minx, maxx, miny, maxy
-
-def solveBoth():
- count = 0
- distx = None
- disty = None
- while True:
- for i in range(len(data)):
- posdata[i][0] += veldata[i][0]
- posdata[i][1] += veldata[i][1]
- count += 1
-
- minx, maxx, miny, maxy = calcMax()
- if distx == None:
- distx = maxx - minx
- disty = maxy - miny
- else:
- cdistx = maxx - minx
- cdisty = maxy - miny
- if cdistx > distx or cdisty > disty:
- for i in range(len(data)):
- posdata[i][0] -= veldata[i][0]
- posdata[i][1] -= veldata[i][1]
- count -= 1
- break
- else:
- distx = cdistx
- disty = cdisty
-
- if count % 100 == 0:
- print("\r" + " " * 50, end="")
- print(f"\rcluster size: {distx}, {disty}", end="")
-
- print("\r" + " " * 50 + "\r", end="")
- print("part 1: " + str(count))
- minx, maxx, miny, maxy = calcMax()
- print("part 2: ");
- for y in range(maxy - miny + 1):
- print("".join([("#" if list([x + minx, y + miny]) in posdata else " ") for x in range(maxx - minx + 1)]))
-
-solveBoth()
diff --git a/src/13/solve.py~ b/src/13/solve.py~ deleted file mode 100644 index 7121398..0000000 --- a/src/13/solve.py~ +++ /dev/null @@ -1,158 +0,0 @@ -f = open("input.txt")
-contents = f.read()
-contents_sample = """
-
-/->-\
-| | /----\\
-| /-+--+-\ |
-| | | | v |
-\-+-/ \-+--/
- \------/
-
-"""
-
-tmap = [list(l) for l in contents.split("\n") if len(l) != 0]
-xlen = len(tmap[0])
-ylen = len(tmap)
-f.close()
-
-arrows = dict()
-arrows["<"] = (-1, 0)
-arrows[">"] = (1, 0)
-arrows["^"] = (0, -1)
-arrows["v"] = (0, 1)
-
-directions = [(-1,0), (0,-1), (1, 0), (0, 1)] # l - u - r - d
-
-def checkPos(x,y):
- """
- if x >= xlen:
- x = x % xlen
- elif x < 0:
- x = xlen + x
- if y >= ylen:
- y = y % ylen
- elif y < 0:
- y = ylen + y
- """
- v = 0
- if x < xlen and x >= 0 and y < ylen and y >= 0:
- if tmap[y][x] != " ": v = 1
-
- return v
-
-def correct(x, y):
- r = checkPos(x+1, y)
- l = checkPos(x-1, y)
- u = checkPos(x, y-1)
- d = checkPos(x, y+1)
-
- if r + l + d + u >= 3:
- return "+"
-
- # 2 around
- if r:
- if l:
- return "-"
- elif u:
- return "/"
- else:
- return "\\"
- else:
- if not l:
- return "|"
- elif u:
- return "/"
- else:
- return "\\"
-
-carts = list()
-for y in range(ylen):
- for x in range(xlen):
- if tmap[y][x] in arrows:
- carts.append([x, y, arrows[tmap[y][x]], 0])
- tmap[y][x] = correct(x,y)
-
-def cartAt(x, y):
- global carts
- for i in range(len(carts)):
- c = carts[i]
- if c[0] == x and c[1] == y:
- return i
- return None
-
-def advance(cart):
- ncart = [0 for x in range(4)]
- ncart[0] = cart[0]+cart[2][0]
- ncart[1] = cart[1]+cart[2][1]
- col = cartAt(ncart[0], ncart[1])
- if col:
- return ncart[0], ncart[1], col
-
- c = tmap[ncart[1]][ncart[0]]
- d = directions.index(cart[2])
-
- if c == "+":
- d = (d + len(directions)-1 + cart[3]) % len(directions)
- ncart[2] = directions[d]
- ncart[3] = (cart[3] + 1) % 3
- else: #dont need to change direction for '-' and '|'
- if c == "/":
- ncart[2] = directions[3-d]
- elif c == "\\":
- if d == 0: #l
- ncart[2] = directions[1]
- elif d == 1: #u
- ncart[2] = directions[0]
- elif d == 2: #r
- ncart[2] = directions[3]
- elif d == 3: #d
- ncart[2] = directions[2]
- else:
- ncart[2] = cart[2]
- ncart[3] = cart[3]
- return ncart
-
-def drawMap():
- for y in range(ylen):
- print("".join(["#" if cartAt(x,y) else tmap[y][x] for x in range(len(tmap[y]))]))
-
-def solve1():
- global carts
-
- crash = None
- while not crash:
- carts = sorted(carts, key=lambda x:(x[0], x[1]))
- for c in range(len(carts)):
- nc = advance(carts[c])
- if len(nc) == 3:
- crash = nc
- break
- else:
- carts[c] = nc
-
- print("Crash at:", str(crash[0]), str(crash[1]))
- return
-
-def solve2():
- global carts
-
- while len(carts) > 1:
- carts = sorted(carts, key=lambda x:(x[0], x[1]))
- rcarts = list()
- for c in range(len(carts)):
- nc = advance(carts[c])
- if len(nc) == 3:
- print(nc[2], c)
- rcarts.remove(carts[c])
- carts.remove(carts[nc[2]])
- else:
- carts[c] = nc
- for c in rcarts:
- carts.remove(c)
- print(carts[0][0], carts[0][1])
- return
-
-
-#solve1()
-solve2()
diff --git a/src/16/notes.txt b/src/16/notes.txt deleted file mode 100644 index c8cbf8b..0000000 --- a/src/16/notes.txt +++ /dev/null @@ -1,47 +0,0 @@ -R4 = 65536
-n * 256 > 65536 <=> n = 257
-#
-0 : R1 = 123
-1 : R1 = R1 & 456
-2 : R1 = (R1 == 72)
-3 : R3 = R1 + R3
-4 : R3 = 0
-5 : R1 = 0
-6 : R4 = R1 | 65536
-7 : R1 = 3798839
-8 : R5 = R4 & 255
-9 : R1 = R1 + R5
-10 : R1 = R1 & 16777215
-11 : R1 = R1 * 65899
-12 : R1 = R1 & 16777215
-13 : R5 = (256 > R4)
-14 : R3 = R5 + R3
-15 : R3 = R3 + 1
-16 : R3 = 27
-17 : R5 = 0
-18 : R2 = R5 + 1
-19 : R2 = R2 * 256
-20 : R2 = (R2 > R4)
-21 : R3 = R2 + R3
-22 : R3 = R3 + 1
-23 : R3 = 25
-24 : R5 = R5 + 1
-25 : R3 = 17
-26 : R4 = R5
-27 : R3 = 7
-28 : R5 = (R1 == R0)
-29 : R3 = R5 + R3
-30 : R3 = 5
-
-6851325 (low)
-4903765 (low)
-4455450
-13530460
-
-16127846
-3319808
-
-11077029
-1993108
-
-11011493
\ No newline at end of file diff --git a/src/24/notes.txt b/src/24/notes.txt deleted file mode 100644 index c81d665..0000000 --- a/src/24/notes.txt +++ /dev/null @@ -1,26 +0,0 @@ -infection and immune sys are armies - - made of groups of identical units - - group: - - same hitpoint - - same attack damage - - same initiative (who attacks first has highest) - - same weaknesses / immunities - - effective power = n of members * attack damage - -target selection: - - highest effective power chooses first sorted - if tie => higher initiative chooses first - - choose group it would damage most - if tie => largest effective power - if tie => largest intiative - if no group => no attack - -attack: - - attack in descending order of initiative - - regardless of army - - immune: 0 dmg - - weak: 2 x dmg - - only full death, units dont have dynamic health - - -(army, # of units, # of hp, initiative, dict of weaknesses / immunity, damage, type) diff --git a/src/25/solve.py b/src/25/solve.py deleted file mode 100644 index 2e0f817..0000000 --- a/src/25/solve.py +++ /dev/null @@ -1,100 +0,0 @@ -from sys import argv as args
-
-sinput = open("input.txt").read()
-
-ainput = """1,-1,-1,-2
--2,-2,0,1
-0,2,1,3
--2,3,-2,1
-0,2,3,-2
--1,-1,1,-2
-0,-2,-1,0
--2,2,3,-1
-1,2,2,0
--1,-2,0,-2"""
-
-ainput = """1,-1,0,1
-2,0,-1,0
-3,2,-1,0
-0,0,3,1
-0,0,-1,-1
-2,3,-2,0
--2,2,0,0
-2,-2,0,-1
-1,-1,0,-1
-3,2,0,2"""
-
-ainput = """0,0,0,0
- 3,0,0,0
- 0,3,0,0
- 0,0,3,0
- 0,0,0,3
- 0,0,0,6
- 9,0,0,0
-12,0,0,0"""
-
-ainput = """-1,2,2,0
-0,0,2,-2
-0,0,0,-2
--1,2,0,0
--2,-2,-2,2
-3,0,2,-1
--1,3,2,2
--1,0,-1,0
-0,2,1,-2
-3,0,0,0"""
-
-def parseLine(l):
- return [int(v) for v in l.split(",")]
-
-coordinates = [parseLine(l) for l in sinput.split("\n") if len(l) != 0]
-
-def dist(c1, c2):
- return sum([abs(c1[i] - c2[i]) for i in range(4)])
-
-def getClose(coords, c):
- match = list()
- j = 0
- while j in range(len(coords)):
- if dist(c, coords[j]) <= 3:
- match.append(coords[j])
- coords.pop(j)
- else:
- j += 1
- return match
-
-def solve1():
- constellations = list()
- available = coordinates[:]
-
- while len(available) != 0:
- match = getClose(available, available[0])
-
- j = 0
- while j < len(match):
- match += getClose(available, match[j])
- j += 1
-
- constellations.append(match)
-
- print(len(constellations))
-
- """
- sum = 0
- for cons in constellations:
- sum += len(cons)
- print(sum)
- """
- return
-
-def solve2():
- return
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
diff --git a/src/5/solve.py b/src/5/solve.py deleted file mode 100644 index b9e2154..0000000 --- a/src/5/solve.py +++ /dev/null @@ -1,46 +0,0 @@ -from sys import argv as args
-
-file = open("input.txt")
-input = file.read().strip()
-file.close()
-
-#s = list("dabAcCaCBAcCcaDA")
-
-
-def reactPol(s):
- i = 0
- while i < len(s)-1:
- cs = "".join(s[i:i+2])
- csl = cs.lower()
- if csl[0] == csl[1] and cs[0] != cs[1]: # builds pair with next letter
- s.pop(i)
- s.pop(i) # pop both letters
- if i > 0:
- i -= 1 # check prev
- else:
- i += 1
-
- return len(s)
-
-def solve1():
- print(reactPol(list(input)))
-
-def solve2():
- min = None
- for i in range(26):
- ls = str(chr(i+97))
- print(f"\rTesting: {ls}", end="")
- cs = list(input.replace(ls, "").replace(ls.upper(), ""))
- len = reactPol(cs)
- if min == None or len < min:
- min = len
- print(f"\r \r{min}")
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
diff --git a/src/6/solve.py b/src/6/solve.py deleted file mode 100644 index 90383c5..0000000 --- a/src/6/solve.py +++ /dev/null @@ -1,103 +0,0 @@ -from sys import argv as args
-
-f = open("input.txt")
-data = f.readlines()
-f.close()
-
-def parseEntry(l):
- split = l.split(",")
- return int(split[0]), int(split[1])
-
-data = [parseEntry(l) for l in data if len(l) != 0]
-
-minx = None
-miny = None
-maxx = None
-maxy = None
-for c in data:
- if minx == None or c[0] < minx:
- minx = c[0]
- elif maxx == None or c[0] > maxx:
- maxx = c[0]
- if miny == None or c[1] < miny:
- miny = c[1]
- elif maxy == None or c[1] > maxy:
- maxy = c[1]
-
-def getClosest(x,y):
- mc = None
- md = None
- ad = None
- for i in range(len(data)):
- c = data[i]
- dist = abs(c[0] - x) + abs(c[1] - y) # manhattan distance
- if md == None or dist < md:
- md = dist
- mc = i
- ad = None
- elif dist == md:
- ad = dist
- return mc, ad
-
-def getCombinedDist(x,y):
- dist = 0
- for i in range(len(data)):
- c = data[i]
- dist += abs(c[0] - x) + abs(c[1] - y)
- return dist
-
-def solve1():
- areas = dict()
- for x in range(minx, maxx):
- for y in range(miny, maxy):
- mc, ad = getClosest(x, y)
-
- if ad == None:
- if mc not in areas:
- areas[mc] = 1
- else:
- areas[mc] += 1
-
- # remove outside points
-
- for i in range(len(data)):
- c = data[i]
- mc, ac = getClosest(minx, c[1])
- if (mc == i):
- areas.pop(i)
- continue
- mc, ac = getClosest(maxx, c[1])
- if (mc == i):
- areas.pop(i)
- continue
- mc, ac = getClosest(c[0], miny)
- if (mc == i):
- areas.pop(i)
- continue
- mc, ac = getClosest(c[0], maxy)
- if (mc == i):
- areas.pop(i)
- continue
-
- print(max(areas.values()))
-
-def solve2():
- safezone = 0
- for x in range(minx, maxx):
- for y in range(miny, maxy):
- dist = getCombinedDist(x,y)
- if (dist < 10000):
- safezone += 1
- print(safezone)
-
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
-
-
diff --git a/src/7/solve.py b/src/7/solve.py deleted file mode 100644 index b448f38..0000000 --- a/src/7/solve.py +++ /dev/null @@ -1,131 +0,0 @@ -from sys import argv as args
-
-file = open("input.txt")
-data = [x for x in file.readlines()]
-file.close()
-
-"""
-data =
-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.
-"""
-#data = data.split("\n")
-
-def removeReq(req, instructs): # remove requirements
- for res in instructs:
- if req in instructs[res]:
- instructs[res].remove(req)
-
-def parseEntry(l):
- split = l.split(" ")
- firstl = split[1]
- nextl = split[-3]
- return firstl, nextl
-
-
-def genInstructs():
- global data
- data = [parseEntry(l) for l in data if len(l) != 0]
-
- instructs = dict()
-
- for ins in data:
- req = ins[0]
- res = ins[1]
- if res not in instructs:
- instructs[res] = [ req ]
- else:
- instructs[res].append(req)
-
- values = list(instructs.values())[:]
- for reslist in values:
- for res in reslist:
- if res not in instructs:
- instructs[res] = []
-
- return instructs
-
-def solve1():
- instructs = genInstructs()
- i = 0
- plan = list()
- while i < len(instructs):
- res = sorted(instructs.keys())[i] # alphabetically
- if len(instructs[res]) == 0:
- plan.append(res)
- instructs.pop(res, None)
- removeReq(res, instructs)
- i = 0
- else:
- i += 1
-
- print("".join(plan))
-
- return
-
-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 solve2():
- instructs = genInstructs()
- # (5) 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]:
- removeReq(w[0], instructs)
- #print("end : " + str(i) + " - " + str((w[0], w[1])))
- w[2] = False
- #i = 0
- if len(instructs) == 0 and checkfail(workers):
- stop = True
- break
-
- for i in range(len(workers)):
- w = workers[i]
- if time >= w[1]:
- for res in sorted(instructs.keys()):
- if len(instructs[res]) == 0:
- w[0] = res
- #print(instructs)
- #print("start : " + str(i) + " - " + str((res, time)))
- w[1] = time + ord(res)-65+1 + 60
- w[2] = True
- instructs.pop(res, None)
- break
-
- #print()
- print(time)
-
- return
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
diff --git a/src/8/solve.py b/src/8/solve.py deleted file mode 100644 index 9efff4f..0000000 --- a/src/8/solve.py +++ /dev/null @@ -1,52 +0,0 @@ -from sys import argv as args
-
-file = open("input.txt")
-data = [int(x) for x in file.read().strip().split(" ")]
-file.close()
-
-#data = [int(x) for x in "2 3 0 3 10 11 12 1 1 0 1 99 2 1 1 2".split(" ")]
-
-def getNodes(nsize, index):
- nodes = list()
- for i in range(nsize):
- cnsize = data[index + 0]
- mdsize = data[index + 1]
- cnodes, index = getNodes(cnsize, index + 2)
- metadata = data[index:index + mdsize]
- nodes.append([cnodes, metadata])
- index = index + mdsize
- return nodes, index
-
-def nodeSum(nodes):
- metadata = 0
- for n in nodes:
- metadata += sum(n[1]) + nodeSum(n[0])
- return metadata
-
-def nodeValue(n):
- if len(n[0]) == 0:
- return sum(n[1])
- else:
- value = 0
- for i in range(len(n[1])):
- ni = n[1][i]-1
- if ni < len(n[0]):
- value += nodeValue(n[0][ni])
- return value
-
-def solve1():
- nodes,index = getNodes(1, 0)
- print(nodeSum(nodes))
-
-def solve2():
- nodes,index = getNodes(1, 0)
- print(nodeValue(nodes[0]))
-
-def main():
- if len(args) > 1:
- if args[1] == "1":
- solve1()
- elif args[1] == "2":
- solve2()
-
-main()
|