Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Signpost by Sillte
from collections import defaultdict
from itertools import product
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)}
class Solver:
"""
Member variables:
to_dict[pos] -> ``set`` of pos, to which moves from ``pos``.
from_dict[pos] -> ``set`` of ``paths``(set), from which move to ``pos``.
number_to_pos[number] -> ``tuple`` or ``set of tuple``;
(pos, which is ``tuple`` if number is fixed.
Otherwise, ``set`` of ``tuple``, which are possible candidates.)
``_init_dict`` set the above variables.
"""
def __init__(self, grid, directions):
self.height, self.width = len(grid), len(grid[0])
H, W = self.height, self.width
self._init_dict(grid, directions)
cand_to_pos = defaultdict(lambda: set((y, x) for y, x in product(range(H), range(W))))
for index in range(1, self.height * self.width + 1):
cand_to_pos[index] = set((y, x) for y, x in product(range(H), range(W)))
for number, pos in self.number_to_pos.items():
self._update_cand_to_pos(cand_to_pos, number, pos)
self.cand_to_pos = self._forward_one_step(cand_to_pos)
def _forward_one_step(self, cand_to_pos):
""" Deep First Search.
"""
next_numbers = [key for key in cand_to_pos.keys() if isinstance(cand_to_pos[key], set)]
if not next_numbers:
# Succeed to place all the numbers
return cand_to_pos
# The number whose candiadte positions are the smallest is searched firstly.
next_numbers = sorted(next_numbers, key=lambda key:len(cand_to_pos[key]))
target_number = next_numbers[0]
positions = cand_to_pos[target_number]
for pos in positions:
is_flag, change_dict = self._can_update(cand_to_pos, target_number, pos)
if not is_flag:
continue
""" Since the state(``cand_to_pos``) is very large,
simple copy takes very long time.
Hence, only incremental difference is changed and reverted.
"""
# Change of state.
revert_dict = {key: cand_to_pos[key] for key in change_dict.keys()}
for key, value in change_dict.items():
cand_to_pos[key] = value
result = self._forward_one_step(cand_to_pos)
if result:
return result
# Revert of state.
for key, value in revert_dict.items():
cand_to_pos[key] = value
return None
def _can_update(self, cand_to_pos, number, pos):
""" Judge whether it is valid to place ``nubmer`` on ``pos``.
Return: (is_ok, change_dict).
``is_ok`` is a boolean, which signifies whether it is valid or not.
``change_dict`` is incremental difference of ``cand_to_pos`` when actually ``number`` is placed on ``pos``.
"""
H, W = self.height, self.width
change_dict = dict()
fixed_poses = {value for value in cand_to_pos.values() if isinstance(value, tuple)}
if pos in fixed_poses:
return False, {}
change_dict[number] = pos
if number != 1:
if isinstance(cand_to_pos[number - 1], tuple):
if not cand_to_pos[number - 1] in self.from_dict[pos]:
return False, {}
else:
assert isinstance(cand_to_pos[number -1], set)
change_dict[number - 1] = cand_to_pos[number - 1] & self.from_dict[pos]
if not change_dict[number -1]:
return False, {}
if number != H * W:
if isinstance(cand_to_pos[number + 1], tuple):
if not cand_to_pos[number + 1] in self.to_dict[pos]:
return False, {}
else:
assert isinstance(cand_to_pos[number + 1], set)
change_dict[number + 1] = cand_to_pos[number + 1] & self.to_dict[pos]
if not change_dict[number + 1]:
return False, {}
for n in cand_to_pos.keys():
if n == number:
continue
if pos in cand_to_pos[n]:
if n in change_dict:
change_dict[n] = change_dict[n] - {pos}
else:
change_dict[n] = cand_to_pos[n] - {pos}
if not change_dict[n]:
return False, {}
return True, change_dict
def _update_cand_to_pos(self, cand_to_pos, number, pos):
H, W = self.height, self.width
cand_to_pos[number] = pos # Fixed.
if number != 1:
if isinstance(cand_to_pos[number - 1], tuple):
if not cand_to_pos[number - 1] in self.from_dict[pos]:
raise RuntimeError("Invalid Problem.")
else:
assert isinstance(cand_to_pos[number -1], set)
cand_to_pos[number - 1] = cand_to_pos[number - 1] & self.from_dict[pos]
if not cand_to_pos[number -1]:
raise RuntimeError("Invalid Problem.")
if number != H * W:
if isinstance(cand_to_pos[number + 1], tuple):
if not cand_to_pos[number + 1] in self.to_dict[pos]:
raise RuntimeError("Invalid Problem.")
else:
assert isinstance(cand_to_pos[number + 1], set)
cand_to_pos[number + 1] = cand_to_pos[number + 1] & self.to_dict[pos]
if not cand_to_pos[number + 1]:
raise RuntimeError("Invalid Problem.")
for number in cand_to_pos.keys():
if pos in cand_to_pos[number]:
cand_to_pos[number].remove(pos)
if not cand_to_pos[number]:
raise RuntimeError("Invalid Problem.")
def _init_dict(self, grid, directions):
H, W = len(grid), len(grid[0])
self.number_to_pos = dict()
self.to_dict = defaultdict(set)
self.from_dict = defaultdict(set)
for y, x in product(range(H), range(W)):
if grid[y][x] != 0:
self.number_to_pos[grid[y][x]] = (y, x)
start_point = self.number_to_pos[1]
end_point = self.number_to_pos[H * W]
for y, x in product(range(H), range(W)):
if grid[y][x] == H * W:
self.to_dict[y, x] = set()
else:
direction = directions[y][x]
reachables = self._to_reachable((y, x), direction)
for reachable in reachables:
if reachable != start_point:
self.to_dict[y, x].add(reachable)
for s_pos in self.to_dict.keys():
for e_pos in self.to_dict[s_pos]:
if s_pos != end_point:
self.from_dict[e_pos].add(s_pos)
def _to_reachable(self, current_pos, direction):
vector = VECTORS[direction]
pos = current_pos
result = set()
while True:
pos = pos[0] + vector[0], pos[1] + vector[1]
if not self._is_within_range(pos):
break
result.add(pos)
return result
def _is_within_range(self, pos):
h, w = pos
return 0 <= h < self.height and 0 <= w < self.width
def get_result(self):
""" Return the result.
"""
result = [[None] * self.width for _ in range(self.height)]
for cand, pos in self.cand_to_pos.items():
assert isinstance(pos, tuple)
result[pos[0]][pos[1]] = cand
return result
def signpost(grid, directions):
return Solver(grid, directions).get_result()
""" # Comments
## Important lessons for me.
### Handling of states.
Copy of states takes much time.
Hence, storing incremental change is very important to reduce the time.
## Failed Attempts
Not thoroughly considered, but as my personal memo, I write some of my trials and errors.
### Naive DFS.
The DFS of numbers from 1 to (H*W) has failed. It took very very long time.
### Memorization of ``steps``
The memorization of the following takes very very much time.
```
to_dict[s_pos][step][d_pos] -> ``set`` of paths, which moves from ``s_pos`` to ``d_pos`` with ``step``.
```
### Ineffective Pruning.
Calc the minimum distance and while DFS, use this info to stop the searching.
If the distance of adjacent positions exceeds the minimum distance, then it is invalid placement of numbers.
However, it seems not efficient pruning in this game.
```
min_dist[s_pos][e_pos] -> the minimum distance between from ``s_pos`` to ``e_pos``.
If ``None``, ``s_pos`` is not reachable to ``e_pos``.
```
"""
Feb. 10, 2019
Comments: