Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Unique neighbors and small paths search solution in Speedy category for Signpost by Phil15
from collections import defaultdict
MOVES = {'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):
nb_rows, nb_cols = len(grid), len(grid[0])
size = nb_rows * nb_cols
def number_compatibility(xA, yA, xB, yB) -> bool:
""" Say if A can go to B according to grid numbers. """
nA, nB = grid[xA][yA], grid[xB][yB]
return nB == nA + 1 if nA and nB else True
# Preprocess what is next/previous to each cell of the grid.
next_neighbors, prev_neighbors = defaultdict(set), defaultdict(set)
fix = {}
# fix[x][0] (/ fix[x][1]) is True when previous (/ next) cell is known.
for i, row in enumerate(grid):
for j, n in enumerate(row):
A = i, j # Cell A is pointing to a few cells B.
fix[A] = [n == 1, n == size]
if n != size: # else no direction given since it's the end.
di, dj = MOVES[directions[i][j]]
B = i + di, j + dj
while 0 <= B[0] < nb_rows and 0 <= B[1] < nb_cols:
if number_compatibility(*A, *B):
next_neighbors[A].add(B)
prev_neighbors[B].add(A)
B = B[0] + di, B[1] + dj
def follow_uniques(position, neighbors):
""" Generate the path from a position, looking in neighbors. """
while len(neighbors[position]) == 1:
for position in neighbors[position]:
yield position
def link(A, B) -> bool:
""" Create a link A --> B by updating data structures. """
if fix[A][1] and fix[B][0]:
return False # We knew this link before.
# Update neighbors and fix a few things.
next_neighbors[A], fix[A][1] = {B}, True
prev_neighbors[B], fix[B][0] = {A}, True
(xA, yA), (xB, yB) = A, B
nA, nB = grid[xA][yA], grid[xB][yB]
# If a A or B have number but not the other, inform next/prev cells.
# Next cells can't point to a previous cell, update neighbors.
for n, (x, y) in enumerate(follow_uniques(A, next_neighbors), 1):
# A --> B --> ... --> (x, y) so (x, y) can't point to A.
# nA < nA+1 < ... < nA + n
next_neighbors[x, y].discard(A)
if nA and not nB:
grid[x][y] = nA + n
for n, (x, y) in enumerate(follow_uniques(B, prev_neighbors), 1):
# B <-- A <-- ... <-- (x, y) so (x, y) can't come from B.
# nB > nB-1 > ... > nB - n
prev_neighbors[x, y].discard(B)
if nB and not nA:
grid[x][y] = nB - n
return True # We learned a new link
def find_unique_neighbors() -> int:
""" Go through the grid looking for unique previous/next neighbors. """
nb_new_links = 0 # This will say if we found something, or not.
for i, j in fix:
if not fix[i, j][0]: # The previous cell is not known yet.
end = i, j # What is the start?
discard = set() # Discard useless previous neighbors.
for start in prev_neighbors[end]:
# Discard cells that already have a next cell fixed.
# Discard cells without a compatible number.
if fix[start][1] or not number_compatibility(*start, *end):
discard.add(start)
prev_neighbors[end] -= discard
if len(prev_neighbors[end]) == 1: # start is known now!
for start in prev_neighbors[end]:
nb_new_links += link(start, end)
if not fix[i, j][1]: # The next cell is not known yet.
start = i, j # What is the end?
discard = set() # Discard useless next neighbors.
for end in next_neighbors[start]:
# Discard cells that already have a previous cell fixed.
# Discard cells without a compatible number.
if fix[end][0] or not number_compatibility(*start, *end):
discard.add(end)
next_neighbors[start] -= discard
if len(next_neighbors[start]) == 1: # end is known now!
for end in next_neighbors[start]:
nb_new_links += link(start, end)
return nb_new_links
def paths(steps, A, B) -> int: # Steps won't be > 3 (it's not needed).
""" Search a common thing to all paths
between A and B in the given number of steps. """
def dfs_links(): # Will generate links for all wanted paths.
stack = [[A]]
while stack:
path = stack.pop()
for neighbor in next_neighbors[path[-1]]:
if neighbor not in path:
new_path = path + [neighbor]
if len(new_path) <= steps:
stack.append(new_path)
elif neighbor == B: # new_path is complete here.
yield set(zip(new_path, new_path[1:]))
return sum(link(a, b) for a, b in set.intersection(*dfs_links()))
def smart_bruteforce() -> int:
""" Search little paths between cells with known numbers. """
starts, ends = {}, {}
for i, j in fix:
n = grid[i][j]
if n:
if not fix[i, j][0]: # (i, j) predecessor is unknown.
ends[n] = i, j
if not fix[i, j][1]: # (i, j) successor is unknown.
starts[n] = i, j
starts, ends = sorted(starts.items()), sorted(ends.items())
return sum(paths(nB - nA, A, B) # No need to look for big paths.
for (nA, A), (nB, B) in zip(starts, ends) if nB - nA <= 3)
smart_bruteforce() # Save time to first search little paths on big grids!
while find_unique_neighbors() or smart_bruteforce():
pass # While we find something, we continue.
return grid
March 14, 2019
Comments:
