Skip to content

Instantly share code, notes, and snippets.

@pawlos
Created December 15, 2017 14:52
Show Gist options
  • Save pawlos/4b322a408e5c3c65c923571062ccdee2 to your computer and use it in GitHub Desktop.
Save pawlos/4b322a408e5c3c65c923571062ccdee2 to your computer and use it in GitHub Desktop.
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