Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
connecting the shortest bridges first solution in Clear category for Signpost by David_Jones
from collections import defaultdict
from itertools import product
GRADIENTS = {
'NW': (-1,-1), 'N': (-1,0), 'NE': (-1,1),
'W': ( 0,-1), 'E': ( 0,1),
'SW': ( 1,-1), 'S': ( 1,0), 'SE': ( 1,1)
}
def signpost(grid, directions):
def prune_singles():
while True:
no_progress = True
for cell in prev_layer:
if len(prev_layer[cell]) == 1:
for prev_cell in prev_layer[cell]:
break
for sibling in next_layer[prev_cell] - {cell}:
no_progress = False
prev_layer[sibling].remove(prev_cell)
next_layer[prev_cell] = {cell}
if len(next_layer[cell]) == 1:
for next_cell in next_layer[cell]:
break
for sibling in prev_layer[next_cell] - {cell}:
no_progress = False
next_layer[sibling].remove(next_cell)
prev_layer[next_cell] = {cell}
if no_progress:
return
def find_single_path(start, end):
single_path = None
stack = [(coords[start],)]
while stack:
current_path = stack.pop()
if len(current_path) == end - start + 1:
if single_path:
return None
single_path = current_path
else:
for (x,y) in next_layer[current_path[-1]]:
if (x,y) not in current_path:
if len(current_path) < end - start:
if grid[x][y] == 0:
stack.append(current_path + ((x,y),))
elif grid[x][y] == end:
stack.append(current_path + ((x,y),))
return single_path
def prune_layers(start, end):
for i in range(start, end):
if i in coords and (i+1) in coords:
prev_cell = coords[i]
curr_cell = coords[i+1]
for cell in next_layer[prev_cell] - {curr_cell}:
prev_layer[cell].remove(prev_cell)
for cell in prev_layer[curr_cell] - {prev_cell}:
next_layer[cell].remove(curr_cell)
prev_layer[curr_cell] = {prev_cell}
next_layer[prev_cell] = {curr_cell}
n, m = len(grid), len(grid[0])
coords = {}
prev_layer, next_layer = defaultdict(set), defaultdict(set)
for (xA,yA) in product(range(n), range(m)):
num_A = grid[xA][yA]
coords[num_A] = (xA,yA)
if directions[xA][yA]:
(dx,dy) = GRADIENTS[directions[xA][yA]]
(xB,yB) = (xA+dx,yA+dy)
while 0 <= xB < n and 0 <= yB < m:
num_B = grid[xB][yB]
if num_A == 0 or num_B == 0 or num_A + 1 == num_B:
prev_layer[(xB,yB)].add((xA,yA))
next_layer[(xA,yA)].add((xB,yB))
(xB,yB) = (xB+dx,yB+dy)
coords[0] = (-1,-1)
prune_layers(0, n*m)
prune_singles()
nums = sorted(coords)
intervals = ((nums[i], nums[i+1]) for i in range(len(nums) - 1))
intervals = sorted(intervals, key=lambda x: x[1] - x[0])
while intervals:
for (i,j) in intervals:
single_path = find_single_path(i,j)
if single_path:
for k, (x,y) in enumerate(single_path, i):
grid[x][y] = k
coords[k] = (x,y)
prune_layers(i, j)
break
else:
break
intervals.remove((i,j))
stack = [(coords[1],)]
while stack:
path = stack.pop()
if len(path) == n * m:
break
for (x,y) in next_layer[path[-1]]:
if grid[x][y] in (0, len(path)+1) and (x,y) not in path:
stack.append(path + ((x,y),))
for i, (x,y) in enumerate(path, 1):
grid[x][y] = i
return grid
June 20, 2019
