Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Fast, short (215 with comments) and tested for hard cases solution in Clear category for Train Tracks by r_tchaik
from collections import defaultdict, deque
from copy import deepcopy
from typing import Tuple, Dict, Set, List
Counts, Coords = List[int], Tuple[int, int]
# find coordinates of the neighbour in the given direction
def make_move(node, move):
return tuple(sum(axis) for axis in zip(node, move))
def train_tracks(rows: Counts, columns: Counts, start: Coords, end: Coords, constraints: Dict[Coords, Set[str]],
open_nodes=None) -> str:
MOVES = {'N': (-1, 0), 'S': (1, 0), 'W': (0, -1), 'E': (0, 1)}
OPPOSITE = dict(zip('NSWE', 'SNEW'))
# find valid moves for a location
def valid_moves(node, all_moves):
return {move for move in all_moves
if 0 <= (next_node := make_move(node, MOVES[move]))[0] < len(rows)
and 0 <= next_node[1] < len(columns)
and constraints.get(next_node, {OPPOSITE[move]}) & {OPPOSITE[move]}}
# find route from node in direction path
# returns the full path and the last node
def find_path(path, node):
while True:
node = make_move(node, MOVES[path[-1]])
if len(constraints.get(node, '')) != 2:
return path, node
path += list(constraints[node] - {OPPOSITE[path[-1]]})[0]
# initiate variables on start
if open_nodes is None:
# track segments under analysis (have more than 2 directions valid)
open_nodes = set()
# new track segments identified by the current loop
new_nodes = {next_node for node, all_moves in constraints.items()
for move in all_moves if (next_node := make_move(node, MOVES[move])) not in constraints}
else:
new_nodes = set()
while open_nodes or new_nodes:
open_nodes.update(new_nodes)
constraints.update({node: valid_moves(node, {'N', 'S', 'W', 'E'}) for node in new_nodes})
# analyze identified segments
# final score 'xxyy': xx - track segments, yy - empty
current_rows = defaultdict(int)
current_cols = defaultdict(int)
for k, v in constraints.items():
current_rows[k[0]] += 100 if v else 1
current_cols[k[1]] += 100 if v else 1
new_nodes = {}
# look for changes in the current loop
has_changed = False
remove_nodes = set()
# analyze track segment from the investigation list
for node in open_nodes:
# if the track segment has 2 directions only it's removed from investigation
# its neighbours should be in constraints or added to the investigation list
if len(constraints[node]) == 2:
for move in constraints[node]:
if (next_node := make_move(node, MOVES[move])) not in constraints:
new_nodes[next_node] = {'N', 'S', 'W', 'E'}
remove_nodes.add(node)
has_changed = True
# analyze neighbours of the track segment
else:
valid_final = set()
closed = set()
for move in constraints[node]:
next_node_moves = constraints.get(make_move(node, MOVES[move]), {'N', 'S', 'W', 'E'})
# check if the neighbour has an open direction with the current segment
# we mark the direction as closed in case of negative outcome
if next_node_moves.isdisjoint({OPPOSITE[move]}):
closed.add(move)
# otherwise we add the direction to the final list if the neighbour is not under investigation
elif len(next_node_moves) < 3:
valid_final.add(move)
# in case we identified 2 correct destinations we remove others
if len(valid_final) == 2:
constraints[node] = valid_final
has_changed = True
else:
# remove discovered impasses
if closed:
constraints[node] -= closed
has_changed = True
# the investigation list cleaning
open_nodes -= remove_nodes
# fast analysis of dimensions (rows(mode 0) or columns (mode 1)) by items
def check_totals(current, items, size, mode=0):
nonlocal has_changed
for idx, item in enumerate(items):
road, empty = map(int, ((s := str(current[idx]).zfill(4))[:-2], s[-2:]))
# check if track and empty segments are within constraints
if (road > item) or (empty > size - item):
return True
elif road + empty != size:
for x in range(size):
node = (x, idx) if mode else (idx, x)
if node not in constraints:
# if all empty segments are identified mark remaining as track ones
if size - empty == item:
new_nodes[node] = {'N', 'S', 'W', 'E'}
# if all road segments are identified mark remaining as empty ones
elif road == item:
constraints[node] = set()
has_changed = True
return False
if any((check_totals(current_rows, rows, len(columns)), check_totals(current_cols, columns, len(rows), 1))):
return ''
# perform more complex analysis if nothing found in the current loop iteration
# after high-level scan of rows and columns we go to the segment level
def check_totals2(current, items, size, mode=0):
nonlocal has_changed
for idx, item in enumerate(items):
road, empty = map(int, ((s := str(current[idx]).zfill(4))[:-2], s[-2:]))
if road + empty != size:
choices = []
transit = {'W', 'E'} if mode else {'S', 'N'}
for x in range(size):
node = (x, idx) if mode else (idx, x)
if node not in constraints:
valid = valid_moves(node, {'N', 'S', 'W', 'E'})
# look for the last unidentified track segment in the line
# the valid segment should meet any of 2 criteria:
# 1) have connections with 2 perpendicular nodes
# 2) have a connection with one of the valid track segment from the same dimension
# 3) if we have one option only mark it as a track segment
if item - road == 1:
if valid >= transit or \
any(make_move(node, MOVES[move]) in constraints for move in valid - transit):
choices.append(node)
else:
constraints[node] = set()
has_changed = True
# mark empty those unidentified segments which have less than 2 open directions
else:
if len(valid) < 2:
constraints[node] = set()
has_changed = True
if len(choices) == 1:
new_nodes[choices[0]] = valid_moves(choices[0], {'N', 'S', 'W', 'E'})
if not new_nodes and not has_changed:
check_totals2(current_rows, rows, len(columns))
check_totals2(current_cols, columns, len(rows), 1)
# perform next level analysis if nothing found
if not new_nodes and not has_changed:
# identify and remove directions for track segments which lead to circles
crossroads = {}
for node in open_nodes:
if len(constraints[node]) == 3:
neighbours = {make_move(node, MOVES[move]): move for move in constraints[node]}
direction = [(n, move) for n, move in neighbours.items() if
n not in open_nodes and n in constraints and len(constraints[n]) > 1]
if direction:
del neighbours[direction[0][0]]
crossroads[node] = neighbours
path = find_path(direction[0][1], node)[1]
if path in neighbours:
constraints[node] -= {neighbours[path]}
has_changed = True
# mark empty those unidentified areas which have less than 2 open directions
not_checked = set()
for y in range(len(rows)):
for x in range(len(columns)):
if (y, x) not in constraints:
not_checked.add((y, x))
while not_checked:
to_check = deque()
clique = set()
current = not_checked.pop()
clique.add(current)
track_segments = set()
to_check.append(current)
while to_check:
node = to_check.popleft()
neighbours = {make_move(node, MOVES[move]) for move in valid_moves(node, {'N', 'S', 'W', 'E'})}
new_track_segm = {node for node in neighbours if node in constraints}
track_segments |= new_track_segm
to_check.extend(neighbours - new_track_segm - clique)
clique |= (neighbours - new_track_segm)
if len(track_segments) < 2:
for item in clique:
constraints[item] = set()
has_changed = True
not_checked -= clique
# perform backtracking as a final measure
if not has_changed:
if not crossroads:
return ''
current = crossroads.popitem()
for dir in current[1].values():
new_cons = deepcopy(constraints)
new_open = deepcopy(open_nodes)
new_cons[current[0]] -= {dir}
way = train_tracks(rows, columns, start, end, new_cons, new_open)
if way:
return way
return ''
result = find_path(list(constraints[tuple(start)])[0], start)[0]
return result if sum(bool(v) for v in constraints.values()) == len(result) + 1 else ''
if __name__ == '__main__':
def checker(test, user_result):
assert isinstance(user_result, str) and user_result, \
'You must return a (non-empty) string.'
MOVES = {'N': (-1, 0), 'S': (1, 0), 'W': (0, -1), 'E': (0, 1)}
forbidden_chars = ''.join(set(user_result) - MOVES.keys())
assert not forbidden_chars, ('You can only give N, W, S or E as '
f'directions, not: {forbidden_chars}')
OPPOSITE = dict(zip('NSWE', 'SNEW'))
rows, columns, start, end, constraints = test
path = [start]
for step, nwse in enumerate(user_result, 1):
r, c = last = path[-1]
if last in constraints:
assert nwse in constraints[last], \
f'You can not get out of {last} with {nwse!r}.'
constraints[last].remove(nwse)
dr, dc = MOVES[nwse]
position = r, c = r + dr, c + dc
assert 0 <= r < len(rows) and 0 <= c < len(columns), \
f'You are outside the grid at {position} after {step} moves.'
assert position not in path, \
f'You can not pass twice at {position}.'
if position in constraints:
assert OPPOSITE[nwse] in constraints[position], \
f'You can not enter at {position} with {nwse!r}.'
constraints[position].remove(OPPOSITE[nwse])
path.append(position)
if position == end:
assert len(user_result) == step, \
(f'You reached the end after {step} moves, '
'why are you continuing?')
break
else:
raise AssertionError(f'After all your {step} moves, '
'you still have not reached the end!')
constraints = {k: v for k, v in constraints.items() if v}
assert not constraints, (f'{sum(map(len, constraints.values()))}'
' constraints not respected.')
from collections import Counter
all_res_counts = (('Row', rows, Counter(i for i, _ in path)),
('Column', columns, Counter(j for _, j in path)))
for row_or_col, lines, res_counts in all_res_counts:
for i, count in enumerate(lines):
assert res_counts[i] == count, \
(f'{row_or_col} {i}: you passed by {res_counts[i]} cells '
f'instead of {count}.')
TESTS = (
(
[4, 6, 5, 3, 1, 3, 3, 4],
[4, 2, 2, 3, 4, 5, 6, 3],
(3, 0),
(7, 6),
{(3, 0): {'N'}, (4, 7): {'N', 'S'},
(6, 4): {'E', 'W'}, (7, 6): {'W'}},
),
(
[8, 7, 7, 5, 5, 3, 2, 3],
[3, 6, 7, 5, 4, 3, 6, 6],
(3, 0),
(7, 3),
{(1, 2): {'E', 'W'}, (1, 6): {'N', 'W'},
(3, 0): {'E'}, (7, 3): {'W'}},
),
(
[6, 7, 5, 6, 4, 3, 6, 4],
[3, 2, 3, 4, 6, 6, 5, 5, 5, 2],
(3, 0),
(7, 4),
{(1, 3): {'N', 'E'}, (3, 0): {'N'}, (4, 5): {'N', 'E'},
(5, 6): {'E', 'S'}, (7, 4): {'N'}, (7, 8): {'E', 'W'}},
),
)
from copy import deepcopy
for n, test in enumerate(TESTS, 1):
user_result = train_tracks(*deepcopy(test))
try:
checker(test, user_result)
except AssertionError as error:
print(f'You failed the test #{n}:', *error.args)
break
else:
print('Done! Click on "Check" for bigger tests.')
June 27, 2020
Comments:
