In [2]:
import sys
import os
import re
import collections
import itertools
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 [2]:
! cat day1_input.txt
In [18]:
input_data = None
with open("day1_input.txt") as f:
input_data = f.read().strip().split()[0]
The captcha requires you to review a sequence of digits (your puzzle input) and
find the sum of all digits that match the next digit in the list. The list is circular,
so the digit after the last digit is the first digit in the list.
In [68]:
def get_captcha11(s):
ssum = 0
for i1, i2 in zip(s, s[1:]+s[0]):
if i1 == i2:
ssum += int(i1)
return ssum
In [69]:
def get_captcha12(s):
n = len(s)
ssum = int(s[0]) if s[0] == s[-1] else 0
i1 = 0
while i1 < n-1:
if s[i1] == s[i1+1]:
ssum += int(s[i1])
i1+=1
return ssum
In [70]:
assert get_captcha12("1122") == 3
assert get_captcha12("1111") == 4
assert get_captcha12("1234") == 0
assert get_captcha12("91212129") == 9
In [71]:
get_captcha12(input_data)
Out[71]:
Now, instead of considering the next digit, it wants you to consider the digit halfway around
the circular list. That is, if your list contains 10 items, only include a digit in your sum
if the digit 10/2 = 5 steps forward matches it. Fortunately, your list has an even number of elements.
In [88]:
def get_captcha21(s):
n = len(s)
ssum = 0
i1 = 0
halfway_circle = n//2
while i1 < n:
if s[i1] == s[(i1+halfway_circle)%n]:
ssum += int(s[i1])
i1+=1
return ssum
In [89]:
assert get_captcha21("1212") == 6
assert get_captcha21("1221") == 0
assert get_captcha21("123425") == 4
assert get_captcha21("123123") == 12
assert get_captcha21("12131415") == 4
In [90]:
get_captcha21(input_data)
Out[90]:
In [92]:
! cat day2_input.txt
In [118]:
input_data = []
with open("day2_input.txt") as f:
for line in f.read().split("\n"):
input_data += [list(map(int,line.split("\t")))] if line else []
For each row, determine the difference between the largest value and the
smallest value; the checksum is the sum of all of these differences.
In [124]:
def get_checksum1(ll):
return sum([max(l) - min(l) for l in ll])
In [125]:
assert get_checksum1([[5,1,9,5],[7,5,3],[2,4,6,8]]) == 18
In [126]:
get_checksum1(input_data)
Out[126]:
the goal is to find the only two numbers in each row where one evenly
divides the other - that is, where the result of the division operation is
a whole number. They would like you to find those numbers on each line,
divide them, and add up each line's result.
In [137]:
def get_checksum2(ll):
csum = 0
for l in ll:
ht = {}
for i,a in enumerate(l):
for b in l[i:]:
if a == b:
continue
if a%b == 0:
csum += a//b
break
elif b%a == 0:
csum += b//a
break
return csum
In [138]:
assert get_checksum2([[5,9,2,8],[9,4,7,3],[3,8,6,5]]) == 9
In [139]:
get_checksum2(input_data)
Out[139]:
In [247]:
import math
def get_md_spiral_mem(n):
# this number marks the odd square end from where the counting starts.
# this counting is used to estimate the catesian cor ordinate which
# can be used to find the manhattan distance
ref = math.floor(math.sqrt(n))
# the spiral starts after the squared odd number
# if this is even reduce by 1 to get this place for reference
ref = ref - 1 if ref%2==0 else ref
# the number can be on either of the 4 sides when spiraling
# find difference from the squared odd number reference
diff = n - ref**2
# since all are odd number squares
# and the side considers the full side including
# the number that starts on the next side
side_size = ref+1
print("------", ref, diff, side_size)
# lets estimate the absolutre value of thier
# cartesian co ordinates. Since the reference is taken from the odd
# square numbers, handle them properly, this part is not implemented
# also this can be done pretty simply using comprehension,
# but this way the code is understandable
x,y = None, None
if n <= ref**2 + side_size:
# right side
x = side_size//2
d = ref**2 + side_size - n
print("----right",d)
y = (side_size//2) - d
elif n <= ref**2 + 2*side_size:
# top side
y = side_size//2
d = ref**2 + 2*side_size - n
print("----top",d)
x = (side_size//2) - d
elif n <= ref**2 + 3*side_size:
# left side
x = side_size//2
d = ref**2 + 3*side_size - n
print("----left",d)
y = (side_size//2) - d
else:
# bottom side
y = side_size//2
d = ref**2 + 4*side_size - n
print("----bottom",d)
x = (side_size//2) - d
print("-----",x,y)
return x + y
In [248]:
get_md_spiral_mem(347991)
Out[248]:
In [ ]:
In [249]:
! cat day4_input.txt
In [15]:
input_data = []
with open("day4_input.txt") as f:
for line in f.read().split("\n"):
input_data += [list(line.split())] if line else []
In [266]:
def get_valid1(list_of_strings):
valids = 0
for l in list_of_strings:
valids += 1 if len(set(l)) == len(l) else 0
return valids
In [267]:
assert get_valid([['aa','bb','cc','dd','ee']]) == 1
assert get_valid([['aa','bb','cc','dd','aaa']]) == 1
assert get_valid([['aa','bb','cc','dd','aa']]) == 0
In [268]:
get_valid(input_data)
Out[268]:
In [41]:
import collections
def get_valid2(list_of_strings):
valids = 0
for l in list_of_strings:
counts = [collections.Counter(s) for s in l]
valids += 1 if all([c1 != c2 for i,c1 in enumerate(counts) for c2 in counts[i+1:]]) else 0
return valids
In [46]:
assert get_valid2([["abcde","fghij"]]) == 1
assert get_valid2([["abcde","xyz","ecdab"]]) == 0
assert get_valid2([["a","ab","abc","abd","abf","abj"]]) == 1
assert get_valid2([["iiii","oiii","ooii","oooi","oooo"]]) == 1
assert get_valid2([["oiii","ioii","iioi","iiio"]]) == 0
In [42]:
get_valid2(input_data)
Out[42]:
In [47]:
! cat day5_input.txt
In [20]:
input_data = []
with open("day5_input.txt") as f:
input_data = list(map(int,f.read().strip().split("\n")))
In [21]:
def when_out1(list_of_nos):
l = list_of_nos[:]
current_index = 0
steps = 0
while current_index <= len(l)-1 and current_index >= 0:
# print("----",steps, l,current_index, current_index <= len(l)-1, current_index >= 0)
steps += 1
forward_index_by = l[current_index]
l[current_index] += 1
current_index += forward_index_by
return steps
In [22]:
assert(when_out1([0,3,0,1,-3])) == 5
In [23]:
when_out1(input_data)
Out[23]:
In [24]:
def when_out2(list_of_nos):
l = list_of_nos[:]
current_index = 0
steps = 0
while current_index <= len(l)-1 and current_index >= 0:
# print("----",steps, l,current_index, current_index <= len(l)-1, current_index >= 0)
steps += 1
forward_index_by = l[current_index]
if forward_index_by >= 3:
l[current_index] -= 1
else:
l[current_index] += 1
current_index += forward_index_by
return steps
In [29]:
assert(when_out2([0,3,0,1,-3])) == 10
In [28]:
when_out2(input_data)
Out[28]:
In [155]:
! cat day6_input.txt
In [156]:
input_data = []
with open("day6_input.txt") as f:
input_data = list(map(int,f.read().strip().split()))
In [177]:
import numpy as np
def cycling_reallocated_buffers1(buffers):
l = np.array(buffers)
n = len(l)
diviup_by = n-1
visited_buff_configs = set()
buffer_config = "-".join(list(map(str,l)))
step = 1
while buffer_config not in visited_buff_configs:
visited_buff_configs.add(buffer_config)
max_index = np.argmax(l)
divided = l[max_index]//diviup_by
remainder = l[max_index]%diviup_by
if divided == 0:
for i in range(1,l[max_index]+1):
l[(max_index+i)%n] += 1
l[max_index] = 0
else:
l += divided
l[max_index] = 0
l[max_index] += remainder
buffer_config = "-".join(list(map(str,l)))
step += 1
return step - 1
In [178]:
assert cycling_reallocated_buffers1([0,2,7,0]) == 5
In [179]:
cycling_reallocated_buffers1(input_data)
Out[179]:
In [180]:
import numpy as np
def cycling_reallocated_buffers2(buffers):
l = np.array(buffers)
n = len(l)
diviup_by = n-1
visited_buff_configs = {}
buffer_config = "-".join(list(map(str,l)))
step = 1
while buffer_config not in visited_buff_configs:
visited_buff_configs[buffer_config] = step
max_index = np.argmax(l)
divided = l[max_index]//diviup_by
remainder = l[max_index]%diviup_by
if divided == 0:
for i in range(1,l[max_index]+1):
l[(max_index+i)%n] += 1
l[max_index] = 0
else:
l += divided
l[max_index] = 0
l[max_index] += remainder
buffer_config = "-".join(list(map(str,l)))
step += 1
return step - visited_buff_configs[buffer_config]
In [182]:
assert cycling_reallocated_buffers2([0,2,7,0]) == 4
In [183]:
cycling_reallocated_buffers2(input_data)
Out[183]:
In [184]:
! cat day7_input.txt
In [215]:
input_data_adj_list = {}
input_data_values = {}
with open("day7_input.txt") as f:
for line in f.read().strip().split("\n"):
m = re.match(r"([a-z]+)\s+\((\d+)\)\s*[->\s]*(.*)",line)
input_data_values[m.group(1)] = int(m.group(2))
input_data_adj_list[m.group(1)] = m.group(3).split(", ") if m.group(3) else []
# input_data_adj_list
# input_data_values
In [216]:
def find_source1(adj_list):
# hash table to track incoming edges
nodes = {node:0 for node in adj_list.keys()}
for from_node, to_nodes in adj_list.items():
for to_node in to_nodes:
nodes[to_node] += 1
return [node for node,val in nodes.items() if val == 0][0]
In [225]:
sample = """pbga (66)
xhth (57)
ebii (61)
havc (66)
ktlj (57)
fwft (72) -> ktlj, cntj, xhth
qoyq (66)
padx (45) -> pbga, havc, qoyq
tknk (41) -> ugml, padx, fwft
jptl (61)
ugml (68) -> gyxo, ebii, jptl
gyxo (61)
cntj (57)
"""
sample_values = {}
sample_adj_list = {}
for line in sample.strip().split("\n"):
m = re.match(r"([a-z]+)\s+\((\d+)\)\s*[->\s]*(.*)",line)
sample_values[m.group(1)] = int(m.group(2))
sample_adj_list[m.group(1)] = m.group(3).split(", ") if m.group(3) else []
assert find_source1(sample_adj_list) == "tknk"
In [226]:
find_source1(input_data_adj_list)
Out[226]:
In [235]:
def find_unbalanced_weight(adj_list, values):
# get sum from all the leaf nodes that map to a single parent
for from_node, to_nodes in adj_list.items():
# finding the leaf nodes
if len(to_nodes) > 0 and all([len(adj_list[to_node]) == 0 for to_node in to_nodes]):
print("----",from_node,values[from_node]+sum([values[to_node] for to_node in to_nodes]))
In [236]:
find_unbalanced_weight(sample_adj_list, sample_values)
In [242]:
[(to_nodes,input_data_adj_list[to_nodes]) for to_nodes in input_data_adj_list["okzkfw"]]
Out[242]:
In [237]:
find_unbalanced_weight(input_data_adj_list, input_data_values)
In [245]:
! cat day8_input.txt
In [280]:
input_data_registers = {}
input_inc_dec = []
input_cond = []
with open("day8_input.txt") as f:
for line in f.read().strip().split("\n"):
m = re.match(r"(([a-z]+)\s[a-z]+\s[-]*\d+)\sif\s(([a-z]+)\s[!><=]+\s[-]*\d+)",line)
input_data_registers[m.group(2)] = 0
input_data_registers[m.group(4)] = 0
input_inc_dec += [m.group(1)]
input_cond += [m.group(3)]
len(input_data_registers),input_data_registers
Out[280]:
In [268]:
import operator
def get_operator_fn(op):
return {
'<' : operator.lt,
'<=' : operator.le,
'==' : operator.eq,
'!=' : operator.ne,
'>=' : operator.ge,
'>' : operator.gt,
'inc': operator.add,
'dec': operator.sub
}[op]
def find_largest_reg1(data_registers, inc_dec, cond):
for i in range(len(inc_dec)):
cond_l = cond[i].split(" ")
if get_operator_fn(cond_l[1])(data_registers[cond_l[0]], int(cond_l[2])):
inc_dec_l = inc_dec[i].split(" ")
data_registers[inc_dec_l[0]] = get_operator_fn(inc_dec_l[1])(data_registers[inc_dec_l[0]], int(inc_dec_l[2]))
return max(data_registers.items(), key=operator.itemgetter(1))[1]
In [291]:
sample = """b inc 5 if a > 1
a inc 1 if b < 5
c dec -10 if a >= 1
c inc -20 if c == 10
"""
sample_data_registers = {}
sample_inc_dec = []
sample_cond = []
for line in sample.strip().split("\n"):
m = re.match(r"(([a-z]+)\s[a-z]+\s[-]*\d+)\sif\s(([a-z]+)\s[!><=]+\s[-]*\d+)",line)
sample_data_registers[m.group(2)] = 0
input_data_registers[m.group(4)] = 0
sample_inc_dec += [m.group(1)]
sample_cond += [m.group(3)]
In [284]:
assert find_largest_reg1(sample_data_registers, sample_inc_dec, sample_cond) == 1
In [271]:
find_largest_reg1(input_data_registers, input_inc_dec, input_cond)
Out[271]:
In [290]:
def find_largest_reg2(data_registers, inc_dec, cond):
max_value = -float('inf')
for i in range(len(inc_dec)):
cond_l = cond[i].split(" ")
if get_operator_fn(cond_l[1])(data_registers[cond_l[0]], int(cond_l[2])):
inc_dec_l = inc_dec[i].split(" ")
data_registers[inc_dec_l[0]] = get_operator_fn(inc_dec_l[1])(data_registers[inc_dec_l[0]], int(inc_dec_l[2]))
max_value = max(max_value, data_registers[inc_dec_l[0]])
return max_value
In [292]:
assert find_largest_reg2(sample_data_registers, sample_inc_dec, sample_cond) == 10
In [293]:
find_largest_reg2(input_data_registers, input_inc_dec, input_cond)
Out[293]:
In [2]:
! cat day9_input.txt
In [5]:
input_data = None
with open("day9_input.txt") as f:
input_data = f.read().strip()
In [45]:
def update_cancelled_chars(s):
n = len(s)
updated_s = ''
i = 0
while i < n:
if s[i] == '!':
i += 2
else:
updated_s += s[i]
i += 1
return updated_s
def score_stream1(s):
matching_braces = {'{':'}', '<':'>'}
updated_s = update_cancelled_chars(s)
# print("----",updated_s)
n = len(updated_s)
# some corner cases to add the first character
# are not verified
# push and pop at the end
stack = []
score = 0
current_stream_score = 0
seen_garbage_start = False
for c in updated_s:
if c not in ['{','}','<','>']:
continue
if c == '<':
seen_garbage_start = True
if c == '>':
seen_garbage_start = False
if seen_garbage_start is False:
if c == '{':
current_stream_score += 1
stack += [('{', current_stream_score)]
score += current_stream_score
elif c == matching_braces[stack[-1][0]]:
stack.pop()
current_stream_score -= 1
# print("----",score)
return score
In [46]:
assert update_cancelled_chars("<!!!>>") == "<>"
assert update_cancelled_chars("<{o\"i!a,<{i<a>") == "<{o\"i,<{i<a>"
assert update_cancelled_chars("<!!>") == "<>"
assert update_cancelled_chars("<{!>}>") == "<{}>"
In [47]:
assert score_stream1("{}") == 1
assert score_stream1("{{{}}}") == 6
assert score_stream1("{{},{}}") == 5
assert score_stream1("{{{},{},{{}}}}") == 16
assert score_stream1("{<a>,<a>,<a>,<a>}") == 1
assert score_stream1("{{<ab>},{<ab>},{<ab>},{<ab>}}") == 9
assert score_stream1("{{<!!>},{<!!>},{<!!>},{<!!>}}") == 9
assert score_stream1("{{<a!>},{<a!>},{<a!>},{<ab>}}") == 3
In [48]:
score_stream1(input_data)
Out[48]:
In [57]:
def score_stream2(s):
matching_braces = {'{':'}', '<':'>'}
updated_s = update_cancelled_chars(s)
n = len(updated_s)
garbage_count = 0
seen_garbage_start = False
for c in updated_s:
if seen_garbage_start is True:
garbage_count += 1
if c == '<':
seen_garbage_start = True
if c == '>':
seen_garbage_start = False
garbage_count -= 1
return garbage_count
In [58]:
assert score_stream2("<>") == 0
assert score_stream2("<random characters>") == 17
assert score_stream2("<<<<>") == 3
assert score_stream2("<{!>}>") == 2
assert score_stream2("<!!>") == 0
assert score_stream2("<!!!>>") == 0
assert score_stream2("<{o\"i!a,<{i<a>") == 10
In [59]:
score_stream2(input_data)
Out[59]:
In [19]:
! cat day10_input.txt
In [20]:
input_data = None
with open('day10_input.txt') as f:
input_data = f.read().strip()
input_data
Out[20]:
In [21]:
def perform_one_round_knot_hash(l,lengths,ci=0,skip_size=0):
n = len(l)
# ci current index
for length in lengths:
#print("ci",ci,"skip",skip_size,"length",length,l)
if ci+length > n:
length_in_end = ci+length-n
new_l = (l[ci:ci+length] + l[:length_in_end])[::-1]
# print("new_l",new_l)
# print(l[ci:ci+length],new_l[:-length_in_end])
# print(l[:length_in_end],new_l[-length_in_end:])
l[ci:ci+length] = new_l[:-length_in_end]
l[:length_in_end] = new_l[-length_in_end:]
else:
l[ci:ci+length] = l[ci:ci+length][::-1]
ci = (ci + length + skip_size)%n
skip_size += 1
# print("ci",ci,l)
# print("======")
return (l, ci, skip_size)
def howmany_knothashes(input_chars, lengths):
l, _, _ = perform_one_round_knot_hash(input_chars, lengths)
return l[0]*l[1]
In [22]:
assert howmany_knothashes(list(range(5)),[3,4,1,5]) == 12
In [23]:
howmany_knothashes(list(range(256)),list(map(int,input_data.split(","))))
Out[23]:
In [24]:
def knot_hash(input_string, rounds=64):
suffix = [17, 31, 73, 47, 23]
lengths = [ord(ch) for ch in input_string] + suffix
l = list(range(256))
# round 1
l, ci, skip_size = perform_one_round_knot_hash(l, lengths)
for r in range(rounds-1):
l, ci, skip_size = perform_one_round_knot_hash(l, lengths, ci, skip_size)
import functools
si,ei = 0,16
dense_hash = ""
for i in range(16):
xored = functools.reduce(lambda x,y: x^y, l[si:ei])
dense_hash += '{:02x}'.format(xored)
si += 16
ei += 16
return dense_hash
In [25]:
assert knot_hash("") == "a2582a3a0e66e6e86e3812dcb672a272"
assert knot_hash("AoC 2017") == "33efeb34ea91902bb2f59c9920caa6cd"
assert knot_hash("1,2,3") == "3efbe78a8d82f29979031a4aa0b16a9d"
assert knot_hash("1,2,4") == "63960835bcdc130f0b66d7ff4f6a5a8e"
In [26]:
knot_hash(input_data)
Out[26]:
In [28]:
len(bin(0xa2582a3a0e66e6e86e3812dcb672a272))-2
Out[28]:
In [21]:
! cat day11_input.txt
In [32]:
input_data = None
with open("day11_input.txt") as f:
input_data = f.read().strip().split(",")
len(input_data)
Out[32]:
In [33]:
from IPython.display import Image
Image(filename='/home/bicepjai/Projects/mypuzzles/adventofcode/2017/images/hex_grid.png')
Out[33]:
In [50]:
# hex grid directions in cube co ordinates (x,y,z)
dir_map = {"n" :(0,1,-1), "ne":(1,0,-1), "nw":(-1,1,0),
"s" :(0,-1,1), "se":(1,-1,0), "sw":(-1,0,1)}
add_2cube_cord = lambda xyz1,xyz2:(xyz1[0]+xyz2[0],xyz1[1]+xyz2[1],xyz1[2]+xyz2[2])
distance_from_origin = lambda xyz: max(abs(xyz[0]), abs(xyz[1]), abs(xyz[2]))
def shortest_distance_to_hexgrid1(path):
# starting at origin
cco = (0,0,0) #current_co_ordinate
for d in path:
cco = add_2cube_cord(cco, dir_map[d])
# shortest distance from origin
return distance_from_origin(cco)
In [51]:
assert shortest_distance_to_hexgrid1(["ne","ne","ne"]) == 3
assert shortest_distance_to_hexgrid1(["ne","ne","sw","sw"]) == 0
assert shortest_distance_to_hexgrid1(["ne","ne","s","s"]) == 2
assert shortest_distance_to_hexgrid1(["se","sw","se","sw","sw"]) == 3
In [52]:
shortest_distance_to_hexgrid(input_data)
Out[52]:
In [53]:
def shortest_distance_to_hexgrid2(path):
# starting at origin
cco = (0,0,0) #current_co_ordinate
max_distance = 0
for d in path:
cco = add_2cube_cord(cco, dir_map[d])
max_distance = max(max_distance, distance_from_origin(cco))
return max_distance
In [54]:
shortest_distance_to_hexgrid2(input_data)
Out[54]:
In [55]:
def get_path_cords(path):
# starting at origin
path_cords = []
cco = (0,0,0) #current_co_ordinate
for d in path:
path_cords += [cco]
cco = add_2cube_cord(cco, dir_map[d])
return path_cords
In [75]:
path_cords = get_path_cords(input_data)
fig,axes = plt.subplots(nrows=1,ncols=3)
fig.set_size_inches(18,8)
axes[0].set(title="pathxy")
axes[0].plot([t[0] for t in path_cords],[t[1] for t in path_cords])
axes[1].set(title="pathyz")
axes[1].plot([t[1] for t in path_cords],[t[2] for t in path_cords])
axes[2].set(title="pathzx")
axes[2].plot([t[2] for t in path_cords],[t[0] for t in path_cords])
plt.show()
In [76]:
! cat day12_input.txt
forming adjaceny list as provided
In [244]:
input_data = {}
with open("day12_input.txt") as f:
for line in f.read().strip().split("\n"):
m = re.match(r"(\d+)\s*<->(.*)",line)
input_data[int(m.group(1).strip())] = [int(n.strip()) for n in m.group(2).strip().split(",")]
len(input_data)
Out[244]:
In [245]:
def connected_componenets_dfs1(adj_list):
# perform depth first search to count the components
# connected to the node 0
num_connected = 0
visited = set()
def helper_dfs(node):
nonlocal num_connected, visited, adj_list
if node not in visited:
visited.add(node)
num_connected += 1
for child in adj_list[node]:
helper_dfs(child)
helper_dfs(0)
return num_connected
def connected_componenets_dfs2(adj_list):
# perform depth first search to count the components
# connected to the node 0
num_connected = 0
visited = set()
def helper_dfs(node):
nonlocal num_connected, visited, adj_list
visited.add(node)
num_connected += 1
for child in adj_list[node]:
if child not in visited:
helper_dfs(child)
helper_dfs(0)
return num_connected
In [246]:
def connected_componenets_bfs1(adj_list):
# perform breadth first search to count the components
# connected to the node 0
num_connected = 0
visited = set()
q = [0] # enqueue->append dequeue->pop(0)
while len(q) > 0:
node = q.pop(0)
if node not in visited:
visited.add(node)
num_connected += 1
for child in adj_list[node]:
q += [child]
return num_connected
def connected_componenets_bfs2(adj_list):
# perform breadth first search to count the components
# connected to the node 0
num_connected = 0
visited = set()
q = [0] # enqueue->append dequeue->pop(0)
while len(q) > 0:
node = q.pop(0)
for child in adj_list[node]:
if child not in visited:
visited.add(child)
num_connected += 1
q += [child]
return num_connected
In [247]:
sample_input="""0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5
"""
sample_data = {}
for line in sample_input.strip().split("\n"):
m = re.match(r"(\d+)\s*<->(.*)",line)
sample_data[int(m.group(1).strip())] = [int(n.strip()) for n in m.group(2).strip().split(",")]
In [248]:
assert connected_componenets_dfs1(sample_data) == connected_componenets_dfs2(sample_data)
assert connected_componenets_dfs1(sample_data) == connected_componenets_bfs1(sample_data)
assert connected_componenets_bfs1(sample_data) == connected_componenets_bfs2(sample_data)
assert connected_componenets_dfs1(sample_data) == connected_componenets_bfs2(sample_data)
In [250]:
assert connected_componenets_dfs1(input_data) == connected_componenets_dfs2(input_data)
assert connected_componenets_dfs1(input_data) == connected_componenets_bfs1(input_data)
assert connected_componenets_bfs1(input_data) == connected_componenets_bfs2(input_data)
assert connected_componenets_dfs1(input_data) == connected_componenets_bfs2(input_data)
connected_componenets_bfs2(input_data)
Out[250]:
In [159]:
def nof_connected_componenets_bfs(adj_list):
num_groups = 0
visited = set()
# lets go thru all the nodes
# and form connected compenents
for root in adj_list:
if root not in visited:
num_groups += 1
q = [root]
while len(q) > 0:
node = q.pop(0)
if node not in visited:
visited.add(node)
for child in adj_list[node]:
q += [child]
return num_groups
In [161]:
assert nof_connected_componenets_bfs(sample_data) == 2
In [162]:
nof_connected_componenets_bfs(input_data)
Out[162]:
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 [ ]: