In [1]:
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 [ ]: