Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Signpost by kurosawa4434
from functools import lru_cache
def signpost(grid, directions):
# ----------------------------------------------
#
# step 0: get values
#
# ----------------------------------------------
height = len(grid)
width = len(grid[0])
cell_dic, fix_cells, fix_nums = {}, {}, {}
start_cell, goal_cell, goal_num = (), (), ()
for r in range(height):
for c in range(width):
direction = directions[r][c]
number = grid[r][c]
cell_dic[(r, c)] = direction
if number:
fix_cells[(r, c)] = number
fix_nums[number] = (r, c)
if not direction:
goal_cell = (r, c)
goal_num = number
if number == 1:
start_cell = (r, c)
# ----------------------------------------------
#
# func: search_octas
#
# ----------------------------------------------
@lru_cache()
def search_octas(cell, rev):
octas_cells = set()
y, x = cell
h = [(y, c) for c in range(width)] # -
v, d1, d2 = [], [], []
for r in range(height):
v.append((r, x)) # |
if 0 <= x - (r - y) < width:
d1.append((r, x - (r - y))) # /
if 0 <= x + (r - y) < width:
d2.append((r, x + (r - y))) # \
for ty, tx in set(v + h + d1 + d2) - {cell}:
ey, ex = [(ty, tx), cell][rev]
sy, sx = [cell, (ty, tx)][rev]
# up
if ex == sx and ey > sy and cell_dic[(sy, sx)] == 'S':
octas_cells.add((ty, tx))
# down
if ex == sx and ey < sy and cell_dic[(sy, sx)] == 'N':
octas_cells.add((ty, tx))
# left
if ex > sx and ey == sy and cell_dic[(sy, sx)] == 'E':
octas_cells.add((ty, tx))
# right
if ex < sx and ey == sy and cell_dic[(sy, sx)] == 'W':
octas_cells.add((ty, tx))
if abs(ex - sx) == abs(ey - sy):
# \
# *
if ex > sx and ey > sy and cell_dic[(sy, sx)] == 'SE':
octas_cells.add((ty, tx))
# /
# *
if ex < sx and ey > sy and cell_dic[(sy, sx)] == 'SW':
octas_cells.add((ty, tx))
# *
# /
if ex > sx and ey < sy and cell_dic[(sy, sx)] == 'NE':
octas_cells.add((ty, tx))
# *
# \
if ex < sx and ey < sy and cell_dic[(sy, sx)] == 'NW':
octas_cells.add((ty, tx))
return octas_cells
# ----------------------------------------------
#
# func: get_steps
#
# ----------------------------------------------
def get_steps(start, steps, rev):
new_steps = [{start}]
next_cells = {start}
for idx, step in enumerate(steps):
search_cells = next_cells
next_cells = set()
tgt_num = [idx + 2, goal_num - idx - 1][rev]
if tgt_num in fix_nums:
next_cells |= {fix_nums[tgt_num]}
else:
for sc in search_cells:
next_cells |= search_octas(sc, rev) - set(fix_cells.keys())
if step:
next_cells &= set(step)
new_steps.append(next_cells)
return new_steps
# ----------------------------------------------
#
# step 1: get possibility (goal -> start, start -> goal... *repeat* )
#
# ----------------------------------------------
possibility = get_steps(goal_cell, [set() for _ in range(height * width - 1)], True)
prev_possibility_len = sum(map(len, possibility))
while True:
for i, s in enumerate(possibility):
if len(s) == 1:
y, x = list(s).pop()
fix_cells[(y, x)] = goal_num - i
fix_nums[goal_num - i] = (y, x)
possibility = get_steps(start_cell, list(reversed(possibility[:-1])), False)
new_possibility_len = sum(map(len, possibility))
if new_possibility_len == prev_possibility_len:
break
prev_possibility_len = new_possibility_len
for i, s in enumerate(possibility):
if len(s) == 1:
y, x = list(s).pop()
fix_cells[(y, x)] = i + 1
fix_nums[i + 1] = (y, x)
possibility = get_steps(goal_cell, list(reversed(possibility[:-1])), True)
# ----------------------------------------------
#
# func: search_path (recursive)
#
# ----------------------------------------------
def search_path(tgt, rest, path, step=1):
while step < goal_num:
if len(possibility[step]) == 1:
next_cell = list(possibility[step]).pop()
path.append(next_cell)
step += 1
rest -= {next_cell}
tgt = next_cell
else:
break
if step == goal_num:
if not rest:
return path
return False
for cell in search_octas(tgt, False) & possibility[step] & rest:
ret = search_path(cell, rest - {cell}, path + [cell], step + 1)
if ret:
return ret
# ----------------------------------------------
#
# step 2: search path & get answer
#
# ----------------------------------------------
result = search_path(start_cell, set(cell_dic.keys()) - {start_cell}, [start_cell])
return [[result.index((r, c)) + 1 for c in range(width)] for r in range(height)]
if __name__ == '__main__':
def checker(func, grid, directions):
result = func([row[:] for row in grid], directions)
nb_rows, nb_cols = len(grid), len(grid[0])
N = nb_rows * nb_cols
# check types
if not (isinstance(result, (list, tuple)) and
all(isinstance(row, (list, tuple)) and
all(isinstance(n, int) for n in row) for row in result)):
print("Result should be a list/tuple of lists/tuples of integers.")
return False
# check sizes and content compatibility
if not (len(result) == nb_rows and
all(len(row) == nb_cols for row in result)):
print("You should not have changed sizes.")
return False
if not all(user_n == n for row, user_row in zip(grid, result)
for n, user_n in zip(row, user_row) if n):
print("You should not have changed non-zero numbers.")
return False
# check if numbers describe range(1, N + 1)
numbers = sorted(n for row in result for n in row)
if 0 in numbers:
print("Still a zero in the grid.")
return False
if numbers != list(range(1, N + 1)):
print(f"Numbers in the grid should be integers between 1 and {N}.")
return False
path = {n: (i, j) for i, row in enumerate(result)
for j, n in enumerate(row)}
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)}
same_direction = lambda x1, y1, x2, y2: (x1 * y2 == x2 * y1 and
x1 * x2 >= 0 and y1 * y2 >= 0)
for n in range(1, N):
(i, j), (x, y) = path[n], path[n + 1]
vector, nwse = (x - i, y - j), directions[i][j]
if not same_direction(*vector, *vectors[nwse]):
print(f"Arrow from {n} to {n + 1}: "
f"direction at {(i, j)} is not respected.")
return False
return True
TESTS = (([[1, 0, 0],
[0, 0, 0],
[0, 0, 9]],
(('S', 'E', 'S'),
('S', 'S', 'NW'),
('NE', 'NE', ''))),
([[16, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]],
(('', 'E', 'SW', 'W'),
('E', 'SE', 'S', 'W'),
('SE', 'SE', 'NW', 'N'),
('NE', 'W', 'NE', 'N'))),
([[1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 24]],
(('SE', 'E', 'SW', 'W', 'S', 'S'),
('E', 'E', 'SE', 'W', 'NW', 'S'),
('E', 'E', 'SW', 'W', 'SW', 'S'),
('E', 'W', 'NE', 'NW', 'NW', ''))),
([[1, 0, 0, 0, 0],
[0, 0, 9, 0, 18],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 25]],
(('SE', 'E', 'SW', 'S', 'S'),
('E', 'W', 'S', 'NE', 'SW'),
('S', 'N', 'N', 'N', 'S'),
('NE', 'N', 'NE', 'SE', 'W'),
('NE', 'NE', 'W', 'W', ''))))
for n, (grid, directions) in enumerate(TESTS, 1):
assert checker(signpost, grid, directions), f"example #{n}"
Jan. 29, 2019
Comments:
