Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in 3rd party category for Net Game by _Chico_
from copy import deepcopy
import numpy as np
def checkio(grid):
nb_rows, nb_cols = len(grid), len(grid[0])
visited = {(i, j): False for i in range(nb_rows)
for j in range(nb_cols)}
queue = []
MOVES = {'N': (-1, 0), 'S': (1, 0), 'W': (0, -1), 'E': (0, 1)}
DIRECTIONS = {(-1, 0):'N', (1, 0):'S', (0, -1):'W', (0, 1):'E'}
OPPOSITE = {'N': 'S', 'S': 'N', 'W': 'E', 'E': 'W'}
types = {'.' : ('N', 'W', 'S', 'E'),
'--': ('NS', 'EW'),
'_|': ('NW', 'SW', 'EN', 'ES'),
'T' : ('ENW', 'ENS', 'ESW', 'NSW')}
types_2 = {dirs: tile_type for tile_type, sorted_dirs in types.items()
for dirs in sorted_dirs}
tile_type = lambda tile: types_2.get(''.join(sorted(tile)), None)
corner = {(0,0):'ES', (0,nb_cols-1):'SW', (nb_rows-1,0):'EN',(nb_rows-1,nb_cols-1):'NW'}
for (i,j) in [(0,0),(0,nb_cols-1),(nb_rows-1,0),(nb_rows-1,nb_cols-1)]:
if tile_type(grid[i][j]) == '_|':
visited[(i,j)] = True
grid[i][j] = corner[(i,j)]
def obvious(visited,grid):
n = 0
temp_visited = deepcopy(visited)
temp_grid = deepcopy(grid)
while list(temp_visited.values()).count(False) != n:
n = list(temp_visited.values()).count(False)
potential = []
# collect neighbours of determined tiles as potential
for (i,j) in temp_visited.keys():
if temp_visited[(i,j)]:
for (di,dj) in [(-1,0),(1,0),(0,-1),(0,1)]:
if 0 <= i+di < nb_rows and 0 <= j+dj < nb_cols and not temp_visited[(i+di,j+dj)]:
potential.append((i+di,j+dj))
for i in range(nb_cols):
if not temp_visited[(0,i)]: potential.append((0,i))
if not temp_visited[(nb_rows-1,i)]: potential.append((nb_rows-1,i))
for i in range(1,nb_rows-1):
if not temp_visited[(i,0)]: potential.append((i,0))
if not temp_visited[(i,nb_cols-1)]: potential.append((i,nb_cols-1))
for i in range(1,nb_rows-1):
for j in range(1,nb_cols-1):
if not temp_visited[(i,j)] and tile_type(temp_grid[i][j]) == '.':
potential.append((i,j))
potential = set(potential)
# for each potential
for (i,j) in potential:
neighbours = []
must = []
mustnot = []
# exclude outward direction
if i == 0:
mustnot.append('N')
elif i == nb_rows-1:
mustnot.append('S')
if j == 0:
mustnot.append('W')
elif j == nb_cols-1:
mustnot.append('E')
# collect neighboured determined tiles of potential
for (di,dj) in [(-1,0),(1,0),(0,-1),(0,1)]:
if 0 <= i+di < nb_rows and 0 <= j+dj < nb_cols and temp_visited[(i+di,j+dj)]:
neighbours.append((i+di,j+dj))
# hints given by neighboured determined tiles
for (k,l) in neighbours:
for nwse in temp_grid[k][l]:
dk, dl = MOVES[nwse]
if k+dk == i and l+dl == j:
must.append(OPPOSITE[nwse])
break
else:
mustnot.append(DIRECTIONS[(k-i,l-j)])
if tile_type(temp_grid[i][j]) == '.':
for k in MOVES.keys():
(di,dj) = MOVES[k]
if 0 <= i+di < nb_rows and 0 <= j+dj < nb_cols and tile_type(temp_grid[i+di][j+dj]) == '.':
mustnot.append(k)
# judge
must = set(must)
mustnot = set(mustnot)
if len(must)+len(mustnot) > 4 or len(must) > len(temp_grid[i][j]) or len(mustnot) > 4-len(temp_grid[i][j]):
raise ValueError
if tile_type(temp_grid[i][j]) == '--':
if len(must) == 2 and tile_type(''.join(sorted(list(must)))) == '_|':
raise ValueError
if len(mustnot) == 2 and tile_type(''.join(sorted(list(mustnot)))) == '_|':
raise ValueError
if tile_type(temp_grid[i][j]) == '_|':
if len(must) == 2 and tile_type(''.join(sorted(list(must)))) == '--':
raise ValueError
if len(mustnot) == 2 and tile_type(''.join(sorted(list(mustnot)))) == '--':
raise ValueError
if len(must) == len(temp_grid[i][j]):
temp_grid[i][j] = ''.join(sorted(list(must)))
temp_visited[(i,j)] = True
elif 4-len(mustnot) == len(temp_grid[i][j]):
temp_grid[i][j] = ''.join(sorted(list({'E','W','N','S'}-mustnot)))
temp_visited[(i,j)] = True
elif tile_type(temp_grid[i][j]) == '--' and (must or mustnot):
if 'N' in must or 'S' in must or 'W' in mustnot or 'E' in mustnot:
temp_grid[i][j] = 'NS'
else:
temp_grid[i][j] = 'EW'
temp_visited[(i,j)] = True
elif tile_type(temp_grid[i][j]) == '_|' and len(must) == len(mustnot) == 1:
if list(must)[0] != OPPOSITE[list(mustnot)[0]]:
temp_grid[i][j] = ''.join(sorted([list(must)[0],OPPOSITE[list(mustnot)[0]]]))
temp_visited[(i,j)] = True
return [temp_visited, temp_grid]
def cycle_existence(new, old = None):
""" Recursively search if there is a closed loop / cycle. """
check_visited[old] = True
i, j = new
for nwse in temp_grid2[i][j]:
di, dj = MOVES[nwse]
x, y = neighbor = i + di, j + dj
if not (0 <= x < nb_rows and 0 <= y < nb_cols):
raise ValueError
if OPPOSITE[nwse] not in temp_grid2[x][y]:
raise ValueError
if check_visited[neighbor]:
if neighbor != old:
return True # closed loop / cycle found.
elif cycle_existence(neighbor, new): # Visit the neighbor.
return True
check_visited[new] = True
[visited, grid] = obvious(visited, grid)
if False not in visited.values():
return grid
queue.append([visited,grid])
while queue:
temp_visited, temp_grid = queue.pop(0)
try:
[temp_visited2, temp_grid2] = obvious(temp_visited, temp_grid)
if False not in temp_visited2.values():
check_visited = {(i, j): False for i in range(nb_rows)
for j in range(nb_cols)}
try:
if cycle_existence((0,0)):
continue
except:
continue
if all(check_visited.values()):
return temp_grid2
else:
continue
except:
continue
for [i,j] in list(np.mgrid[0:nb_rows,0:nb_cols].T.reshape((-1,2))):
if not temp_visited2[(i,j)]:
temp_visited3 = deepcopy(temp_visited2)
temp_visited3[(i,j)] = True
neighbours = []
must = []
mustnot = []
# exclude outward direction
if i == 0:
mustnot.append('N')
elif i == nb_rows-1:
mustnot.append('S')
if j == 0:
mustnot.append('W')
elif j == nb_cols-1:
mustnot.append('E')
# collect neighboured determined tiles of potential
for (di,dj) in [(-1,0),(1,0),(0,-1),(0,1)]:
if 0 <= i+di < nb_rows and 0 <= j+dj < nb_cols and temp_visited[(i+di,j+dj)]:
neighbours.append((i+di,j+dj))
# hints given by neighboured determined tiles
for (k,l) in neighbours:
for nwse in temp_grid[k][l]:
dk, dl = MOVES[nwse]
if k+dk == i and l+dl == j:
must.append(OPPOSITE[nwse])
break
else:
mustnot.append(DIRECTIONS[(k-i,l-j)])
# judge
must = set(must)
mustnot = set(mustnot)
for k in types[tile_type(grid[i][j])]:
if not any(l in mustnot for l in k) and all(l in k for l in must):
temp_grid3 = deepcopy(temp_grid2)
temp_grid3[i][j] = k
queue.append([deepcopy(temp_visited3), temp_grid3])
break
return grid
May 10, 2021
