Advent of Code 2017, Day 14

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")