In [1]:
import sys
import os
import re
import collections
import itertools
import math
import copy
import bcolz
import pickle
import numpy as np
import pandas as pd
import gc
import random
import smart_open
import h5py
import csv
import tensorflow as tf
import gensim
import string
import datetime as dt
from tqdm import tqdm_notebook as tqdm
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
plt.style.use('seaborn-poster')
import seaborn as sns
random_state_number = 967898
In [163]:
! cat day13_input.txt
In [3]:
input_data = {}
with open("day13_input.txt") as f:
for line in f.read().strip().split("\n"):
k,v = (p for p in line.split(":"))
input_data[int(k)] = int(v)
len(input_data)
Out[3]:
Brute Force Solution where we are updating all the scanners as per the time step
In [208]:
def update_scanner_depths(scanner_pos,scanner_depths):
for d in scanner_depths:
scanner_pos[d][0] += scanner_pos[d][1]
if (scanner_pos[d][0] == scanner_depths[d]-1 or scanner_pos[d][0] == 0):
scanner_pos[d][1] *= -1
def scanner_severity_bf(scanner_depths):
"""
given scanner depths find serverity
"""
# dict holding the current depth and the inc/dec flag
# once it reached bottom or top flag multiplies by -1, thus rotating
scanner_pos = {k:[0,1] for k in scanner_depths.keys()}
# since we always get caught first
caughts = []
# going thru each pico second thru each scanner
# if scanner find us in place, we are not caught
# cur_pos is same as current time
total_time_range = max(scanner_depths.keys()) + 1
for cur_time in range(total_time_range):
# when the cur_pos that indicates the
# scanner caught us, its index will be top one i.e, 0
if cur_time in scanner_depths.keys() and scanner_pos[cur_time][0] == 0:
caughts += [(cur_time, scanner_depths[cur_time])]
# update scanner depths
update_scanner_depths(scanner_pos,scanner_depths)
return sum([a*b for a,b in caughts])
one could notice that we are interested only in the 0th position not others, lets say the depth is 3. the channel would be tracking as
depth 3
time 0 1 2 3 4 5 6 7 8 9
position 0 1 2 1 0 1 2 1 0 1
one could notice the 0s are always occuring at timesteps that are multiple of 4. can we generalize this pattern
depth: 2
time 0 1 2 3 4 5 6 7 8 9
position 0 1 0 1 0 1 0 1 0 1
depth: 4
time 0 1 2 3 4 5 6 7 8 9
position 0 1 2 3 2 1 0 1 2 3
its (depth - 1)*2
In [209]:
def scanner_severity(scanner_depths):
severity = 0
# here sc_id is also time
for sc_id_time, depth in scanner_depths.items():
if sc_id_time % ((depth - 1)*2) == 0:
severity += (sc_id_time * depth)
return severity
In [212]:
sample_depths = {0:3, 1:2, 4:4, 6:4}
assert scanner_severity(sample_depths) == 24
In [213]:
scanner_severity(input_data)
Out[213]:
In [215]:
def escaped_scanners_bf(scanner_depths):
caught = True
delay_time = 0
while caught:
# dict holding the current depth and the inc/dec flag
# once it reached bottom or top flag multiplies by -1, thus rotating
scanner_pos = {k:[0,1] for k in scanner_depths.keys()}
caught = False
# run for the delayed time
for i in range(delay_time):
update_scanner_depths(scanner_pos,scanner_depths)
# go thru the scanners now
total_time_range = max(scanner_depths.keys()) + 1
for cur_time in range(total_time_range):
# when the cur_pos that indicates the
# scanner caught us, its index will be top one i.e, 0
# print("---b4 ",cur_time+10,scanner_pos)
if cur_time in scanner_depths.keys() and scanner_pos[cur_time][0] == 0:
# print("---caught---",cur_time,scanner_pos[cur_time])
caught = True
delay_time += 1
break
# update scanner depths
update_scanner_depths(scanner_pos,scanner_depths)
# print("---aftr",cur_time+10,scanner_pos)
# successfully ran thru without getting caught
# print("=====================",delay_time)
if not caught:
break
return delay_time
In [232]:
def escaped_scanners(scanner_depths):
delay_time = 0
caught = True
while caught:
caught = False
for sc_id_time,depth in scanner_depths.items():
if (sc_id_time + delay_time) % ((depth-1)*2) == 0:
caught = True
delay_time += 1
break
if not caught:
break
return delay_time
In [233]:
assert escaped_scanners_bf(sample_depths) == 10
assert escaped_scanners(sample_depths) == 10
In [234]:
escaped_scanners(input_data)
Out[234]:
In [243]:
(1,1,"u")[:2]
Out[243]:
In [112]:
input_data = 'ffayrhll'
sample_data = 'flqrgnkx'
In [114]:
bit_map = {
0:0, 1:1, 2:1, 3:2,
4:1, 5:2, 6:2, 7:3,
8:1, 9:2, 10:2, 11:3,
12:2, 13:3, 14:3, 15:4
}
def count_bits(hex_string):
nof1s = 0
# print("----",hex_string)
for hex_ch in hex_string:
nof1s += bit_map[int(hex_ch, 16)]
return nof1s
In [121]:
def square_fragment_bits(data):
fragment_bits = []
for i in range(0,128):
hash_str = data + "-" + str(i)
fragment_bits += [knot_hash(hash_str)]
return fragment_bits
def number_of_square_fragments(data):
nofsquares = 0
for hash_str in square_fragment_bits(data):
nofsquares += sum(bin(int(ch, 16))[2:].count('1') for ch in hash_str)
return nofsquares
In [122]:
number_of_square_fragments(sample_data) == 8108
Out[122]:
In [123]:
number_of_square_fragments(input_data)
Out[123]:
In [263]:
def mark_regions(data, r, c, region):
if r > 127 or r < 0 or c > 127 or c < 0:
return
if data[r][c] == 1:
# mark
data[r][c] = region
# recurse near by squares
mark_regions(data, r+1, c, region)
mark_regions(data, r-1, c, region)
mark_regions(data, r, c-1, region)
mark_regions(data, r, c+1, region)
def count_regions(data):
fragment_bits = square_fragment_bits(data)
bit_strings = []
# lets make 128 x 128 bit strings
for hash_str in fragment_bits:
bit_string = bin(int(hash_str, 16))[2:]
bit_string = "".join(['0']*(128-len(bit_string))) + bit_string
bit_strings += [list(map(int,bit_string))]
# go thru each square
regions = 2
for r in range(0,128):
for c in range(0,128):
if bit_strings[r][c] == 1:
mark_regions(bit_strings, r, c, regions)
regions += 1
return regions - 2
In [264]:
sys.getrecursionlimit()
Out[264]:
In [265]:
count_regions(sample_data) == 1242
Out[265]:
In [266]:
count_regions(input_data)
Out[266]:
input_data
Generator A starts with 512
Generator B starts with 191
In [3]:
gen_A_input = 512
gen_B_input = 191
gen_A_sample = 65
gen_B_sample = 8921
In [26]:
def generatorA(input_value):
current_value = input_value
while True:
current_value = (16807*current_value) % 2147483647
yield current_value
def generatorB(input_value):
current_value = input_value
while True:
current_value = (48271*current_value) % 2147483647
yield current_value
def num_matches(gena_input, genb_input, rounds=int(4e7)):
matches = 0
gena_output = generatorA(gena_input)
genb_output = generatorB(genb_input)
bits16 = 0xFFFF
for i in range(rounds):
if next(gena_output)&bits16 == next(genb_output)&bits16:
matches += 1
return matches
In [28]:
num_matches(gen_A_sample, gen_B_sample, rounds=5) == 1
num_matches(gen_A_sample, gen_B_sample, rounds=int(4e7)) == 588
Out[28]:
In [29]:
num_matches(gen_A_input, gen_B_input, rounds=int(4e7))
Out[29]:
In [30]:
def generatorA(input_value):
current_value = input_value
while True:
current_value = (16807*current_value) % 2147483647
if current_value % 4 == 0:
yield current_value
def generatorB(input_value):
current_value = input_value
while True:
current_value = (48271*current_value) % 2147483647
if current_value % 8 == 0:
yield current_value
In [32]:
num_matches(gen_A_sample, gen_B_sample, rounds=int(5e6)) == 309
Out[32]:
In [33]:
num_matches(gen_A_input, gen_B_input, rounds=int(5e6))
Out[33]:
In [35]:
! cat day16_input.txt
In [44]:
input_data = None
with open('day16_input.txt') as f:
input_data = list(map(lambda s: (s[0],s[1:]) if s[0] == 's' else (s[0], tuple(s[1:].split('/'))), f.read().strip().split(",")))
In [107]:
def one_dance_move(programs, command, params):
if command == 's':
index = int(params)
programs = programs[-index:] + programs[:-index]
elif command == 'x':
i1,i2 = tuple(map(int, params))
c1, c2 = programs[i1], programs[i2]
programs = programs.replace(c1,'z')
programs = programs.replace(c2,c1)
programs = programs.replace('z',c2)
elif command == 'p':
c1,c2 = params
programs = programs.replace(c1,'z')
programs = programs.replace(c2,c1)
programs = programs.replace('z',c2)
return programs
def danceit1(data, programs=None, length=16):
programs = "".join([chr(ord('a')+i) for i in range(length)]) if programs is None else programs
for command, params in data:
programs = one_dance_move(programs, command, params)
return programs
In [108]:
danceit1([('s','1'),('x',('3','4')),('p',('e','b'))], length=5) == 'baedc'
Out[108]:
In [109]:
danceit1(input_data, length=16)
Out[109]:
In [121]:
def danceit2(data, length=16, rounds=int(1e9)):
programs = "".join([chr(ord('a')+i) for i in range(length)])
# lets find the cycle
hash_map = {}
prev_programs = programs
cycle_round = None
recycled_programs = None
for r in range(rounds):
programs = danceit1(input_data, prev_programs)
if prev_programs in hash_map:
cycle_round = r
recycled_programs = prev_programs
break
hash_map[prev_programs] = programs
prev_programs = programs
# thru inspection we know its the same starting pattern
# 'abcdefghijklmnop' occuring again, hence just harding coding this
# if we need a general program, we need to process hash table to
# figure out the starting and the ending cycle and form the transformation as necessary
programs = "".join([chr(ord('a')+i) for i in range(length)])
for r in range(rounds%cycle_round):
programs = danceit1(input_data, programs)
print("----aftr",programs)
return programs
In [122]:
danceit2(input_data)
Out[122]:
In [4]:
input_data = 348
sample_data = 3
In [24]:
def spin_lock_insert(spin_size, last_insert=2017):
current_insert = 2
current_position = 1
buffer = [0, 1]
while current_insert <= last_insert:
current_len = len(buffer)
# inserting right after current_position
# current_position = current_position + spin_size + 1
# current_position = current_position % current_len if current_position > current_len else current_position
current_position = ((current_position + spin_size) % current_len) + 1
# print("b4",buffer, current_position)
# print("b4",buffer[:current_position],[current_insert],buffer[current_position:])
# buffer = buffer[:current_position] + [current_insert] + buffer[current_position:]
buffer[current_position:current_position] = [current_insert]
current_insert += 1
# print("aftr",buffer, current_position)
# print("------------------------")
return buffer[buffer.index(2017) + 1]
In [25]:
spin_lock_insert(sample_data, last_insert=2017) == 638
Out[25]:
In [26]:
spin_lock_insert(input_data, last_insert=2017)
Out[26]:
In [29]:
def spin_lock_insert2(spin_size):
current_position = 0
insert_at_1 = 1
# current_len is also the current_insert from prev part
for current_len in range(1,int(5e7)+1):
current_position = ((current_position + spin_size) % current_len) + 1
# if we are inserting right after 0
if current_position == 1:
insert_at_1 = current_len
# print("aftr",buffer, current_position)
# print("------------------------")
return insert_at_1
In [30]:
spin_lock_insert2(input_data)
Out[30]:
In [1]:
#!cat day18_input.txt
In [3]:
input_data = None
with open("day18_input.txt") as f:
input_data = [(inst.split()[0],tuple(inst.split()[1:])) for inst in f.read().strip().split("\n")]
len(input_data), input_data[0]
Out[3]:
In [14]:
import operator
def is_digit(n):
try:
int(n)
return True
except ValueError:
return False
def process_instructions1(data):
registers = {}
played = {}
get_register = lambda x: int(x) if is_digit(x) else registers.setdefault(x, 0)
get_played = lambda x: played[x] if x in played else played.setdefault(x, 0)
def get_operator_fn(op):
return {
'set' : lambda x,y: registers.update({x:get_register(y)}) ,
'add' : lambda x,y: registers.update({x:get_register(x) + get_register(y)}) ,
'mul' : lambda x,y: registers.update({x:get_register(x) * get_register(y)}) ,
'mod' : lambda x,y: registers.update({x:get_register(x) % get_register(y)}) ,
'snd' : lambda x: played.update({x:get_register(x)}),
'rcv' : lambda x: get_played(x),
}[op]
current_cmd = None
current_index = 0
last_played_sound = 0
while last_played_sound == 0:
current_cmd, params = data[current_index]
if current_cmd == 'jgz':
if get_register(params[0]) > 0:
current_index += int(params[1])
# print("----", current_index, registers)
continue
else:
output = get_operator_fn(current_cmd)(*params)
# print("----",current_cmd, params, output)
if current_cmd == 'rcv' and output is not None:
last_played_sound = output
# print("----", current_index, registers)
# print("----", current_index, played)
current_index += 1
return last_played_sound
In [15]:
sample_data = """set a 1
add a 2
mul a a
mod a 5
snd a
set a 0
rcv a
jgz a -1
set a 1
jgz a -2
"""
sample_data = [(inst.split()[0],tuple(inst.split()[1:])) for inst in sample_data.strip().split("\n")]
sample_data
Out[15]:
In [16]:
process_instructions1(sample_data) == 4
Out[16]:
In [17]:
process_instructions1(input_data)
Out[17]:
In [82]:
import queue as q
def process_instructions2(data):
registers = {0: {'p':0}, 1:{'p':1}}
status = {0: 'active', 1:'active'} # waiting
current_index = {0: 0, 1:0}
nof_sends = {0: 0, 1:0}
q1 = [] # q.Queue() # send for 0, recv for 1
q2 = [] # q.Queue() # send for 1, recv for 0
queues = {0: (q1, q2), 1: (q2, q1)} # index 0-> send, index 1-> recv
snd_qindex, rcv_qindex = 0,1
# p refers to program id
get_register = lambda p,x: int(x) if is_digit(x) else registers[p].setdefault(x, 0)
def get_operator_fn(p,op):
return {
'set' : lambda x,y: registers[p].update({x:get_register(p,y)}) ,
'add' : lambda x,y: registers[p].update({x:get_register(p,x) + get_register(p,y)}) ,
'mul' : lambda x,y: registers[p].update({x:get_register(p,x) * get_register(p,y)}) ,
'mod' : lambda x,y: registers[p].update({x:get_register(p,x) % get_register(p,y)}) ,
}[op]
pgm_id = 0
while True:
if len(queues[pgm_id][rcv_qindex]) == 0 and status[0] == 'waiting' and status[1] == 'waiting':
# deadlock if both the rcv qs are empty
break
cmd, params = data[current_index[pgm_id]]
# print("--- {}: {} -> {}".format(pgm_id, cmd, params) )
if cmd == 'jgz':
if get_register(pgm_id, params[0]) > 0:
current_index[pgm_id] += get_register(pgm_id, params[1])
continue
elif cmd == 'snd':
queues[pgm_id][snd_qindex].append(get_register(pgm_id, params[0]))
nof_sends[pgm_id] += 1
elif cmd == 'rcv':
if len(queues[pgm_id][rcv_qindex]) == 0:
if status[pgm_id] == 'active':
status[pgm_id] = 'waiting'
pgm_id = 1 - pgm_id # this just oscillates between 0 and 1
continue
else:
val = queues[pgm_id][rcv_qindex].pop(0)
registers[pgm_id].update({params[0]: val})
status[pgm_id] = 'active'
else:
# normal operation non snd/rcv
output = get_operator_fn(pgm_id, cmd)(*params)
current_index[pgm_id] += 1
print("\n---- Done bitches",nof_sends, current_index, list(q1), list(q2))
return nof_sends[1]
In [83]:
sample_data = """snd 1
snd 2
snd p
rcv a
rcv b
rcv c
rcv d
"""
sample_data = [(inst.split()[0],tuple(inst.split()[1:])) for inst in sample_data.strip().split("\n")]
sample_data
Out[83]:
In [84]:
process_instructions2(sample_data)
Out[84]:
In [85]:
process_instructions2(input_data)
Out[85]:
In [87]:
#!cat day19_input.txt
In [2]:
input_data = None
with open("day19_input.txt") as f:
input_data = [ list(line) for line in f.read().split("\n")]
del input_data[-1]
len(input_data), " ".join(map(str,[len(sd) for sd in input_data]))
Out[2]:
In [3]:
sample_input=""" |
| +--+
A | C
F---|----E|--+
| | | D
+B-+ +--+
"""
sample_data = [ list(line) for line in sample_input.split("\n")]
del sample_data[-1]
len(sample_data), [len(sd) for sd in sample_data]
Out[3]:
In [19]:
def traverse_path1(data):
cur_row_col = (0,0) # row, col
for i,ch in enumerate(data[0]):
if ch == '|':
cur_row_col = (0,i)
# print("----start",cur_row_col)
update_dir = {
'up': (-1,0),
'down': (1,0),
'right': (0,1),
'left': (0,-1)
}
mirror_dir = {
'up': 'down',
'down': 'up',
'right': 'left',
'left': 'right'
}
tuple_sum = lambda t1,t2: (t1[0]+t2[0], t1[1]+t2[1])
def next_rc(cur_rc, cur_d):
ch = data[cur_rc[0]][cur_rc[1]]
# print("---",cur_rc, ch)
if str.isalpha(ch):
cur_rc = tuple_sum(cur_rc,update_dir[cur_d])
return (cur_rc, cur_d, ch)
elif ch == '|':
new_rc = tuple_sum(cur_rc,update_dir[cur_d])
if data[new_rc[0]][new_rc[1]] == '-':
new_rc = tuple_sum(new_rc,update_dir[cur_d])
return (new_rc, cur_dir, None)
elif ch == '-':
new_rc = tuple_sum(cur_rc,update_dir[cur_d])
if data[new_rc[0]][new_rc[1]] == '|':
new_rc = tuple_sum(new_rc,update_dir[cur_d])
return (new_rc, cur_dir, None)
elif ch == '+':
# print(list(set(update_dir.keys())-set([cur_d])))
for d in list(set(update_dir.keys())-set([mirror_dir[cur_d]])):
rc = tuple_sum(cur_rc,update_dir[d])
if data[rc[0]][rc[1]] != " ":
return (rc, d, None)
return (None, None, None)
cur_dir = 'down'
letters = ""
while True:
(cur_row_col,cur_dir,letter) = next_rc(cur_row_col,cur_dir)
# print((cur_row_col,cur_dir,letter))
letters += "" if letter is None else letter
if cur_dir == None:
break
# print("----", letters)
return letters
In [20]:
assert traverse_path1(sample_data) == 'ABCDEF'
In [21]:
traverse_path1(input_data)
Out[21]:
In [34]:
def traverse_path2(data):
cur_row_col = (0,0) # row, col
for i,ch in enumerate(data[0]):
if ch == '|':
cur_row_col = (0,i)
# print("----start",cur_row_col)
update_dir = {
'up': (-1,0),
'down': (1,0),
'right': (0,1),
'left': (0,-1)
}
mirror_dir = {
'up': 'down',
'down': 'up',
'right': 'left',
'left': 'right'
}
tuple_sum = lambda t1,t2: (t1[0]+t2[0], t1[1]+t2[1])
steps = 0
def next_rc(cur_rc, cur_d):
nonlocal steps
ch = data[cur_rc[0]][cur_rc[1]]
# print("---",cur_rc, ch)
if str.isalpha(ch):
cur_rc = tuple_sum(cur_rc,update_dir[cur_d])
steps += 1
return (cur_rc, cur_d, ch)
elif ch == '|':
new_rc = tuple_sum(cur_rc,update_dir[cur_d])
steps += 1
if data[new_rc[0]][new_rc[1]] == '-':
new_rc = tuple_sum(new_rc,update_dir[cur_d])
steps += 1
return (new_rc, cur_dir, None)
elif ch == '-':
new_rc = tuple_sum(cur_rc,update_dir[cur_d])
steps += 1
if data[new_rc[0]][new_rc[1]] == '|':
new_rc = tuple_sum(new_rc,update_dir[cur_d])
steps += 1
return (new_rc, cur_dir, None)
elif ch == '+':
# print(list(set(update_dir.keys())-set([cur_d])))
for d in list(set(update_dir.keys())-set([mirror_dir[cur_d]])):
rc = tuple_sum(cur_rc,update_dir[d])
if data[rc[0]][rc[1]] != " ":
steps += 1
return (rc, d, None)
return (None, None, None)
cur_dir = 'down'
letters = ""
while True:
(cur_row_col,cur_dir,letter) = next_rc(cur_row_col,cur_dir)
# print((cur_row_col,cur_dir,letter))
letters += "" if letter is None else letter
if cur_dir == None:
break
# print("----", letters)
return steps
In [36]:
assert traverse_path2(sample_data) == 38
In [37]:
traverse_path2(input_data)
Out[37]:
In [42]:
#!cat day20_input.txt
In [42]:
input_data = {}
with open("day20_input.txt") as f:
i = 0
for line in f.read().strip().split("\n"):
m = re.match("p=<([-]*\d+,[-]*\d+,[-]*\d+)>,\s*v=<([-]*\d+,[-]*\d+,[-]*\d+)>,\s*a=<([-]*\d+,[-]*\d+,[-]*\d+)>\s*", line)
input_data[i] = {'p':list(map(int, m.group(1).split(','))),
'v':list(map(int, m.group(2).split(','))),
'a':list(map(int, m.group(3).split(',')))}
i += 1
len(input_data), input_data[2]
Out[42]:
In [96]:
def swarm_particles1(data_in, simulation_length=5000):
data = data_in.copy()
def update_new_positions():
nonlocal data
for i,particle in data.items():
# update velocity
particle['v'][0] += particle['a'][0]
particle['v'][1] += particle['a'][1]
particle['v'][2] += particle['a'][2]
# update position
particle['p'][0] += particle['v'][0]
particle['p'][1] += particle['v'][1]
particle['p'][2] += particle['v'][2]
def find_nearest_using_manhattan():
nonlocal data
min_dist = float('inf')
nearest_particle = None
for i,particle in data.items():
dist = sum(list(map(abs, particle['p'])))
if min_dist > dist:
min_dist = dist
nearest_particle = i
return nearest_particle
# simulation particle movement
for i in range(simulation_length):
update_new_positions()
return find_nearest_using_manhattan()
In [97]:
sample_data = {
0:{'a': [3,0,0], 'p': [2,0,0], 'v': [-1,0,0]},
1:{'a': [4,0,0], 'p': [0,0,0], 'v': [-2,0,0]}
}
In [98]:
assert swarm_particles1(sample_data) == 0
In [99]:
swarm_particles1(input_data)
Out[99]:
In [36]:
def swarm_particles2(data_in, simulation_length=5000):
data = copy.deepcopy(data_in)
def update_positions_filter_collisions():
nonlocal data
inv_p_dict = {}
colliding_particles = set()
for i,particle in data.items():
# update velocity
particle['v'][0] += particle['a'][0]
particle['v'][1] += particle['a'][1]
particle['v'][2] += particle['a'][2]
# update position
particle['p'][0] += particle['v'][0]
particle['p'][1] += particle['v'][1]
particle['p'][2] += particle['v'][2]
p = tuple(particle['p'])
# current positions
if p not in inv_p_dict:
inv_p_dict[p] = i
else:
colliding_particles.add(i)
colliding_particles.add(inv_p_dict[p])
# filter colliding particles
for i in colliding_particles:
del data[i]
# simulation particle movement
for i in range(simulation_length):
update_positions_filter_collisions()
return len(data)
In [37]:
sample_data = {
0: {'p': [-6,0,0], 'v': [3,0,0], 'a': [0,0,0]},
1: {'p': [-4,0,0], 'v': [2,0,0], 'a': [0,0,0]},
2: {'p': [-2,0,0], 'v': [1,0,0], 'a': [0,0,0]},
3: {'p': [ 3,0,0], 'v': [1,0,0], 'a': [0,0,0]}
}
In [40]:
# assert swarm_particles2(sample_data) == 1
swarm_particles2(sample_data)
Out[40]:
In [43]:
swarm_particles2(input_data)
Out[43]:
In [ ]:
!cat day21_input.txt
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [2]:
#!cat day22_input.txt
In [134]:
input_data = []
with open("day22_input.txt") as f:
i = 0
input_data = [list(line) for line in f.read().strip().split("\n")]
len(input_data), len(input_data[0])
Out[134]:
In [143]:
def virus_burst1(data, bursts=10000):
grid_size = bursts//4
# lets place extra space around the data on sides
grid = [['.']*(grid_size) + data[i] + ['.']*(grid_size) for i in range(len(data)) ]
# lets place extra space around the data on top and bottom
grid = [['.' for _ in range(len(grid[0]))] for _ in range(grid_size)] + grid
grid += [['.' for _ in range(len(grid[0]))] for _ in range(grid_size)]
# find the starting point
cur_row, cur_col, cur_dir = len(grid)//2, len(grid[0])//2, 'up'
# direction update dictionary
directions = {
'up' : {'left':(0,-1,'left'), 'right':(0,1,'right')},
'down' : {'left':(0,1,'right'), 'right':(0,-1,'left')},
'left' : {'left':(1,0,'down'), 'right':(-1,0,'up')},
'right': {'left':(-1,0,'up'), 'right':(1,0,'down')}
}
move = lambda rcd,d: (rcd[0]+directions[rcd[2]][d][0], rcd[1]+directions[rcd[2]][d][1], directions[rcd[2]][d][2])
infections = 0
for burst in range(bursts):
# print("\n ----- ",burst,"\n")
# print("cur_row, cur_col, cur_dir",cur_row, cur_col, cur_dir)
# print("\n".join(["".join(p) for p in grid]))
# non infected
if grid[cur_row][cur_col] == '.':
# print("moving left")
infections += 1
grid[cur_row][cur_col] = '#'
(cur_row,cur_col, cur_dir) = move((cur_row,cur_col, cur_dir), 'left')
else: # infected
# print("moving right")
grid[cur_row][cur_col] = '.'
(cur_row,cur_col, cur_dir) = move((cur_row,cur_col, cur_dir), 'right')
return infections
In [144]:
sample_data = [['.','.','#'],['#','.','.'],['.','.','.']]
In [145]:
assert virus_burst1(sample_data, bursts=10000) == 5587
In [146]:
virus_burst1(input_data, bursts=10000)
Out[146]:
In [161]:
def virus_burst2(data, bursts=10000):
grid_size = 10000 #bursts//4
# lets place extra space around the data on sides
grid = [['.']*(grid_size) + data[i] + ['.']*(grid_size) for i in range(len(data)) ]
# lets place extra space around the data on top and bottom
grid = [['.' for _ in range(len(grid[0]))] for _ in range(grid_size)] + grid
grid += [['.' for _ in range(len(grid[0]))] for _ in range(grid_size)]
# find the starting point
cur_row, cur_col, cur_dir = len(grid)//2, len(grid[0])//2, 'up'
# direction update dictionary
cids = {
'up' : {'left':(0,-1,'left'), 'right':(0,1,'right')},
'down' : {'left':(0,1,'right'), 'right':(0,-1,'left')},
'left' : {'left':(1,0,'down'), 'right':(-1,0,'up')},
'right': {'left':(-1,0,'up'), 'right':(1,0,'down')}
}
wfds = {
'w': {
'up' : (-1,0,'up'),
'down' : (1,0,'down'),
'left' : (0,-1,'left'),
'right': (0,1,'right')
},
'f': {
'up' : (1,0,'down'),
'down' : (-1,0,'up'),
'left' : (0,1,'right'),
'right': (0,-1,'left')
}
}
move_ci = lambda r,c,d,t: (r+cids[d][t][0], c+cids[d][t][1], cids[d][t][2])
move_wf = lambda r,c,d,s: (r+wfds[s][d][0], c+wfds[s][d][1], wfds[s][d][2])
infections = 0
for burst in range(bursts):
# print("\n ----- ",burst,"\n")
# print("cur_row, cur_col, cur_dir",cur_row, cur_col, cur_dir)
# print("\n".join(["".join(p) for p in grid]))
if grid[cur_row][cur_col] == '.': # clean
# print("moving left")
grid[cur_row][cur_col] = 'w'
(cur_row,cur_col, cur_dir) = move_ci(cur_row, cur_col, cur_dir, 'left')
elif grid[cur_row][cur_col] == 'w': # weakened
# print("no turn moving left")
infections += 1
grid[cur_row][cur_col] = '#'
(cur_row,cur_col, cur_dir) = move_wf(cur_row, cur_col, cur_dir, 'w')
elif grid[cur_row][cur_col] == '#': # infected
# print("moving right")
grid[cur_row][cur_col] = 'f'
(cur_row,cur_col, cur_dir) = move_ci(cur_row, cur_col, cur_dir, 'right')
else: # flagged
# print("reverses moving right")
grid[cur_row][cur_col] = '.'
(cur_row,cur_col, cur_dir) = move_wf(cur_row, cur_col, cur_dir, 'f')
return infections
In [162]:
sample_data = [['.','.','#'],['#','.','.'],['.','.','.']]
In [163]:
assert virus_burst2(sample_data, bursts=100) == 26
assert virus_burst2(sample_data, bursts=10000000) == 2511944
In [164]:
virus_burst2(input_data, bursts=10000000)
Out[164]:
In [ ]:
# !cat day23_input.txt
In [52]:
input_data = None
with open("day23_input.txt") as f:
input_data = [(inst.split()[0],tuple(inst.split()[1:])) for inst in f.read().strip().split("\n")]
len(input_data), input_data
Out[52]:
In [46]:
import operator
def is_digit(n):
try:
int(n)
return True
except ValueError:
return False
def coprocessing1(data):
registers = {}
played = {}
get_register = lambda x: int(x) if is_digit(x) else registers.setdefault(x, 0)
get_played = lambda x: played[x] if x in played else played.setdefault(x, 0)
def get_operator_fn(op):
return {
'set' : lambda x,y: registers.update({x:get_register(y)}) ,
'sub' : lambda x,y: registers.update({x:get_register(x) - get_register(y)}) ,
'mul' : lambda x,y: registers.update({x:get_register(x) * get_register(y)}) ,
}[op]
current_cmd = None
current_index = 0
nof_muls = 0
while current_index < len(data):
current_cmd, params = data[current_index]
print("----", current_index, current_cmd, params, registers)
if current_cmd == 'mul':
nof_muls += 1
if current_cmd == 'jnz':
if get_register(params[0]) != 0:
current_index += int(params[1])
#print("----", current_index, registers)
continue
else:
get_operator_fn(current_cmd)(*params)
current_index += 1
return nof_muls
In [47]:
sample_data = """set a 1
sub a 2
mul a a
set a 0
jnz a -1
set a 0
mul a a
jnz a -2
"""
sample_data = [(inst.split()[0],tuple(inst.split()[1:])) for inst in sample_data.strip().split("\n")]
sample_data
Out[47]:
In [48]:
coprocessing1(sample_data)
Out[48]:
In [49]:
coprocessing1(input_data)
Out[49]:
In [62]:
import operator
def is_digit(n):
try:
int(n)
return True
except ValueError:
return False
def coprocessing2(data):
registers = {'a':1}
played = {}
get_register = lambda x: int(x) if is_digit(x) else registers.setdefault(x, 0)
get_played = lambda x: played[x] if x in played else played.setdefault(x, 0)
def get_operator_fn(op):
return {
'set' : lambda x,y: registers.update({x:get_register(y)}) ,
'sub' : lambda x,y: registers.update({x:get_register(x) - get_register(y)}) ,
'mul' : lambda x,y: registers.update({x:get_register(x) * get_register(y)}) ,
}[op]
current_cmd = None
# at current index 20
# registers = {'a': 1, 'b': 108400, 'c': 125400, 'f': 1, 'd': 2, 'e': 108400, 'g': 0}
# current_index = 20
# at current index 25
registers = {'a': 1, 'b': 108400, 'c': 125400, 'f': 1, 'd': 108400, 'e': 108400, 'g': 0}
current_index = 25
while current_index < len(data):
current_cmd, params = data[current_index]
print("----", current_index, current_cmd, params, registers)
if current_cmd == 'jnz':
if get_register(params[0]) != 0:
current_index += int(params[1])
#print("----", current_index, registers)
continue
else:
get_operator_fn(current_cmd)(*params)
current_index += 1
return registers['h']
In [65]:
# coprocessing2(input_data)
In [68]:
count = 0
for num in range(108400,125400 + 1, 17):
for i in range(2,num):
if (num % i) == 0:
count += 1
break
print(count)
In [3]:
# !cat day24_input.txt
In [2]:
input_data = []
with open("day24_input.txt") as f:
for line in f.read().strip().split("\n"):
input_data += [list(map(int,line.strip().split('/')))]
len(input_data)
# input_data
Out[2]:
In [13]:
sample_input ="""0/2
2/2
2/3
3/4
3/5
0/1
10/1
9/10"""
sample_data = []
for line in sample_input.strip().split("\n"):
sample_data += [list(map(int,line.strip().split('/')))]
sample_data
Out[13]:
In [14]:
def emMoat1(components, last_port):
max_strength = 0
bridge = []
max_strength_bridge = []
for i, component in enumerate(components):
if component[0] == last_port or component[1] == last_port:
new_components = components[:i]+components[i+1:]
new_last_port = component[0] if component[1] == last_port else component[1]
bridge = component + emMoat1(new_components, new_last_port)
strength = sum(bridge)
if strength > max_strength:
max_strength = strength
max_strength_bridge = bridge
return max_strength_bridge
In [7]:
assert sum(emMoat1(sample_data, 0)) == 31
In [8]:
sum(emMoat1(input_data, 0))
Out[8]:
In [28]:
def emMoat2(components, last_port):
max_long_strength = 0
max_length = 0
bridge = []
long_max_strength_bridge = []
for i, component in enumerate(components):
if component[0] == last_port or component[1] == last_port:
new_components = components[:i]+components[i+1:]
new_last_port = component[0] if component[1] == last_port else component[1]
bridge = component + emMoat2(new_components, new_last_port)
strength = sum(bridge)
length = len(bridge)
if length > max_length:
max_long_strength, max_length = strength, length
long_max_strength_bridge = bridge
elif length == max_length:
if strength > max_long_strength:
max_long_strength, max_length = strength, length
long_max_strength_bridge = bridge
return long_max_strength_bridge
In [31]:
assert sum(emMoat2(sample_data, 0)) == 19
In [30]:
sum(emMoat2(input_data, 0))
Out[30]:
In [2]:
!cat day25_input.txt
In [7]:
input_steps = 12317297
input_table={
'A':{ 0: (1,1,'B'), 1:(0,-1,'D') },
'B':{ 0: (1,1,'C'), 1:(0,1,'F') },
'C':{ 0: (1,-1,'C'), 1:(1,-1,'A') },
'D':{ 0: (0,-1,'E'), 1:(1,1,'A') },
'E':{ 0: (1,-1,'A'), 1:(0,1,'B') },
'F':{ 0: (0,1,'C'), 1:(0,1,'E') },
}
sample_steps = 6
sample_table={
'A':{ 0: (1,1,'B'), 1:(0,-1,'B') },
'B':{ 0: (1,-1,'A'), 1:(1,1,'A') },
}
In [8]:
def executeTuringMachine(table, steps):
tape = [0 for i in range(10000)]
cursor = 500 # current index
next_state = 'A' # begining state
for i in range(steps):
new_value, cursor_update, next_state = table[next_state][tape[cursor]]
tape[cursor] = new_value
cursor += cursor_update
return sum(tape)
In [10]:
assert executeTuringMachine(table=sample_table, steps=sample_steps) == 3
In [ ]:
executeTuringMachine(table=input_table, steps=input_steps)
In [ ]: