159 lines
4.3 KiB
Python
159 lines
4.3 KiB
Python
#!/bin/python3
|
|
import sys,time,re,os,copy
|
|
from pprint import pprint
|
|
sys.path.insert(0, '../../')
|
|
from fred import *
|
|
start_time = time.time()
|
|
|
|
if sys.argv[1] == 'test':
|
|
input_f = 'test'
|
|
elif sys.argv[1] == 'input':
|
|
input_f = 'input'
|
|
else:
|
|
print('No argv provided')
|
|
exit()
|
|
|
|
|
|
#########################################
|
|
# #
|
|
# Part 1 #
|
|
# #
|
|
#########################################
|
|
|
|
def part1():
|
|
|
|
grid = toGrid(input_f)
|
|
|
|
directions = ['up','down','left','right','up-left','up-right','down-left','down-right']
|
|
|
|
score = 0
|
|
|
|
for ydx,y in enumerate(grid):
|
|
for xdx, x in enumerate(y):
|
|
limit = 0
|
|
if get_value_in_direction(grid,(xdx,ydx)) == '@':
|
|
for d in directions:
|
|
val = get_value_in_direction(grid,(xdx,ydx),d)
|
|
if val == '@':
|
|
limit += 1
|
|
# print(xdx,ydx,limit)
|
|
if limit < 4:
|
|
score+=1
|
|
|
|
return score
|
|
|
|
start_time = time.time()
|
|
p1 = part1()
|
|
print('Part 1:',p1, '\t\t', round((time.time() - start_time)*1000), 'ms')
|
|
|
|
#########################################
|
|
# #
|
|
# Part 2 #
|
|
# #
|
|
#########################################
|
|
|
|
def part2():
|
|
grid = toGrid(input_f)
|
|
|
|
directions = ['up','down','left','right','up-left','up-right','down-left','down-right']
|
|
removed = []
|
|
score = 0
|
|
empty = False
|
|
prev_score = 1 # Set to 1 to avoid exit loop instantly.
|
|
tmp = 0
|
|
while score != prev_score:
|
|
|
|
prev_score = score
|
|
new_grid = copy.deepcopy(grid) # use deepcopy so the original grid isn't manipulated. Using new_grid=grid will change grid too later on.
|
|
for ydx,y in enumerate(grid):
|
|
for xdx, x in enumerate(y):
|
|
limit = 0
|
|
if get_value_in_direction(grid,(xdx,ydx)) == '@':
|
|
for d in directions:
|
|
val = get_value_in_direction(grid,(xdx,ydx),d)
|
|
if val == '@':
|
|
limit += 1
|
|
if limit < 4:
|
|
score+=1
|
|
new_grid[xdx][ydx] = 'X'
|
|
grid = copy.deepcopy(new_grid)
|
|
tmp += 1
|
|
print(tmp)
|
|
return score
|
|
|
|
def get_values_in_dir(grid:list, position:set):
|
|
values = {}
|
|
|
|
x,y=position
|
|
|
|
|
|
offsets = {
|
|
'up': (-1, 0),
|
|
'down': (1, 0),
|
|
'left': (0, -1),
|
|
'right': (0, 1),
|
|
'up-left': (-1, -1),
|
|
'up-right': (-1, 1),
|
|
'down-left': (1, -1),
|
|
'down-right': (1, 1)
|
|
}
|
|
|
|
for key,value in offsets.items():
|
|
dx, dy = value
|
|
new_x, new_y = x + dx, y + dy
|
|
|
|
if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[new_x]):
|
|
values[key] = grid[new_x][new_y]
|
|
return values, grid[x][y]
|
|
|
|
def part2_optimized():
|
|
|
|
grid = toGrid(input_f)
|
|
|
|
queue = []
|
|
score = 0
|
|
|
|
offsets = {
|
|
'up': (-1, 0),
|
|
'down': (1, 0),
|
|
'left': (0, -1),
|
|
'right': (0, 1),
|
|
'up-left': (-1, -1),
|
|
'up-right': (-1, 1),
|
|
'down-left': (1, -1),
|
|
'down-right': (1, 1)
|
|
}
|
|
|
|
for ydx,y in enumerate(grid):
|
|
for xdx, x in enumerate(y):
|
|
values,center = get_values_in_dir(grid,(xdx,ydx))
|
|
|
|
if center == '@' and sum(v == '@' for v in values.values()) < 4:
|
|
queue.append((xdx,ydx))
|
|
|
|
while len(queue) > 0:
|
|
(x,y) = queue.pop()
|
|
grid[x][y] = '.'
|
|
score += 1
|
|
|
|
neighbors,center = get_values_in_dir(grid,(x,y))
|
|
|
|
for key,value in neighbors.items():
|
|
if value == '@':
|
|
pos = addTuples((x,y),offsets[key])
|
|
values,center = get_values_in_dir(grid,pos)
|
|
if sum(value == '@' for value in values.values()) < 4:
|
|
if pos not in queue:
|
|
queue.append(pos)
|
|
|
|
return score
|
|
|
|
start_time = time.time()
|
|
p2 = part2_optimized()
|
|
print('Part 2:',p2, '', round((time.time() - start_time)*1000), 'ms')
|
|
|
|
start_time = time.time()
|
|
p2 = part2()
|
|
print('Part 2:',p2, '', round((time.time() - start_time)*1000), 'ms')
|
|
|