Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Climbing Route by kurosawa4434
from functools import lru_cache
from collections import defaultdict
from itertools import permutations
def climbing_route(maze):
mz_dic = defaultdict(list)
hills = []
i_maze = [list(map(int, row)) for row in maze]
# setp1: make maze dictionary
for r, row in enumerate(i_maze):
for c, cell in enumerate(map(int, list(row))):
if cell and r < len(maze)-1 and i_maze[r+1][c]:
hills.append(((r, c), (r+1, c)))
if cell and c < len(maze[0])-1 and i_maze[r][c+1]:
hills.append(((r, c), (r, c+1)))
if r < len(maze)-1 and abs(cell - i_maze[r+1][c]) < 2:
mz_dic[(r, c)].append((r+1, c))
mz_dic[(r+1, c)].append((r, c))
if c < len(maze[0])-1 and abs(cell - i_maze[r][c+1]) < 2:
mz_dic[(r, c)].append((r, c+1))
mz_dic[(r, c+1)].append((r, c))
# setp2: make mountain list
mt = []
for h1, h2 in hills:
if not mt:
mt.append({h1, h2})
continue
for i, m in enumerate(mt):
if {h1, h2} & m:
mt[i] |= {h1, h2}
break
else:
mt.append({h1, h2})
ok = False
while not ok:
ok = True
for i, m1 in enumerate(mt):
for j, m2 in enumerate(mt[i+1:], start=i+1):
if m1 & m2:
mt[j] |= m1
del mt[i]
ok = False
break
if not ok:
break
# setp3: make tops list
tops = []
for m in mt:
tops.append(sorted(m, key=lambda x: i_maze[x[0]][x[1]])[-1])
# sub: calc_steps
@lru_cache()
def calc_steps(start, goal):
steps = 0
used_cells = {start}
next_cells = mz_dic[start]
while 1:
steps += 1
if goal in next_cells:
break
wk_cells = set()
for nc in next_cells:
wk_cells |= set(mz_dic[nc]) - used_cells
next_cells = wk_cells
used_cells |= wk_cells
return steps
# setp4: search shortest path
min_steps = 9999
for tgt in permutations(tops):
tgt = [(0, 0)] + list(tgt) + [(len(maze)-1, len(maze[0])-1)]
steps = 0
for start, goal in zip(tgt, tgt[1:]):
steps += calc_steps(start, goal)
min_steps = min(steps, min_steps)
return min_steps
July 13, 2017