127 lines
3.6 KiB
Python
127 lines
3.6 KiB
Python
from collections import Counter
|
|
import time
|
|
|
|
|
|
def read_moves():
|
|
with open('day24/input') as reader:
|
|
return reader.read().splitlines()
|
|
|
|
|
|
def split_move(move):
|
|
split_moves = []
|
|
cur = ''
|
|
for c in move:
|
|
if cur == '' and c in ('e', 'w'):
|
|
split_moves.append(c)
|
|
elif c in ('n', 's'):
|
|
cur = c
|
|
else:
|
|
split_moves.append(cur + c)
|
|
cur = ''
|
|
return split_moves
|
|
|
|
|
|
all_possibilities = ['e', 'w', 'ne', 'nw', 'se', 'sw']
|
|
simplify_move1 = [('ne', 'se', 'e'), ('nw', 'sw', 'w')]
|
|
simplify_move2 = [
|
|
('w', 'ne', 'nw'), ('w', 'se', 'sw'),
|
|
('e', 'nw', 'ne'), ('e', 'sw', 'se')
|
|
]
|
|
opposite_moves = [('e', 'w'), ('se', 'nw'), ('sw', 'ne')]
|
|
|
|
|
|
def add_empty(move_count):
|
|
for p in all_possibilities:
|
|
if p not in move_count:
|
|
move_count[p] = 0
|
|
return move_count
|
|
|
|
|
|
def simplify_moves(move_count, simplify):
|
|
first, second, res = simplify
|
|
number_to_simplify = min(move_count[first], move_count[second])
|
|
move_count[first] -= number_to_simplify
|
|
move_count[second] -= number_to_simplify
|
|
move_count[res] += number_to_simplify
|
|
return move_count
|
|
|
|
|
|
def reduce_opposite_move(move_count, opposite):
|
|
first, second = opposite
|
|
if move_count[first] > move_count[second]:
|
|
move_count[first] = move_count[first] - move_count[second]
|
|
move_count[second] = 0
|
|
else:
|
|
move_count[second] = move_count[second] - move_count[first]
|
|
move_count[first] = 0
|
|
return move_count
|
|
|
|
|
|
def produce_unique_move(move_count):
|
|
m = ''
|
|
for p in all_possibilities:
|
|
if move_count[p] > 0:
|
|
m += p * move_count[p]
|
|
return m
|
|
|
|
|
|
def reduce_moves(move):
|
|
global opposite_moves
|
|
move_count = Counter(move)
|
|
move_count = add_empty(move_count)
|
|
for o in opposite_moves:
|
|
move_count = reduce_opposite_move(move_count, o)
|
|
for s in simplify_move1:
|
|
move_count = simplify_moves(move_count, s)
|
|
for o in opposite_moves:
|
|
move_count = reduce_opposite_move(move_count, o)
|
|
for s in simplify_move2:
|
|
move_count = simplify_moves(move_count, s)
|
|
for o in opposite_moves:
|
|
move_count = reduce_opposite_move(move_count, o)
|
|
return produce_unique_move(move_count)
|
|
|
|
|
|
moves = read_moves()
|
|
|
|
split_moves = list(map(split_move, moves))
|
|
|
|
unique_move_count = Counter(map(reduce_moves, split_moves))
|
|
res = sum([v % 2 for v in unique_move_count.values()])
|
|
|
|
print(res)
|
|
|
|
|
|
def black_needs_to_turn_white(adjacents, current_black):
|
|
black_adjacents = adjacents.intersection(current_black)
|
|
return len(black_adjacents) == 0 or len(black_adjacents) > 2
|
|
|
|
|
|
def white_needs_to_turn_black(white, current_black):
|
|
adjecent_to_white = set(map(lambda p: reduce_moves(split_move(white + p)), all_possibilities))
|
|
blacks_adjecent_to_white = adjecent_to_white.intersection(current_black)
|
|
return len(blacks_adjecent_to_white) == 2
|
|
|
|
start = time.time()
|
|
previous_black = set([key for key, value in unique_move_count.items() if value % 2 == 1])
|
|
for i in range(100):
|
|
black_next = set()
|
|
already_checked = set(previous_black)
|
|
|
|
for black in previous_black:
|
|
adjacents = set(map(lambda p: reduce_moves(split_move(black + p)), all_possibilities))
|
|
if not black_needs_to_turn_white(adjacents, previous_black):
|
|
black_next.add(black)
|
|
|
|
for a in adjacents:
|
|
if a not in already_checked:
|
|
already_checked.add(a)
|
|
if white_needs_to_turn_black(a, previous_black):
|
|
black_next.add(a)
|
|
|
|
print("Day {}: {}".format(str(i+1), len(black_next)))
|
|
previous_black = black_next
|
|
|
|
end = time.time()
|
|
print(end - start)
|