adventofpython2020

import numpy as np

d = np.loadtxt("data/day01.txt", dtype=int) d

# the loopy way # loop through each item, and, for each, loop through every other item for i in d: for j in d: if i + j == 2020: print("i:", i, "j:", j, "i*j:", i*j)

from itertools import combinations

for pair in combinations(d, 2): # pair is a tuple containing two options from the input d if sum(pair) == 2020: print(pair[0]*pair[1])

[i*j for i,j in combinations(d, 2) if i+j == 2020]

[i*j*k for i,j,k in combinations(d, 3) if i+j+k == 2020]

def solve_slow(d): return [i*j*k for i,j,k in combinations(d, 3) if i+j+k == 2020] %timeit print(solve_slow(d))

# exit the loop earlier, when the solution is found def solve_better(d, n): for group in combinations(d, n): if sum(group) == 2020: return np.product(group) %timeit print(solve_better(d, 3))

%%time combs = np.array(list(combinations(d, 3))) def solve_with_numpy(combs): idx = np.where(np.sum(combs, axis=1) == 2020)[0] return np.product(combs[int(idx)]) %timeit solve_with_numpy(combs)

import numpy as np

password_data = np.loadtxt("data/day02.txt", dtype=str) password_data

with open("data/day02.txt", "r") as datafile: data_lines = datafile.readlines() data_lines

password_data = [l.strip().replace(":", "").split(" ") for l in data_lines] password_data

valid_passwords = 0 for (freqs, letter, password) in password_data: min_freq, max_freq = freqs.split("-") min_freq, max_freq = int(min_freq), int(max_freq) count = password.count(letter) if (count >= min_freq) & (count <= max_freq): valid_passwords += 1 valid_passwords

valid_passwords = 0 for (positions, letter, password) in password_data: pos1, pos2 = positions.split("-") pos1, pos2 = int(pos1), int(pos2) check1 = password[pos1 - 1] == letter check2 = password[pos2 - 1] == letter if check1 + check2 == 1: valid_passwords += 1 valid_passwords

with open("data/day03.txt", "r") as mapfile: lines = mapfile.readlines() lines = [l.strip() for l in lines] lines

position = 0 trees_encountered = 0 line_length = len(lines[0]) for line in lines: trees_encountered += int(line[position] == "#") print(line, int(line[position] == "#")) position += 3 position %= line_length trees_encountered

move_options = [1, 3, 5, 7, 1] lines_options = [lines, lines, lines, lines, lines[::2]] total_trees = 1 for move_i, lines_i in zip(move_options, lines_options): position = 0 trees_encountered = 0 line_length = len(lines_i[0]) for line in lines_i: trees_encountered += int(line[position] == "#") # print(line, int(line[position] == "#")) position += move_i position %= line_length total_trees *= trees_encountered total_trees

with open("data/day04.txt") as f: # load as one long string data = f.read() # \n\n (two newlines) marks separation between passports passports = data.split("\n\n") # Now harmonize the entries within passports # (some separated by \n, some by space) # change all to spaces passports = [p.replace("\n", " ") for p in passports] passports

p = passports[0].split(" ") p

p = [i.split(":") for i in p] p

{i[0]: i[1] for i in p}

# build a list of dictionaries passport_dicts = [] for passport in passports: p = passport.split(" ") p = [i.split(":") for i in p] d = {i[0]: i[1] for i in p} passport_dicts.append(d) passport_dicts

valid = 0 for p in passport_dicts: # identify the keys present # remove the cid entry # check that there are now 7 entries keys = list(p.keys()) if "cid" in keys: keys.remove("cid") if len(keys) == 7: valid += 1 valid

num_valid = 0 validators = [] for p in passport_dicts: # identify the keys present # remove the cid entry # check that there are now 7 entries keys = list(p.keys()) if "cid" in keys: keys.remove("cid") valid_length = len(keys) == 7 def _check_min_max(x, mini, maxi): x = int(x) return (x >= mini) & (x <= maxi) if valid_length: # BYR, IYR, EYR valid_byr = _check_min_max(p["byr"], 1920, 2002) valid_iyr = _check_min_max(p["iyr"], 2010, 2020) valid_eyr = _check_min_max(p["eyr"], 2020, 2030) # HGT if "cm" in p["hgt"]: hgt = p["hgt"].replace("cm", "") valid_hgt = _check_min_max(hgt, 150, 193) elif "in" in p["hgt"]: hgt = p["hgt"].replace("in", "") valid_hgt = _check_min_max(hgt, 59, 76) else: valid_hgt = False # HCL if (len(p["hcl"]) == 7) & (p["hcl"][0] == "#"): allowed_chars = set("0123456789abcdef") valid_hcl = set(p["hcl"][1:]).issubset(allowed_chars) else: valid_hcl = False # ECL valid_ecl = p["ecl"] in ["amb", "blu", "brn", "gry", "grn", "hzl", "oth"] # PID allowed_chars = set("0123456789") valid_pid = (len(p["pid"]) == 9) & set(p["pid"]).issubset(allowed_chars) # COMBINED valid = valid_byr & valid_iyr & valid_eyr & valid_hgt & valid_hcl & valid_ecl & valid_pid validators += [[valid_byr, valid_iyr, valid_eyr, valid_hgt, valid_hcl, valid_ecl, valid_pid]] if valid: num_valid += 1 num_valid

# an opportunity to use recursion... def find_row(x, nrange): half_n = int(len(nrange)/2) # reduce nrange and x each time the function is called if x[0] == "F": nrange = nrange[:half_n] elif x[0] == "B": nrange = nrange[half_n:] print(x, ":", nrange) if len(x) == 1: return nrange[0] x = x[1:] return find_row(x, nrange) seat_code = "FBFBBFFRLR" N = 128 row_number = find_row(seat_code[:7], range(N)) row_number

def find_seat(x, nrange, option="row", report=True): if option == "row": lower = "F" upper = "B" elif option == "col": lower = "L" upper = "R" half_n = int(len(nrange)/2) if x[0] == lower: nrange = nrange[:half_n] elif x[0] == upper: nrange = nrange[half_n:] if report: print(x, ":", nrange) if len(x) == 1: return nrange[0] x = x[1:] return find_seat(x, nrange, option, report) seat_code = "FBFBBFFRLR" row_number = find_seat(seat_code[:7], range(128), option="row") row_number

col_number = find_seat(seat_code[7:], range(8), option="col") col_number

find_seat(seat_code[7:], range(8), option="col", report=False)

seat_ID = row_number*8 + col_number seat_ID

# load and identify each seat with open("data/day05.txt", "r") as f: seat_codes = f.readlines() seat_codes = [s.strip() for s in seat_codes] seat_IDs = [] for s in seat_codes: row = find_seat(s[:7], range(128), "row", report=False) col = find_seat(s[7:], range(8), "col", report=False) seat_IDs.append(row*8 + col) max(seat_IDs)

# the seats are a continuous list (the only jump is at our seat) # so go through each possible option and see if it's there or not seat_IDs.sort() for i in range(seat_IDs[0], seat_IDs[-1]+1): if i not in seat_IDs: print(i)

# alternatively... [i for i in range(min(seat_IDs), max(seat_IDs)+1) if i not in seat_IDs]

possible_seats = set(range(min(seat_IDs), max(seat_IDs)+1)) possible_seats.difference(seat_IDs)

s = "FBFBBFFRLR" sb = s.replace("F", "0").replace("B", "1").replace("L", "0").replace("R", "1") print(s, ":", sb) print("seat number:", int(sb, 2))

with open("data/day06.txt") as f: data = f.read() # Like in an earlier task, we can split the data into a list # according to where there are two newlines data = data.split("\n\n") # Now each group is an element in this list, so we can loop through # them and probe each one in turn count = 0 for group in data: # Remove the meaningless "person" divisions within each group responses = group.replace("\n", "") # Identify only unique characters; count them (len of the set) unique_responses = set(responses) count += len(unique_responses) count

count = 0 for group in data: # Turn each group into a list of sets (one set for each person) responses_list = group.split("\n") if "\n" in group else [group] responses = [set(r) for r in responses_list] print(responses_list, "as sets:", responses) if len(responses) == 1: shared_responses = responses[0] else: # use intersection with the first set of responses # and "argument unpacking" with * to feed the remaining sets # as args to the intersection call shared_responses = responses[0].intersection(*responses[1:]) print("shared responses:", shared_responses) count += len(shared_responses) count

with open("data/day07.txt", "r") as f: data = f.read() rules = data.split("\n") # parse the contents to into strings and lists with only the essential info # Store all these in a dictionary rule_dict = {} for rule in rules: print(f"INPUT: {rule}") outerbag, contents = rule.split(" bags contain ") contents = contents.split(",") contents = [ c.replace(" bags", "").replace(".", "").replace(" bag", "").strip() for c in contents ] print(f"{outerbag}: {contents}") rule_dict[outerbag] = contents

[i.split(" ") for i in rule_dict["faded gold"]]

class Bag(): def __init__(self, name, number): self.name = name self.number = int(number) # set a list of bags to self.inner_bags self.set_contents() def __repr__(self): s = f"Bag('{self.name}', {self.number})" return s def __str__(self): s = f"{self.number} x '{self.name}' bag contains:\n" for b in self.inner_bags: s += "\t" + f"{b.number} x '{b.name}' bag(s)\n" return s def set_contents(self): contents = [i.split(" ") for i in rule_dict[self.name]] if contents == [['no', 'other']]: self.inner_bags = [] return for (number, name1, name2) in contents: name = " ".join((name1, name2)) bag = Bag(name, number) if hasattr(self, "inner_bags"): self.inner_bags.append(bag) else: self.inner_bags = [bag] def dig_for_gold(self, interesting_bag="shiny gold", report=True): if report: print(f"checking '{self.name}': {[b.name for b in self.inner_bags]}") if len(self.inner_bags) == 0: return False found_gold = interesting_bag in [b.name for b in self.inner_bags] if found_gold: if report: print("found", interesting_bag) return True else: if report: print("digging deeper...") for b in self.inner_bags: if b.dig_for_gold(interesting_bag, report): return True b = Bag("faded gold", 1) b

b.inner_bags

b = Bag("faded gold", 1) print(b)

for ib in b.inner_bags: print(ib)

%%time bag_names = rule_dict.keys() bag_collection = [] for bn in bag_names: bag_collection.append(Bag(bn, 1))

b.dig_for_gold("drab violet", report=True)

%%time count = 0 for b in bag_collection: if b.dig_for_gold(report=False): count += 1 count

class Bag2(): def __init__(self, name, number): self.name = name self.number = int(number) # set a list of bags to self.inner_bags self.set_contents() def __repr__(self): s = f"Bag2('{self.name}', {self.number})" return s def __str__(self): s = f"{self.number} x '{self.name}' bag, each contains:\n" for b in self.inner_bags: s += "\t" + f"{b.number} x '{b.name}' bag(s)\n" return s def set_contents(self): contents = [i.split(" ") for i in rule_dict[self.name]] if contents == [['no', 'other']]: self.inner_bags = [] return for (number, name1, name2) in contents: name = " ".join((name1, name2)) bag = Bag2(name, number) if hasattr(self, "inner_bags"): self.inner_bags.append(bag) else: self.inner_bags = [bag] def count_bags(self): """The number of bags at this level *and* the level deeper""" if len(self.inner_bags) == 0: N = self.number else: N = self.number + self.number*sum([b.count_bags() for b in self.inner_bags]) print(f"'{self.name}'({self.number}) contains {N}'") return N b = Bag2("shiny gold", 1) b

print(b) print("------------------------------") for i in b.inner_bags: print(i)

b.count_bags()

example = """nop +0 acc +1 jmp +4 acc +3 jmp -3 acc -99 acc +1 jmp -4 acc +6""" instruction_list = example.split("\n") instruction_list = [i.split(" ") for i in instruction_list] instruction_list = [(i[0], int(i[1])) for i in instruction_list] instruction_list

class Instruction(): def __init__(self, operation, value): self.operation, self.value = operation, value def __repr__(self): return f"Instruction('{self.operation}', {self.value})" Instruction("nop", 0)

class Program(): def __init__(self, instructions=None, instructions_raw=None): if instructions_raw: instructions = instructions_raw.split("\n") instructions = [i.split(" ") for i in instructions] instructions = [(i[0], int(i[1])) for i in instructions] instructions = [Instruction(i[0], i[1]) for i in instructions] self.instructions = instructions self.pointer = 0 self.accumulator = 0 self.history = [] def __repr__(self): return "Programme([\n\t" + \ ",\n\t".join([i.__repr__() for i in self.instructions]) + \ "\n])" def __str__(self): # list of strings showing instructions l = [i.__repr__() for i in self.instructions] l[self.pointer] += " <- pointer" return f"Programme([\n\t" + \ ",\n\t".join(l) + \ "\n])" def step(self): if self.pointer in self.history: raise Exception(f"Loop found at pointer:{self.pointer}, with accumulator:{self.accumulator}") self.history.append(self.pointer) i = self.instructions[self.pointer] if i.operation == "acc": self.accumulator += i.value self.pointer += 1 elif i.operation == "nop": self.pointer += 1 elif i.operation == "jmp": self.pointer += i.value else: raise Exception(f"Invalid instruction: {i}") p = Program(instructions_raw=example) p

p = Program(instructions_raw=example) while True: try: print(p) p.step() except Exception as e: print(e) break

with open("data/day08.txt", "r") as f: instructions_raw = f.read() p = Program(instructions_raw=instructions_raw) while True: try: p.step() except Exception as e: print(e) break

class ProgramLoopError(Exception): pass class ProgramEndError(Exception): pass class Program(): def __init__(self, instructions=None, instructions_raw=None): if instructions_raw: instructions = instructions_raw.split("\n") instructions = [i.split(" ") for i in instructions] instructions = [(i[0], int(i[1])) for i in instructions] instructions = [Instruction(i[0], i[1]) for i in instructions] self.instructions = instructions self.pointer = 0 self.accumulator = 0 self.history = [] def __repr__(self): return "Programme([\n\t" + \ ",\n\t".join([i.__repr__() for i in self.instructions]) + \ "\n])" def __str__(self): # list of strings showing instructions l = [i.__repr__() for i in self.instructions] l[self.pointer] += " <- pointer" return f"Programme([\n\t" + \ ",\n\t".join(l) + \ "\n])" def step(self): if self.pointer in self.history: raise ProgramLoopError(f"Loop found at pointer:{self.pointer}, with accumulator:{self.accumulator}") if self.pointer == len(self.instructions): raise ProgramEndError(f"Program complete with accumulator:{self.accumulator}") self.history.append(self.pointer) i = self.instructions[self.pointer] if i.operation == "acc": self.accumulator += i.value self.pointer += 1 elif i.operation == "nop": self.pointer += 1 elif i.operation == "jmp": self.pointer += i.value else: raise Exception(f"Invalid instruction: {i}") def switch_jmp_or_nop(self, x, report=True): """Modify a jmp or switch at position x""" instr = self.instructions[x] if instr.operation == "jmp": instr.operation = "nop" elif instr.operation == "nop": instr.operation == "jmp" if (instr.operation == "jmp") and (instr.value == 0): raise ProgramLoopError("jmp 0 encountered") self.instructions[x] = instr if report: print(f"modified {self.instructions[x]}")

def test_program(instructions_raw=example): p = Program(instructions_raw=instructions_raw) while True: try: p.step() except ProgramLoopError as e: print(e) break test_program(example)

def test_modifying_program(instructions_raw=example, report=True): x = 0 while True: p = Program(instructions_raw=instructions_raw) p.switch_jmp_or_nop(x, report=report) while True: try: p.step() except ProgramLoopError as e: break except ProgramEndError as e: return e.args x += 1 test_modifying_program(example)

test_modifying_program(instructions_raw=instructions_raw, report=False)

example = [35, 20, 15, 25, 47, 40, 62, 55, 65, 95, 102, 117, 150, 182, 127, 219, 299, 277, 309, 576]

from itertools import combinations

def find_first_invalid(d, preamble=5): # Loop through relevant indexes in d for i in range(preamble, len(d)): # find sums of combinations from the preceding chunk chunk = d[i-preamble:i] sums = [sum(pair) for pair in combinations(chunk, 2)] if d[i] not in sums: return d[i] find_first_invalid(example)

with open("data/day09.txt", "r") as f: data = f.readlines() data = [int(d) for d in data] find_first_invalid(data, preamble=25)

invalid_number = find_first_invalid(example) def find_matching_chunk(d, x): # starting index i for i in range(len(d)): # ending index j for j in range(1, len(d)): chunk = d[i:j] if sum(chunk) == x: return chunk def solve(d, preamble=5): inval = find_first_invalid(d, preamble) chunk = find_matching_chunk(d, inval) return sum([min(chunk), max(chunk)]) solve(example, 5)

solve(data, 25)

import numpy as np example = np.array([28, 33, 18, 42, 31, 14, 46, 20, 48, 47, 24, 23, 49, 45, 19, 38, 39, 11, 1, 32, 25, 35, 8, 17, 7, 9, 4, 2, 34, 10, 3]) def solve(d): d = np.sort(d) # Add the connection to the wall d = np.append([0], d) # Add the connection to the device d = np.append(d, [d.max() + 3]) # The differences between every step diffs = np.diff(d) # Identify the steps of one and three jolts num_ones = sum(diffs == 1) num_threes = sum(diffs == 3) return num_ones * num_threes solve(example)

solve(np.loadtxt("data/day10.txt"))

example = np.sort(example) diffs = np.diff(np.array([0, *list(example), example[-1]+3])) diffs

example

import numpy as np with open("data/day11.txt", "r") as f: seatmap_in = f.read().splitlines() seatmap_in = [["."] + list(l) + ["."] for l in seatmap_in] seatmap_in.insert(0, list(".")*96) seatmap_in.append(list(".")*96) seatmap_in = np.array(seatmap_in) seatmap = np.zeros_like(seatmap_in, dtype=float) # seatmap[np.where(seatmap_in == "L")] = 0 seatmap[np.where(seatmap_in == ".")] = np.nan # NaN: no seat # 0: empty seat # 1: occupied seat # Padded with non-seats round the edge seatmap, seatmap.shape

# inner square, with seats to check seatmap[1:-1, 1:-1]

example = """L.LL.LL.LL LLLLLLL.LL L.L.L..L.. LLLL.LL.LL L.LL.LL.LL L.LLLLL.LL ..L.L..... LLLLLLLLLL L.LLLLLL.L L.LLLLL.LL""" example = example.splitlines() example = [["."] + list(l) + ["."] for l in example] example.insert(0, list(".")*12) example.append(list(".")*12) example = np.array(example) example_seatmap = np.zeros_like(example, dtype=float) # seatmap[np.where(seatmap_in == "L")] = 0 example_seatmap[np.where(example == ".")] = np.nan example_seatmap

def solve_seatmap(seatmap=example_seatmap): seatmap0 = seatmap.copy() count = 0 unstable = True while unstable: # Evaluate the next step in the sequence seatmap1 = seatmap0.copy() # check empty seats indexes = np.where(seatmap0 == 0) for i in range(len(indexes[0])): idx_x = indexes[0][i] idx_y = indexes[1][i] # fill the seat if the surrounding are all empty if not (seatmap0[idx_x-1:idx_x+2, idx_y-1:idx_y+2] == 1).any(): seatmap1[idx_x, idx_y] = 1 # check occupied seats indexes = np.where(seatmap0 == 1) for i in range(len(indexes[0])): idx_x = indexes[0][i] idx_y = indexes[1][i] # empty the seat if at least four surrounding are occupied if np.sum(seatmap0[idx_x-1:idx_x+2, idx_y-1:idx_y+2] == 1) >= 5: seatmap1[idx_x, idx_y] = 0 # Find if stable (then continue if not) if np.array_equal(seatmap0, seatmap1, equal_nan=True): unstable = False number_occupied = np.nansum(seatmap1) else: seatmap0 = seatmap1.copy() count += 1 # print(count) # print(seatmap1) return int(number_occupied)

solve_seatmap(seatmap)

example = """F10 N3 F7 R90 F11"""

class Ship: def __init__(self, cardinal="E", easting=0, northing=0): self.angle = self.cardinal2angle(cardinal) self.easting = easting self.northing = northing def __str__(self): return f"E({self.easting}), N({self.northing}), facing {self.facing()}" @staticmethod def cardinal2angle(cardinal="E"): return {"N": 0, "E": 90, "S": 180, "W": 270}[cardinal] @staticmethod def angle2cardinal(angle=90): return {0: "N", 90: "E", 180: "S", 270: "W"}[angle] def facing(self): return self.angle2cardinal(self.angle) def move_cardinal(self, action, value): if action == "N": self.northing += value elif action == "S": self.northing -= value elif action == "E": self.easting += value elif action == "W": self.easting -= value def rotate(self, action, value): # value is only ever 90 or 180 if action == "R": self.angle = (self.angle + value) % 360 elif action == "L": self.angle = (self.angle - value) % 360 def step(self, action, value): if action in "NSEW": self.move_cardinal(action, value) elif action in "RL": self.rotate(action, value) elif action in "F": self.move_cardinal( self.angle2cardinal(self.angle), value ) def manhattan_distance(self): return abs(self.easting) + abs(self.northing) def navigate(self, instructions=example, report=False): instructions = instructions.splitlines() for i in instructions: action = i[0] value = int(i[1:]) if report: print(self, f" ({action}{value})") self.step(action, value) if report: print(self)

ship = Ship() ship.navigate(example, report=True)

with open("data/day12.txt", "r") as f: instructions = f.read() ship = Ship() ship.navigate(instructions) ship.manhattan_distance()

example = """939 7,13,x,x,59,x,31,19""" arrival_time, bus_IDs = example.splitlines() arrival_time = int(arrival_time) bus_IDs = [b if b=="x" else int(b) for b in bus_IDs.split(",")] arrival_time, bus_IDs

def bus_times(b=7, N=1e6): num = b while num<N: yield num num += b for b in bus_times(7, N=50): print(b)

x = bus_times(7) next(x), next(x), next(x)

bus_time_generators = [bus_times(b) for b in bus_IDs if b!="x"] print([next(b) for b in bus_time_generators]) print([next(b) for b in bus_time_generators])

def find_earliest_bus(bus_IDs, arrival_time, N=1e9): # list of generators bus_IDs = [b for b in bus_IDs if b!="x"] bus_time_generators = [bus_times(b, N) for b in bus_IDs] # for each of the buses, iterate individually until it has gone past the arrival time times = [next(b) for b in bus_time_generators] for i in range(len(times)): past_arrival = False while not past_arrival: # print(times) times[i] = next(bus_time_generators[i]) past_arrival = times[i] >= arrival_time return bus_IDs, times

find_earliest_bus(bus_IDs, arrival_time)

with open("data/day13.txt", "r") as f: text = f.read() arrival_time, bus_IDs = text.splitlines