Skip to content

Instantly share code, notes, and snippets.

@PamelaM

PamelaM/aoc_2017_day14.py

Last active December 14, 2017 19:02
Show Gist options
  • Save PamelaM/5171a7d89a768e2f0493c5d91dcb137a to your computer and use it in GitHub Desktop.
Save PamelaM/5171a7d89a768e2f0493c5d91dcb137a to your computer and use it in GitHub Desktop.
Download ZIP
Advent of Code 2017, Day 14
Raw
aoc_2017_day14.py
def _replace(data, position, chunk):
#print position, chunk
for idx, v in enumerate(chunk):
data[position+idx] = v
def hash_list(lengths, data, position=0, skip_size=0):
#print position, skip_size, data
base_len = len(data)
for length in lengths:
#print length
data = data
end = position+length
if end >= base_len:
data = data + data
chunk = data[position:end]
#print position, end, chunk, '->',
chunk.reverse()
#print chunk
if end >= base_len:
data = data[:base_len]
before_len = base_len - position
after_len = length - before_len
_replace(data, position, chunk[:before_len])
_replace(data, 0, chunk[before_len:])
else:
_replace(data, position, chunk)
position += (length + skip_size)
if position >= base_len:
position = position % base_len
skip_size += 1
#print position, skip_size #, data
return data, position, skip_size
def knot_hash(key):
key = [ord(c) for c in key] + [17, 31, 73, 47, 23]
data = list(range(256))
position = 0
skip_size = 0
for __ in range(64):
data, position, skip_size = hash_list(key, data, position, skip_size)
dense = []
for offset in range(0, 256, 16):
chunk = data[offset:offset+16]
d = chunk[0]
for v in chunk[1:]:
d = d ^ v
dense.append(d)
return "".join("%02x" % d for d in dense)
NBITS = {
hex(n)[-1]:sum(1 for b in bin(n)[2:] if b=='1')
for n in range(16)
}
DOTS = {
hex(n)[-1]:"%04s" % bin(n)[2:]
for n in range(16)
}
def part_one(key):
tot = 0
for row in range(128):
row_key = "%s-%s" % (key, row)
hash_val = knot_hash(row_key)
#print hash_val
#print len(hash_val), len(hash_val)*4
#print [NBITS[c] for c in hash_val]
tot += sum(NBITS[c] for c in hash_val)
return tot
#print part_one("flqrgnkx")
#print part_one("hxtvlmkl")
def grid_2_coords(grid):
for y, row in enumerate(grid):
for x, c in enumerate(row):
if c != '.':
yield x, y
def neighbors(x, y):
yield x, y
if (y - 1) >= 0: yield (x, y-1)
if (y + 1) <= 127: yield (x, y+1)
if (x - 1) >= 0: yield (x-1, y)
if (x + 1) <= 127: yield (x+1, y)
def add_2_groups(target, groups):
pts = set()
for x, y in target:
pts |= set(neighbors(x, y))
#print target, pts
for group in groups:
if group & pts:
group |= target
break
else:
groups.append(target)
def part_two(key):
grid = [['.' for i in range(128)] for x in range(128)]
for row in range(128):
row_key = "%s-%s" % (key, row)
hash_val = knot_hash(row_key)
idx = 0
for c in hash_val:
for d in DOTS[c]:
if d == '1':
grid[row][idx] = '#'
idx += 1
#grid = [row[:8] for row in grid[:8]]
groups = []
for x, y in grid_2_coords(grid):
add_2_groups(set([(x, y),]), groups)
before = len(groups)
after = 0
while before != after:
#print before, after
before = len(groups)
new_groups = []
for group in groups:
add_2_groups(group, new_groups)
after = len(new_groups)
groups = new_groups
if 0:
for idx, group in enumerate(groups):
for x, y in group:
assert(grid[y][x] == '#')
grid[y][x] = str(idx+1)
for row in grid:
print " ".join("%2s" % v for v in row)
return len(groups)
print part_two("flqrgnkx")
print part_two("hxtvlmkl")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment