aoc-2018-python

git clone https://git.sinitax.com/sinitax/aoc-2018-python
Log | Files | Refs | README | sfeed.txt

commit 277e5d08e28b5fcab8b019f66211883d976efbad
parent 73b29dfa9d07c37e8d4db2136cd73fdd9f0650b8
Author: Louis Burda <quent.burda@gmail.com>
Date:   Fri,  7 Apr 2023 16:16:42 -0400

Add helper to check solutions and reorder to new layout

Diffstat:
Rsrc/1/input.txt -> 01/input | 0
A01/part1 | 55+++++++++++++++++++++++++++++++++++++++++++++++++++++++
A01/part2 | 42++++++++++++++++++++++++++++++++++++++++++
A01/solve.py | 48++++++++++++++++++++++++++++++++++++++++++++++++
Rsrc/2/input.txt -> 02/input | 0
A02/part1 | 50++++++++++++++++++++++++++++++++++++++++++++++++++
A02/part2 | 24++++++++++++++++++++++++
A02/solve.py | 40++++++++++++++++++++++++++++++++++++++++
Rsrc/3/input.txt -> 03/input | 0
A03/part1 | 63+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A03/part2 | 11+++++++++++
A03/solve.py | 65+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Rsrc/4/input.txt -> 04/input | 0
A04/part1 | 76++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A04/part2 | 11+++++++++++
A04/solve.py | 92+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Rsrc/5/input.txt -> 05/input | 0
A05/part1 | 40++++++++++++++++++++++++++++++++++++++++
A05/part2 | 30++++++++++++++++++++++++++++++
A05/solve.py | 30++++++++++++++++++++++++++++++
Rsrc/6/input.txt -> 06/input | 0
A06/part1 | 65+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A06/part2 | 52++++++++++++++++++++++++++++++++++++++++++++++++++++
A06/solve.py | 76++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Rsrc/7/input.txt -> 07/input | 0
A07/part1 | 65+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A07/part2 | 46++++++++++++++++++++++++++++++++++++++++++++++
A07/solve.py | 105+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Rsrc/8/input.txt -> 08/input | 0
A08/part1 | 58++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A08/part2 | 33+++++++++++++++++++++++++++++++++
A08/solve.py | 43+++++++++++++++++++++++++++++++++++++++++++
Rsrc/9/input.txt -> 09/input | 0
A09/part1 | 78++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A09/part2 | 7+++++++
A09/solve.py | 43+++++++++++++++++++++++++++++++++++++++++++
Rsrc/10/input.txt -> 10/input | 0
A10/part1 | 160+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A10/part2 | 9+++++++++
A10/solve.py | 105+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Rsrc/10/test-input.txt -> 10/test-input.txt | 0
Rsrc/11/input.txt -> 11/input | 0
A11/part1 | 87+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A11/part2 | 22++++++++++++++++++++++
A11/solve.py | 76++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Rsrc/12/input.txt -> 12/input | 0
A12/part1 | 99+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A12/part2 | 9+++++++++
A12/solve.py | 53+++++++++++++++++++++++++++++++++++++++++++++++++++++
Rsrc/13/input.txt -> 13/input | 0
A13/part1 | 187+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A13/part2 | 49+++++++++++++++++++++++++++++++++++++++++++++++++
A13/solve.py | 148+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A13/test1 | 7+++++++
Rsrc/14/input.txt -> 14/input | 0
A14/part1 | 69+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A14/part2 | 19+++++++++++++++++++
A14/solve.py | 37+++++++++++++++++++++++++++++++++++++
Rsrc/15/input.txt -> 15/input | 0
A15/part1 | 343+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A15/part2 | 91+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A15/solve.py | 229+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A15/test1 | 7+++++++
A15/test2 | 7+++++++
A15/test3 | 7+++++++
A15/test4 | 7+++++++
A15/test5 | 9+++++++++
A15/test6 | 7+++++++
Rsrc/16/input.txt -> 16/input | 0
A16/part1 | 136+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A16/part2 | 8++++++++
A16/solve.py | 109+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Rsrc/17/.gitignore -> 17/.gitignore | 0
Rsrc/17/input.txt -> 17/input | 0
A17/part1 | 177+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A17/part2 | 10++++++++++
A17/solve.py | 183+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A17/test1 | 8++++++++
Rsrc/18/input.txt -> 18/input | 0
A18/part1 | 174+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A18/part2 | 8++++++++
A18/solve.py | 81+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A18/test1 | 10++++++++++
Rsrc/19/input.txt -> 19/input | 0
A19/part1 | 92+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A19/part2 | 8++++++++
A19/solve.py | 109+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A19/test1 | 8++++++++
Rsrc/20/.gitignore -> 20/.gitignore | 0
Rsrc/20/input.txt -> 20/input | 0
A20/part1 | 187+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A20/part2 | 8++++++++
A20/solve.py | 151++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A20/test1 | 1+
Rsrc/21/input.txt -> 21/input | 0
A21/part1 | 41+++++++++++++++++++++++++++++++++++++++++
A21/part2 | 9+++++++++
A21/solve.py | 112+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A21/test1 | 8++++++++
Rsrc/22/input.txt -> 22/input | 0
A22/part1 | 105+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A22/part2 | 302++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A22/solve.py | 93+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Rsrc/23/input.txt -> 23/input | 0
A23/part1 | 64++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A23/part2 | 27+++++++++++++++++++++++++++
A23/solve.py | 108+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Rsrc/24/input.txt -> 24/input | 0
A24/part1 | 199+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A24/part2 | 150+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A24/solve.py | 127+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Rsrc/25/input.txt -> 25/input | 0
A25/part1 | 108+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A25/part2 | 15+++++++++++++++
A25/solve.py | 50++++++++++++++++++++++++++++++++++++++++++++++++++
A25/test1 | 10++++++++++
A25/test2 | 10++++++++++
A25/test3 | 8++++++++
A25/test4 | 10++++++++++
AMakefile | 15+++++++++++++++
MREADME.md | 2+-
Acommon/aoc.py | 35+++++++++++++++++++++++++++++++++++
Ddata/template.py | 25-------------------------
Dsrc/1/solve.py | 61-------------------------------------------------------------
Dsrc/10/solve.py | 81-------------------------------------------------------------------------------
Dsrc/11/solve.py | 80-------------------------------------------------------------------------------
Dsrc/12/solve.py | 61-------------------------------------------------------------
Dsrc/13/solve.py | 167-------------------------------------------------------------------------------
Dsrc/13/solve.py~ | 158-------------------------------------------------------------------------------
Dsrc/14/solve.py | 42------------------------------------------
Dsrc/15/solve.py | 291------------------------------------------------------------------------------
Dsrc/16/notes.txt | 48------------------------------------------------
Dsrc/16/solve.py | 121-------------------------------------------------------------------------------
Dsrc/17/solve.py | 212-------------------------------------------------------------------------------
Dsrc/18/solve.py | 106-------------------------------------------------------------------------------
Dsrc/19/solve.py | 131-------------------------------------------------------------------------------
Dsrc/2/solve.py | 47-----------------------------------------------
Dsrc/20/solve.py | 164-------------------------------------------------------------------------------
Dsrc/21/solve.py | 139-------------------------------------------------------------------------------
Dsrc/22/solve.py | 108-------------------------------------------------------------------------------
Dsrc/23/solve.py | 116-------------------------------------------------------------------------------
Dsrc/24/notes.txt | 26--------------------------
Dsrc/24/solve.py | 129-------------------------------------------------------------------------------
Dsrc/25/solve.py | 100-------------------------------------------------------------------------------
Dsrc/3/solve.py | 74--------------------------------------------------------------------------
Dsrc/4/solve.py | 109-------------------------------------------------------------------------------
Dsrc/5/solve.py | 46----------------------------------------------
Dsrc/6/solve.py | 103-------------------------------------------------------------------------------
Dsrc/7/solve.py | 131-------------------------------------------------------------------------------
Dsrc/8/solve.py | 52----------------------------------------------------
Dsrc/9/solve.py | 48------------------------------------------------
151 files changed, 6266 insertions(+), 2977 deletions(-)

diff --git a/src/1/input.txt b/01/input diff --git a/01/part1 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 @@ -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/01/solve.py b/01/solve.py @@ -0,0 +1,48 @@ +import sys +sys.path.append("../common") +import aoc + +data = [int(l) for l in aoc.data.split("\n")] + +def solve1(args): + return sum(data) + +def solve2(args): + totshift = 0 + fvals = list() + for c in data: + fvals.append(totshift) + totshift += c + aoc.debug("total shift: " + str(totshift)) + + doubles = list() + + if totshift == 0: + doubles.append([len(data), 0]) + + i = 0 + while i < len(fvals): + for j in range(len(fvals)): + if i == j: + continue + dif = fvals[j] - fvals[i] + if dif % totshift == 0: + inds = list([i, j]) + if j > i: + inds = inds[::-1] + if totshift > 0: #ends on c + if fvals[inds[0]] > fvals[inds[1]]: + inds = inds[::-1] + else: + if fvals[inds[0]] < fvals[inds[1]]: + inds = inds[::-1] + + pos = (abs(dif) // totshift) * len(data) + inds[0] + doubles.append([pos, fvals[inds[1]]]) + i += 1 + + assert(len(doubles) != 0) + + return min(doubles, key = lambda x: x[0])[1] + +aoc.run(solve1, solve2, sols=[411, 56360]) diff --git a/src/2/input.txt b/02/input diff --git a/02/part1 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 @@ -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/02/solve.py b/02/solve.py @@ -0,0 +1,40 @@ +import sys +sys.path.append("../common") +import aoc + +data = aoc.data.split("\n") + +def solve1(args): + doubles = 0 + triples = 0 + for s in data: + 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 + return doubles * triples + +def compare(s1, s2): + dif = 0 + same = list() + for i in range(len(s1)): + if s1[i] != s2[i]: + dif += 1 + else: + same.append(s1[i]) + return (dif, same) + +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: + return "".join(res[1]) + + +aoc.run(solve1, solve2, sols=[3952, "vtnikorkulbfejvyznqgdxpaw"]) diff --git a/src/3/input.txt b/03/input diff --git a/03/part1 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 @@ -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/03/solve.py b/03/solve.py @@ -0,0 +1,65 @@ +import sys +sys.path.append("../common") +import aoc + +data = aoc.data.split("\n") + +#data = "#1 @ 1,3: 4x4","#2 @ 3,1: 4x4","#3 @ 5,5: 2x2" + +def parse_rect(l): + split = l.split("@") + id = int(split[0].replace("#","")) + split = split[1].split(":") + pos = [int(x) for x in split[0].split(",")] + size = [int(x) for x in split[1].split("x")] + return pos, size, id + +def create_map(): + global rectdata + rectdata = [parse_rect(l) for l in data] + msize = list([0,0]) + for i in range(len(rectdata)): + r = rectdata[i] + xm = r[0][0] + r[1][0] + ym = r[0][1] + r[1][1] + if i == 0 or xm > msize[0]: + msize[0] = xm + if i == 0 or ym > msize[1]: + msize[1] = ym + + map = [[list() for y in range(msize[1])] for x in range(msize[0])] + for r in rectdata: + sx = r[0][0] + sy = r[0][1] + for x in range(sx, sx + r[1][0]): + for y in range(sy, sy + r[1][1]): + map[x][y].append(r[2]) + + return map + +def solve1(args): + map = create_map() + + overlap = 0 + for x in range(len(map)): + for y in range(len(map[0])): + if len(map[x][y]) > 1: + overlap += 1 + + return overlap + +def solve2(args): + map = create_map() + + overlap = set() + for x in range(len(map)): + for y in range(len(map[0])): + if len(map[x][y]) > 1: + for id in map[x][y]: + overlap.add(id) + + for i in range(1, len(rectdata)): + if i not in overlap: + return i + +aoc.run(solve1, solve2, sols=[114946, 877]) diff --git a/src/4/input.txt b/04/input diff --git a/04/part1 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 @@ -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/04/solve.py b/04/solve.py @@ -0,0 +1,92 @@ +import sys +sys.path.append("../common") +import aoc + +data = aoc.data.split("\n") + +def parse_entry(l): + split = l.split(" ") + date = " ".join(split[:2]) + time = int(split[1].split(":")[1].replace("]","")) + if split[2] == "Guard": + awake = None + id = int(split[3].replace("#","")) + else: + id = 0 + awake = (True if split[2] == "wakes" else False) + return time, id, awake, date + +class guard: + def __init__(self, _id): + self.shifts = list() + self.id = _id + self.awake = None + +def gen_shiftmap(): + shiftdata = [parse_entry(l) for l in data] + shiftdata = sorted(shiftdata, key=lambda x: x[3]) # sort by date + + shiftmap = dict() + ltime = shiftdata[0][0] + cgid = shiftdata[0][1] + for i in range(len(shiftdata)): + entry = shiftdata[i] + ctime = entry[0] + gid = entry[1] + cawake = entry[2] + + if gid != 0: + if gid not in shiftmap: + shiftmap[gid] = guard(gid) + cgid = gid + else: + g = shiftmap[cgid] + if cawake: + if not g.awake: + shiftmap[cgid].shifts.append((ltime, ctime - ltime)) + else: + ltime = ctime + g.awake = cawake + + return shiftmap + +def solve1(args): + shiftmap = gen_shiftmap() + + maxsleep = None + mg = None + for g in shiftmap.values(): + minslept = 0 + for t in g.shifts: + minslept += t[1] + if not maxsleep or minslept > maxsleep: + maxsleep = minslept + mg = g + + + timel = [0 for x in range(60)] + + for t in mg.shifts: + for i in range(t[0], t[0] + t[1]): + timel[(i-1)%60] += 1 + + minute = timel.index(max(timel))+1 + + return minute * mg.id + +def solve2(args): + shiftmap = gen_shiftmap() + timetables = dict() + + for g in shiftmap.values(): + timetables[g.id] = [0 for x in range(60)] + for t in g.shifts: + for i in range(t[0], t[0] + t[1]): + timetables[g.id][i] += 1 + + 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 diff --git a/05/part1 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 @@ -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 @@ -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 diff --git a/06/part1 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 @@ -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 @@ -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 diff --git a/07/part1 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 @@ -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 @@ -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 diff --git a/08/part1 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 @@ -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 @@ -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 diff --git a/09/part1 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 @@ -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/09/solve.py b/09/solve.py @@ -0,0 +1,43 @@ +import sys +sys.path.append("../common") +import aoc + +from collections import deque + +words = aoc.data.split(" ") +playercount = int(words[0]) +lastworth = int(words[6]) + +def highscore(playercount, lastworth): + lastworth = lastworth - lastworth % 23 + + players = [0 for x in range(playercount)] + marbles = deque([0]) + pos = 0 + for i in range(1, lastworth+1): + if i % 23 == 0: + cp = (i-1) % playercount + players[cp] += i + marbles[(len(marbles) + pos - 7) % len(marbles)] + marbles.rotate((len(marbles) - 1 - pos) + 7) + marbles.pop() + pos = 0 + else: + if i < 3: + pos = 1 + marbles.rotate(1) + marbles.append(i) + else: + marbles.rotate((len(marbles)- 1 -pos) - 1) + marbles.append(i) + pos = len(marbles)-1 + + return max(players) + + +def solve1(args): + return highscore(playercount, lastworth) + +def solve2(args): + return highscore(playercount, lastworth * 100) + +aoc.run(solve1, solve2, sols=[412127, 3482394794]) diff --git a/src/10/input.txt b/10/input diff --git a/10/part1 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 @@ -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 @@ -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 diff --git a/src/11/input.txt b/11/input diff --git a/11/part1 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 @@ -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/11/solve.py b/11/solve.py @@ -0,0 +1,76 @@ +import sys +sys.path.append("../common") +import aoc + +gridserial = int(aoc.data) + +# rack ID = x + 10 +# intial power = rackID * y +# power += gridserial +# power *= rackID +# power = str(power)[2] +# power -= 5 + +def get_power(x,y): + id = x + 10 + power = id * y + power += gridserial + power *= id + spower = str(power) + if len(spower) > 2: + power = int(spower[-3]) + else: + power = 0 + power -= 5 + return power + +def solve1(args): + maxpower = None + coords = None + for x in range(300-2): + for y in range(300-2): + power = 0; + for i in range(3): + for j in range(3): + power += get_power(x+i,y+j) + if maxpower == None or power > maxpower: + maxpower = power + coords = (x, y) + + 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] = get_power(x,y) + return vmap + +def solve2(args): + maxpower = None + res = None + pmap = gen_map() + vmap = [[list() for y in range(300)] for x in range(300)] + for s in range(1, 301): + aoc.debug(f"\rTrying: {s}", end="") + cmaxpower = None + cres = None + for x in range(300-(s-1)): + for y in range(300-(s-1)): + vmap[x][y] += [pmap[x+(s-1)][y+i] for i in range(s)] + vmap[x][y] += [pmap[x+i][y+(s-1)] for i in range(s-1)] + power = sum(vmap[x][y]); + if cmaxpower == None or power > cmaxpower: + cmaxpower = power + cres = (x, y, s) + if maxpower == None or cmaxpower > maxpower: + maxpower = cmaxpower + res = cres + elif cmaxpower < maxpower: + break + + aoc.debug("\r" + " " * 50 + "\r", end="") + + return f"{res[0]},{res[1]},{res[2]}" + +aoc.run(solve1, solve2, sols=["21,93", "231,108,14"]) diff --git a/src/12/input.txt b/12/input diff --git a/12/part1 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 @@ -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/12/solve.py b/12/solve.py @@ -0,0 +1,53 @@ +import sys +sys.path.append("../common") +import aoc + +lines = aoc.data.split("\n") +istate = lines[0].split(": ")[1] +rules = [l.split(" => ") for l in lines[2:] if l != ""] +rules = [r[0] for r in rules if r[1] == "#"] + +def next_gen(pots): + pmin = min(pots) + pmax = max(pots) + npots = list() + for i in range(pmin-4, pmax+1): + for r in rules: + match = True + for j in range(5): + if (r[j] == "#") != ((i+j) in pots): + match = False + break + if match: + npots.append(i+2) + break + return npots + +def get_pots(): + pots = list() + for i in range(len(istate)): + if istate[i] == "#": + pots.append(i) + return pots + +def solve1(args): + pots = get_pots() + for i in range(20): + pots = next_gen(pots) + return sum(pots) + +def solve2(args): + pots = get_pots() + psum = sum(pots) + pdif = None + i = 0 + while (True): + pots = next_gen(pots) + i += 1 + csum = sum(pots) + if pdif == csum - psum: + return csum + pdif * (50000000000 - 164) + pdif = csum - psum + psum = csum + +aoc.run(solve1, solve2, sols=[1987, 1150000000358]) diff --git a/src/13/input.txt b/13/input diff --git a/13/part1 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 @@ -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/13/solve.py b/13/solve.py @@ -0,0 +1,148 @@ +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) +arrows[">"] = (1, 0) +arrows["^"] = (0, -1) +arrows["v"] = (0, 1) + +directions = [(-1,0), (0,-1), (1, 0), (0, 1)] # l - u - r - d + +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 = 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 = " " + if cu == "-": cu = " " + if cd == "-": cd = " " + + r = cr != " " + l = cl != " " + u = cu != " " + d = cd != " " + + vsum = r + l + u + d + if vsum > 2: + 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, 0]) + tmap[y][x] = correct(x,y) + +def cart_at(x, y): + global carts + for i in range(len(carts)): + c = carts[i] + if c[0] == x and c[1] == y and not c[4]: + return i + return None + +def draw_map(): + for y in range(ylen): + 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 = cart_at(ncart[0], ncart[1]) + if col != None: + 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 solve1(args): + 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 + + return f"{crash[0]},{crash[1]}" + +def solve2(args): + global carts + + while len(carts) > 1: + carts = sorted(carts, key=lambda x:(x[0], x[1])) + rcarts = list() + for c in range(len(carts)): + if carts[c][4]: continue; + nc = advance(carts[c]) + if len(nc) == 3: + carts[c][4] = 1 + carts[nc[2]][4] = 1 + rcarts.append(carts[c]) + rcarts.append(carts[nc[2]]) + else: + carts[c] = nc + for c in rcarts: + if c in carts: # prevent doubles + carts.remove(c) + + return f"{carts[0][0]},{carts[0][1]}" + +aoc.run(solve1, solve2) diff --git a/13/test1 b/13/test1 @@ -0,0 +1,7 @@ +/>-<\ +| | +| /<+-\ +| | | v +\>+</ | + | ^ + \<->/ diff --git a/src/14/input.txt b/14/input diff --git a/14/part1 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 @@ -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/14/solve.py b/14/solve.py @@ -0,0 +1,37 @@ +import sys +sys.path.append("../common") +import aoc + +data = aoc.data +recipes = [3, 7] + +def solve1(args): + global recipes, data + + 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) + return "".join([str(x) for x in recipes[end:]]) + +def solve2(args): + global recipes, data + + 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:] == data: + stop = True + break + recipes.append(v) + for i in range(len(workers)): + workers[i] = (workers[i] + recipes[workers[i]]+1) % len(recipes) + return len(recipes) - ilen + +aoc.run(solve1, solve2, sols=["6107101544", 20291131]) diff --git a/src/15/input.txt b/15/input diff --git a/15/part1 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 @@ -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/15/solve.py b/15/solve.py @@ -0,0 +1,229 @@ +import sys +sys.path.append("../common") +import aoc + +data = aoc.data.split("\n") +actors = list() + +def parse_entity(x, y): + global actors + c = data[y][x] + if c == "#": + return 1 + else: + if c == "G": + actors.append([x, y, 200, 1, len(actors), 3]) + elif c == "E": + actors.append([x, y, 200, 0, len(actors), 3]) + return 0 + +ylen = len(data) +xlen = len(data[0]) + +adjacent = [[0, -1], [-1, 0], [1, 0], [0, 1]] # first in reading order +vmap = list() + +def set_game(): + global vmap, actors + actors = list() + vmap = [[parse_entity(x, y) for x in range(xlen)] for y in range(ylen)] + + +def inmap(cmap, cx, cy): + for i in range(len(cmap)): + ent = cmap[i] + if ent[0] == cx and ent[1] == cy: + return i + return None + +def iswall(x,y): + return vmap[y][x] != 0 + +def isblocked(x, y): + return (vmap[y][x] != 0 or inmap(actors, x, y) != None) + +def freeAdjacent(x, y): + poslist = list() + for dir in adjacent: + nx = x + dir[0] + ny = y + dir[1] + if not isblocked(nx, ny): + poslist.append((nx,ny)) + return poslist + +def flatten(l): + flat = list() + for ll in l: + flat += ll + return flat + +def drawMap(): + global actors + + for y in range(ylen): + for x in range(xlen): + ind = inmap(actors, x, y) + 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 + npos = [[a1[0] + dir[0], a1[1] + dir[1]] for dir in adjacent] + + # pos of enemy and distance + steps = [[np[0], np[1], cmap[np[0], np[1]]] for np in npos if (np[0], np[1]) in cmap] + + return steps + +def closestStep(a1, a2): + countmap = dict() + next = dict() + next[(a2[0], a2[1])] = 0 + counter = 0 + steps = list() + while len(next) > 0 and len(steps) == 0: # first steps available will be shortest + countmap = {**countmap, **next} # merge dictionaries + counter += 1 + temp = dict() + for n in next: + for dir in adjacent: + nx = n[0]+dir[0] + ny = n[1]+dir[1] + if not isblocked(nx, ny) and (nx, ny) not in countmap and (nx, ny) not in temp: + temp[(nx,ny)] = counter + next = temp + steps = getSteps(countmap, a1) + + # if reachable + if len(steps) != 0: + return sorted(steps, key = lambda x : (x[1], x[0]))[0] + else: + return [None] + +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]] + + # only where step is possible + steps = [s for s in steps if s[2] != None] + + # skip when none possible + if len(steps) == 0: + return + + # best move + bestmove = sorted(steps, key = lambda x : (x[4], x[1], x[0]))[0] + a[0] = bestmove[2] + a[1] = bestmove[3] + +def getInrange(a): + global actors + + inrange = list() + for dir in adjacent: + nx = a[0] + dir[0] + ny = a[1] + dir[1] + ind = inmap(actors, nx, ny) + if ind != None and actors[ind][3] != a[3]: + inrange.append(ind) + return inrange + +def next_tick(tick): + global actors + + actors = sorted(actors, key=lambda x: (x[1], x[0]), reverse=True) + i = len(actors)-1 + + while i >= 0: + a = actors[i] + inrange = getInrange(a) # get enemies in range + if len(inrange) == 0: + move(a) + inrange = getInrange(a) + + if len(inrange) != 0: + inrange = [actors[ai] + [ai] for ai in inrange] + + # lowest health in reading order + cai = sorted(inrange, key = lambda x : (x[2], x[1], x[0]))[0][-1] + + # attack player + actors[cai][2] -= a[5] # attack + if actors[cai][2] <= 0: + actors.pop(cai) # dead + aoc.debug("death -",cai) + if min_alive() == 0 and i != 0: # incomplete round + return False + if cai < i: i -= 1 + + if aoc.debug_lvl and False: + aoc.debug() + aoc.debug("small step -",a[4]) + drawMap() + status_report() + i -= 1 + + if aoc.debug_lvl: + aoc.debug() + aoc.debug("tick:", tick) + drawMap() + status_report() + else: + aoc.debug(tick) + + return True + +def min_alive(): + alive = [0,0] + for a in actors: + alive[1 * (a[3] == 0)] += 1 + return min(alive) + +def sum_hp(): + return sum(a[2] for a in actors) + +def status_report(): + global actors + + sactors = sorted(actors, key = lambda x:x[4]) + for a in sactors: + aoc.debug("HP:", a[2]) + aoc.debug() + +def elves_alive(): + return len([a for a in actors if a[3] == 0]) + +def start_battle(eap): + global actors + + set_game() + for a in actors: + if a[3] == 0: + a[5] = eap + + elfcount = elves_alive() + + ticks = 0 + while min_alive() > 0: + if next_tick(ticks): + ticks += 1 + status_report() + + return ((sum_hp() * ticks), (elfcount - elves_alive())) + +def solve1(args): + res = start_battle(3) + return res[0] + +def solve2(args): + eap = 4 + res = start_battle(eap) + while res[1] != 0: + eap += 1 + res = start_battle(eap) + return res[0] + +aoc.run(solve1, solve2, sols=[229798, 52972]) diff --git a/15/test1 b/15/test1 @@ -0,0 +1,7 @@ +####### +#G..#E# +#E#E.E# +#G.##.# +#...#E# +#...E.# +####### diff --git a/15/test2 b/15/test2 @@ -0,0 +1,7 @@ +####### +#E..EG# +#.#G.E# +#E.##E# +#G..#.# +#..E#.# +####### diff --git a/15/test3 b/15/test3 @@ -0,0 +1,7 @@ +####### +#E.G#.# +#.#G..# +#G.#.G# +#G..#.# +#...E.# +####### diff --git a/15/test4 b/15/test4 @@ -0,0 +1,7 @@ +####### +#.E...# +#.#..G# +#.###.# +#E#G#G# +#...#G# +####### diff --git a/15/test5 b/15/test5 @@ -0,0 +1,9 @@ +######### +#G......# +#.E.#...# +#..##..G# +#...##..# +#...#...# +#.G...G.# +#.....G.# +######### diff --git a/15/test6 b/15/test6 @@ -0,0 +1,7 @@ +####### +#.G...# +#...EG# +#.#.#G# +#..G#E# +#.....# +####### diff --git a/src/16/input.txt b/16/input diff --git a/16/part1 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 @@ -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/16/solve.py b/16/solve.py @@ -0,0 +1,109 @@ +import sys +sys.path.append("../common") +import aoc + +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) + +inslog = [] +data = aoc.data.split("\n") +progsec = None +for i in range(0, len(data), 4): + if data[i] == "\n": + progsec = i + break + inslog.append(parse_log(data[i:i+4])) + +register = list() + +opmap = dict() +opmap["addr"] = lambda a, b : register[a] + register[b] +opmap["addi"] = lambda a, b : register[a] + b +opmap["mulr"] = lambda a, b : register[a] * register[b] +opmap["muli"] = lambda a, b : register[a] * b +opmap["banr"] = lambda a, b : register[a] & register[b] +opmap["bani"] = lambda a, b : register[a] & b +opmap["borr"] = lambda a, b : register[a] | register[b] +opmap["bori"] = lambda a, b : register[a] | b +opmap["setr"] = lambda a, b : register[a] +opmap["seti"] = lambda a, b : a +opmap["gtir"] = lambda a, b : 1 * (a > register[b]) +opmap["gtri"] = lambda a, b : 1 * (register[a] > b) +opmap["gtrr"] = lambda a, b : 1 * (register[a] > register[b]) +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 get_possible(ins): + global register + sregister = register[:] + before = ins[0] + after = ins[2] + register = before + a = ins[1][1] + b = ins[1][2] + c = ins[1][3] + ops = list(opmap.values()) + possibles = list() + for i in range(len(ops)): + op = ops[i] + res = None + try: + res = op(a, b) + except: + continue + if res == after[c]: + possibles.append(i) + register = sregister + return possibles + +def solve1(args): + global register + uncertain = 0 + for ins in inslog: + if len(get_possible(ins)) >= 3: + uncertain += 1 + return uncertain + +def solve2(args): + possible = dict() + for ins in inslog: + o = ins[1][0] + if o in possible: + possible[o] = [op for op in get_possible(ins) if op in possible[o]] + else: + possible[o] = get_possible(ins) + + certain = False + while not certain: + singles = [p[0] for p in possible.values() if len(p) == 1] + for p in possible: + if len(possible[p]) != 1: + possible[p] = [v for v in possible[p] if v not in singles] + + certain = True + for p in possible.values(): + if len(p) != 1: + certain = False + break + + ntrans = dict() + for p in possible: # flatten + ntrans[p] = possible[p][0] + + 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]: + register.append(0) + + register[cmd[3]] = list(opmap.values())[ntrans[cmd[0]]](cmd[1], cmd[2]) + + return register[0] + +aoc.run(solve1, solve2, sols=[531, 649]) diff --git a/src/17/.gitignore b/17/.gitignore diff --git a/src/17/input.txt b/17/input diff --git a/17/part1 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 @@ -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/17/solve.py b/17/solve.py @@ -0,0 +1,183 @@ +import sys +sys.path.append("../common") +import aoc + +def parse_line(l): + s = l.split(", ") + if s[0].startswith("y="): + s = s[::-1] + + res = [[int(x) for x in v.split("=")[1].split("..")] for v in s] + return res + +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 +ymin = min(c[1][0] for c in constraints) +ymax = max(c[1][-1] for c in constraints) +xdif = xmax - xmin + 1 +ydif = ymax - ymin + 1 + +vmap = [[0 for x in range(xdif)] for y in range(ydif)] + +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 get_map(x, y): + global vmap + if x > xmax or x < xmin: + return 1 + elif y > ymax: + return 0 + return vmap[y-ymin][x-xmin] + +def drawWall(c): + if len(c[0]) == 1: + for y in range(c[1][0], c[1][1] + 1): + set_map(c[0][0], y, 1) + else: + for x in range(c[0][0], c[0][1] + 1): + set_map(x, c[1][0], 1) + +for c in constraints: + drawWall(c) + +spring = (500, 0) + + +### SETUP END + + +def interpretChar(v): + chars = [".", "#", "|", "~"] + return chars[v] + +def drawMap(): + for y in range(ydif): + aoc.debug("".join([interpretChar(v) for v in vmap[y]])) + +def fwriteMap(): + f = open("output","w+") + for y in range(ydif): + f.write("".join([interpretChar(v) for v in vmap[y]])+"\n") + f.close() + +def isstatic(p): + return get_map(p[0], p[1]) in (1, 3) + +def isfree(p): + return get_map(p[0], p[1]) == 0 + +def move(p): + x = p[0] + y = p[1] + if isfree((x, y+1)): + return (x, y+1) + onblock = isstatic((x, y+1)) + if not onblock: + return (x,y) + npos = [(x + dir, y) for dir in [-1, 1]] + npos = [np for np in npos if isfree(np) and onblock] + if len(npos) > 1: + return npos + elif len(npos) == 1: + return npos[0] + return (x, y) + +def fillfloor(p): + onblock = True + isblock = False + x = p[0] + while onblock and not isblock and x >= xmin: + x -= 1 + isblock = isstatic((x, p[1])) + onblock = isstatic((x, p[1]+1)) + if not isblock: + return None # edge + lx = x+1 + + onblock = True + isblock = False + x = p[0] + while onblock and not isblock and x <= xmax: + x += 1 + isblock = isstatic((x, p[1])) + onblock = isstatic((x, p[1]+1)) + if not isblock: + return None + rx = x-1 + + return [(i, p[1]) for i in range(lx, rx+1)] + +def count_w_flowing(): + water = 0 + for y in range(ymin, ymax+1): + for x in range(xmin, xmax+1): + if get_map(x,y) == 2: + water += 1 + return water + +def count_w_static(): + water = 0 + for y in range(ymin, ymax+1): + for x in range(xmin, xmax+1): + if get_map(x,y) == 3: + water += 1 + return water + +def simulate(): + heads = [spring] + while len(heads) > 0: + cp = heads[-1] + if isstatic((cp[0], cp[1]+1)): + # solid below => expand + res = fillfloor(cp) + if res: + for p in res: + 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 get_map(np[0], np[1]) == 2: + nhead = np + break + if nhead == None: # head got trapped + heads.pop() + else: + heads[-1] = nhead + continue + + res = move(cp) + if type(res[0]) == tuple: + heads.pop() + heads += res + for p in res: + set_map(p[0], p[1], 2) + else: + if res != cp: + if res[1] <= ymax: + set_map(res[0], res[1], 2) + heads[-1] = res + else: + heads.pop() + else: + heads.pop() + + if aoc.debug_lvl: + aoc.debug(heads) + input() + fwriteMap() + +def solve1(args): + simulate() + return count_w_flowing() + count_w_static() + +def solve2(args): + simulate() + return count_w_static() + +aoc.run(solve1, solve2, sols=[39557, 32984]) diff --git a/17/test1 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 diff --git a/18/part1 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 @@ -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/18/solve.py b/18/solve.py @@ -0,0 +1,81 @@ +import sys +sys.path.append("../common") +import aoc +from copy import deepcopy +from collections import deque + +states = (".", "|", "#") + +ivals = dict() +ivals["#"] = 0 +ivals["."] = 0 +ivals["|"] = 0 + +def pasrse_line(l): + return tuple([states.index(c) for c in l]) + +vmap = [pasrse_line(l) for l in aoc.data.split("\n")] +xlen, ylen = len(vmap[0]), len(vmap) + +def get_at(x, y): + if y < 0 or y >= ylen or x < 0 or x >= xlen: + return None + return vmap[y][x] + +def next(x, y): + v = vmap[y][x] + around = list() + [[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 + elif v == 1: + if len([v for v in around if v == 2]) >= 3: + return 2 + elif v == 2: + if len([v for v in around if v == 1]) < 1 or len([v for v in around if v == 2]) < 1: + return 0 + return v + +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 draw_map(cmap): + for y in range(ylen): + aoc.debug("".join([str(c) for c in cmap[y]])) + +def iterate(n): + global vmap + for i in range(n): + omap = [deque() for y in range(ylen)] + for y in range(ylen): + for x in range(xlen): + omap[y].append(next(x, y)) + vmap = omap + +def get_res(): + vals = get_vals() + return (vals[1] * vals[2]) + +def solve1(args): + iterate(10) + vals = get_vals() + return vals[1] * vals[2] + +def solve2(args): + iterate(1000) + omap = deepcopy(vmap) + counter = 0 + while True: + iterate(1) + counter += 1 + if vmap == omap: + break + + return get_res() + +aoc.run(solve1, solve2, sols=[574590, 183787]) diff --git a/18/test1 b/18/test1 @@ -0,0 +1,10 @@ +.#.#...|#. +.....#|##| +.|..|...#. +..|#.....# +#.#|||#|#| +...#.||... +.|....|... +||...#|.#| +|.||||..|. +...#.|..|. diff --git a/src/19/input.txt b/19/input diff --git a/19/part1 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 @@ -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/19/solve.py b/19/solve.py @@ -0,0 +1,109 @@ +import sys +sys.path.append("../common") +import aoc +from math import sqrt + +def parse_command(l): + s = l.split(" ") + args = [s[0]] + args = args + [int(v) for v in s[1:]] + return args + +data = aoc.data.split("\n") + +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)] + +opmap = dict() +opmap["addr"] = lambda a, b : register[a] + register[b] +opmap["addi"] = lambda a, b : register[a] + b +opmap["mulr"] = lambda a, b : register[a] * register[b] +opmap["muli"] = lambda a, b : register[a] * b +opmap["banr"] = lambda a, b : register[a] & register[b] +opmap["bani"] = lambda a, b : register[a] & b +opmap["borr"] = lambda a, b : register[a] | register[b] +opmap["bori"] = lambda a, b : register[a] | b +opmap["setr"] = lambda a, b : register[a] +opmap["seti"] = lambda a, b : a +opmap["gtir"] = lambda a, b : 1 * (a > register[b]) +opmap["gtri"] = lambda a, b : 1 * (register[a] > b) +opmap["gtrr"] = lambda a, b : 1 * (register[a] > register[b]) +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 solve1(args): + global register, insptr + while register[inspaddr] < len(instructs): + insptr = register[inspaddr] + ins = instructs[insptr] + #aoc.debug(register) + + # execute command + if len(register) <= ins[3]: + register += [0 for x in range(ins[3] - len(register) + 1)] + register[ins[3]] = opmap[ins[0]](ins[1], ins[2]) + + # increment instruction pointer + register[inspaddr] += 1 + + return register[0] + + +alpha = [chr(c + ord('a')) for c in range(26)] + +dismap = dict() +dismap["addr"] = lambda a, b : "%s + %s" % (alpha[a], alpha[b]) +dismap["addi"] = lambda a, b : "%s + %d" % (alpha[a], b) +dismap["mulr"] = lambda a, b : "%s * %s" % (alpha[a], alpha[b]) +dismap["muli"] = lambda a, b : "%s * %d" % (alpha[a], b) +dismap["banr"] = lambda a, b : str(alpha[a] & alpha[b]) +dismap["bani"] = lambda a, b : str(alpha[a] & b) +dismap["borr"] = lambda a, b : str(alpha[a] | alpha[b]) +dismap["bori"] = lambda a, b : str(alpha[a] | b) +dismap["setr"] = lambda a, b : str(alpha[a]) +dismap["seti"] = lambda a, b : str(a) +dismap["gtir"] = lambda a, b : "(%d > %s)" % (a, alpha[b]) +dismap["gtri"] = lambda a, b : "(%s > %d)" % (alpha[a], b) +dismap["gtrr"] = lambda a, b : "(%s > %s)" % (alpha[a], alpha[b]) +dismap["eqir"] = lambda a, b : "(%d == %s)" % (a, alpha[b]) +dismap["eqri"] = lambda a, b : "(%s == %d)" % (alpha[a], b) +dismap["eqrr"] = lambda a, b : "(%s == %s)" % (alpha[a], alpha[b]) + +def disassemble(): + for i in range(len(instructs)): + ins = instructs[i] + 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 + sqrtf = sqrt(f) + for i in range(1, int(sqrtf)): + if f % i == 0: + res += i + f / i + + if int(sqrtf) % f == 0: + res += sqrtf + + return int(res) + +aoc.run(solve1, solve2, sols=[2072, 27578880]) diff --git a/19/test1 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 diff --git a/src/20/input.txt b/20/input diff --git a/20/part1 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 @@ -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/20/solve.py b/20/solve.py @@ -0,0 +1,151 @@ +import sys +sys.path.append("../common") +import aoc +from copy import deepcopy + +data = list(aoc.data) + +def get_map(p): + return vmap[p[1] + spos[1]][p[0] + spos[0]] + +def set_map(p, c): + global vmap, spos + vmap[p[1] + spos[1]][p[0] + spos[0]] = c + +def new_pos(p, c): + p = p[:] + if c == "N": + p[1] -= 2 + elif c == "S": + p[1] += 2 + elif c == "W": + p[0] -= 2 + elif c == "E": + p[0] += 2 + return p + +def calc_pos(stack): + p = [0,0] + for c in stack: + p = new_pos(p, c) + return p + +xmin = 0 +xmax = 0 +ymin = 0 +ymax = 0 + +def check_size(stack): + global xmin, xmax, ymin, ymax + + p = calc_pos(stack) + if p[0] < xmin: + xmin = p[0] + if p[0] > xmax: + xmax = p[0] + if p[1] < ymin: + ymin = p[1] + if p[1] > ymax: + ymax = p[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) + set_map(cp, "+") + +def iter_regex(func): + stacklens = [0] + stack = [] + for i in range(1, len(data)-1): + c = data[i] + if c == "(": + stacklens.append(0) + elif c == "|": + for i in range(stacklens[-1]): + stack.pop() + stacklens[-1] = 0 + elif c == ")": + for i in range(stacklens[-1]): + stack.pop() + stacklens.pop() + else: + stack.append(c) + stacklens[-1] += 1 + func(stack) + +def fwriteMap(): + f = open("output", "w+") + for y in range(len(vmap)): + f.write("".join([str(v) for v in vmap[y]]) + "\n") + f.close() + +mshape = None +spos = None +vmap = None + +def genMap(): + global vmap, mshape, spos + + iter_regex(check_size) + xdif = xmax - xmin + 2 + ydif = ymax - ymin + 2 + + spos = (-xmin+1, -ymin+1) + mshape = (xdif, ydif) + + vmap = [["#" for x in range(xdif+1)] for y in range(ydif+1)] + vmap[spos[1]][spos[0]] = "X" + + iter_regex(draw_route) + + +adjacent = ((-1, 0), (0, -1), (1, 0), (0, 1)) + +def gen_countmap(sp): + countmap = dict() + next = dict() + next[(sp[0], sp[1])] = 0 + counter = 0 + steps = list() + while len(next) > 0 and len(steps) == 0: # first steps available will be shortest + countmap = {**countmap, **next} # merge dictionaries + counter += 1 + temp = dict() + for n in next: + for dir in adjacent: + nx = n[0]+dir[0] + ny = n[1]+dir[1] + 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 next_step(cmap, p): + # adjacent squares + npos = [[p[0] + dir[0], p[1] + dir[1]] for dir in adjacent] + + # steps and dist + steps = [[np[0], np[1], cmap[np[0], np[1]]] for np in npos if (np[0], np[1]) in cmap] + + if len(steps) == 0: + return None + else: + return sorted(steps, key = lambda x: x[2])[0] #closest + +genMap() + +def solve1(args): + cmap = gen_countmap((0,0)) + ipos = sorted(cmap, key = lambda x : cmap[x])[-1] + 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 @@ -0,0 +1 @@ +^ENWWW(NEEE|SSE(EE|N))$ diff --git a/src/21/input.txt b/21/input diff --git a/21/part1 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 @@ -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/21/solve.py b/21/solve.py @@ -0,0 +1,112 @@ +import sys +sys.path.append("../common") +import aoc +from math import sqrt + +def parse_command(l): + s = l.split(" ") + args = [s[0]] + args = args + [int(v) for v in s[1:]] + return args + +data = aoc.data.split("\n") + +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)] + +opmap = dict() +opmap["addr"] = lambda a, b : register[a] + register[b] +opmap["addi"] = lambda a, b : register[a] + b +opmap["mulr"] = lambda a, b : register[a] * register[b] +opmap["muli"] = lambda a, b : register[a] * b +opmap["banr"] = lambda a, b : register[a] & register[b] +opmap["bani"] = lambda a, b : register[a] & b +opmap["borr"] = lambda a, b : register[a] | register[b] +opmap["bori"] = lambda a, b : register[a] | b +opmap["setr"] = lambda a, b : register[a] +opmap["seti"] = lambda a, b : a +opmap["gtir"] = lambda a, b : 1 * (a > register[b]) +opmap["gtri"] = lambda a, b : 1 * (register[a] > b) +opmap["gtrr"] = lambda a, b : 1 * (register[a] > register[b]) +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 varname(v): + return "R"+str(v) + +dismap = dict() +dismap["addr"] = lambda a, b : "%s + %s" % (varname(a), varname(b)) +dismap["addi"] = lambda a, b : "%s + %d" % (varname(a), b) +dismap["mulr"] = lambda a, b : "%s * %s" % (varname(a), varname(b)) +dismap["muli"] = lambda a, b : "%s * %d" % (varname(a), b) +dismap["banr"] = lambda a, b : "%s & %s" % (varname(a), varname(b)) +dismap["bani"] = lambda a, b : "%s & %d" % (varname(a), b) +dismap["borr"] = lambda a, b : "%s | %s" % (varname(a), varname(b)) +dismap["bori"] = lambda a, b : "%s | %d" % (varname(a), b) +dismap["setr"] = lambda a, b : "%s" % (varname(a)) +dismap["seti"] = lambda a, b : "%d" % (a) +dismap["gtir"] = lambda a, b : "(%d > %s)" % (a, varname(b)) +dismap["gtri"] = lambda a, b : "(%s > %d)" % (varname(a), b) +dismap["gtrr"] = lambda a, b : "(%s > %s)" % (varname(a), varname(b)) +dismap["eqir"] = lambda a, b : "(%d == %s)" % (a, varname(b)) +dismap["eqri"] = lambda a, b : "(%s == %d)" % (varname(a), b) +dismap["eqrr"] = lambda a, b : "(%s == %s)" % (varname(a), varname(b)) + +def disassemble(s, e): + for i in range(s, e): + ins = instructs[i] + aoc.debug(i ,":",varname(ins[3]),"=", dismap[ins[0]](ins[1], ins[2])) + aoc.debug() + +def execute(): + global register, insptr + + while register[inspaddr] < len(instructs): + insptr = register[inspaddr] + ins = instructs[insptr] + + # execute command + if len(register) <= ins[3]: + register += [0 for x in range(ins[3] - len(register) + 1)] + register[ins[3]] = opmap[ins[0]](ins[1], ins[2]) + + # part 1 + #if insptr == 13 and register[4] == 1: + # aoc.debug(register) + # return + + # increment instruction pointer + register[inspaddr] += 1 + +def solve1(args): + r0 = 1797184 # (first opportunity for comparison r1 and r0) + + #disassemble(0, len(instructs)) + #execute() + + return r0 + +def solve2(args): + r1 = 0 + candidates = list() + while True: + r4 = r1 | 65536 # flip 9th bit + r1 = 3798839 + while True: # scan bytes of r4 and add them to r1 and multiply + r5 = r4 & 255 + r1 += r5 + r1 = r1 & 16777215 + r1 *= 65899 # equals 1 00000001 01101011 + r1 = r1 & 16777215 + if r4 < 256: + break + r4 = int(r4/256) # bit shift 8 to the right + 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 @@ -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 diff --git a/22/part1 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 @@ -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/22/solve.py b/22/solve.py @@ -0,0 +1,93 @@ +import sys +sys.path.append("../common") +import aoc +import networkx + +adjacent = [[-1, 0], [0, -1], [1, 0], [0, 1]] + +# create symbol definitions +symbols = [".", "=", "|"] +rocky, wet, narrow = 0, 1, 2 +torch, gear, neither = 0, 1, 2 + +tooloptions = dict() +tooloptions[rocky] = (torch, gear) +tooloptions[wet] = (gear, neither) +tooloptions[narrow] = (torch, neither) + +# parse input file +def parse_input(si): + s = si.split("\n") + depth = int(s[0].split(": ")[1]) + target = [int(v) for v in s[1].split(": ")[1].split(",")] + return depth, target + +# get erosion level from geological index +def get_erosion_level(n): + return (n + depth) % 20183 + +# generate map of erosion types +def gen_map(): + grid = [[0 for x in range(mrange[0])] for y in range(mrange[1])] + + # generate values on x side + grid[0] = [get_erosion_level(x * 16807) for x in range(mrange[0])] + + # generate values on y side + for y in range(mrange[1]): + grid[y][0] = get_erosion_level(y * 48271) + + # fill in other positions + for y in range(1, mrange[1]): + for x in range(1, mrange[0]): + grid[y][x] = get_erosion_level(grid[y-1][x] * grid[y][x-1]) + + # mod 3 for env type + grid = [[grid[y][x] % 3 for x in range(mrange[0])] for y in range(mrange[1])] + + # start position is rocky + grid[target[1]][target[0]] = 0 + + return grid + +# define constants from input file +depth, target = parse_input(aoc.data) +mrange = (target[0] + 100, target[1] + 100) # 100 block padding for potential hook-paths + +vmap = gen_map() + +def risk_level(width, height): + risk = 0 + for y in range(height + 1): + for x in range(width + 1): + risk += vmap[y][x] + return risk + +def adj(p): + return [[p[0] + di[0], p[1] + di[1]] for di in adjacent] + +def dijkstra(): + graph = networkx.Graph() + for y in range(mrange[1]): + for x in range(mrange[0]): + tools = tooloptions[vmap[y][x]] + # always takes 7 minutes to switch, 2 z-options for each tool + graph.add_edge((x, y, tools[0]), (x, y, tools[1]), weight = 7) + for (nx, ny) in adj((x, y)): + if 0 <= nx < mrange[0] and 0 <= ny < mrange[1]: + ntools = tooloptions[vmap[ny][nx]] + # if tool is usable in both environments + for tool in [t for t in tools if t in ntools]: + # then it only takes 1 minute + graph.add_edge((x, y, tool), (nx, ny, tool), weight = 1) + + return networkx.dijkstra_path_length(graph, + (0, 0, torch), (target[0], target[1], torch)) + +def solve1(args): + return risk_level(target[0], target[1]) + +def solve2(args): + return dijkstra() + +aoc.run(solve1, solve2, sols=[11359, 976]) diff --git a/src/23/input.txt b/23/input diff --git a/23/part1 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 @@ -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/23/solve.py b/23/solve.py @@ -0,0 +1,108 @@ +import sys +sys.path.append("../common") +import aoc +import math + +# nanobots consist of tuples containing: (position, radius) +nanobots = list() + +# parse a line of input file +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)) + +data = [parse_entry(l) for l in aoc.data.split("\n") if len(l) != 0] + +# manhattan distance +def dist(p1, p2): + xd = abs(p1[0] - p2[0]) + yd = abs(p1[1] - p2[1]) + zd = abs(p1[2] - p2[2]) + return xd + yd + zd + +# two nanobots range overlap +def is_overlap(nb1, nb2): + return nb1[1] + nb2[1] >= dist(nb1[0], nb2[0]) + +# nanobots range completely inside anothers range +def is_inside(nb1, nb2): + return dist(nb1[0], nb2[0]) <= nb2[1] - nb1[1] + +# check if range of nanobot is inside grid +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)] + md = max(ds) + if md == 0: + return True + ds = [d * hgridsize / md for d in ds] # get distance along squares sides + return dist(nbp, tile) - sum(ds) <= nb[1] + +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 + return inrange + +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] + minpz = min(nanobots, key = lambda x : x[0][2])[0][2] + minp = (minpx, minpy, minpz) + + maxpx = max(nanobots, key = lambda x : x[0][0])[0][0] + maxpy = max(nanobots, key = lambda x : x[0][1])[0][1] + maxpz = max(nanobots, key = lambda x : x[0][2])[0][2] + maxp = (maxpx, maxpy, maxpz) + + gridsize = max([maxp[i] - minp[i] for i in range(3)]) # largest dif dim to ensure all nanbots are in the grid + + bestpos = None + while gridsize >= 1: + maxintile = 0 + + # traverse grid in steps of gridsize + xsteps = math.ceil((maxp[0] - minp[0]) / gridsize) + 1 + ysteps = math.ceil((maxp[1] - minp[1]) / gridsize) + 1 + zsteps = math.ceil((maxp[2] - minp[2]) / gridsize) + 1 + for nx in range(xsteps): + for ny in range(ysteps): + for nz in range(zsteps): + x = minp[0] + nx * gridsize + y = minp[1] + ny * gridsize + z = minp[2] + nz * gridsize + intile = 0 + for nb in nanobots: + # 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: + 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] + + return sum(bestpos) + +aoc.run(solve1, solve2, sols=[573, 107279292]) diff --git a/src/24/input.txt b/24/input diff --git a/24/part1 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 @@ -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/24/solve.py b/24/solve.py @@ -0,0 +1,127 @@ +import sys +sys.path.append("../common") +import aoc + +immunesys = 0 +infection = 1 +ctype = 0 + +# parse input from file +def parse_input(): + groups = list() + for l in aoc.data.split("\n"): + pl = parse_entry(l) + if pl != None: + groups.append(pl) + return groups + +# parse line of input +def parse_entry(line): + global ctype + group = None + if "Immune" in line: + ctype = immunesys + elif "Infection" in line: + ctype = infection + elif line != "": + ls = line.split() + group = dict() + group["type"] = ctype + group["units"] = int(ls[0]) + group["unithp"] = int(ls[4]) + group["initiative"] = int(ls[-1]) + group["weak"] = list() + group["immune"] = list() + if "(" in line: + parenthstr = line.split("(")[1].split(")")[0] + traits = parenthstr.split(";") + for traitstr in traits: + info = traitstr.split() + group[info[0]] = [v.replace(",","") for v in info[2:]] + dmginfo = line.split("does")[1].split("damage")[0].split() + group["dmg"] = int(dmginfo[0]) + group["dmgtype"] = dmginfo[1] + return group + +def effective_power(g): + return g["units"] * g["dmg"] + +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 = parse_input() + +def fight(): + global groups + + lunits = 0 + + immalive = len([g for g in groups if g["type"] == immunesys]) + infalive = len([g for g in groups if g["type"] == infection]) + + while immalive > 0 and infalive > 0: + # target selection + attacked = list() + attackpairs = list() + 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 : \ + (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))) + + # attacking phase + attackpairs = sorted(attackpairs, key = lambda x : groups[x[0]]["initiative"], reverse = True) + + for ap in attackpairs: + attacker = groups[ap[0]] + attacked = groups[ap[1]] + # 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]) + infalive = sum([g["units"] for g in groups if g["type"] == infection]) + units = immalive + infalive + if units == lunits: + return units + lunits = units + + return units + +def solve1(args): + return fight() + +def solve2(args): + global groups + + immunewin = False + boost = 1 + while not immunewin: + groups = parse_input() + for g in groups: + if g["type"] == immunesys: + g["dmg"] += boost + + fight() + + immunewin = (sum([0 if g["type"] == immunesys else 1 for g in groups]) == 0) + + boost += 1 + + aoc.debug("boost:", boost) + + return sum([v["units"] for v in groups]) + +aoc.run(solve1, solve2, sols=[10538, 9174]) diff --git a/src/25/input.txt b/25/input diff --git a/25/part1 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 @@ -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 @@ -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 @@ -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 @@ -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 @@ -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 @@ -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 @@ -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)))) diff --git a/README.md b/README.md @@ -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 @@ -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 @@ -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/1/solve.py b/src/1/solve.py @@ -1,61 +0,0 @@ -from sys import argv as args - -file = open("input.txt") -data = [int(x) for x in file.readlines()] -file.close() - -def solve1(): # answer: 411 - print(sum(data)) - -def solve2(): # answer: 56360 - totshift = 0 - fvals = list() - for c in data: - fvals.append(totshift) - totshift += c - print("total shift: " + str(totshift)) - - doubles = list() - - if totshift == 0: - doubles.append([len(data), 0]) - - i = 0 - while i < len(fvals): - for j in range(len(fvals)): - if i == j: - continue - dif = fvals[j] - fvals[i] - if dif % totshift == 0: - inds = list([i, j]) - if j > i: - inds = inds[::-1] - if totshift > 0: #ends on c - if fvals[inds[0]] > fvals[inds[1]]: - inds = inds[::-1] - else: - if fvals[inds[0]] < fvals[inds[1]]: - inds = inds[::-1] - - pos = (abs(dif) // totshift) * len(data) + inds[0] - doubles.append([pos, fvals[inds[1]]]) - i += 1 - - if len(doubles) == 0: #fail - return - - min = doubles[0] - for d in doubles: - if d[0] < min[0]: - min = d - - print(min[1]) - -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 @@ -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/11/solve.py b/src/11/solve.py @@ -1,80 +0,0 @@ -import sys -args = sys.argv - -gridserial = int(open("input.txt").read()) - -# rack ID = x + 10 -# intial power = rackID * y -# power += gridserial -# power *= rackID -# power = str(power)[2] -# power -= 5 - -def getPower(x,y): - id = x + 10 - power = id * y - power += gridserial - power *= id - spower = str(power) - if len(spower) > 2: - power = int(spower[-3]) - else: - power = 0 - power -= 5 - return power - -def solve1(): - maxpower = None - coords = None - for x in range(300-2): - for y in range(300-2): - power = 0; - for i in range(3): - for j in range(3): - power += getPower(x+i,y+j) - if maxpower == None or power > maxpower: - maxpower = power - coords = (x, y) - print(f"{coords[0]},{coords[1]}") - -def genMap(): - 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) - return vmap - -def solve2(): - maxpower = None - res = None - pmap = genMap() - vmap = [[list() for y in range(300)] for x in range(300)] - for s in range(1, 301): - print(f"\rTrying: {s}", end="") - cmaxpower = None - cres = None - for x in range(300-(s-1)): - for y in range(300-(s-1)): - vmap[x][y] += [pmap[x+(s-1)][y+i] for i in range(s)] - vmap[x][y] += [pmap[x+i][y+(s-1)] for i in range(s-1)] - power = sum(vmap[x][y]); - if cmaxpower == None or power > cmaxpower: - cmaxpower = power - cres = (x, y, s) - if maxpower == None or cmaxpower > maxpower: - maxpower = cmaxpower - res = cres - elif cmaxpower < maxpower: - break - - print("\r" + " " * 50 + "\r", end="") - print(f"{res[0]},{res[1]},{res[2]}") - -def main(): - if len(args) > 1: - if args[1] == "1": - solve1() - elif args[1] == "2": - solve2() - -main() diff --git a/src/12/solve.py b/src/12/solve.py @@ -1,61 +0,0 @@ -from sys import argv as args - -lines = open("input.txt").read().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): - pmin = min(pots) - pmax = max(pots) - npots = list() - for i in range(pmin-4, pmax+1): - for r in rules: - match = True - for j in range(5): - if (r[j] == "#") != ((i+j) in pots): - match = False - break - if match: - npots.append(i+2) - break - return npots - -def getPots(): - pots = list() - for i in range(len(istate)): - if istate[i] == "#": - pots.append(i) - return pots - -def solve1(): - pots = getPots() - for i in range(20): - pots = nextGen(pots) - print(sum(pots)) - return - -def solve2(): - pots = getPots() - psum = sum(pots) - pdif = None - i = 0 - while (True): - pots = nextGen(pots) - i += 1 - csum = sum(pots) - if pdif == csum - psum: - print(csum + pdif * (50000000000 - 164)) - break - pdif = csum - psum - psum = csum - return - -def main(): - if len(args) > 1: - if args[1] == "1": - solve1() - elif args[1] == "2": - solve2() - -main() diff --git a/src/13/solve.py b/src/13/solve.py @@ -1,167 +0,0 @@ -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() - -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 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) - - if cr == "|": cr = " " - if cl == "|": cl = " " - if cu == "-": cu = " " - if cd == "-": cd = " " - - r = cr != " " - l = cl != " " - u = cu != " " - d = cd != " " - - sum = r + l + u + d - - if sum > 2: - 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, 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 and not c[4]: - return i - return None - -def drawMap(): - for y in range(ylen): - print("".join(["#" if cartAt(x,y) != None else tmap[y][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]) - if col != None: - 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 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(f"{crash[0]},{crash[1]}") - -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)): - if carts[c][4]: continue; - nc = advance(carts[c]) - if len(nc) == 3: - carts[c][4] = 1 - carts[nc[2]][4] = 1 - rcarts.append(carts[c]) - rcarts.append(carts[nc[2]]) - else: - carts[c] = nc - for c in rcarts: - 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() - -main() diff --git a/src/13/solve.py~ b/src/13/solve.py~ @@ -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/14/solve.py b/src/14/solve.py @@ -1,42 +0,0 @@ -from sys import argv as args - -inputstr = open("input.txt").read().replace("\n","") -recipes = [3,7] - -def solve1(): - global recipes, inputstr - - end = int(inputstr) - 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:]])) - -def solve2(): - global recipes, inputstr - - ilen = len(inputstr) - inputstr = [int(c) for c in inputstr] - 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: - 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) - -def main(): - if len(args) > 1: - if args[1] == "1": - solve1() - elif args[1] == "2": - solve2() - -main() diff --git a/src/15/solve.py b/src/15/solve.py @@ -1,291 +0,0 @@ -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 - -actors = list() -input = [l.replace("\n","") for l in input] - -def parseEntity(x, y): - global actors - c = input[y][x] - if c == "#": - return 1 - else: - if c == "G": - actors.append([x, y, 200, 1, len(actors), 3]) - elif c == "E": - actors.append([x, y, 200, 0, len(actors), 3]) - return 0 - -ylen = len(input) -xlen = len(input[0]) - -adjacent = [[0, -1], [-1, 0], [1, 0], [0, 1]] # first in reading order -vmap = list() - -def setGame(): - global vmap, actors - actors = list() - vmap = [[parseEntity(x, y) for x in range(xlen)] for y in range(ylen)] - - -def inmap(cmap, cx, cy): - for i in range(len(cmap)): - ent = cmap[i] - if ent[0] == cx and ent[1] == cy: - return i - return None - -def iswall(x,y): - return vmap[y][x] != 0 - -def isblocked(x, y): - return (vmap[y][x] != 0 or inmap(actors, x, y) != None) - -def freeAdjacent(x, y): - poslist = list() - for dir in adjacent: - nx = x + dir[0] - ny = y + dir[1] - if not isblocked(nx, ny): - poslist.append((nx,ny)) - return poslist - -def flatten(l): - flat = list() - for ll in l: - flat += ll - return flat - -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() - -def getSteps(cmap, a1): - # adjacent squares - npos = [[a1[0] + dir[0], a1[1] + dir[1]] for dir in adjacent] - - # pos of enemy and distance - steps = [[np[0], np[1], cmap[np[0], np[1]]] for np in npos if (np[0], np[1]) in cmap] - - return steps - -def closestStep(a1, a2): - countmap = dict() - next = dict() - next[(a2[0], a2[1])] = 0 - counter = 0 - steps = list() - while len(next) > 0 and len(steps) == 0: # first steps available will be shortest - countmap = {**countmap, **next} # merge dictionaries - counter += 1 - temp = dict() - for n in next: - for dir in adjacent: - nx = n[0]+dir[0] - ny = n[1]+dir[1] - if not isblocked(nx, ny) and (nx, ny) not in countmap and (nx, ny) not in temp: - temp[(nx,ny)] = counter - next = temp - steps = getSteps(countmap, a1) - - # if reachable - if len(steps) != 0: - return sorted(steps, key = lambda x : (x[1], x[0]))[0] - else: - return [None] - -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]] - - # only where step is possible - steps = [s for s in steps if s[2] != None] - - # skip when none possible - if len(steps) == 0: - return - - # best move - bestmove = sorted(steps, key = lambda x : (x[4], x[1], x[0]))[0] - a[0] = bestmove[2] - a[1] = bestmove[3] - -def getInrange(a): - global actors - inrange = list() - for dir in adjacent: - nx = a[0] + dir[0] - ny = a[1] + dir[1] - ind = inmap(actors, nx, ny) - if ind != None and actors[ind][3] != a[3]: - inrange.append(ind) - return inrange - -def nextTick(tick): - global actors - actors = sorted(actors, key=lambda x: (x[1], x[0]), reverse=True) - i = len(actors)-1 - - while i >= 0: - a = actors[i] - inrange = getInrange(a) # get enemies in range - if len(inrange) == 0: - move(a) - inrange = getInrange(a) - - if len(inrange) != 0: - inrange = [actors[ai] + [ai] for ai in inrange] - - # lowest health in reading order - cai = sorted(inrange, key = lambda x : (x[2], x[1], x[0]))[0][-1] - - # attack player - 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 - return False - if cai < i: i -= 1 - - if debug and False: - print() - print("small step -",a[4]) - drawMap() - statusReport() - i -= 1 - - if debug: - print() - print("tick:", tick) - drawMap() - statusReport() - else: - print(tick) - return True - -def minalive(): - alive = [0,0] - for a in actors: - alive[1 * (a[3] == 0)] += 1 - return min(alive) - -def sumHP(): - return sum(a[2] for a in actors) - -def statusReport(): - global actors - #drawMap() - sactors = sorted(actors, key = lambda x:x[4]) - for a in sactors: - print("HP:", a[2]) - print() - -def elvesAlive(): - return len([a for a in actors if a[3] == 0]) - -def startBattle(eap): - global actors - setGame() # reset - for a in actors: - if a[3] == 0: - a[5] = eap - - elfcount = elvesAlive() - - ticks = 0 - while minalive() > 0: - if nextTick(ticks): - ticks += 1 - statusReport() - return ((sumHP() * ticks), (elfcount - elvesAlive())) # res and casualties - -def solve1(): - res = startBattle(3) - print("answer:", res[0]); - -def solve2(): - eap = 4 - res = startBattle(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() diff --git a/src/16/notes.txt b/src/16/notes.txt @@ -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/16/solve.py b/src/16/solve.py @@ -1,121 +0,0 @@ -from sys import argv as args - - -def parseLog(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() -progsec = None - -for i in range(0, len(input), 4): - if input[i] == "\n": - progsec = i - break - inslog.append(parseLog(input[i:i+4])) - - -register = list() - -opmap = dict() -opmap["addr"] = lambda a, b : register[a] + register[b] -opmap["addi"] = lambda a, b : register[a] + b -opmap["mulr"] = lambda a, b : register[a] * register[b] -opmap["muli"] = lambda a, b : register[a] * b -opmap["banr"] = lambda a, b : register[a] & register[b] -opmap["bani"] = lambda a, b : register[a] & b -opmap["borr"] = lambda a, b : register[a] | register[b] -opmap["bori"] = lambda a, b : register[a] | b -opmap["setr"] = lambda a, b : register[a] -opmap["seti"] = lambda a, b : a -opmap["gtir"] = lambda a, b : 1 * (a > register[b]) -opmap["gtri"] = lambda a, b : 1 * (register[a] > b) -opmap["gtrr"] = lambda a, b : 1 * (register[a] > register[b]) -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): - global register - sregister = register[:] - before = ins[0] - after = ins[2] - register = before - a = ins[1][1] - b = ins[1][2] - c = ins[1][3] - ops = list(opmap.values()) - possibles = list() - for i in range(len(ops)): - op = ops[i] - res = None - try: - res = op(a, b) - except: - continue - if res == after[c]: - possibles.append(i) - register = sregister - return possibles - -def solve1(): - global register - uncertain = 0 - for ins in inslog: - if len(getPossible(ins)) >= 3: - uncertain += 1 - print(uncertain) - return - -def solve2(): - 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]] - else: - possible[o] = getPossible(ins) - - certain = False - while not certain: - singles = [p[0] for p in possible.values() if len(p) == 1] - for p in possible: - if len(possible[p]) != 1: - possible[p] = [v for v in possible[p] if v not in singles] - - certain = True - for p in possible.values(): - if len(p) != 1: - certain = False - break - - ntrans = dict() - for p in possible: # flatten - ntrans[p] = possible[p][0] - - for i in range(progsec, len(input)): # execute program - l = input[i] - if l == "\n": continue - cmd = [int(v) for v in l.split(" ")] - while len(register)-1 < cmd[3]: - register.append(0) - - register[cmd[3]] = list(opmap.values())[ntrans[cmd[0]]](cmd[1], cmd[2]) - - - print(register[0]) - -def main(): - if len(args) > 1: - if args[1] == "1": - solve1() - elif args[1] == "2": - solve2() - -main() diff --git a/src/17/solve.py b/src/17/solve.py @@ -1,212 +0,0 @@ -from sys import argv as args - -debug = False - -def parseLine(l): - s = l.split(", ") - if s[0].startswith("y="): - s = s[::-1] - - 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] - -xmin = min(c[0][0] for c in constraints)-1 -xmax = max(c[0][-1] for c in constraints)+1 -ymin = min(c[1][0] for c in constraints) -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): - 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): - global vmap - if x > xmax or x < xmin: - return 1 - elif y > ymax: - return 0 - return vmap[y-ymin][x-xmin] - -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) - else: - for x in range(c[0][0], c[0][1] + 1): - setMap(x, c[1][0], 1) - -for c in constraints: - drawWall(c) - -spring = (500, 0) - - -### SETUP END - - -def interpretChar(v): - chars = [".", "#", "|", "~"] - return chars[v] - -def drawMap(): - for y in range(ydif): - print("".join([interpretChar(v) for v in vmap[y]])) - -def fwriteMap(): - f = open("output","w+") - for y in range(ydif): - f.write("".join([interpretChar(v) for v in vmap[y]])+"\n") - f.close() - -def isstatic(p): - return getMap(p[0], p[1]) in (1, 3) - -def isfree(p): - return getMap(p[0], p[1]) == 0 - -def move(p): - x = p[0] - y = p[1] - if isfree((x, y+1)): - return (x, y+1) - onblock = isstatic((x, y+1)) - if not onblock: - return (x,y) - npos = [(x + dir, y) for dir in [-1, 1]] - npos = [np for np in npos if isfree(np) and onblock] - if len(npos) > 1: - return npos - elif len(npos) == 1: - return npos[0] - return (x, y) - -def fillfloor(p): - onblock = True - isblock = False - x = p[0] - while onblock and not isblock and x >= xmin: - x -= 1 - isblock = isstatic((x, p[1])) - onblock = isstatic((x, p[1]+1)) - if not isblock: - return None # edge - lx = x+1 - - onblock = True - isblock = False - x = p[0] - while onblock and not isblock and x <= xmax: - x += 1 - isblock = isstatic((x, p[1])) - onblock = isstatic((x, p[1]+1)) - if not isblock: - return None - rx = x-1 - - return [(i, p[1]) for i in range(lx, rx+1)] - -def countWFlowing(): - water = 0 - for y in range(ymin, ymax+1): - for x in range(xmin, xmax+1): - if getMap(x,y) == 2: - water += 1 - return water - -def countWStatic(): - water = 0 - for y in range(ymin, ymax+1): - for x in range(xmin, xmax+1): - if getMap(x,y) == 3: - water += 1 - return water - -def simulate(): - heads = [spring] - while len(heads) > 0: - cp = heads[-1] - if isstatic((cp[0], cp[1]+1)): - # solid below => expand - res = fillfloor(cp) - if res: - for p in res: - setMap(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: - nhead = np - break - if nhead == None: # head got trapped - heads.pop() - else: - heads[-1] = nhead - continue - - res = move(cp) - if type(res[0]) == tuple: - heads.pop() - heads += res - for p in res: - setMap(p[0], p[1], 2) - else: - if res != cp: - if res[1] <= ymax: - setMap(res[0], res[1], 2) - heads[-1] = res - else: - heads.pop() - else: - heads.pop() - - if debug: - print(heads) - input() - fwriteMap() - -def solve1(): - simulate() - #fwriteMap() - print(countWFlowing() + countWStatic()) - return - -def solve2(): - simulate() - #fwriteMap() - print(countWStatic()) - return - -def main(): - if len(args) > 1: - if args[1] == "1": - solve1() - elif args[1] == "2": - solve2() - -main() diff --git a/src/18/solve.py b/src/18/solve.py @@ -1,106 +0,0 @@ -from sys import argv as args -from copy import deepcopy -from collections import deque - -states = (".", "|", "#") - -ivals = dict() -ivals["#"] = 0 -ivals["."] = 0 -ivals["|"] = 0 - -def parseLine(l): - return tuple([states.index(c) for c in l]) - -inputstr = open("input.txt").read() - -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): - if y < 0 or y >= ylen or x < 0 or x >= xlen: - return None - return vmap[y][x] - -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)] - if v == 0: - if len([v for v in around if v == 1]) >= 3: - return 1 - elif v == 1: - if len([v for v in around if v == 2]) >= 3: - return 2 - elif v == 2: - if len([v for v in around if v == 1]) < 1 or len([v for v in around if v == 2]) < 1: - return 0 - return v - -def getVals(): - 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): - for y in range(ylen): - print("".join([str(c) for c in cmap[y]])) - -def iterate(n): - global vmap - for i in range(n): - omap = [deque() for y in range(ylen)] - for y in range(ylen): - for x in range(xlen): - omap[y].append(next(x, y)) - vmap = omap - -def getRes(): - vals = getVals() - return (vals[1] * vals[2]) - -def solve1(): - #drawMap(vmap) - iterate(10) - vals = getVals() - #drawMap(vmap) - print(vals[1] * vals[2]) - return - -def solve2(): - iterate(1000) - omap = deepcopy(vmap) - counter = 0 - while True: - iterate(1) - counter += 1 - 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() - -main() diff --git a/src/19/solve.py b/src/19/solve.py @@ -1,131 +0,0 @@ -from sys import argv as args -from math import sqrt - -def parseCommand(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() - -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] - -register = [0 for x in range(inspaddr+1)] - -opmap = dict() -opmap["addr"] = lambda a, b : register[a] + register[b] -opmap["addi"] = lambda a, b : register[a] + b -opmap["mulr"] = lambda a, b : register[a] * register[b] -opmap["muli"] = lambda a, b : register[a] * b -opmap["banr"] = lambda a, b : register[a] & register[b] -opmap["bani"] = lambda a, b : register[a] & b -opmap["borr"] = lambda a, b : register[a] | register[b] -opmap["bori"] = lambda a, b : register[a] | b -opmap["setr"] = lambda a, b : register[a] -opmap["seti"] = lambda a, b : a -opmap["gtir"] = lambda a, b : 1 * (a > register[b]) -opmap["gtri"] = lambda a, b : 1 * (register[a] > b) -opmap["gtrr"] = lambda a, b : 1 * (register[a] > register[b]) -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 solve1(): - global register, insptr - while register[inspaddr] < len(instructs): - insptr = register[inspaddr] - ins = instructs[insptr] - #print(register) - - # execute command - if len(register) <= ins[3]: - register += [0 for x in range(ins[3] - len(register) + 1)] - register[ins[3]] = opmap[ins[0]](ins[1], ins[2]) - - # increment instruction pointer - register[inspaddr] += 1 - - print(register[0]) - - -alpha = [chr(c + ord('a')) for c in range(26)] - -dismap = dict() -dismap["addr"] = lambda a, b : "%s + %s" % (alpha[a], alpha[b]) -dismap["addi"] = lambda a, b : "%s + %d" % (alpha[a], b) -dismap["mulr"] = lambda a, b : "%s * %s" % (alpha[a], alpha[b]) -dismap["muli"] = lambda a, b : "%s * %d" % (alpha[a], b) -dismap["banr"] = lambda a, b : str(alpha[a] & alpha[b]) -dismap["bani"] = lambda a, b : str(alpha[a] & b) -dismap["borr"] = lambda a, b : str(alpha[a] | alpha[b]) -dismap["bori"] = lambda a, b : str(alpha[a] | b) -dismap["setr"] = lambda a, b : str(alpha[a]) -dismap["seti"] = lambda a, b : str(a) -dismap["gtir"] = lambda a, b : "(%d > %s)" % (a, alpha[b]) -dismap["gtri"] = lambda a, b : "(%s > %d)" % (alpha[a], b) -dismap["gtrr"] = lambda a, b : "(%s > %s)" % (alpha[a], alpha[b]) -dismap["eqir"] = lambda a, b : "(%d == %s)" % (a, alpha[b]) -dismap["eqri"] = lambda a, b : "(%s == %d)" % (alpha[a], b) -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 - - f = 10551276 # found by running - - res = 0 - sqrtf = sqrt(f) - for i in range(1, int(sqrtf)): - if f % i == 0: - res += i + f / i - - 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() diff --git a/src/2/solve.py b/src/2/solve.py @@ -1,47 +0,0 @@ -from sys import argv as args - -file = open("input.txt") -data = [x.replace("\n","") for x in file.readlines()] -file.close() - -def solve1(): - doubles = 0 - triples = 0 - for s in data: - counts = list((0,) * 26) # characters - 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) - -def compare(s1, s2): - dif = 0 - same = list() - for i in range(len(s1)): - if s1[i] != s2[i]: - dif += 1 - else: - same.append(s1[i]) - return(dif, same) - -def solve2(): - 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 - -def main(): - if len(args) > 1: - if args[1] == "1": - solve1() - elif args[1] == "2": - solve2() - -main() diff --git a/src/20/solve.py b/src/20/solve.py @@ -1,164 +0,0 @@ -from sys import argv as args -from copy import deepcopy - -sinput = list(open("input.txt").read().strip()) - -ainput = "^ENWWW(NEEE|SSE(EE|N))$" - -def getMap(p): - return vmap[p[1] + spos[1]][p[0] + spos[0]] - -def setMap(p, c): - global vmap, spos - vmap[p[1] + spos[1]][p[0] + spos[0]] = c - -def newpos(p, c): - p = p[:] - if c == "N": - p[1] -= 2 - elif c == "S": - p[1] += 2 - elif c == "W": - p[0] -= 2 - elif c == "E": - p[0] += 2 - return p - -def calcpos(stack): - p = [0,0] - for c in stack: - p = newpos(p, c) - return p - -xmin = 0 -xmax = 0 -ymin = 0 -ymax = 0 - -def checkSize(stack): - global xmin, xmax, ymin, ymax - p = calcpos(stack) - if p[0] < xmin: - xmin = p[0] - if p[0] > xmax: - xmax = p[0] - if p[1] < ymin: - ymin = p[1] - if p[1] > ymax: - ymax = p[1] - -def drawRoute(stack): - p = calcpos(stack) - setMap(p, ".") - np = newpos(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, "+") - -def iterRegex(func): - stacklens = [0] - stack = [] - for i in range(1, len(sinput)-1): - c = sinput[i] - if c == "(": - stacklens.append(0) - elif c == "|": - for i in range(stacklens[-1]): - stack.pop() - stacklens[-1] = 0 - elif c == ")": - for i in range(stacklens[-1]): - stack.pop() - stacklens.pop() - else: - stack.append(c) - stacklens[-1] += 1 - func(stack) - -def fwriteMap(): - f = open("output", "w+") - for y in range(len(vmap)): - f.write("".join([str(v) for v in vmap[y]]) + "\n") - f.close() - -mshape = None -spos = None -vmap = None - -def genMap(): - global vmap, mshape, spos - iterRegex(checkSize) - xdif = xmax - xmin + 2 - ydif = ymax - ymin + 2 - - spos = (-xmin+1, -ymin+1) - mshape = (xdif, ydif) - - vmap = [["#" for x in range(xdif+1)] for y in range(ydif+1)] - vmap[spos[1]][spos[0]] = "X" - - iterRegex(drawRoute) - - -adjacent = ((-1, 0), (0, -1), (1, 0), (0, 1)) - -def genCountmap(sp): - countmap = dict() - next = dict() - next[(sp[0], sp[1])] = 0 - counter = 0 - steps = list() - while len(next) > 0 and len(steps) == 0: # first steps available will be shortest - countmap = {**countmap, **next} # merge dictionaries - counter += 1 - temp = dict() - for n in next: - 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: - temp[(nx,ny)] = counter - next = temp - return countmap - -def nextStep(cmap, p): - # adjacent squares - npos = [[p[0] + dir[0], p[1] + dir[1]] for dir in adjacent] - - # steps and dist - steps = [[np[0], np[1], cmap[np[0], np[1]]] for np in npos if (np[0], np[1]) in cmap] - - if len(steps) == 0: - return None - else: - return sorted(steps, key = lambda x: x[2])[0] #closest - -### SETUP - -genMap() -#print("finished generating..") - -### PROBLEM CODE - -def solve1(): - cmap = genCountmap((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() diff --git a/src/21/solve.py b/src/21/solve.py @@ -1,139 +0,0 @@ -from sys import argv as args -from math import sqrt - -def parseCommand(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() - -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] - -register = [0 for x in range(inspaddr+1)] - -opmap = dict() -opmap["addr"] = lambda a, b : register[a] + register[b] -opmap["addi"] = lambda a, b : register[a] + b -opmap["mulr"] = lambda a, b : register[a] * register[b] -opmap["muli"] = lambda a, b : register[a] * b -opmap["banr"] = lambda a, b : register[a] & register[b] -opmap["bani"] = lambda a, b : register[a] & b -opmap["borr"] = lambda a, b : register[a] | register[b] -opmap["bori"] = lambda a, b : register[a] | b -opmap["setr"] = lambda a, b : register[a] -opmap["seti"] = lambda a, b : a -opmap["gtir"] = lambda a, b : 1 * (a > register[b]) -opmap["gtri"] = lambda a, b : 1 * (register[a] > b) -opmap["gtrr"] = lambda a, b : 1 * (register[a] > register[b]) -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 varname(v): - return "R"+str(v) - -dismap = dict() -dismap["addr"] = lambda a, b : "%s + %s" % (varname(a), varname(b)) -dismap["addi"] = lambda a, b : "%s + %d" % (varname(a), b) -dismap["mulr"] = lambda a, b : "%s * %s" % (varname(a), varname(b)) -dismap["muli"] = lambda a, b : "%s * %d" % (varname(a), b) -dismap["banr"] = lambda a, b : "%s & %s" % (varname(a), varname(b)) -dismap["bani"] = lambda a, b : "%s & %d" % (varname(a), b) -dismap["borr"] = lambda a, b : "%s | %s" % (varname(a), varname(b)) -dismap["bori"] = lambda a, b : "%s | %d" % (varname(a), b) -dismap["setr"] = lambda a, b : "%s" % (varname(a)) -dismap["seti"] = lambda a, b : "%d" % (a) -dismap["gtir"] = lambda a, b : "(%d > %s)" % (a, varname(b)) -dismap["gtri"] = lambda a, b : "(%s > %d)" % (varname(a), b) -dismap["gtrr"] = lambda a, b : "(%s > %s)" % (varname(a), varname(b)) -dismap["eqir"] = lambda a, b : "(%d == %s)" % (a, varname(b)) -dismap["eqri"] = lambda a, b : "(%s == %d)" % (varname(a), b) -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() - -def executeProgram(): - global register, insptr - while register[inspaddr] < len(instructs): - insptr = register[inspaddr] - ins = instructs[insptr] - - # execute command - if len(register) <= ins[3]: - register += [0 for x in range(ins[3] - len(register) + 1)] - register[ins[3]] = opmap[ins[0]](ins[1], ins[2]) - - # part 1 - #if insptr == 13 and register[4] == 1: - # print(register) - # return - - # increment instruction pointer - register[inspaddr] += 1 - -### SETUP - - -### PROGRAM CODE - - -def solve1(): - r0 = 1797184 # (first opportunity for comparison r1 and r0) - - #disassemble(0, len(instructs)) - #executeProgram() - - print(r0) - return - -def solve2(): - r1 = 0 - possibles = list() - while True: - r4 = r1 | 65536 # flip 9th bit - r1 = 3798839 - while True: # scan bytes of r4 and add them to r1 and multiply - r5 = r4 & 255 - r1 += r5 - r1 = r1 & 16777215 - r1 *= 65899 # equals 1 00000001 01101011 - r1 = r1 & 16777215 - 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() diff --git a/src/22/solve.py b/src/22/solve.py @@ -1,108 +0,0 @@ -# second part was solved with help from subreddit - -from sys import argv as args -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 -torch, gear, neither = 0, 1, 2 - -tooloptions = dict() -tooloptions[rocky] = (torch, gear) -tooloptions[wet] = (gear, neither) -tooloptions[narrow] = (torch, neither) - -# parse input file -def parseInput(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): - return (n + depth) % 20183 - -# generate map of erosion types -def genMap(): - 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])] - - # generate values on y side - for y in range(mrange[1]): - grid[y][0] = getErosionLevel(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]) - - # mod 3 for env type - grid = [[grid[y][x] % 3 for x in range(mrange[0])] for y in range(mrange[1])] - - # start position is rocky - grid[target[1]][target[0]] = 0 - - return grid - -# define constants from input file -depth, target = parseInput(sinput) -mrange = (target[0] + 100, target[1] + 100) # 100 block padding for potential hook-paths - -vmap = genMap() - -# risk level of area is sum of risk levels -def getRiskLevel(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): - 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 - 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 - -def solve1(): - print(getRiskLevel(target[0], target[1])) - -def solve2(): - print(dijkstra()) - -def main(): - if len(args) > 1: - if args[1] == "1": - solve1() - elif args[1] == "2": - solve2() - -main() diff --git a/src/23/solve.py b/src/23/solve.py @@ -1,116 +0,0 @@ -# 2nd part solved with the help of subreddit - -from sys import argv as args -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): - 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] - -# manhattan distance -def dist(p1, p2): - xd = abs(p1[0] - p2[0]) - yd = abs(p1[1] - p2[1]) - zd = abs(p1[2] - p2[2]) - return xd + yd + zd - -# two nanobots range overlap -def isoverlap(nb1, nb2): - return nb1[1] + nb2[1] >= dist(nb1[0], nb2[0]) - -# nanobots range completely inside anothers range -def isinside(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): - 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)] - md = max(ds) - if md == 0: - return True - 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(): - 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) - -def solve2(): - 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] - minpz = min(nanobots, key = lambda x : x[0][2])[0][2] - minp = (minpx, minpy, minpz) - - maxpx = max(nanobots, key = lambda x : x[0][0])[0][0] - maxpy = max(nanobots, key = lambda x : x[0][1])[0][1] - maxpz = max(nanobots, key = lambda x : x[0][2])[0][2] - maxp = (maxpx, maxpy, maxpz) - - gridsize = max([maxp[i] - minp[i] for i in range(3)]) # largest dif dim to ensure all nanbots are in the grid - - bestpos = None - while gridsize >= 1: - maxintile = 0 - - # traverse grid in steps of gridsize - xsteps = math.ceil((maxp[0] - minp[0]) / gridsize) + 1 - ysteps = math.ceil((maxp[1] - minp[1]) / gridsize) + 1 - zsteps = math.ceil((maxp[2] - minp[2]) / gridsize) + 1 - for nx in range(xsteps): - for ny in range(ysteps): - for nz in range(zsteps): - x = minp[0] + nx * gridsize - y = minp[1] + ny * gridsize - 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 - 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 - 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() - -main() diff --git a/src/24/notes.txt b/src/24/notes.txt @@ -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/24/solve.py b/src/24/solve.py @@ -1,129 +0,0 @@ -from sys import argv as args - -sinput = open("input.txt").read() - -immunesys = 0 -infection = 1 -ctype = 0 - -# parse input from file -def parseInput(): - groups = list() - for l in sinput.split("\n"): - pl = parseLine(l) - if pl != None: - groups.append(pl) - return groups - -# parse line of input -def parseLine(line): - global ctype - group = None - if "Immune" in line: - ctype = immunesys - elif "Infection" in line: - ctype = infection - elif line != "": - ls = line.split() - group = dict() - group["type"] = ctype - group["units"] = int(ls[0]) - group["unithp"] = int(ls[4]) - group["initiative"] = int(ls[-1]) - group["weak"] = list() - group["immune"] = list() - if "(" in line: - parenthstr = line.split("(")[1].split(")")[0] - traits = parenthstr.split(";") - for traitstr in traits: - info = traitstr.split() - group[info[0]] = [v.replace(",","") for v in info[2:]] - dmginfo = line.split("does")[1].split("damage")[0].split() - group["dmg"] = int(dmginfo[0]) - group["dmgtype"] = dmginfo[1] - return group - -def getEffectivePower(g): - return g["units"] * g["dmg"] - -def getDamage(attacker, defender): - dmg = getEffectivePower(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() - -def fight(): - global groups - - lunits = 0 - - immalive = len([g for g in groups if g["type"] == immunesys]) - infalive = len([g for g in groups if g["type"] == infection]) - - while immalive > 0 and infalive > 0: - # target selection - attacked = list() - attackpairs = list() - groups = sorted(groups, key = lambda x : (getEffectivePower(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 - attacked.append(target) - attackpairs.append((groups.index(group), groups.index(target))) - - # attacking phase - attackpairs = sorted(attackpairs, key = lambda x : groups[x[0]]["initiative"], reverse = True) - - 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 - - groups = [g for g in groups if g["units"] > 0] - immalive = sum([g["units"] for g in groups if g["type"] == immunesys]) - infalive = sum([g["units"] for g in groups if g["type"] == infection]) - units = immalive + infalive - if units == lunits: - return units - lunits = units - return units - -def solve1(): - print(fight()) - -def solve2(): - global groups - - immunewin = False - boost = 1 - while not immunewin: - groups = parseInput() - for g in groups: - if g["type"] == immunesys: - g["dmg"] += boost - - fight() - - immunewin = (sum([0 if g["type"] == immunesys else 1 for g in groups]) == 0) - - boost += 1 - - #print("boost:", boost) - print("units:", sum([v["units"] for v in groups])) - -def main(): - if len(args) > 1: - if args[1] == "1": - solve1() - elif args[1] == "2": - solve2() - -main() diff --git a/src/25/solve.py b/src/25/solve.py @@ -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/3/solve.py b/src/3/solve.py @@ -1,74 +0,0 @@ -from sys import argv as args - -file = open("input.txt") -data = [x for x in file.readlines()] -file.close() - -#data = "#1 @ 1,3: 4x4","#2 @ 3,1: 4x4","#3 @ 5,5: 2x2" - -def parserect(l): - split = l.split("@") - id = int(split[0].replace("#","")) - split = split[1].split(":") - pos = [int(x) for x in split[0].split(",")] - size = [int(x) for x in split[1].split("x")] - return pos, size, id - -def createMap(): - global rectdata - rectdata = [parserect(l) for l in data] - msize = list([0,0]) - for i in range(len(rectdata)): - r = rectdata[i] - xm = r[0][0] + r[1][0] - ym = r[0][1] + r[1][1] - if i == 0 or xm > msize[0]: - msize[0] = xm - if i == 0 or ym > msize[1]: - msize[1] = ym - - map = [[list() for y in range(msize[1])] for x in range(msize[0])] - for r in rectdata: - sx = r[0][0] - sy = r[0][1] - for x in range(sx, sx + r[1][0]): - for y in range(sy, sy + r[1][1]): - map[x][y].append(r[2]) - - return map - -def solve1(): # answer: 114946 - map = createMap() - - overlap = 0 - for x in range(len(map)): - for y in range(len(map[0])): - if len(map[x][y]) > 1: - overlap += 1 - - print(overlap) - -def solve2(): # answer: 877 - map = createMap() - - overlap = set() - for x in range(len(map)): - for y in range(len(map[0])): - if len(map[x][y]) > 1: - 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() - -main() diff --git a/src/4/solve.py b/src/4/solve.py @@ -1,109 +0,0 @@ -from sys import argv as args - -file = open("input.txt") -data = [x for x in file.readlines()] -file.close() - -def parse_entry(l): - split = l.split(" ") - date = " ".join(split[:2]) - time = int(split[1].split(":")[1].replace("]","")) - if split[2] == "Guard": - awake = None - id = int(split[3].replace("#","")) - else: - id = 0 - awake = (True if split[2] == "wakes" else False) - return time, id, awake, date - -class guard: - def __init__(self, _id): - self.shifts = list() - self.id = _id - self.awake = None - -def gen_shiftmap(): - shiftdata = [parse_entry(l) for l in data] - shiftdata = sorted(shiftdata, key=lambda x: x[3]) #sort by date - - shiftmap = dict() - ltime = shiftdata[0][0] - cgid = shiftdata[0][1] - for i in range(len(shiftdata)): - entry = shiftdata[i] - ctime = entry[0] - gid = entry[1] - cawake = entry[2] - - if gid != 0: # new shift - 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] - if cawake: - if not g.awake: - shiftmap[cgid].shifts.append((ltime, ctime - ltime)) - else: - ltime = ctime - g.awake = cawake - - return shiftmap - -def solve1(): - shiftmap = gen_shiftmap() - - maxsleep = None - mg = None - for g in shiftmap.values(): - minslept = 0 - for t in g.shifts: - minslept += t[1] - if not maxsleep or minslept > maxsleep: - maxsleep = minslept - mg = g - - - timel = [0 for x in range(60)] - - for t in mg.shifts: - for i in range(t[0], t[0] + t[1]): - timel[(i-1)%60] += 1 - - minute = timel.index(max(timel))+1 - print(minute * mg.id) - -def solve2(): - shiftmap = gen_shiftmap() - timetables = dict() - - for g in shiftmap.values(): - timetables[g.id] = [0 for x in range(60)] - for t in g.shifts: - 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() diff --git a/src/5/solve.py b/src/5/solve.py @@ -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 @@ -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 @@ -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 @@ -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() diff --git a/src/9/solve.py b/src/9/solve.py @@ -1,48 +0,0 @@ -from collections import deque -from sys import argv as args - -words = open("input.txt").read().split(" ") -playercount = int(words[0]) -lastworth = int(words[6]) - -def getHighScore(playercount, lastworth): #optimized with deque - lastworth = lastworth - lastworth % 23 - - players = [0 for x in range(playercount)] - marbles = deque([0]) - pos = 0 - for i in range(1, lastworth+1): - if i % 23 == 0: - cp = (i-1) % playercount - players[cp] += i + marbles[(len(marbles) + pos - 7) % len(marbles)] - marbles.rotate((len(marbles) - 1 - pos) + 7) - marbles.pop() - pos = 0 - else: - if i < 3: - pos = 1 - marbles.rotate(1) - marbles.append(i) - else: - marbles.rotate((len(marbles)- 1 -pos) - 1) - marbles.append(i) - pos = len(marbles)-1 - #print(pos,marbles) - - print(max(players)) - - -def solve1(): - getHighScore(playercount, lastworth) - -def solve2(): - getHighScore(playercount, lastworth * 100) - -def main(): - if len(args) > 1: - if args[1] == "1": - solve1() - elif args[1] == "2": - solve2() - -main()