Solution to Day 14: Disk Defragmentation - Part 2

advent_of_code_d14_p2.py

#aoc_d14.py


def knot_hash(inputstr):
	skip_size = 0
	inp = range(0,256)
	ind = 0
	for i in range(0,64):
		lengths = [ord(c) for c in inputstr]
		add = [17, 31, 73, 47, 23]
		lengths = lengths + add

		for l in lengths:
			w = []
			for i in range(ind,ind+l):
				w.append(inp[i%len(inp)])
			rev = w[::-1]
			o = {}
			for i in range(ind,ind+l):
				o[i%len(inp)] = rev[i-ind]
			n = [None]*len(inp)
			for i in range(0,len(inp)):
				if i in o:
					n[i]= o[i]
				else:
					n[i] = inp[i]
			inp = n
			ind = (ind + (l + skip_size)) % len(inp)
			skip_size += 1

	res = ''
	for i in range(0,16):
		w = inp[i*16:(i+1)*16]
		z = w[0]
		for r in range(1,len(w)):
			z = z ^ w[r]
		res += '{:02x}'.format(z)
	return res

bits = []
sum_bits = 0
for i in range(128):
	r = knot_hash("stpzcrnm-"+str(i))#flqrgnkx stpzcrnm

	bits.append([c for c in bin(int(r,16)).replace('0b','').zfill(128).replace('0',' ')])

color = 'r'
cnt = 0

def check(bits, line, pos):
	if line < 0: 
		return False
	if line >= len(bits):
		return False
	if pos < 0:
		return False
	if pos >= 128:
		return False

	return bits[line][pos] == '1'

def mark(bits, line, pos, color, level):

	bits[line][pos] = color
	if check(bits, line, pos+1):
		mark(bits, line, pos+1, color, level + 1)
	if check(bits, line, pos-1):
		mark(bits, line, pos-1, color, level + 1)
	if check(bits, line+1, pos):
		mark(bits, line+1, pos, color, level + 1)
	if check(bits, line-1, pos):
		mark(bits, line-1, pos, color, level + 1)

line = 0
pos = 0
print 'Start'

while True:
	while bits[line][pos] != '1':
		pos += 1
		if pos >= len(bits[line]):
			line += 1
			pos = 0
		if line >= len(bits):
			break
	if line >= len(bits):
		break
	mark(bits, line, pos, color, 0)

	if color == 'r':
		color = 'b'
	else:
		color = 'r'
	cnt += 1

print cnt