diff options
Diffstat (limited to 'scratch/advent-of-code-2019')
| -rw-r--r-- | scratch/advent-of-code-2019/README.md | 4 | ||||
| -rw-r--r-- | scratch/advent-of-code-2019/day_1.py | 119 | ||||
| -rw-r--r-- | scratch/advent-of-code-2019/day_2.py | 32 | ||||
| -rw-r--r-- | scratch/advent-of-code-2019/day_3.py | 137 | ||||
| -rw-r--r-- | scratch/advent-of-code-2019/day_4.py | 35 | ||||
| -rw-r--r-- | scratch/advent-of-code-2019/day_5.py | 170 | ||||
| -rw-r--r-- | scratch/advent-of-code-2019/day_6.py | 155 | ||||
| -rw-r--r-- | scratch/advent-of-code-2019/day_7.py | 49 |
8 files changed, 701 insertions, 0 deletions
diff --git a/scratch/advent-of-code-2019/README.md b/scratch/advent-of-code-2019/README.md new file mode 100644 index 000000000000..e7c105a7f60f --- /dev/null +++ b/scratch/advent-of-code-2019/README.md @@ -0,0 +1,4 @@ +# 2019 Advent of Code + +Here are my attempts at the 2019 Advent of Code challenge before my dedication +to the effort plummeted. diff --git a/scratch/advent-of-code-2019/day_1.py b/scratch/advent-of-code-2019/day_1.py new file mode 100644 index 000000000000..bd4024e3ec7d --- /dev/null +++ b/scratch/advent-of-code-2019/day_1.py @@ -0,0 +1,119 @@ +from math import floor + +xs = [ + 102473, + 84495, + 98490, + 68860, + 62204, + 72810, + 65185, + 145951, + 77892, + 108861, + 70764, + 67286, + 74002, + 80773, + 52442, + 131505, + 107162, + 126993, + 59784, + 64231, + 91564, + 68585, + 98735, + 69020, + 77332, + 60445, + 65826, + 111506, + 95431, + 146687, + 135119, + 86804, + 95915, + 85434, + 111303, + 148127, + 132921, + 136213, + 89004, + 143137, + 144853, + 143017, + 104386, + 100612, + 54760, + 63813, + 144191, + 84481, + 69718, + 84936, + 98621, + 124993, + 92736, + 60369, + 137284, + 101902, + 112726, + 51784, + 126496, + 85005, + 101661, + 137278, + 136637, + 90340, + 100209, + 53683, + 50222, + 132060, + 98797, + 139054, + 135638, + 100632, + 137849, + 125333, + 103981, + 76954, + 134352, + 74229, + 93402, + 62552, + 50286, + 57066, + 98439, + 120708, + 117827, + 107884, + 72837, + 148663, + 125645, + 61460, + 120555, + 142473, + 106668, + 58612, + 58576, + 143366, + 90058, + 121087, + 89546, + 126161, +] + + +def fuel_for_mass(x): + """Return the amount of fuel (in mass) required for a mass of X. The total + amount of fuel includes the amount of fuel required for the fuel itself, + since fuel also has a mass weights.""" + mass_fuel = floor(x / 3) - 2 + if mass_fuel < 0: + return 0 + else: + fuel_fuel = fuel_for_mass(mass_fuel) + return mass_fuel + fuel_fuel + + +print(sum(fuel_for_mass(x) for x in xs)) diff --git a/scratch/advent-of-code-2019/day_2.py b/scratch/advent-of-code-2019/day_2.py new file mode 100644 index 000000000000..77774c1bb5ad --- /dev/null +++ b/scratch/advent-of-code-2019/day_2.py @@ -0,0 +1,32 @@ +from itertools import product + +x = [ + 1, 0, 0, 3, 1, 1, 2, 3, 1, 3, 4, 3, 1, 5, 0, 3, 2, 1, 10, 19, 1, 6, 19, 23, + 2, 23, 6, 27, 2, 6, 27, 31, 2, 13, 31, 35, 1, 10, 35, 39, 2, 39, 13, 43, 1, + 43, 13, 47, 1, 6, 47, 51, 1, 10, 51, 55, 2, 55, 6, 59, 1, 5, 59, 63, 2, 9, + 63, 67, 1, 6, 67, 71, 2, 9, 71, 75, 1, 6, 75, 79, 2, 79, 13, 83, 1, 83, 10, + 87, 1, 13, 87, 91, 1, 91, 10, 95, 2, 9, 95, 99, 1, 5, 99, 103, 2, 10, 103, + 107, 1, 107, 2, 111, 1, 111, 5, 0, 99, 2, 14, 0, 0 +] + + +def interpret(i, x): + op, a, b, out = x[i + 0], x[i + 1], x[i + 2], x[i + 3] + if op == 1: + x[out] = x[a] + x[b] + return interpret(i + 4, x) + elif op == 2: + x[out] = x[a] * x[b] + return interpret(i + 4, x) + elif op == 99: + return x + else: + raise Exception('Unsupported opcode: {}. {}, {}'.format(op, a, b)) + + +for a, b in product(range(100), range(100)): + y = x[:] + y[1] = a + y[2] = b + if interpret(0, y)[0] == 19690720: + print(100 * a + b) diff --git a/scratch/advent-of-code-2019/day_3.py b/scratch/advent-of-code-2019/day_3.py new file mode 100644 index 000000000000..6dd863528c1c --- /dev/null +++ b/scratch/advent-of-code-2019/day_3.py @@ -0,0 +1,137 @@ +from math import floor +from heapq import heappush, heappop + +xs = [ + "R1009", "U993", "L383", "D725", "R163", "D312", "R339", "U650", "R558", + "U384", "R329", "D61", "L172", "D555", "R160", "D972", "L550", "D801", + "L965", "U818", "L123", "D530", "R176", "D353", "L25", "U694", "L339", + "U600", "L681", "D37", "R149", "D742", "R762", "U869", "R826", "U300", + "L949", "U978", "L303", "U361", "R136", "D343", "L909", "U551", "R745", + "U913", "L566", "D292", "R820", "U886", "R205", "D431", "L93", "D71", + "R577", "U872", "L705", "U510", "L698", "U963", "R607", "U527", "L669", + "D543", "R690", "U954", "L929", "D218", "R490", "U500", "L589", "D332", + "R949", "D538", "R696", "U659", "L188", "U468", "L939", "U833", "L445", + "D430", "R78", "D303", "R130", "D649", "R849", "D712", "L511", "U745", + "R51", "U973", "R799", "U829", "R605", "D771", "L837", "U204", "L414", + "D427", "R538", "U116", "R540", "D168", "R493", "U900", "L679", "U431", + "L521", "D500", "L428", "U332", "L954", "U717", "L853", "D339", "L88", + "U807", "L607", "D496", "L163", "U468", "L25", "U267", "L759", "D898", + "L591", "U445", "L469", "U531", "R596", "D486", "L728", "D677", "R350", + "D429", "R39", "U568", "R92", "D875", "L835", "D841", "R877", "U178", + "L221", "U88", "R592", "U692", "R455", "U693", "L419", "U90", "R609", + "U672", "L293", "U168", "R175", "D456", "R319", "D570", "R504", "D165", + "L232", "D624", "L604", "D68", "R807", "D59", "R320", "D281", "L371", + "U956", "L788", "D897", "L231", "D829", "R287", "D798", "L443", "U194", + "R513", "D925", "L232", "U225", "L919", "U563", "R448", "D889", "R661", + "U852", "L950", "D558", "L269", "U186", "L625", "U673", "L995", "U732", + "R435", "U849", "L413", "D690", "L158", "D234", "R361", "D458", "L271", + "U90", "L781", "U754", "R256", "U162", "L842", "U927", "L144", "D62", + "R928", "D238", "R473", "U97", "L745", "U303", "L487", "D349", "L520", + "D31", "L825", "U385", "L133", "D948", "L39", "U62", "R801", "D664", + "L333", "U134", "R692", "U385", "L658", "U202", "L279", "D374", "R489", + "D686", "L182", "U222", "R733", "U177", "R94", "D603", "L376", "U901", + "R216", "D851", "L155", "D214", "L460", "U758", "R121", "D746", "L180", + "U175", "L943", "U146", "L166", "D251", "L238", "U168", "L642", "D341", + "R281", "U182", "R539", "D416", "R553", "D67", "L748", "U272", "R257", + "D869", "L340", "U180", "R791", "U138", "L755", "D976", "R731", "U713", + "R602", "D284", "L258", "U176", "R509", "U46", "R935", "U576", "R96", + "U89", "L913", "U703", "R833" +] +ys = [ + "L1006", "D998", "R94", "D841", "R911", "D381", "R532", "U836", "L299", + "U237", "R781", "D597", "L399", "D800", "L775", "D405", "L485", "U636", + "R589", "D942", "L878", "D779", "L751", "U711", "L973", "U410", "L151", + "U15", "L685", "U417", "L106", "D648", "L105", "D461", "R448", "D743", + "L589", "D430", "R883", "U37", "R155", "U350", "L421", "U23", "R337", + "U816", "R384", "D671", "R615", "D410", "L910", "U914", "L579", "U385", + "R916", "U13", "R268", "D519", "R289", "U410", "L389", "D885", "L894", + "U734", "L474", "U707", "L72", "U155", "L237", "U760", "L127", "U806", + "L15", "U381", "L557", "D727", "L569", "U320", "L985", "D452", "L8", + "D884", "R356", "U732", "L672", "D458", "L485", "U402", "L238", "D30", + "R644", "U125", "R753", "U183", "L773", "U487", "R849", "U210", "L164", + "D808", "L595", "D668", "L340", "U785", "R313", "D72", "L76", "D263", + "R689", "U604", "R471", "U688", "R462", "D915", "R106", "D335", "R869", + "U499", "R190", "D916", "R468", "D882", "R56", "D858", "L143", "D741", + "L386", "U856", "R50", "U853", "R151", "D114", "L773", "U854", "L290", + "D344", "L23", "U796", "L531", "D932", "R314", "U960", "R643", "D303", + "L661", "D493", "L82", "D491", "L722", "U848", "L686", "U4", "L985", + "D509", "L135", "D452", "R500", "U105", "L326", "D101", "R222", "D944", + "L645", "D362", "L628", "U305", "L965", "U356", "L358", "D137", "R787", + "U728", "R967", "U404", "R18", "D928", "L695", "D965", "R281", "D597", + "L791", "U731", "R746", "U163", "L780", "U41", "L255", "U81", "L530", + "D964", "R921", "D297", "R475", "U663", "L226", "U623", "L984", "U943", + "L143", "U201", "R926", "U572", "R343", "U839", "R764", "U751", "R128", + "U939", "R987", "D108", "R474", "U599", "R412", "D248", "R125", "U797", + "L91", "D761", "L840", "U290", "L281", "U779", "R650", "D797", "R185", + "D320", "L25", "U378", "L696", "U332", "R75", "D620", "L213", "D667", + "R558", "U267", "L846", "U306", "R939", "D220", "R311", "U827", "R345", + "U534", "R56", "D679", "R48", "D845", "R898", "U8", "R862", "D960", "R753", + "U319", "L886", "D795", "R805", "D265", "R876", "U729", "R894", "D368", + "R858", "U744", "R506", "D327", "L903", "U919", "L721", "U507", "L463", + "U753", "R775", "D719", "R315", "U128", "R17", "D376", "R999", "D386", + "L259", "U181", "L162", "U605", "L265", "D430", "R35", "D968", "R207", + "U466", "R796", "D667", "R93", "U749", "L315", "D410", "R312", "U929", + "L923", "U260", "R638" +] + + +def to_coords(xs): + row, col = 0, 0 + coords = [] + for x in xs: + d, amt = x[0], int(x[1:]) + if d == 'U': + for i in range(1, amt + 1): + coords.append((row + i, col)) + row += amt + elif d == 'D': + for i in range(1, amt + 1): + coords.append((row - i, col)) + row -= amt + elif d == 'L': + for i in range(1, amt + 1): + coords.append((row, col - i)) + col -= amt + elif d == 'R': + for i in range(1, amt + 1): + coords.append((row, col + i)) + col += i + return coords + + +def contains(row, col, d): + if row not in d: + return False + return col in d[row] + + +def intersections(xs, ys): + d = {} + ints = set() + for row, col in to_coords(xs): + if row in d: + d[row].add(col) + else: + d[row] = {col} + for row, col in to_coords(ys): + if contains(row, col, d): + ints.add((row, col)) + return ints + + +def trace_to(coord, xs): + count = 0 + for coord_x in to_coords(xs): + count += 1 + if coord_x == coord: + return count + raise Exception("Intersection doesn't exist") + + +answer = [] +for coord in intersections(xs, ys): + x = trace_to(coord, xs) + y = trace_to(coord, ys) + heappush(answer, x + y) + +print(heappop(answer)) diff --git a/scratch/advent-of-code-2019/day_4.py b/scratch/advent-of-code-2019/day_4.py new file mode 100644 index 000000000000..adef73b452dc --- /dev/null +++ b/scratch/advent-of-code-2019/day_4.py @@ -0,0 +1,35 @@ +import re + +start = 134792 +end = 675810 + + +def satisfies(x): + x = str(x) + result = False + double, not_decreasing = False, False + + # double and *only* double exists + for i in range(len(x) - 1): + # double and left-of-a is BOL or !x + # and right-of-b is EOL or !x + a, b = x[i], x[i + 1] + bol = i - 1 < 0 + eol = i + 2 >= len(x) + if a == b and (bol or x[i - 1] != a) and (eol or x[i + 2] != a): + double = True + break + + # not_decreasing + prev = int(x[0]) + for a in x[1:]: + a = int(a) + if prev > a: + return False + prev = a + not_decreasing = True + + return double and not_decreasing + + +print(len([x for x in range(start, end + 1) if satisfies(x)])) diff --git a/scratch/advent-of-code-2019/day_5.py b/scratch/advent-of-code-2019/day_5.py new file mode 100644 index 000000000000..3d82846e6126 --- /dev/null +++ b/scratch/advent-of-code-2019/day_5.py @@ -0,0 +1,170 @@ +x = [ + 3, 225, 1, 225, 6, 6, 1100, 1, 238, 225, 104, 0, 1102, 31, 68, 225, 1001, + 13, 87, 224, 1001, 224, -118, 224, 4, 224, 102, 8, 223, 223, 1001, 224, 7, + 224, 1, 223, 224, 223, 1, 174, 110, 224, 1001, 224, -46, 224, 4, 224, 102, + 8, 223, 223, 101, 2, 224, 224, 1, 223, 224, 223, 1101, 13, 60, 224, 101, + -73, 224, 224, 4, 224, 102, 8, 223, 223, 101, 6, 224, 224, 1, 224, 223, + 223, 1101, 87, 72, 225, 101, 47, 84, 224, 101, -119, 224, 224, 4, 224, + 1002, 223, 8, 223, 1001, 224, 6, 224, 1, 223, 224, 223, 1101, 76, 31, 225, + 1102, 60, 43, 225, 1102, 45, 31, 225, 1102, 63, 9, 225, 2, 170, 122, 224, + 1001, 224, -486, 224, 4, 224, 102, 8, 223, 223, 101, 2, 224, 224, 1, 223, + 224, 223, 1102, 29, 17, 224, 101, -493, 224, 224, 4, 224, 102, 8, 223, 223, + 101, 1, 224, 224, 1, 223, 224, 223, 1102, 52, 54, 225, 1102, 27, 15, 225, + 102, 26, 113, 224, 1001, 224, -1560, 224, 4, 224, 102, 8, 223, 223, 101, 7, + 224, 224, 1, 223, 224, 223, 1002, 117, 81, 224, 101, -3645, 224, 224, 4, + 224, 1002, 223, 8, 223, 101, 6, 224, 224, 1, 223, 224, 223, 4, 223, 99, 0, + 0, 0, 677, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1105, 0, 99999, 1105, 227, 247, + 1105, 1, 99999, 1005, 227, 99999, 1005, 0, 256, 1105, 1, 99999, 1106, 227, + 99999, 1106, 0, 265, 1105, 1, 99999, 1006, 0, 99999, 1006, 227, 274, 1105, + 1, 99999, 1105, 1, 280, 1105, 1, 99999, 1, 225, 225, 225, 1101, 294, 0, 0, + 105, 1, 0, 1105, 1, 99999, 1106, 0, 300, 1105, 1, 99999, 1, 225, 225, 225, + 1101, 314, 0, 0, 106, 0, 0, 1105, 1, 99999, 8, 226, 677, 224, 102, 2, 223, + 223, 1005, 224, 329, 1001, 223, 1, 223, 1108, 677, 226, 224, 102, 2, 223, + 223, 1006, 224, 344, 101, 1, 223, 223, 108, 677, 226, 224, 102, 2, 223, + 223, 1006, 224, 359, 101, 1, 223, 223, 7, 677, 226, 224, 102, 2, 223, 223, + 1005, 224, 374, 101, 1, 223, 223, 1007, 226, 677, 224, 102, 2, 223, 223, + 1005, 224, 389, 101, 1, 223, 223, 8, 677, 677, 224, 102, 2, 223, 223, 1006, + 224, 404, 1001, 223, 1, 223, 1007, 677, 677, 224, 1002, 223, 2, 223, 1006, + 224, 419, 101, 1, 223, 223, 1108, 677, 677, 224, 1002, 223, 2, 223, 1005, + 224, 434, 1001, 223, 1, 223, 1107, 226, 677, 224, 102, 2, 223, 223, 1005, + 224, 449, 101, 1, 223, 223, 107, 226, 226, 224, 102, 2, 223, 223, 1006, + 224, 464, 101, 1, 223, 223, 1108, 226, 677, 224, 1002, 223, 2, 223, 1005, + 224, 479, 1001, 223, 1, 223, 7, 677, 677, 224, 102, 2, 223, 223, 1006, 224, + 494, 1001, 223, 1, 223, 1107, 677, 226, 224, 102, 2, 223, 223, 1005, 224, + 509, 101, 1, 223, 223, 107, 677, 677, 224, 1002, 223, 2, 223, 1006, 224, + 524, 101, 1, 223, 223, 1008, 677, 677, 224, 1002, 223, 2, 223, 1006, 224, + 539, 101, 1, 223, 223, 7, 226, 677, 224, 1002, 223, 2, 223, 1005, 224, 554, + 101, 1, 223, 223, 108, 226, 226, 224, 1002, 223, 2, 223, 1006, 224, 569, + 101, 1, 223, 223, 1008, 226, 677, 224, 102, 2, 223, 223, 1005, 224, 584, + 101, 1, 223, 223, 8, 677, 226, 224, 1002, 223, 2, 223, 1005, 224, 599, 101, + 1, 223, 223, 1007, 226, 226, 224, 1002, 223, 2, 223, 1005, 224, 614, 101, + 1, 223, 223, 1107, 226, 226, 224, 1002, 223, 2, 223, 1006, 224, 629, 101, + 1, 223, 223, 107, 677, 226, 224, 1002, 223, 2, 223, 1005, 224, 644, 1001, + 223, 1, 223, 1008, 226, 226, 224, 1002, 223, 2, 223, 1006, 224, 659, 101, + 1, 223, 223, 108, 677, 677, 224, 1002, 223, 2, 223, 1005, 224, 674, 1001, + 223, 1, 223, 4, 223, 99, 226 +] + +# Interpretter spec: +# Op-code width: 2 +# ABCDE +# A: Mode of 3rd parameter +# B: Mode of 2rd parameter +# C: Mode of 1st parameter +# DE: 2-digit op-code +# +# Not every op-code has the same arity. +# +# Parameter modes: +# - positional: index of memory. 0 +# - immediate: raw value. 1 +# Assert that you never attempt to write to an "immediate value" + +# Parameter modes +POS = '0' # positional parameter mode +VAL = '1' # immediate parameter mode + + +# Pasted from day-2.py +# interpretter :: Int -> [Int] -> [Int] -> IO () +def interpret(i, x, argv=[], outs=[]): + """Values in `argv` will be applied to any `input` fields.""" + # The widest op-code we'll see is 3 + 2 = 5 for either addition or + # multiplication since each of those is a 3-arity function with a two-digit + # op-code. + instruction = '{:05d}'.format(x[i]) + op = instruction[-2:] + + if op == '01': + a, b, out = x[i + 1], x[i + 2], x[i + 3] + mode_a, mode_b, mode_out = instruction[2], instruction[1], instruction[ + 0] + a = a if mode_a == VAL else x[a] + b = b if mode_b == VAL else x[b] + assert mode_out == POS + x[out] = a + b + return interpret(i + 4, x, argv=argv, outs=outs) + elif op == '02': + a, b, out = x[i + 1], x[i + 2], x[i + 3] + mode_a, mode_b, mode_out = instruction[2], instruction[1], instruction[ + 0] + a = a if mode_a == VAL else x[a] + b = b if mode_b == VAL else x[b] + assert mode_out == POS + x[out] = a * b + return interpret(i + 4, x, argv=argv, outs=outs) + # input + elif op == '03': + a = x[i + 1] + mode_a = instruction[2] + assert mode_a == POS + # What's the pythonic way to defensively get this value? + if len(argv) and argv[0] is not None: + x[a] = argv[0] + return interpret(i + 2, x, argv=argv[1:], outs=outs) + elif len(outs) and outs[-1] is not None: + x[a] = outs[-1] + return interpret(i + 2, x, argv=argv, outs=outs) + else: + # Here we want to block until the user applies input. This could be + # done easily with message passing for something similar. + x[a] = int(input('Enter: ')) + return interpret(i + 2, x, argv=argv) + # output + elif op == '04': + a = x[i + 1] + mode_a = instruction[2] + a = a if mode_a == VAL else x[a] + outs.append(a) + return interpret(i + 2, x, argv=argv, outs=outs) + # jump-if-true + elif op == '05': + a, b = x[i + 1], x[i + 2] + mode_a, mode_b = instruction[2], instruction[1] + a = a if mode_a == VAL else x[a] + b = b if mode_b == VAL else x[b] + if a != 0: + return interpret(b, x, argv=argv, outs=outs) + else: + return interpret(i + 3, x, argv=argv, outs=outs) + # jump-if-false + elif op == '06': + a, b = x[i + 1], x[i + 2] + mode_a, mode_b = instruction[2], instruction[1] + a = a if mode_a == VAL else x[a] + b = b if mode_b == VAL else x[b] + if a == 0: + return interpret(b, x, argv=argv, outs=outs) + else: + return interpret(i + 3, x, argv=argv, outs=outs) + pass + # less than + elif op == '07': + a, b, out = x[i + 1], x[i + 2], x[i + 3] + mode_a, mode_b, mode_out = instruction[2], instruction[1], instruction[ + 0] + a = a if mode_a == VAL else x[a] + b = b if mode_b == VAL else x[b] + assert mode_out == POS + if a < b: + x[out] = 1 + else: + x[out] = 0 + return interpret(i + 4, x, argv=argv, outs=outs) + # equals + elif op == '08': + a, b, out = x[i + 1], x[i + 2], x[i + 3] + mode_a, mode_b, mode_out = instruction[2], instruction[1], instruction[ + 0] + a = a if mode_a == VAL else x[a] + b = b if mode_b == VAL else x[b] + assert mode_out == POS + if a == b: + x[out] = 1 + else: + x[out] = 0 + return interpret(i + 4, x, argv=argv, outs=outs) + elif op == '99': + return x[0] + else: + raise Exception('Unsupported opcode: {}.'.format(op)) diff --git a/scratch/advent-of-code-2019/day_6.py b/scratch/advent-of-code-2019/day_6.py new file mode 100644 index 000000000000..aba99b8239ff --- /dev/null +++ b/scratch/advent-of-code-2019/day_6.py @@ -0,0 +1,155 @@ +from graphviz import Digraph + +data = """6WF)DRK 2PT)PSM H42)FN8 1XR)LQD HRK)9KL TD6)H8W 98Z)BJM RCQ)LVG +RWQ)Q7H 2PS)X94 NHB)25X PXC)W57 L8L)MVX CFK)D8K R1B)43T PDY)QKX FQK)82K JJ6)MQJ +FB6)6V1 R28)5MZ BN2)5HN 6BQ)JVC W57)22C MQJ)DL2 MTC)84R RH8)CRN Y27)3GN CKQ)31C +R7V)9BK ZDY)PDY X2Q)Y6S Q8B)SAN 1Z3)PVT R87)57R KCJ)44X PWQ)9CB HLC)VYW HFP)9XS +X33)MC3 RYS)R7R JRF)VHW 79R)FXZ YQQ)STV 8J6)JWX Q6D)RV6 LL9)B4D 6R1)T1Z VK9)42M +PQP)17N K6C)HMK GLY)N47 KDW)CDC DQ4)RY5 SND)FDR 7YF)1VN MDT)B3S D3F)98Z 5VH)MR7 +KNR)2L8 CJW)QDL FWY)14X SJD)79R COM)BXW T2B)FPB B2Q)BRJ Z21)HYC VHW)5XR WZ4)2JM +8HF)342 PYR)X9Y RKF)P43 S1S)9WT 2PB)BSB QF7)M9T HML)HMC 7J9)7Q6 8F1)29K DH1)NDM +1YC)PXC P32)HR7 PMX)7Y9 STV)SLW NYY)NF1 TG9)998 DMB)DLW XGL)1Z3 GK8)WCS YHR)HQC +9Q5)B6D R2T)CM5 6KC)J5G ZM9)L8L J8T)F89 3LN)YOU T2T)Z8F SCY)FKG 9W4)195 QLM)DD7 +4QY)JCB WKM)3JF 693)YM8 61M)B6Y DSP)X2M YZ5)DPL BC9)3B1 BDB)JTG 3TJ)TW1 W5M)SF6 +K4Q)X56 5HT)YHX YJG)DM5 68N)X2Q 2YP)DS5 BLK)MY3 6WV)VZ4 2JQ)ZT8 G93)V2W WN1)SBD +SS7)DY9 X56)8HP JY1)VS4 XQ6)L94 98Z)DMC V6S)NWT D9L)Y44 V6G)GVS JDW)FZW FJT)S38 +L2Z)VPL 7ZX)DKK X2M)8WM YVZ)XWS HMK)P87 47M)TD6 TDZ)21T 19R)95B GD9)Q1L 9QX)DFR +Y64)XGN CRG)6VY V3L)61D RJ4)C9Z XXG)P53 VJ8)QTF CPQ)2M9 JRN)8V1 KMH)K94 DLW)VQ4 +91W)2QQ G4B)RWQ 4P1)MKS K6G)DZ7 WCS)JR9 LXM)7RY 6ZB)K6G HMC)622 Z21)BLK Q6N)48V +66S)MK4 PDK)6WV Y6S)GY1 2L8)ZMG 42W)ZN6 6MS)8TZ JBY)STQ NSF)3ZM 5CV)X9N K4V)WFL +J6R)DT8 N3N)CX4 PTD)YXT F74)4T5 C51)3FW KRW)DS1 NWT)CKQ 195)6G6 HVQ)S18 Q7H)BKM +SKN)4D4 GK2)MLX MVX)TG9 YPK)RHQ Y9F)Z8W 42M)WNL 84R)6JP KNC)NHF FZW)PGM 3FW)HGX +DBK)FB6 45T)HLT L11)JVN HB5)K6C QH5)888 BTJ)J55 8BT)8ZS FR1)XGL S87)PS9 C4K)BN2 +N2Q)18C KTF)ZM9 TN2)B2Q DF3)CFK 9T3)TMR P29)3P1 P1W)7SQ 4D4)1DJ LML)ZJ3 Q4L)RKF +MW2)79T LVG)CPQ BDC)JH5 DNZ)232 998)GTM YGS)4WH GY1)C51 J55)QBT B8Z)34W FJ2)H42 +58J)326 T1Z)DCJ 1ZH)GLV 1YC)JG6 14K)22B RY5)QRY 7V2)2WT 4GQ)XHV ZJ3)TQ8 2G8)SN3 +FPB)HMN SC4)57D 5LQ)R2T LXM)R8Z JQ6)G4B WNL)GK2 42M)P75 LM3)YPK ZN6)753 PN4)835 +C4H)JY1 LR4)VD5 PSM)P1W VWL)C6C G2V)WBC 85M)R24 B1V)QW7 175)2PM Y1V)1ZH 34W)3MJ +WN7)TTB 3PV)CQD N7Y)9T3 223)8D4 RV6)LJ9 HFP)JRF VMT)DNB GJP)D3F J5G)KMS 7Q6)ZW2 +YCB)JBY XGN)MNL 888)DSP X61)Q6N WT5)X12 SDN)FD1 2QC)54W V98)964 T7S)YVZ MLX)9VZ +FR8)QH5 TVQ)2PS 2PV)FHY F4S)MPT 3J9)JNB J6M)GDC Q4C)MJN 9VZ)BZK P2P)B69 WBC)M1W +D97)HPF JKB)9L4 593)6YJ RMB)4Q5 QZB)38C H12)6R1 MKY)DDD HGX)CRG P53)WY7 22B)GMM +44X)2D8 DT8)L7H 3Y2)D3S FB8)68N 3BC)1XR 4XF)TVQ VPL)R7V Z4V)JSK B3S)FW5 49Z)YQQ +99V)D13 54Q)SS7 CYC)TXH PQ3)78W X4M)G9H WFL)M99 ZYY)3Y2 12Y)PSW W38)P29 H8W)JJ6 +P66)VPH GK2)45T H5F)FJT JDJ)SNV 14F)96Q JG6)TQ4 2L6)52Q SCY)CBJ 3GN)KNC KLM)XPR +DH1)QZB DMB)X7G DPL)7SX D97)N3N GNS)T95 53P)GW2 BHR)HNB YHX)XQV 2CR)Y1V C9D)Z7P +FN8)2PT 6LF)FCQ JNL)LQR SPV)YCB HGX)N83 VS4)8BT 5RH)FTX HYC)X2J 69V)J6S 9XS)PN4 +SD7)5Q3 2RN)82D QRY)FFY K2Y)3X2 79Z)S2Z YN2)Y64 JKB)MDT KJ8)NDH N57)5VH 3XK)1Q1 +SCH)FJ6 17N)GMP QR4)7V2 GLV)GLY NHF)ZDY QDL)S14 QF1)BMC ZLF)DHN 3JF)7TR MKS)GCY +964)91R 9L4)L5G RRX)6ZB CD7)73M 3X2)PGC HNB)S9Z L94)KLM 8MQ)SCR 18C)3TJ M4Y)BTJ +BC9)5YR TV5)SCY 2NX)8CC C9Z)MTC B69)3QP HR7)CHJ 8ZS)JRN 31C)TJW D43)4NH 93Q)X9X +T95)DNZ LQ5)BC9 9T5)S2C RP8)DH1 GCY)SD7 Y44)9B5 VG5)ZYY 7RY)V3L PWV)Q4L NF1)7YF +DRK)Y8V D13)GYG TW1)2PB ZVZ)2VV BRJ)V2V 9CB)Y7B MK4)9CJ TMR)6XS HWF)GK8 QTF)S1S +DFW)6LF N3S)WN1 N2Q)MSW CZ5)X61 FXZ)C4H SCQ)MF7 9LY)3LN 5MZ)PMX CN9)WF9 FHY)PR8 +S38)NWH M29)G5S 4NH)GZJ 5YR)54H CLX)MNY TJD)HQL RRZ)4GQ YHB)CZ5 P37)93Q YJG)3Q3 +95B)QMF CMQ)BLZ QD9)45M JSK)R28 YCW)CLX 8K3)JGB N8M)PQW P75)1HL XBS)T2T 22C)PVW +689)6MS FFY)RWX YHL)2G8 Y8V)4P1 Y7B)62Z YKJ)JDJ 1HL)5LQ PZ3)B1C 52Q)7HB 3Q2)ZV7 +YBF)Z4V J95)SDH NM6)YBF 8YN)J3M J6S)KNR PVT)N4X SDH)RFW RFW)7Y1 JCB)52B 3MJ)H58 +4QF)XHZ F62)DFW 7LJ)KDW JHL)C9D B4D)Q8B 342)YGS PFR)ZQT Z9K)TNS 8F8)WLB 94N)DMB +QBT)RYS 3VR)KRR 8D4)ST6 X9N)2PV 632)8K3 MX5)XNP 57D)Y27 18D)PQP D3F)RJ4 PLS)PBL +1JP)YDC 79V)BG2 S14)2NX 4Q5)NCQ FTX)555 2PM)KMH HQC)RMB 9Z9)BNZ XHV)Y94 7ZP)YHR +BNZ)49Z W6D)LX6 SLS)JL3 PVW)P9W Z1L)HB5 DS5)G2V Z9Q)RV8 DFR)LPJ 836)693 K94)VWL +HRG)836 J3V)593 52N)LPK 9KL)Y7M LX6)F7D JL3)511 L4G)D97 1RH)Y9F NJ2)LML GW2)9WV +8KZ)NRC XQV)G6D R8Z)QF7 326)HML R7R)8PM 622)YCW WQY)LGS NF1)FF3 5LQ)QF1 5XR)PTD +V2V)PFR 9T5)JQ6 CBQ)8KZ VZ4)HVQ TJW)DQT 9WT)5M6 CFK)YHL JR9)1JP Y1K)CF4 8WS)JPY +VYC)1D6 GKK)7J9 JTG)RRX 6V1)F74 1H5)QR4 SN3)NMG MF7)GQ1 RYK)SCH BNZ)9LY 1DJ)9LP +L6W)5BK FCQ)BFL DCJ)3RD MXD)8MQ RWX)1RH NBF)WKM K6C)WNH H58)L6W Y7B)BJH PGC)NBF +96Q)Q2W F7D)BSN 223)Z9K K94)VYC X9X)7M3 Q1M)3J9 QXF)XQ6 DD7)3Q2 Q1L)NHB 79T)LXQ +8TZ)M29 21T)Q4C B1C)NSF 8D8)FJ2 LJH)HGJ QS2)PS1 5KX)Z2L C6C)6BQ VQ2)2YP P87)N8M +ST5)L4G 8SP)W5M T4H)69V 9WF)GHS FF3)SND C5G)GKK VQ2)X4M P43)8J6 TD6)384 66V)CN9 +CX4)T9T NCQ)2JQ 29K)K8K RY5)K4Q GQ3)T4H FNH)P32 3BC)PRQ 5HN)4QY M1W)BGT 84R)ST5 +S45)CJW CK4)W7G SGX)19R S2C)7ZX DHN)W5Y 8D9)HM2 BSB)SPV D8K)DFV JHL)2L6 KYP)12Y +KDN)6X7 Y44)SQZ 6G6)SJD N7D)QGF Q84)8WJ F89)LL9 LYJ)2RN 25X)Q84 HM3)53P JNB)QD9 +SLW)1DQ 384)3BC PR8)NGV 49N)7ZP 65H)LHJ 6XS)S45 ZMG)FR1 X2M)Y86 QD3)QLM P4R)PQ3 +RTK)4M3 4YW)N7D R7V)M4M 73M)CBF DFV)64R Z7P)LMK HRG)Y1K 3ZM)BCZ WY7)QXP DMC)9Q5 +PSW)1H5 8CC)TV5 TTB)S88 BZK)K2Y T2B)CBQ HJB)Y19 DQW)KML Z8W)8ZL PBL)5TK 1D6)MX5 +3MJ)4YW MDT)HJB 62Z)X33 DZ7)BDC 9CJ)FRD 82D)KDN LK7)18D 9QQ)61M Y34)DZG J4T)6KC +971)QD3 511)GQ3 MJN)F62 RNM)NKG BGW)KJ8 DL2)1YH ZQT)RYZ 1YH)ZJ6 2WT)YYQ 7HB)DYQ +3BN)WQY 2M9)62D TSK)YR1 N7Y)VJ8 WZ4)FWT MNY)YN2 DYQ)RRZ 3RG)YT3 2SM)VK9 JH5)ZXH +GYG)K2M PKF)V6G JGB)S87 X94)N57 MSW)L2Z X4N)25G BLZ)4QF JPY)GD9 WLB)V6S KML)2SM +TXH)9X1 48V)KTR 8PM)WZ4 ZW2)967 PS9)3BN 4WH)9T5 8M1)R6V N7M)VWK S88)978 N4X)8KH +6VY)PLS NRC)874 QGF)QWJ NMG)J3V B8Z)WPF 45M)2QC KDW)VQ2 FZW)223 BXW)QXF FRD)PWV +8HP)4G7 KDN)YYL LHJ)SDN P6P)XMC W5Y)RYK HX8)KW3 Z2L)H12 WPF)T2B L7H)BGW MNL)17B +GHS)66V QKX)XWV FW5)W38 PDK)Y34 FKG)Q6D DQT)YJG 15G)79V 4VK)51Y BJH)LR4 48V)6GC +DM5)Y1F CM5)VG5 KB8)HRK 5HN)RCQ 6JP)SDQ LGH)NJ2 L94)N7Y 4Y2)ZLF 25G)C4K K8K)SLS +232)ZVZ GQ1)58J RV8)H5F 78W)565 YCF)8D9 DZG)99V N83)CKR TN2)ZCX NGV)8SP BSN)FTN +LPJ)94N 3Q3)Q1M JVX)971 54W)LGH 67Y)P66 R24)P37 3QP)QTY YHR)FLT GMP)NM6 NDH)632 +PWV)8D8 LMK)3PV ZWJ)KB8 967)4VK 3B1)WN7 XWS)5CV YR1)FNH 565)4PH 5BK)V98 W5Y)FR8 +PS1)HX8 38C)XXG XWV)1YC M4M)LQ5 S9Z)49N XMC)R1B YYL)VC9 GMM)SCQ LXQ)J95 51Y)RP8 +HLT)XBS 82K)B8Z NR5)7K3 K2M)67Y SF6)W6D CF4)85M MC3)LXM HMN)RNM BFL)4XF MT2)PM4 +VWK)JKB 3JF)ZTZ QWJ)9QQ KRR)TJD VYW)Z9Q CK4)QS2 8NQ)NR5 57R)BHR 8WM)YHB Y86)GNS +2Y2)Z21 X12)9QX LJ9)YKJ 3RD)8F1 7SQ)CK4 ZXH)3XK DDD)5KX ZCX)PYR GZJ)KXL KC5)52N +PM4)RYP 14X)ZWJ FJ6)175 17B)689 HQL)14F LQR)DBK LGS)4Y2 2QQ)SGR 2VV)8F8 J6S)LM3 +RTP)YZ5 XDD)14K VQ4)MT2 KMH)KYC CKR)RTP VD5)MRM CM5)KRW BG3)XDD PGM)J4T MY3)JVX +Z8F)WNP BKM)WT5 FLT)KTF N7D)8M1 Y19)CMQ HPF)WDL 65H)JJP 2MQ)66S 4Q5)54Q Q2W)ZL4 +QTY)659 MRM)9Z9 X2J)SC4 YWH)RB3 FTN)LYJ LMK)N7M SGX)15G KW3)FQK 3VV)JNL JWX)R8R +9Z3)9MB BMC)N3S W7G)Z1L SD7)MW2 376)RH8 NWT)JHL 7CD)N2Z KTR)HM3 1Q1)TDZ DY9)2CR +6YJ)14G FWT)JDW C2S)C5G SNV)J6M 5TK)YWH J3M)8HF HM2)GJP P9W)7CD 1VN)SGX KMS)RBK +64R)B1V 62D)3VV 61D)F4S XPR)SKN FJT)N3P 9WV)D43 TQ8)BDB 46H)K4V 8WJ)MXD NDM)9WF +8ZL)1QJ SCR)2MQ 7Y9)LJH VPH)MKY YDC)PDK 4G7)65H 2JM)NYY T9T)VMT 8M1)TSK G5S)X4N +6FH)KYP D98)DQW G6D)C2S 6X7)N2Q 1QJ)T7S ZL4)J8T 5BT)3VR 835)KCJ YM8)3RG Y7M)PWQ +54W)9W4 CBF)7LJ 4T5)8WS RHQ)HBK CQD)D98 HGJ)J6R JVC)79Z FD1)PKF VC9)5BT C4H)6WF +D3S)P6P MR7)BG3 R6V)DF3 9X1)NQ5 ZTZ)2Y2 8WM)HFP CDC)376 TQ4)M4Y 9MB)N1R HBK)DQ4 +1DQ)CYC WNP)DM8 CBJ)LK7 ZT8)FWY LQD)PNN 555)9Z3 TNS)D9L QMF)L11 FR8)5RH WF9)R87 +NKG)5HT L5G)91W N2Z)YV9 9B5)CD7 ZV7)8NQ ST6)74T ZJ6)CQV S18)47M 74T)8YN WNH)TN2 +874)46H 3VV)PZ3 Y1F)42W MPT)2LP FDR)HWF X7G)RTK 52B)P4R RYP)G93 NWH)YCF 7TR)FB8 +RWQ)6FH 8F8)HLC CRN)P2P B6D)KC5 PNN)HRG""".split() + +# COM is the root in this tree + + +# parent :: Vertex -> [Edge] -> Maybe(Vertex) +def parent(x, xs): + for a, b in xs: + if b == x: + return a + return None + + +# parents :: Vertex -> [Edge] -> [Vertex] +def parents(x, xs): + parents = [] + p = parent(x, xs) + while p: + parents.append(p) + p = parent(p, xs) + return parents + + +# alias Vertex :: String +# alias Edge :: (String, String) +# to_edge_list :: [String] -> [(String, String)] +def to_edge_list(xs): + """Returns a list of tuples where (A, B) represents a directed edge from + vertex A to vertex B.""" + return [(x[0:3], x[4:]) for x in xs] + + +# to_graphviz :: [Edge] -> String +def to_graphviz(xs): + d = Digraph() + for a, b in xs: + d.node(a, label=a) + d.edge(a, b) + return d.source + + +graph = to_edge_list(data) +you = parents('YOU', graph) +san = parents('SAN', graph) + +# Distance from YOU to shared point with SAN +yd = 1 +for i in range(len(you)): + if you[i] in san: + break + yd += 1 + +# Distance from SAN to shared point with YOU +sd = 1 +for i in range(len(san)): + if san[i] in you: + break + sd += 1 + +print('Number of orbital transfers required: {}'.format(yd - 1 + sd - 1)) diff --git a/scratch/advent-of-code-2019/day_7.py b/scratch/advent-of-code-2019/day_7.py new file mode 100644 index 000000000000..14597d5104e3 --- /dev/null +++ b/scratch/advent-of-code-2019/day_7.py @@ -0,0 +1,49 @@ +from day_5 import interpret +from itertools import permutations + +# TODO: I may need to re-write this in Elixir modelling each amplifier as a +# `Process` and `Process.send`ing each amplifier the signals. + +data = [ + 3, 8, 1001, 8, 10, 8, 105, 1, 0, 0, 21, 38, 59, 76, 89, 106, 187, 268, 349, + 430, 99999, 3, 9, 1002, 9, 3, 9, 101, 2, 9, 9, 1002, 9, 4, 9, 4, 9, 99, 3, + 9, 1001, 9, 5, 9, 1002, 9, 5, 9, 1001, 9, 2, 9, 1002, 9, 3, 9, 4, 9, 99, 3, + 9, 1001, 9, 4, 9, 102, 4, 9, 9, 1001, 9, 3, 9, 4, 9, 99, 3, 9, 101, 4, 9, + 9, 1002, 9, 5, 9, 4, 9, 99, 3, 9, 1002, 9, 3, 9, 101, 5, 9, 9, 1002, 9, 3, + 9, 4, 9, 99, 3, 9, 102, 2, 9, 9, 4, 9, 3, 9, 1002, 9, 2, 9, 4, 9, 3, 9, + 1002, 9, 2, 9, 4, 9, 3, 9, 101, 2, 9, 9, 4, 9, 3, 9, 1002, 9, 2, 9, 4, 9, + 3, 9, 102, 2, 9, 9, 4, 9, 3, 9, 101, 1, 9, 9, 4, 9, 3, 9, 1001, 9, 1, 9, 4, + 9, 3, 9, 1002, 9, 2, 9, 4, 9, 3, 9, 101, 2, 9, 9, 4, 9, 99, 3, 9, 1002, 9, + 2, 9, 4, 9, 3, 9, 101, 2, 9, 9, 4, 9, 3, 9, 1002, 9, 2, 9, 4, 9, 3, 9, 101, + 1, 9, 9, 4, 9, 3, 9, 102, 2, 9, 9, 4, 9, 3, 9, 102, 2, 9, 9, 4, 9, 3, 9, + 101, 2, 9, 9, 4, 9, 3, 9, 101, 2, 9, 9, 4, 9, 3, 9, 102, 2, 9, 9, 4, 9, 3, + 9, 1001, 9, 2, 9, 4, 9, 99, 3, 9, 1002, 9, 2, 9, 4, 9, 3, 9, 1001, 9, 2, 9, + 4, 9, 3, 9, 101, 1, 9, 9, 4, 9, 3, 9, 101, 2, 9, 9, 4, 9, 3, 9, 101, 2, 9, + 9, 4, 9, 3, 9, 102, 2, 9, 9, 4, 9, 3, 9, 1001, 9, 2, 9, 4, 9, 3, 9, 102, 2, + 9, 9, 4, 9, 3, 9, 1001, 9, 1, 9, 4, 9, 3, 9, 1001, 9, 2, 9, 4, 9, 99, 3, 9, + 1001, 9, 2, 9, 4, 9, 3, 9, 102, 2, 9, 9, 4, 9, 3, 9, 1001, 9, 2, 9, 4, 9, + 3, 9, 102, 2, 9, 9, 4, 9, 3, 9, 101, 2, 9, 9, 4, 9, 3, 9, 1002, 9, 2, 9, 4, + 9, 3, 9, 1002, 9, 2, 9, 4, 9, 3, 9, 1002, 9, 2, 9, 4, 9, 3, 9, 101, 1, 9, + 9, 4, 9, 3, 9, 101, 1, 9, 9, 4, 9, 99, 3, 9, 101, 2, 9, 9, 4, 9, 3, 9, 102, + 2, 9, 9, 4, 9, 3, 9, 1002, 9, 2, 9, 4, 9, 3, 9, 1001, 9, 2, 9, 4, 9, 3, 9, + 1001, 9, 2, 9, 4, 9, 3, 9, 1001, 9, 2, 9, 4, 9, 3, 9, 1001, 9, 1, 9, 4, 9, + 3, 9, 1001, 9, 2, 9, 4, 9, 3, 9, 1001, 9, 2, 9, 4, 9, 3, 9, 102, 2, 9, 9, + 4, 9, 99 +] + +data_a, data_b, data_c, data_d, data_e = data[:], data[:], data[:], data[:], data[:] + +# m = 0 +# for a, b, c, d, e in permutations(range(5, 10)): +# answer = None +# z = 0 +# while z is not None: +# print(a, b, c, d, e) +# print('---') +# v = interpret(0, data_a, argv=[a, z]) +# print(v) +# w = interpret(0, data_b, argv=[b, v]) +# x = interpret(0, data_c, argv=[c, w]) +# y = interpret(0, data_d, argv=[d, x]) +# z = interpret(0, data_e, argv=[e, y]) +# m = max(m, z) |