Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
79-liner: indestructible jungle solution in Clear category for Net Game by przemyslaw.daniel
from itertools import product
from copy import deepcopy
def is_correct(x, y, grid, final=False):
''' Verify if there is any cycle starting from position x, y also
for the final solution check if all fields are visited '''
height, width = len(grid), len(grid[0])
stack, visited = [((-1, -1), (x, y))], set()
while stack:
prev, (x, y) = stack.pop()
if (x, y) in visited:
return False
if len(grid[x][y]) > 1:
continue
visited |= {(x, y)}
for direct in list(grid[x][y])[0]:
stack += [((x, y), (x-1, y))]*(direct == 'N' and (x-1, y) != prev)
stack += [((x, y), (x+1, y))]*(direct == 'S' and (x+1, y) != prev)
stack += [((x, y), (x, y-1))]*(direct == 'W' and (x, y-1) != prev)
stack += [((x, y), (x, y+1))]*(direct == 'E' and (x, y+1) != prev)
return len(visited) == height*width if final else True
def solve(grid, data):
''' Firstly try to find out fields that can be easily solved '''
height, width = len(grid), len(grid[0])
last_solved, solved = -1, 0
while last_solved < solved:
last_solved, solved = solved, 0
for x, y in product(range(height), range(width)):
if not data[x][y]:
return
if len(data[x][y]) > 1:
continue
solved += 1
neighbors = [(x-1, y, 'NS'), (x+1, y, 'SN')]
neighbors += [(x, y+1, 'EW'), (x, y-1, 'WE')]
for nx, ny, (a, b) in neighbors:
if a in data[x][y][0]:
data[nx][ny] = [z for z in data[nx][ny] if b in z]
elif 0 <= nx < height and 0 <= ny < width:
data[nx][ny] = [z for z in data[nx][ny] if b not in z]
if solved == height*width:
if not is_correct(0, 0, data, True):
return
return [[x[0] for x in y] for y in data]
''' Not all fields are solved we need to branch off '''
for x, y in product(range(height), range(width)):
if len(data[x][y]) > 1:
break
for option in data[x][y]:
branch = deepcopy(data)
branch[x][y] = [option]
if not is_correct(x, y, branch):
continue
solution = solve(grid, branch)
if solution:
return solution
def checkio(grid):
rotation = {'E': 'ESWN', 'N': 'NESW', 'S': 'SWNE', 'W': 'WNES'}
height, width = len(grid), len(grid[0])
data = [['']*width for _ in range(height)]
''' init data with correct values '''
for x, y in product(range(height), range(width)):
variations = zip(*[list(rotation[p]) for p in sorted(grid[x][y])])
data[x][y] = {''.join(sorted(x)) for x in variations}
neighbors = [(x+1, y, 'S'), (x-1, y, 'N'), (x, y+1, 'E'), (x, y-1, 'W')]
for nx, ny, direct in neighbors:
if not (0 <= nx < height and 0 <= ny < width):
data[x][y] = [r for r in data[x][y] if direct not in r]
return solve(grid, data)
Dec. 23, 2018
Comments:
