Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Second; I did it! solution in Clear category for Train Tracks by pokosasa
from itertools import product
from collections import Counter
from typing import Tuple, Dict, Set, List
from copy import deepcopy
Counts, Coords = List[int], Tuple[int, int]
def train_tracks(rows: Counts, columns: Counts,
start: Coords, end: Coords,
constraints: Dict[Coords, Set[str]]) -> str:
H, W = len(rows), len(columns)
NEWS = {"N": (-1, 0, "S"), "E": (0, 1, "W"),
"W": (0, -1, "E"), "S": (1, 0, "N")}
UNKNOWN, PLACEABLE, UNPLACEABLE, PLACED = "?+*X"
cells = {(i, j): UNKNOWN for i, j in product(range(H), range(W))}
tracks = {}
row_counters = [Counter([UNKNOWN]*W) for i in range(H)]
col_counters = [Counter([UNKNOWN]*H) for j in range(W)]
def set_state(i, j, new_state, data):
cells, _, row_counters, col_counters = data
old_state = cells[(i, j)]
cells[(i, j)] = new_state
row_counters[i][old_state] -= 1
col_counters[j][old_state] -= 1
row_counters[i][new_state] += 1
col_counters[j][new_state] += 1
def place_track(i, j, track, data):
cells, tracks, _, _ = data
tracks[(i, j)] = track
set_state(i, j, PLACED, data)
for dir in track:
di, dj, here = NEWS[dir]
if cells[(i+di, j+dj)] == UNKNOWN:
set_state(i+di, j+dj, PLACEABLE, data)
def fill_row(i, new_state, data):
cells, _, _, _ = data
for j in range(W):
if cells[(i, j)] == UNKNOWN:
set_state(i, j, new_state, data)
def fill_col(j, new_state, data):
cells, _, _, _ = data
for i in range(H):
if cells[(i, j)] == UNKNOWN:
set_state(i, j, new_state, data)
def init(data):
for (i, j), track in constraints.items():
place_track(i, j, track, data)
def check_fill(data):
_, _, row_counters, col_counters = data
nonlocal reboot
cnt = 0
while True:
updated = False
for i in range(H):
counter = row_counters[i]
if W-counter[UNPLACEABLE] < rows[i]:
reboot = True
return False
if counter[PLACEABLE]+counter[PLACED] > rows[i]:
reboot = True
return False
if counter[UNKNOWN] == 0:
continue
if W-counter[UNPLACEABLE] == rows[i]:
fill_row(i, PLACEABLE, data)
updated = True
continue
if counter[PLACEABLE]+counter[PLACED] == rows[i]:
fill_row(i, UNPLACEABLE, data)
updated = True
for j in range(W):
counter = col_counters[j]
if H-counter[UNPLACEABLE] < columns[j]:
reboot = True
return False
if counter[PLACEABLE]+counter[PLACED] > columns[j]:
reboot = True
return False
if counter[UNKNOWN] == 0:
continue
if H-counter[UNPLACEABLE] == columns[j]:
fill_col(j, PLACEABLE, data)
updated = True
continue
if counter[PLACEABLE]+counter[PLACED] == columns[j]:
fill_col(j, UNPLACEABLE, data)
updated = True
if updated:
cnt += 1
continue
break
return cnt > 0
def search_placeable_cells(data):
cells, tracks, _, _ = data
nonlocal reboot
cnt = 0
while True:
updated = False
for i, j in product(range(H), range(W)):
if cells[(i, j)] != PLACEABLE:
continue
joints, ng = 0, 0
new_track_1 = set()
new_track_2 = set()
for there, (di, dj, here) in NEWS.items():
si, sj = i+di, j+dj
if (si, sj) not in cells:
ng += 1
continue
cell = cells[(si, sj)]
if cell in (PLACEABLE, UNKNOWN):
new_track_1.add(there)
continue
if cell == PLACED:
if here in tracks[(si, sj)]:
new_track_1.add(there)
new_track_2.add(there)
joints += 1
else:
ng += 1
continue
if cell == UNPLACEABLE:
ng += 1
if ng >= 3:
reboot = True
return False
if joints == 2:
place_track(i, j, new_track_2, data)
start_point = (i, j)
edge = min(new_track_2)
if check_loop(start_point, edge, data):
reboot = True
return False
updated = True
elif ng == 2:
place_track(i, j, new_track_1, data)
updated = True
if updated:
cnt += 1
continue
break
return cnt > 0
def search_unknown_cells_1(data):
cells, _, _, _ = data
cnt = 0
while True:
updated = False
for i, j in product(range(H), range(W)):
if cells[(i, j)] != UNKNOWN:
continue
ng = 0
for di, dj, _ in NEWS.values():
if (i+di, j+dj) not in cells:
ng += 1
continue
if cells[(i+di, j+dj)] in (UNPLACEABLE, PLACED):
ng += 1
if ng >= 3:
set_state(i, j, UNPLACEABLE, data)
updated = True
if updated:
cnt += 1
continue
break
return cnt > 0
def search_unknown_cells_2(data):
cells, _, row_counters, col_counters = data
res = []
updated = False
for i in range(H):
rest = rows[i]-(row_counters[i][PLACED]+row_counters[i][PLACEABLE])
if rest == 1:
for j in range(W):
if cells[(i, j)] != UNKNOWN:
continue
ng = 0
if i == 0 or cells[(i-1, j)] in (PLACED, UNPLACEABLE):
ng += 1
if i == H-1 or cells[(i+1, j)] in (PLACED, UNPLACEABLE):
ng += 1
if ng == 0:
continue
cnt = 0
if j > 0 and cells[(i, j-1)] == PLACEABLE:
cnt += 1
if j < W-1 and cells[(i, j+1)] == PLACEABLE:
cnt += 1
if cnt == 0:
set_state(i, j, UNPLACEABLE, data)
updated = True
for j in range(W):
rest = columns[j]-(col_counters[j][PLACED] +
col_counters[j][PLACEABLE])
if rest == 1:
for i in range(H):
if cells[(i, j)] != UNKNOWN:
continue
ng = 0
if j == 0 or cells[(i, j-1)] in (PLACED, UNPLACEABLE):
ng += 1
if j == W-1 or cells[(i, j+1)] in (PLACED, UNPLACEABLE):
ng += 1
if ng == 0:
continue
cnt = 0
if i > 0 and cells[(i-1, j)] == PLACEABLE:
cnt += 1
if i < H-1 and cells[(i+1, j)] == PLACEABLE:
cnt += 1
if cnt == 0:
set_state(i, j, UNPLACEABLE, data)
updated = True
return updated
def avoid_loop(data):
cells, tracks, _, _ = data
nonlocal reboot
updated = False
for i in range(H):
edges = []
for j in range(W-1, -1, -1):
if cells[(i, j)] != PLACEABLE:
continue
candidates, idx, dir, joints = [], None, None, 0
for there, (di, dj, here) in NEWS.items():
if (i+di, j+dj) not in cells:
continue
if cells[(i+di, j+dj)] in (PLACEABLE, UNKNOWN):
candidates.append(there)
continue
if cells[(i+di, j+dj)] == PLACED and here in tracks[(i+di, j+dj)]:
idx = j
dir = there
joints += 1
if idx != None and joints != 2:
edges.append((idx, dir, candidates))
if len(edges) < 2:
continue
edge1 = edges.pop()
while edges:
edge2 = edges.pop()
(j1, dir1, candidates1), (j2, dir2, candidates2) = edge1, edge2
if j1+1 != j2:
edge1 = edge2
continue
di1, dj1, here = NEWS[dir1]
start_point = (i + di1, j1 + dj1)
if start_point in (start, end):
edge1 = edge2
continue
path = list(output_path(data, start_point, here))
end_point, _, _ = path[-1]
if (i, j2) != end_point:
edge1 = edge2
continue
candidates1.remove("E")
candidates2.remove("W")
if len(candidates1) == 0 or len(candidates2) == 0:
print("can't avoid loop. reboot!", (i, j1), (i, j2))
reboot = True
return False
if len(candidates1) == 1:
new_track = {dir1, candidates1[0]}
place_track(i, j1, new_track, data)
print("avoid loop in row", (i, j1))
updated = True
if len(candidates2) == 1:
new_track = {dir2, candidates2[0]}
place_track(i, j2, new_track, data)
print("avoid loop in row", (i, j2))
updated = True
edge1 = edge2
continue
for j in range(W):
edges = []
for i in range(H-1, -1, -1):
if cells[(i, j)] != PLACEABLE:
continue
candidates, idx, dir, joints = [], None, None, 0
for there, (di, dj, here) in NEWS.items():
if (i+di, j+dj) not in cells:
continue
if cells[(i+di, j+dj)] in (PLACEABLE, UNKNOWN):
candidates.append(there)
continue
if cells[(i+di, j+dj)] == PLACED and here in tracks[(i+di, j+dj)]:
idx = i
dir = there
joints += 1
if idx != None and joints != 2:
edges.append((idx, dir, candidates))
if len(edges) < 2:
continue
edge1 = edges.pop()
while edges:
edge2 = edges.pop()
(i1, dir1, candidates1), (i2, dir2, candidates2) = edge1, edge2
if i1 + 1 != i2:
edge1=edge2
continue
di1, dj1, here = NEWS[dir1]
start_point = (i1 + di1, j + dj1)
if start_point in (start, end):
edge1=edge2
continue
path = list(output_path(data, start_point, here))
end_point, _, _ = path[-1]
if (i2, j) != end_point:
edge1 = edge2
continue
candidates1.remove("S")
candidates2.remove("N")
if len(candidates1) == 0 or len(candidates2) == 0:
reboot = True
print("can't avoid loop. reboot!", (i1, j), (i2, j))
return False
if len(candidates1) == 1:
new_track = {dir1, candidates1[0]}
place_track(i1, j, new_track, data)
print("avoid loop in col", (i1, j))
updated = True
if len(candidates2) == 1:
new_track = {dir2, candidates2[0]}
place_track(i2, j, new_track, data)
updated = True
print("avoid loop in col", (i2, j))
edge1 = edge2
continue
return updated
def output_path(data, start_point=start, edge=None):
_, tracks, _, _ = data
i, j = start_point
prev_dir = edge
next_dir = min(tracks[(i, j)] - {prev_dir})
yield ((i, j), prev_dir, next_dir)
while True:
di, dj, prev_dir = NEWS[next_dir]
i, j = i + di, j + dj
if (i, j) not in tracks or (i, j) == end or (i, j) == start:
yield ((i, j), prev_dir, "")
break
next_dir = min(tracks[(i, j)] - {prev_dir})
yield ((i, j), prev_dir, next_dir)
def check_loop(start_point, edge, data):
cnt = 0
for ((i, j), _, _) in output_path(data, start_point, edge):
if (i, j) == start_point:
cnt += 1
if cnt == 2:
return True
return False
def dfs(data):
cells, _, _, _, = data
for (i, j), track in tracks.items():
for dir in track:
di, dj, prev_dir = NEWS[dir]
si, sj = i+di, j+dj
if cells[(si, sj)] == PLACEABLE:
for next_dir, (di2, dj2, _) in NEWS.items():
ri, rj = si+di2, sj+dj2
if (ri, rj) not in cells or cells[(ri, rj)] in (PLACED, UNPLACEABLE):
continue
new_data = deepcopy(data)
new_track = {prev_dir, next_dir}
place_track(si, sj, new_track, new_data)
if check_loop((si, sj), prev_dir, new_data):
continue
stack.append(new_data)
return
def show(data):
cells = data[0]
print()
for i in range(H):
row = ""
for j in range(W):
row += cells[(i, j)]+" "
print(row)
print()
data = (cells, tracks, row_counters, col_counters)
init(data)
stack = [data]
while stack:
print("len(stack)",len(stack))
data=stack.pop()
cells, tracks, row_counters, col_counters = data
reboot = False
while True:
updated_1 = check_fill(data)
if reboot:
break
updated_2 = search_placeable_cells(data)
if reboot:
break
updated_3 = search_unknown_cells_1(data)
updated_4 = search_unknown_cells_2(data)
updated_5 = avoid_loop(data)
if reboot:
break
if updated_1 or updated_2 or updated_3 or updated_4 or updated_5:
continue
break
if reboot:
continue
total_counter = sum(row_counters, Counter())
if total_counter[PLACED]+total_counter[UNPLACEABLE] == H*W:
path = [next_dir for _, _, next_dir in output_path(data)]
if len(path) == total_counter[PLACED]:
print("GOAL")
break
else:
continue
print("dfs")
dfs(data)
continue
show(data)
res = "".join(path)
return res
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'}},
),
(
[6, 5, 7, 7, 5, 7, 7, 8, 5, 3],
[5, 4, 7, 8, 7, 6, 7, 4, 4, 8],
(1, 0),
(9, 5),
{(1, 0): {'N'}, (3, 0): {'E', 'S'}, (4, 5): {'W', 'S'},
(6, 2): {'W', 'S'}, (6, 4): {'E', 'S'}, (6, 5): {'E', 'W'},
(8, 3): {'E', 'W'}, (9, 5): {'E'}},
),
)
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.')
May 13, 2020
