Solution to Day 14: Disk Defragmentation - Part 2
#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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment