#!/usr/bin/env python

knothash_dict = {}
def knothash(my_input_string):
	if my_input_string in knothash_dict:
		return knothash_dict[my_input_string]

	my_input = [ord(item) for item in my_input_string]
	my_input += [17, 31, 73, 47, 23]
	my_list = range(0,256)
	my_list_length = len(my_list)
	current_position = 0
	skip_size = 0
	num_of_rounds = 64
	for i in [None]*num_of_rounds:
		for length in my_input:
			end_position = current_position + length
			reversed_list = []
			if end_position > my_list_length:
				end_position = end_position % my_list_length
				reversed_list = my_list[current_position:] + my_list[0:end_position]
				##print("Selected-part: " + str(reversed_list))
				reversed_list.reverse()
				##print("Reversed-part: " + str(reversed_list))
				##raw_input()
				my_list = reversed_list[(my_list_length-current_position):] + my_list[end_position:current_position] + reversed_list[0:(my_list_length-current_position)]
			else:
				reversed_list = my_list[current_position:end_position]
				##print("Selected-part: " + str(reversed_list))
				reversed_list.reverse()
				##print("Reversed-part: " + str(reversed_list))
				##raw_input()
				my_list = my_list[0:current_position] + reversed_list + my_list[end_position:]
			current_position = (current_position + length + skip_size) % my_list_length
			skip_size += 1
	dense_hash = []

	for i in range(0,16):
		dense_hash.append(reduce(lambda x,y: x^y, my_list[i*16:(i+1)*16]))
	dense_hash = [(hex(item)[2:] if len(hex(item)[2:])==2 else '0'+hex(item)[2:]) for item in dense_hash]
	hex_hash = ''.join(dense_hash)
	knothash_dict[my_input_string] = hex_hash	
	return hex_hash

def region(id, adjacency_dict):
	list_of_programs = [id]
	offsets = [1]
	list_of_programs.extend([item for item in adjacency_dict[list_of_programs[0]] if item not in list_of_programs])
	if len(list_of_programs) > offsets[0]:
		offsets.append(len(list_of_programs))
	else: # group is a singleton
		return list_of_programs

	offset_i = 0 # offset index, for indexing into `offsets`

	while offset_i != len(offsets):
		beginning_offset_i = offset_i

		for i in list_of_programs[offsets[offset_i]:]:
			if i in adjacency_dict and any(map(lambda x: x in list_of_programs[offsets[offset_i]:], adjacency_dict[i])):
				if i not in list_of_programs:
					list_of_programs.append(i)
				for j in adjacency_dict[i]:
					if j not in list_of_programs:
						list_of_programs.append(j)

		offsets.append(len(list_of_programs))
		offset_i+=1

		if offsets[beginning_offset_i] == offsets[offset_i]:
			break

	return list_of_programs


def hex_to_bin(hex_string):
	return bin(int(hex_string,16))[2:].zfill(len(hex_string)*4)

my_input = "hfdlxzhv"

num_of_used_squares = sum(map(lambda x: hex_to_bin(knothash(x)).count('1'), [my_input+"-"+str(item) for item in range(0,128)]))

answer1 = num_of_used_squares

print("Part 1: " + str(answer1))

adjacency_dict = {}

# Naming convention: id % 128 = col_num; id // 128 = row_num
#  0    1    2    3    4   ...  127
# 128  129  130  131  132  ...  255
# 256  257  258  259  260  ...  383 
# 384  385  386  387  388  ...  511
#  .    .    .    .    .   ...   .
#  .    .    .    .    .   ...   .
#  .    .    .    .    .   ...   .
#  -    -    -    -    -   ... 16383

def get_adjacent_used_square_ids(id, my_input):
	adjacent_used_ids = [id]
	row_num = id // 128
	col_num = id % 128
	for i in range(-1,3):
		if (row_num+(i//2)) < 128 and (row_num+(i//2)) > -1 and (col_num+(i*2-1-3*(i//2))) < 128 and (col_num+(i*2-1-3*(i//2))) > -1:
			if hex_to_bin(knothash(my_input+"-"+str(row_num+(i//2))))[col_num+(i*2-1-3*(i//2))] == '1':
				adjacent_used_ids.append((row_num+(i//2))*128 + col_num+(i*2-1-3*(i//2)))
	adjacent_used_ids = list(set(adjacent_used_ids))
	return adjacent_used_ids

# Creating the adjacency dictionary
map(lambda x: adjacency_dict.update({x: get_adjacent_used_square_ids(x, my_input)}), [i for i in range(0,128*128) if hex_to_bin(knothash(my_input+"-"+str(i//128)))[i%128]=='1'])

# Counting number of regions in adjacency dict
regions = []
region_temp = region(0, adjacency_dict)
regions.append(region_temp)
not_in_regions = list(set(adjacency_dict.keys()) - set(region_temp))
key_i = 0

while key_i < len(not_in_regions):
	key = not_in_regions[key_i]
	region_temp = region(key, adjacency_dict)
	regions.append(region_temp)
	not_in_regions = list(set(not_in_regions) - set(region_temp))

answer2 = len(regions)
print("Part 2: " + str(answer2))