Last active
December 6, 2018 17:50
-
-
Save ric2b/dc0a099ff810e3779dc682b05415d3fc to your computer and use it in GitHub Desktop.
My solutions (and automated input fetcher and runner) to the daily "christmas calendar" programming puzzles from https://adventofcode.com/2017
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import collections | |
from math import sqrt | |
from functools import reduce | |
import string | |
INPUTS_FILE = 'advent_of_code_inputs.txt' | |
SOLUTIONS_FILE = 'advent_of_code_solutions.txt' | |
SESSION_FILE = 'advent_of_code_session.txt' | |
SOLVER_CLASS_PREFIX = 'Day' | |
class Day25: | |
def __init__(self, input_str: str): | |
self.input = [line for line in input_str.split('\n')] | |
def __solve_part_1(self): | |
states = {} | |
for i in range(3, len(self.input), 10): | |
state = self.input[i].split(' ')[2][0] | |
states[state] = Day25.parse_state(self.input[i+1:i+9]) | |
checksum_after = int(self.input[1].split(' ')[5]) | |
locations_set_at_1 = set() | |
current_state = self.input[0].split(' ')[3][0] | |
current_position = 0 | |
for _ in range(checksum_after): | |
current_value = 1 if current_position in locations_set_at_1 else 0 | |
if states[current_state][current_value]['value_to_write'] == 1: | |
locations_set_at_1.add(current_position) | |
elif current_value == 1: | |
locations_set_at_1.remove(current_position) | |
current_position += states[current_state][current_value]['movement_direction'] | |
current_state = states[current_state][current_value]['next_state'] | |
return len(locations_set_at_1) | |
@staticmethod | |
def parse_state(state_instructions): | |
first_substate = Day25.parse_substate(state_instructions[0:4]) | |
second_substate = Day25.parse_substate(state_instructions[4:8]) | |
if first_substate['tape_state'] == 0: | |
return [first_substate, second_substate] | |
else: | |
return [second_substate, first_substate] | |
@staticmethod | |
def parse_substate(substate_instructions): | |
tape_state = int(substate_instructions[0].strip().split(' ')[5][0]) | |
value_to_write = int(substate_instructions[1].strip().split(' ')[4][0]) | |
movement_direction = -1 if substate_instructions[2].strip().split(' ')[6][:-1] == 'left' else 1 | |
next_state = substate_instructions[3].strip().split(' ')[4][0] | |
return { | |
'tape_state': tape_state, | |
'value_to_write': value_to_write, | |
'movement_direction': movement_direction, | |
'next_state': next_state | |
} | |
def solve_all(self): | |
return [self.__solve_part_1(), None] | |
class Day24: | |
def __init__(self, input_str: str): | |
self.input = [line for line in input_str.split('\n')] | |
@staticmethod | |
def make_component_database(raw_component_list): | |
components = [] | |
for component in raw_component_list: | |
components.append(component.split('/')) | |
return components | |
def __solve_part_1(self): | |
components = Day24.make_component_database(self.input) | |
possible_bridges = [] | |
for index, component in enumerate(components): | |
if component[0] == '0' or component[1] == '0': | |
possible_bridges.append([component]) | |
current_bridge = [component] | |
current_port = component[1] if component[0] == '0' else component[0] | |
remaining_components = components[:] | |
remaining_components[index] = None | |
for bridge in Day24.list_possible_bridges(current_port, current_bridge, remaining_components): | |
possible_bridges.append(bridge) | |
return Day24.get_strongest_bridge(possible_bridges) | |
def __solve_part_2(self): | |
components = Day24.make_component_database(self.input) | |
possible_bridges = [] | |
for index, component in enumerate(components): | |
if component[0] == '0' or component[1] == '0': | |
possible_bridges.append([component]) | |
current_bridge = [component] | |
current_port = component[1] if component[0] == '0' else component[0] | |
remaining_components = components[:] | |
remaining_components[index] = None | |
for bridge in Day24.list_possible_bridges(current_port, current_bridge, remaining_components): | |
possible_bridges.append(bridge) | |
return Day24.get_strongest_bridge(Day24.get_longest_bridges(possible_bridges)) | |
@staticmethod | |
def list_possible_bridges(current_port, current_bridge, components): | |
possible_bridges = [] | |
for index, component in enumerate(components): | |
if component: | |
if component[0] == current_port or component[1] == current_port: | |
remaining_components = components[:] | |
new_bridge = current_bridge[:] | |
new_bridge.append(component) | |
possible_bridges.append(new_bridge) | |
new_port = component[1] if component[0] == current_port else component[0] | |
remaining_components = components[:] | |
remaining_components[index] = None | |
for bridge in Day24.list_possible_bridges(new_port, new_bridge, remaining_components): | |
possible_bridges.append(bridge) | |
return possible_bridges | |
@staticmethod | |
def get_longest_bridges(possible_bridges): | |
longest_bridges = [possible_bridges[0]] | |
for bridge in possible_bridges: | |
if len(bridge) == len(longest_bridges[0]): | |
longest_bridges.append(bridge) | |
if len(bridge) > len(longest_bridges[0]): | |
longest_bridges = [bridge] | |
return longest_bridges | |
@staticmethod | |
def get_strongest_bridge(possible_bridges): | |
strongest_bridge = [0, None] | |
for bridge in possible_bridges: | |
strenght = sum([int(port) for component in bridge for port in component]) | |
if strenght > strongest_bridge[0]: | |
strongest_bridge = [strenght, bridge] | |
return strongest_bridge[0] | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day23: | |
def __init__(self, input_str: str): | |
self.input = [line for line in input_str.split('\n')] | |
def __solve_part_1(self): | |
return Day23.__program(self.input) | |
def __solve_part_2(self): | |
b = int(self.input[0].split(' ')[2]) | |
start = b * 100 + 100000 | |
end = start + 17000 | |
h = 0 | |
for i in range(start, end+17, 17): | |
is_prime = True | |
for j in range(2, int(sqrt(i))+1): | |
if i % j == 0: | |
is_prime = False | |
break | |
if not is_prime: | |
h += 1 | |
return h | |
@staticmethod | |
def __program(code: [str], register_a=0): | |
registers = {letter: 0 for letter in string.ascii_lowercase[:8]} | |
registers['a'] = register_a | |
sending = [] # buffer of values to send | |
program_counter = 0 | |
mul_counter = 0 | |
while 0 <= program_counter < len(code): | |
instruction, argument_1, *other_arguments = code[program_counter].split(' ') | |
if other_arguments: # might as well convert argument 2 here instead of repeating it for all instructions | |
argument_2 = registers[other_arguments[0]] if other_arguments[0] in registers.keys() else int(other_arguments[0]) | |
if instruction == 'set': | |
registers[argument_1] = argument_2 | |
if instruction == 'sub': | |
registers[argument_1] -= argument_2 | |
if instruction == 'mul': | |
registers[argument_1] *= argument_2 | |
mul_counter += 1 | |
if instruction == 'jnz': | |
condition_value = registers[argument_1] if argument_1 in registers.keys() else int(argument_1) | |
if condition_value != 0: | |
program_counter += argument_2 | |
continue | |
program_counter += 1 | |
return mul_counter | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day22: | |
def __init__(self, input_str: str): | |
self.input = [line for line in input_str.split('\n')] | |
self.directions = {'N': (0, -1), 'S': (0, 1), 'E': (1, 0), 'W': (-1, 0)} | |
self.direction_order = ['N', 'E', 'S', 'W'] | |
def __solve_part_1(self): | |
self.infected = set() | |
self.__load_input() | |
infected = 0 | |
for i in range(10000): | |
infected += self.__tick_virus() | |
return infected | |
def __solve_part_2(self): | |
self.infected = set() | |
self.weakened = set() | |
self.flagged = set() | |
self.__load_input() | |
infected = 0 | |
for i in range(10000000): | |
infected += self.__tick_virus(evolved=True) | |
return infected | |
def __load_input(self): | |
for i, line in enumerate(self.input): | |
for j, node in enumerate(line): | |
if node == '#': | |
self.infected.add((j, i)) | |
height = len(self.input) | |
self.direction = 'N' | |
self.position = (0, 0) | |
self.position = (height // 2, height // 2) | |
def __tick_virus(self, evolved=False): | |
infected = self.__toggle_current_node_and_turn(evolved=evolved) | |
new_x = self.position[0] + self.directions[self.direction][0] | |
new_y = self.position[1] + self.directions[self.direction][1] | |
self.position = (new_x, new_y) | |
return infected | |
def __toggle_current_node_and_turn(self, evolved=False): | |
if evolved and self.position in self.infected: | |
self.direction = self.direction_order[(self.direction_order.index(self.direction) + 1) % len(self.direction_order)] | |
self.infected.remove(self.position) | |
self.flagged.add(self.position) | |
return 0 | |
elif evolved and self.position in self.weakened: | |
self.weakened.remove(self.position) | |
self.infected.add(self.position) | |
return 1 | |
elif evolved and self.position in self.flagged: | |
self.direction = self.direction_order[(self.direction_order.index(self.direction) + 2) % len(self.direction_order)] | |
self.flagged.remove(self.position) | |
return 0 | |
elif evolved: | |
self.direction = self.direction_order[(self.direction_order.index(self.direction) - 1) % len(self.direction_order)] | |
self.weakened.add(self.position) | |
return 0 | |
elif self.position in self.infected: | |
self.direction = self.direction_order[(self.direction_order.index(self.direction) + 1) % len(self.direction_order)] | |
self.infected.remove(self.position) | |
return 0 | |
else: | |
self.direction = self.direction_order[(self.direction_order.index(self.direction) - 1) % len(self.direction_order)] | |
self.infected.add(self.position) | |
return 1 | |
def __current_node_infected(self): | |
return self.position in self.infected | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day21: | |
def __init__(self, input_str: str): | |
self.image = ['.#.', | |
'..#', | |
'###'] | |
self.input = ['../.# => ##./#../...', | |
'.#./..#/### => #..#/..../..../#..#'] | |
self.input = [line for line in input_str.split('\n')] | |
@staticmethod | |
def __make_grid(image): | |
grid = [] | |
for line in image: | |
grid.append([c for c in line]) | |
return grid | |
def __solve_part_1(self): | |
grid = Day21.__make_grid(self.image) | |
size = len(grid) | |
for i in range(5): | |
grid = self.__enhance(grid) | |
return sum(line.count('#') for line in grid) | |
def __solve_part_2(self): | |
grid = Day21.__make_grid(self.image) | |
size = len(grid) | |
for i in range(18): | |
print(i) | |
grid = self.__enhance(grid) | |
return sum(line.count('#') for line in grid) | |
def __enhance(self, grid): | |
split_size = 2 if len(grid) % 2 == 0 else 3 | |
subgrids = [] | |
for i in range(len(grid) // split_size): | |
for j in range(len(grid) // split_size): | |
subgrid = [] | |
for k in range(split_size): | |
line = [] | |
for l in range(split_size): | |
line.append(grid[i*split_size+k][j*split_size+l]) | |
subgrid.append(line) | |
subgrids.append(subgrid) | |
enhanced_subgrids = [] | |
for subgrid in subgrids: | |
enhanced_subgrids.append(self.__match_and_apply_rules(subgrid)) | |
enhanced_grid = [] | |
if len(enhanced_subgrids) > 1: | |
enhanced_grid_size = int(sqrt(len(enhanced_subgrids))) | |
subgrid_size = len(enhanced_subgrids[0]) | |
for k in range(enhanced_grid_size): | |
for i in range(subgrid_size): | |
line = [] | |
for j in range(enhanced_grid_size): | |
line += enhanced_subgrids[k*enhanced_grid_size+j][i] | |
enhanced_grid.append(line) | |
else: | |
enhanced_grid = enhanced_subgrids[0] | |
return enhanced_grid | |
def __match_and_apply_rules(self, subgrid): | |
for rule in self.input: | |
rule_matcher, rule_output = rule.split(' => ') | |
for transformation in Day21.__get_transformations(subgrid): | |
if '/'.join([''.join(line) for line in transformation]) == rule_matcher: | |
return [[c for c in line] for line in rule_output.split('/')] | |
print('No matches found!') | |
for line in subgrid: | |
print(line) | |
raise ValueError | |
@staticmethod | |
def __get_transformations(subgrid): | |
rotate_0 = subgrid | |
rotate_0_flip = Day21.__v_flip_subgrid(rotate_0) | |
rotate_90 = Day21.__v_flip_subgrid(Day21.__symmetric_subgrid(subgrid)) | |
rotate_90_flip = Day21.__v_flip_subgrid(rotate_90) | |
rotate_180 = Day21.__v_flip_subgrid(Day21.__symmetric_subgrid(rotate_90)) | |
rotate_180_flip = Day21.__v_flip_subgrid(rotate_180) | |
rotate_270 = Day21.__v_flip_subgrid(Day21.__symmetric_subgrid(rotate_180)) | |
rotate_270_flip = Day21.__v_flip_subgrid(rotate_270) | |
return [rotate_0, rotate_0_flip, | |
rotate_90, rotate_90_flip, | |
rotate_180, rotate_180_flip, | |
rotate_270, rotate_270_flip | |
] | |
@staticmethod | |
def __make_empty_subgrid(subgrid_size): | |
return [[None] * subgrid_size for _ in range(subgrid_size)] | |
@staticmethod | |
def __symmetric_subgrid(subgrid): | |
subgrid_size = len(subgrid) | |
symmetric = Day21.__make_empty_subgrid(subgrid_size) | |
for i in range(subgrid_size): | |
for j in range(subgrid_size): | |
symmetric[i][j] = subgrid[subgrid_size-1-j][subgrid_size-1-i] | |
return symmetric | |
@staticmethod | |
def __v_flip_subgrid(subgrid): | |
subgrid_size = len(subgrid) | |
flip_vertical = Day21.__make_empty_subgrid(subgrid_size) | |
for i in range(subgrid_size): | |
flip_vertical[i] = subgrid[subgrid_size-1-i] | |
return flip_vertical | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day20: | |
def __init__(self, input_str: str): | |
self.input = [line for line in input_str.split('\n')] | |
def __solve_part_1(self): | |
min_i = None | |
minimum_acceleration = None | |
for i, particle in enumerate(self.input): | |
acceleration = particle.split('>')[2][len(', a=<'):] | |
x, y, z = [int(n) for n in acceleration.split(',')] | |
if minimum_acceleration is None or abs(x) + abs(y) + abs(z) < minimum_acceleration: | |
minimum_acceleration = abs(x) + abs(y) + abs(z) | |
min_i = i | |
return min_i | |
def __solve_part_2(self): | |
particles = {} | |
for i, line in enumerate(self.input): | |
raw_position, raw_velocity, raw_acceleration, _ = line.split('>') | |
position = [int(n) for n in raw_position[len('p=<'):].split(',')] | |
velocity = [int(n) for n in raw_velocity[len(', v=<'):].split(',')] | |
acceleration = [int(n) for n in raw_acceleration[len(', a=<'):].split(',')] | |
particles[i] = {'position': position, 'velocity': velocity, 'acceleration': acceleration} | |
for tick in range(100): | |
occupied_positions = {} | |
to_destroy = set() | |
for particle_id, particle in particles.items(): | |
serialized_position = ','.join([str(n) for n in particle['position']]) | |
if serialized_position in occupied_positions: | |
to_destroy.add(particle_id) | |
to_destroy.add(occupied_positions[serialized_position]) | |
else: | |
occupied_positions[serialized_position] = particle_id | |
for i in range(3): | |
particle['velocity'][i] += particle['acceleration'][i] | |
particle['position'][i] += particle['velocity'][i] | |
for particle_id in to_destroy: | |
del particles[particle_id] | |
return len(particles) | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day19: | |
def __init__(self, input_str: str): | |
self.input = [line for line in input_str.split('\n')] | |
self.grid = [] | |
self.position_x, position_y = None, None | |
self.speed_x, self.speed_y = 0, 1 | |
def __build_grid(self): | |
for i, line in enumerate(self.input): | |
if self.position_x is None: | |
try: | |
self.position_x = line.index('|') | |
self.position_y = i | |
except ValueError: | |
pass | |
self.grid.append([c for c in line]) | |
def __see_position(self, x, y): | |
return self.grid[y][x] | |
def __update_speed(self, character): | |
if character == '+': | |
if self.speed_x != 0: # moving horizontally | |
self.speed_x = 0 | |
try: | |
if self.__see_position(self.position_x, self.position_y+1) == ' ': # below is empty | |
self.speed_y = -1 # start moving up | |
else: | |
self.speed_y = 1 | |
except IndexError: # is at the bottom | |
self.speed_y = -1 | |
elif self.speed_y != 0: # moving vertically | |
self.speed_y = 0 | |
try: | |
if self.__see_position(self.position_x+1, self.position_y) == ' ': # right is empty | |
self.speed_x = -1 # start moving left | |
else: | |
self.speed_x = 1 | |
except IndexError: # is at the the far right | |
self.speed_x = -1 | |
def __update_position(self): | |
self.position_x += self.speed_x | |
self.position_y += self.speed_y | |
def __walk_path(self): | |
checkpoints = [] | |
self.__build_grid() | |
distance_traveled = 0 | |
while (0 <= self.position_x < len(self.grid[0])) and (0 <= self.position_y < len(self.grid)): | |
self.__update_position() | |
distance_traveled += 1 | |
current_character = self.__see_position(self.position_x, self.position_y) | |
self.__update_speed(current_character) | |
if current_character in string.ascii_uppercase: | |
checkpoints.append(current_character) | |
if current_character == ' ': # end of line | |
break | |
return ''.join(checkpoints), distance_traveled | |
def solve_all(self): | |
part1, part2 = self.__walk_path() | |
return [part1, part2] | |
class Day18: | |
def __init__(self, input_str: str): | |
self.input = [line for line in input_str.split('\n')] | |
@staticmethod | |
def __program(code: [str], register_p=0): | |
registers = {letter: 0 for letter in string.ascii_lowercase} | |
registers['p'] = register_p | |
sending = [] # buffer of values to send | |
program_counter = 0 | |
while 0 <= program_counter < len(code): | |
instruction, argument_1, *other_arguments = code[program_counter].split(' ') | |
if other_arguments: # might as well convert argument 2 here instead of repeating it for all instructions | |
argument_2 = registers[other_arguments[0]] if other_arguments[0] in registers.keys() else int(other_arguments[0]) | |
if instruction == 'snd': # no need to yield immediatelly, just makes things complicated (trust me) | |
sending.append(registers[argument_1] if argument_1 in registers.keys() else int(argument_1)) | |
if instruction == 'set': | |
registers[argument_1] = argument_2 | |
if instruction == 'add': | |
registers[argument_1] += argument_2 | |
if instruction == 'mul': | |
registers[argument_1] *= argument_2 | |
if instruction == 'mod': | |
registers[argument_1] = registers[argument_1] % argument_2 | |
if instruction == 'rcv': # send own values and wait for a new one | |
registers[argument_1] = yield sending | |
sending = [] | |
if instruction == 'jgz': | |
condition_value = registers[argument_1] if argument_1 in registers.keys() else int(argument_1) | |
if condition_value > 0: | |
program_counter += argument_2 | |
continue | |
program_counter += 1 | |
def __solve_part_1(self): | |
return next(self.__program(self.input))[-1] | |
def __solve_part_2(self): | |
program_0 = self.__program(self.input, register_p=0) | |
program_1 = self.__program(self.input, register_p=1) | |
# do an initial run because of the while loops below | |
to_1, to_0 = next(program_0), next(program_1) | |
sent_by_1_total = 0 | |
while True: | |
while to_0: | |
yielded_by_0 = program_0.send(to_0.pop(0)) | |
if yielded_by_0: | |
to_1 += yielded_by_0 | |
while to_1: | |
yielded_by_1 = program_1.send(to_1.pop(0)) | |
if yielded_by_1: | |
to_0 += yielded_by_1 | |
sent_by_1_total += len(yielded_by_1) | |
if not (to_0 or to_1): # both are waiting but there are no new values | |
print('deadlock detected') | |
break | |
return sent_by_1_total | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day17: | |
def __init__(self, input_str: str): | |
self.input = int(input_str) | |
def __solve_part_1(self): | |
circle = [] | |
next_position = 0 | |
for i in range(2018): | |
circle.insert(next_position+1, i) | |
next_position = (next_position + 1 + self.input) % len(circle) | |
return circle[(circle.index(2017) + 1) % len(circle)] | |
def __solve_part_2(self): | |
circle_size = 0 | |
next_position = 0 | |
for i in range(50*1000*1000): | |
if next_position == 0: | |
after_0 = i | |
circle_size += 1 | |
next_position = (next_position + 1 + self.input) % circle_size | |
return after_0 | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day16: | |
def __init__(self, input_str: str): | |
self.initial_program_order = [program for program in string.ascii_lowercase[:16]] | |
self.input = [move for move in input_str.split(',')] | |
@staticmethod | |
def __shut_up_and_dance(program_order, move_list): | |
for move in move_list: | |
if move[0] == 's': | |
X = int(move[1:]) | |
program_order = program_order[-X:] + program_order[:-X] | |
elif move[0] == 'x': | |
A, B = [int(index) for index in move[1:].split('/')] | |
program_order[A], program_order[B] = program_order[B], program_order[A] | |
elif move[0] == 'p': | |
A, B = [program for program in move[1:].split('/')] | |
index_A, index_B = program_order.index(A), program_order.index(B) | |
program_order[index_A], program_order[index_B] = program_order[index_B], program_order[index_A] | |
return program_order | |
def __solve_part_1(self): | |
final_program_order = self.__shut_up_and_dance(self.initial_program_order[:], self.input) | |
return ''.join(final_program_order) | |
def __solve_part_2(self): | |
dance_until = 1*1000*1000*1000 | |
current_program_order = self.initial_program_order[:] | |
previous_states = [] | |
for i in range(dance_until): | |
if ''.join(current_program_order) in previous_states: | |
return previous_states[dance_until % i] | |
previous_states.append(''.join(current_program_order)) | |
current_program_order = self.__shut_up_and_dance(current_program_order, self.input) | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day15: | |
def __init__(self, input_str: str): | |
self.input = [int(line[len('Generator A starts with '):]) for line in input_str.split('\n')] | |
@staticmethod | |
def generator(start, factor, divisor, multiple=None): | |
value = start | |
while True: | |
value = (value * factor) % divisor | |
if (not multiple) or (value % multiple == 0): | |
yield value | |
def __count_matches(self, multipleA=None, multipleB=None): | |
startA, startB = self.input | |
factorA, factorB = 16807, 48271 | |
common_divisor = 2147483647 | |
iterations = 5*1000*1000 if multipleA and multipleB else 40*1000*1000 | |
generatorA = Day15.generator(startA, factorA, common_divisor, multipleA) | |
generatorB = Day15.generator(startB, factorB, common_divisor, multipleB) | |
matches = 0 | |
for i in range(iterations): | |
if next(generatorA) & 0xFFFF == next(generatorB) & 0xFFFF: | |
matches += 1 | |
return matches | |
def solve_all(self): | |
return [self.__count_matches(), self.__count_matches(multipleA=4, multipleB=8)] | |
class Day14: | |
def __init__(self, input_str: str): | |
self.input = input_str | |
self.grid_side = 128 | |
def __solve_part_1(self): | |
occupied = 0 | |
for i in range(self.grid_side): | |
row_hash = Day10.knot_hash(f'{self.input}-{i}') | |
row_nibbles = ''.join([f"{int(h_char,16):04b}" for h_char in row_hash]) | |
bit_list = [int(bit) for bit in row_nibbles] | |
occupied += sum(bit_list) | |
return occupied | |
def __solve_part_2(self): | |
self.grid = [[None]*self.grid_side for _ in range(self.grid_side)] | |
self.groups = {} # dict of sets of nodes in each group | |
for y in range(self.grid_side): | |
row_hash = Day10.knot_hash(f'{self.input}-{y}') | |
row_nibbles = ''.join([f"{int(h_char,16):04b}" for h_char in row_hash]) | |
for x, bit in enumerate(row_nibbles): | |
if bit == '1': | |
self.__mark_region(x, y) | |
return len(self.groups) | |
def __mark_region(self, x, y): | |
groups_to_join = [] | |
if 0 < x and self.grid[y][x-1]: # check left | |
groups_to_join.append(self.grid[y][x-1]) | |
if 0 < y and self.grid[y-1][x]: # check above | |
groups_to_join.append(self.grid[y-1][x]) | |
if not groups_to_join: # create new group | |
new_group = set() | |
new_group.add((x,y)) | |
self.groups[(x,y)] = new_group | |
self.grid[y][x] = (x,y) | |
else: | |
self.grid[y][x] = self.__join_group(x, y, groups_to_join) | |
def __join_group(self, x, y, groups_to_join,): | |
if len(groups_to_join) == 1 or (groups_to_join[0] == groups_to_join[1]): | |
# simple case, join one existing group | |
self.groups[groups_to_join[0]].add((x,y)) | |
return groups_to_join[0] | |
else: | |
# join and merge two existing groups | |
group_to_keep, group_to_delete = groups_to_join | |
self.groups[group_to_keep].add((x,y)) | |
for region in self.groups[group_to_delete]: | |
self.groups[group_to_keep].add(region) | |
self.grid[region[1]][region[0]] = group_to_keep | |
del self.groups[group_to_delete] | |
return group_to_keep | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day13: | |
def __init__(self, input_str: str): | |
self.input = [[int(value) for value in scanner.replace(' ', '').split(':')] for scanner in input_str.split('\n')] | |
def __solve_part_1(self): | |
severity = 0 | |
for scanner in self.input: | |
layer, s_range = scanner | |
scanner_period = (s_range-1)*2 | |
if layer % scanner_period == 0: | |
severity += layer * s_range | |
return severity | |
def __solve_part_2(self): | |
i = 0 | |
while True: | |
safe_tick = True | |
for scanner in self.input: | |
layer, s_range = scanner | |
scanner_period = (s_range-1)*2 | |
if (layer+i) % scanner_period == 0: | |
safe_tick = False | |
break | |
if safe_tick: | |
return i | |
i += 1 | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day12: | |
def __init__(self, input_str: str): | |
self.input = [[pipe_end for pipe_end in pipe.replace(' ', '').split('<->')] for pipe in input_str.split('\n')] | |
@staticmethod | |
def __create_connection_graph(pipes_input): | |
connections = {} | |
for pipe in pipes_input: | |
left_program = pipe[0] | |
connections[left_program] = set() | |
for right_program in pipe[1].split(','): | |
connections[left_program].add(right_program) | |
return connections | |
@staticmethod | |
def is_connected_to(connections, start_node, target_node, visited=None): | |
if visited is None: | |
visited = set() | |
visited.add(start_node) | |
if start_node == target_node: | |
return True | |
for node in connections[start_node]: | |
if node not in visited and Day12.is_connected_to(connections, node, target_node, visited): | |
return True | |
return False | |
def __solve_part_1(self): | |
connections = Day12.__create_connection_graph(self.input) | |
connected_to_0 = set() | |
for node in connections: | |
if Day12.is_connected_to(connections, node, '0'): | |
connected_to_0.add(node) | |
return len(connected_to_0) | |
def __solve_part_2(self): | |
connections = Day12.__create_connection_graph(self.input) | |
visited = set() | |
groups = {} | |
for target_node in connections: | |
if target_node not in visited: | |
connected_to_target = set() | |
for node in connections: | |
if node not in visited and Day12.is_connected_to(connections, node, target_node): | |
connected_to_target.add(node) | |
visited.add(node) | |
groups[target_node] = connected_to_target | |
visited.add(target_node) | |
return len(groups) | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day11: | |
def __init__(self, input_str: str): | |
self.input = [direction for direction in input_str.split(',')] | |
self.directions = {'n': (0,1,-1), 'ne': (1,0,-1), 'se': (1,-1,0), | |
's': (0,-1,1), 'sw': (-1,0,1), 'nw': (-1,1,0)} | |
@staticmethod | |
def distance_a_b(a: list, b: list): | |
return max(abs(a[0]-b[0]), abs(a[1]-b[1]), abs(a[2]-b[2])) | |
def __walk_hexgrid(self): | |
coordinates = [0,0,0] | |
max_distance = 0 | |
for direction in self.input: | |
coordinates[0] += self.directions[direction][0] | |
coordinates[1] += self.directions[direction][1] | |
coordinates[2] += self.directions[direction][2] | |
max_distance = max(max_distance, Day11.distance_a_b([0,0,0], coordinates)) | |
return Day11.distance_a_b([0,0,0], coordinates), max_distance | |
def solve_all(self): | |
part1, part2 = self.__walk_hexgrid() | |
return [part1, part2] | |
class Day10: | |
def __init__(self, input_str: str): | |
self.input = input_str | |
@staticmethod | |
def knot_hash_iteration(lengths: list, numbers=[i for i in range(256)], current_position=0, skip_size=0) -> (list, int, int): | |
for length in lengths: | |
if current_position + length - len(numbers) < 0: | |
numbers[current_position:current_position+length] = list(reversed(numbers[current_position:current_position+length])) | |
else: | |
r = list(reversed(numbers[current_position:len(numbers)] + numbers[0:(current_position + length) % len(numbers)])) | |
numbers[current_position:len(numbers)] = r[0:len(numbers) - current_position] | |
numbers[0:(current_position + length) % len(numbers)] = r[len(numbers) - current_position:] | |
current_position = (current_position + length + skip_size) % len(numbers) | |
skip_size += 1 | |
return numbers, current_position, skip_size | |
@staticmethod | |
def knot_hash(input): | |
lengths = [ord(c) for c in input] + [17, 31, 73, 47, 23] | |
numbers = [i for i in range(256)] | |
current_position, skip_size = 0, 0 | |
for i in range(64): | |
numbers, current_position, skip_size = Day10.knot_hash_iteration(lengths, numbers, current_position, skip_size) | |
dense_hash = [reduce(lambda x, y: x^y, numbers[i*16:i*16+16]) for i in range(16)] | |
return ''.join([f'{n:0{2}x}' for n in dense_hash]) | |
def __solve_part_1(self): | |
lengths = [int(n) for n in self.input.split(',')] | |
numbers, _, _ = Day10.knot_hash_iteration(lengths) | |
return numbers[0] * numbers[1] | |
def solve_all(self): | |
return [self.__solve_part_1(), Day10.knot_hash(self.input)] | |
class Day9: | |
def __init__(self, input_str: str): | |
self.input = input_str | |
def __stream_processor(self): | |
scores = [] | |
escaped, garbage = False, False | |
current_score = 0 | |
garbage_count = 0 | |
for character in self.input: | |
# deal with '!' escaping | |
if escaped == True: # was previously escaped | |
escaped = False | |
elif character == '!': | |
escaped = True | |
# deal with garbage groups | |
elif not garbage and character == '<': | |
garbage = True | |
elif character == '>': | |
garbage = False | |
# actual scored groups | |
elif not garbage and character == '{': | |
current_score += 1 | |
elif not garbage and character == '}': | |
scores.append(current_score) | |
current_score -= 1 | |
elif garbage: | |
garbage_count += 1 | |
return sum(scores), garbage_count | |
def solve_all(self): | |
part1, part2 = self.__stream_processor() | |
return [part1, part2] | |
class Day8: | |
def __init__(self, input_str: str): | |
self.input = [line.split(' ') for line in input_str.split('\n')] | |
def __process_jumps(self): | |
registers = collections.defaultdict(int) | |
max_anytime = 0 | |
for line in self.input: | |
if eval(f"registers['{line[4]}'] {line[5]} {line[6]}"): | |
if line[1] == 'inc': | |
registers[line[0]] += int(line[2]) | |
if line[1] == 'dec': | |
registers[line[0]] -= int(line[2]) | |
max_anytime = max(max_anytime, registers[line[0]]) | |
return max(registers.values()), max_anytime | |
def solve_all(self): | |
part1, part2 = self.__process_jumps() | |
return [part1, part2] | |
class Day7: | |
def __init__(self, input_str: str): | |
self.input = [line.replace(',','').split(' ') for line in input_str.split('\n')] | |
def __solve_part_1(self): | |
nodes = set() | |
in_tower = set() | |
for line in self.input: | |
nodes.add(line[0]) | |
if '->' in line: | |
for node in line[3:]: | |
in_tower.add(node) | |
return (nodes - in_tower).pop() | |
def __tower_weight(self, disc): | |
total_weight = self.node_weights[disc] | |
for tower in self.towers[disc]: | |
total_weight += self.__tower_weight(tower) | |
return total_weight | |
def __solve_part_2(self): | |
self.towers = {} # {str: [str]}: dependency tree | |
self.node_weights = {} # {str: int} weights of single nodes | |
# make the dependency tree and take note of node weights | |
for line in self.input: | |
tower_base = line[0] | |
self.node_weights[tower_base] = int(line[1][1:-1]) | |
self.towers[tower_base] = [] | |
if len(line) > 2: | |
for node in line[3:]: | |
self.towers[tower_base].append(node) | |
# find unbalanced towers | |
unbalanced_towers = set() | |
for tower in self.towers: | |
on_disc = self.towers[tower] | |
if len(on_disc) > 1: | |
disc_weights = set() | |
for node in on_disc: | |
disc_weights.add(self.__tower_weight(node)) | |
if len(disc_weights) != 1: | |
unbalanced_towers.add(tower) | |
# find the topmost unbalanced tower (since changing the ones below it won't balance it) | |
for tower in unbalanced_towers: | |
if len(set(self.towers[tower]) & unbalanced_towers) == 0: | |
offending_tower = tower | |
# make a dict of the children and their tower weights | |
children_weights = {} | |
for child in self.towers[offending_tower]: | |
children_weights[child] = self.__tower_weight(child) | |
# compute the unbalanced_child, the one with a weight that is only once in children_weights.values() | |
for child in self.towers[offending_tower]: | |
if list(children_weights.values()).count(children_weights[child]) == 1: | |
unbalanced_child = child | |
# get the balanced weight by first removing the unbalanced weight from the dict | |
unbalanced_weight = children_weights[unbalanced_child] | |
del children_weights[unbalanced_child] | |
balanced_weight = set(children_weights.values()).pop() | |
correction = unbalanced_weight - balanced_weight | |
#print(f'{unbalanced_child} has {self.node_weights[unbalanced_child]} but should have {self.node_weights[unbalanced_child] - correction}') | |
return self.node_weights[unbalanced_child] - correction | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day6: | |
def __init__(self, input_str: str): | |
self.input = [int(n) for n in input_str.split('\t')] | |
def __redistribute_memory(self): | |
memory, memory_size = self.input, len(self.input) | |
previous_states = [] | |
while str(memory) not in previous_states: | |
previous_states.append(str(memory)) | |
max_i, max_bank = max(enumerate(memory), key=lambda entry: entry[1]) | |
memory[max_i] = 0 | |
for i in range(max_bank): | |
memory[(max_i+1+i) % memory_size] += 1 | |
return len(previous_states), len(previous_states) - previous_states.index(str(memory)) | |
def solve_all(self): | |
part1, part2 = self.__redistribute_memory() | |
return [part1, part2] | |
class Day5: | |
def __init__(self, input_str: str): | |
self.input = [int(offset) for offset in input_str.split('\n')] | |
@staticmethod | |
def __general_jumps(offsets, advanced_mode=False): | |
offsets_length = len(offsets) | |
total_moves = 0 | |
instruction_register = 0 | |
while instruction_register >= 0 and instruction_register < offsets_length: | |
current_offset = offsets[instruction_register] | |
if advanced_mode == True and current_offset >= 3: | |
offsets[instruction_register] = current_offset - 1 | |
else: | |
offsets[instruction_register] = current_offset + 1 | |
instruction_register += current_offset | |
total_moves += 1 | |
return total_moves | |
def solve_all(self): | |
return [self.__general_jumps(self.input[:]), | |
self.__general_jumps(self.input[:], advanced_mode=True)] | |
class Day4: | |
def __init__(self, input_str: str): | |
self.input = [passphrase for passphrase in input_str.split('\n')] | |
@staticmethod | |
def __count_unique(passphrase_list, transform=lambda word: word): | |
count = 0 | |
for passphrase in passphrase_list: | |
word_list = passphrase.split(' ') | |
word_set = set() | |
for word in word_list: | |
word_set.add(transform(word)) | |
if len(word_set) == len(word_list): | |
count += 1 | |
return count | |
def solve_all(self): | |
return [self.__count_unique(self.input), | |
self.__count_unique(self.input, lambda word: ''.join(sorted(word)))] | |
class Day3: | |
def __init__(self, input_str: str): | |
self.input = int(input_str) | |
@staticmethod | |
def __in_loop(n): | |
return (sqrt(n-1)+1)//2 | |
@staticmethod | |
def __side_of_loop(L): | |
return 1+2*L | |
@staticmethod | |
def __end_of_loop(L): | |
return (Day3.__side_of_loop(L))**2 | |
def __solve_part_1(self): | |
n = self.input | |
if n == 1: | |
return 0 | |
loop = self.__in_loop(n) | |
side_len = self.__side_of_loop(loop) - 1 | |
start_of_loop = self.__end_of_loop(loop-1) + 1 | |
on_side = (n - start_of_loop) // side_len | |
position_on_side = ((n - start_of_loop) % side_len) + 1 | |
if on_side == 0: | |
x, y = loop, -loop + position_on_side | |
if on_side == 1: | |
x, y = loop - position_on_side, loop | |
if on_side == 2: | |
x, y = -loop, loop - position_on_side | |
if on_side == 3: | |
x, y = -loop + position_on_side, -loop | |
return abs(x)+abs(y) | |
def __real_positions(self, x, y): | |
return x+self.grid_side//2, y+self.grid_side//2 | |
def __get_grid(self, x, y): | |
real_x, real_y = self.__real_positions(x, y) | |
return self.grid[real_y][real_x] | |
def __set_grid(self, x, y, value): | |
real_x, real_y = self.__real_positions(x, y) | |
self.grid[real_y][real_x] = value | |
def __get_next_position(self, x, y): | |
if (x >= 0 and y >= 0) and x == y: # upper right corner | |
self.speed_x, self.speed_y = -1, 0 | |
if (x <= 0 and y >= 0) and -x == y: # upper left corner | |
self.speed_x, self.speed_y = 0, -1 | |
if (x <= 0 and y <= 0) and x == y: # lower left corner | |
self.speed_x, self.speed_y = 1, 0 | |
if (x >= 0 and y <= 0) and x == -y+1: # lower right corner | |
self.speed_x, self.speed_y = 0, 1 | |
return x + self.speed_x, y + self.speed_y | |
def __sum_adjacent(self, x, y): | |
sum = 0 | |
sum += self.__get_grid(x-1, y-1) | |
sum += self.__get_grid(x-1, y) | |
sum += self.__get_grid(x-1, y+1) | |
sum += self.__get_grid(x, y-1) | |
sum += self.__get_grid(x, y+1) | |
sum += self.__get_grid(x+1, y-1) | |
sum += self.__get_grid(x+1, y) | |
sum += self.__get_grid(x+1, y+1) | |
return sum | |
def __solve_part_2(self): | |
self.grid_side = int(sqrt(self.input)) | |
self.grid = [[0]*self.grid_side for i in range(self.grid_side)] | |
x, y = 0, 0 | |
self.speed_x, self.speed_y = 1, 0 | |
current = 1 | |
while current < self.input: | |
self.__set_grid(x, y, current) | |
x, y = self.__get_next_position(x, y) | |
current = self.__sum_adjacent(x, y) | |
return current | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day2: | |
def __init__(self, input_str: str): | |
self.input = [[int(n) for n in input_row.split('\t')] for input_row in input_str.split('\n')] | |
def __solve_part_1(self): | |
checksum = 0 | |
for row in self.input: | |
checksum += max(row) - min(row) | |
return checksum | |
def __solve_part_2(self): | |
checksum = 0 | |
for row in self.input: | |
for i, n1 in enumerate(row): | |
for n2 in row[i+1:]: | |
if max([n1, n2]) % min([n1, n2]) == 0: | |
checksum += max([n1, n2]) // min([n1, n2]) | |
break | |
return checksum | |
def solve_all(self): | |
return [self.__solve_part_1(), self.__solve_part_2()] | |
class Day1: | |
def __init__(self, input_str: str): | |
self.input = [int(n) for n in input_str] | |
def __solve_general(self, step_size: int): | |
total = 0 | |
for position, number in enumerate(self.input): | |
lookahead_position = (position + step_size) % len(self.input) | |
if number == self.input[lookahead_position]: | |
total += number | |
return total | |
def solve_all(self): | |
return [self.__solve_general(-1), self.__solve_general(len(self.input)//2)] | |
########################### | |
### BEWARE, MAGIC BELOW ### | |
########################### | |
import requests | |
import datetime | |
import json | |
import sys, inspect | |
# Put all 'SOLVER_CLASS_PREFIX{N}' classes into a SOLVER_CLASSES list | |
SOLVER_CLASSES = {} | |
class_list = inspect.getmembers(sys.modules[__name__], inspect.isclass) | |
ordered_class_list = sorted(class_list, key=lambda class_obj: int(class_obj[0][len(SOLVER_CLASS_PREFIX):])) | |
for class_object in ordered_class_list: | |
if class_object[0].startswith(SOLVER_CLASS_PREFIX): | |
SOLVER_CLASSES[class_object[0]] = class_object[1] | |
if __name__ == '__main__': | |
# Get the session cookie | |
try: | |
with open(SESSION_FILE, 'r') as session_file: | |
SESSION_COOKIE = session_file.readline().rstrip() | |
except FileNotFoundError: | |
print('Please login to "https://adventofcode.com", and get your session cookie from developer tools -> storage -> session cookie -> value') | |
print('You can also store it in a file and run "python3 advent_of_code_2017.py < session.txt"') | |
SESSION_COOKIE = input('Session cookie value: ') | |
# Calculate the daily puzzles already released | |
latest_day = datetime.date.today().day if datetime.date.today() < datetime.date(2017, 12, 25) else 25 | |
# Check for existing inputs | |
try: | |
with open(INPUTS_FILE, 'r') as inputs_file: | |
inputs = json.load(inputs_file) | |
except Exception: | |
print(f'No input file found at {INPUTS_FILE}') | |
inputs = {} | |
have_until_input = len(inputs) | |
# Fetch all missing puzzle inputs | |
if latest_day > have_until_input: | |
for i in range(have_until_input + 1, latest_day + 1): | |
print('fetching input for day ', i) | |
url = f'https://adventofcode.com/2017/day/{i}/input' | |
inputs[f'{SOLVER_CLASS_PREFIX}{i}'] = requests.get(url, cookies={'session': SESSION_COOKIE}).text.rstrip() | |
# Check for existing solutions | |
try: | |
with open(SOLUTIONS_FILE, 'r') as solutions_file: | |
solutions = json.load(solutions_file) | |
except Exception: | |
print(f'No solutions file found at {SOLUTIONS_FILE}') | |
solutions = {} | |
# Solve all released days without a solution + the current day | |
for name, solver in SOLVER_CLASSES.items(): | |
if name not in solutions: | |
solutions[name] = solver(inputs[name]).solve_all() | |
# Print solutions | |
for name, solution in solutions.items(): | |
if solution: | |
print(f'{name}:\n - part 1: {solution[0]}\n - part 2: {solution[1]}') | |
# Update the inputs and solutions files | |
with open(INPUTS_FILE, 'w') as inputs_file: | |
json.dump(inputs, inputs_file) | |
with open(SOLUTIONS_FILE, 'w') as solutions_file: | |
json.dump(solutions, solutions_file) |
Yeah that level
POST param is really confusing. Does it mean there will at some point be another set of days as a separate level?
..Actually the level seems to be the part of the question for that day.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
If I want to make an auto submit later:
http://adventofcode.com/2017/day/1/answer
POST
level=1&answer=2
already completed: You don't seem to be solving the right level. Did you already complete it?
wrong answer: That's not the right answer.
wrong level+url: You don't seem to be solving the right level. Did you already complete it?
wrong session key or logged out: To play, please identify yourself via one of these services:
too fast: You gave an answer too recently; you have to wait after submitting an answer before trying again.
right answer: That's the right answer!