Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Signpost by tokiojapan55
def signpost(grid, directions):
VECTORS = {'NW': (-1, -1), 'N': (-1, 0), 'NE': (-1, 1),
'W' : ( 0, -1), 'E' : ( 0, 1),
'SW': ( 1, -1), 'S': ( 1, 0), 'SE': ( 1, 1),
'':(0,0)}
VECTORS_REV = {'NW':'SE','N':'S','NE':'SW','W':'E','E':'W','SW':'NE','S':'N','SE':'NW'}
get_rc = lambda s: list(s)[0]
def connect(src, dst):
link[src][1] = {dst}
link[src][3] = 1
for rc in link:
if rc!=src:
link[rc][1].discard(dst)
link[dst][0] = {src}
link[dst][2] = 1
for rc in link:
if rc!=dst:
link[rc][0].discard(src)
num = grid[dst[0]][dst[1]]
r,c = dst
while link[(r,c)][2]==1:
r,c = get_rc(link[(r,c)][0])
if num>0 and grid[r][c]<=0:
num -= 1
grid[r][c] = num
numbers[num] = (r,c)
elif grid[r][c]==0:
grid[r][c] = -1
start = (r,c)
num = grid[src[0]][src[1]]
r,c = src
while link[(r,c)][3]==1:
r,c = list(link[(r,c)][1])[0]
if num>0 and grid[r][c]<=0:
num += 1
grid[r][c] = num
numbers[num] = (r,c)
elif grid[r][c]==0:
grid[r][c] = -1
end = (r,c)
link[start][0].discard(end)
link[end][1].discard(start)
len_r,len_c = len(grid),len(grid[0])
numbers = {grid[r][c]:(r,c) for r in range(len_r) for c in range(len_c) if grid[r][c]>0}
link = dict()
for rc in [(r,c) for r in range(len_r) for c in range(len_c)]:
link[rc] = [set(),set(),0,0]
r,c = rc
dr,dc = VECTORS[directions[r][c]]
while (dr,dc)!=(0,0) and 0<=r+dr0:
for rc2 in link[rc][1]:
rr,cc = rc2
if grid[rr][cc]>0 and grid[rr][cc]!=grid[r][c]+1:
link[rc][1].discard(rc2)
link[rc2][0].discard(rc)
loop = True
break
if not loop:
for num in numbers.keys():
if (num+1) in numbers.keys():
src,dst = numbers[num],numbers[num+1]
if link[src][3]==0 or link[dst][2]==0:
connect(src, dst)
loop = True
break
if not loop:
pre_num = 0
for num in sorted(numbers.keys()):
if num>1 and pre_num
May 25, 2020
