Solving the math puzzle of the Schönbrunn maze in Vienna
# read the input from a file | |
n, m = [int(c) for c in input().split(' ')] | |
sx, sy = [int(c) for c in input().split(' ')] | |
ex, ey = [int(c) for c in input().split(' ')] | |
# utilities to convert coordinates to vertex id and vice versa | |
def coord_to_id(i, j): | |
return i * m + j | |
def id_to_coord(x): | |
return (x // m, x % n) | |
# store the grid | |
g = [ [int(c) for c in input().split(' ')] for _ in range(n)] | |
# build the graph | |
graph = {} | |
for i in range(n): | |
for j in range(m): | |
# read how many steps can be taken | |
steps = abs(g[i][j]) | |
if steps == 0: | |
continue | |
x = coord_to_id(i, j) | |
# define the list of neighbors | |
graph[x] = [] | |
# from the current tile x, jump "steps" tile up, left, down, right | |
if i - steps >= 0: | |
graph[x].append(coord_to_id(i-steps, j)) | |
if i + steps < n: | |
graph[x].append(coord_to_id(i+steps, j)) | |
if j - steps >= 0: | |
graph[x].append(coord_to_id(i, j-steps)) | |
if j + steps < m: | |
graph[x].append(coord_to_id(i, j+steps)) | |
start = coord_to_id(sx, sy) | |
end = coord_to_id(ex, ey) | |
# store all the solutions | |
paths = [] | |
# backtrack a solution | |
prev = {} | |
visited = set() | |
prev[start] = None | |
# called dfs, but is actually a complete search | |
def dfs(u): | |
if u == end: | |
a = end | |
p = [] | |
while a != None: | |
p.append(a) | |
a = prev[a] | |
paths.append(p) | |
return | |
for v in graph[u]: | |
if v not in visited: | |
visited.add(v) | |
prev[v] = u | |
dfs(v) | |
# complete search: pretend this path was not explored | |
# to consider it later | |
visited.remove(v) | |
# search | |
visited.add(start) | |
dfs(start) | |
# results | |
solutions = [] | |
for p in paths: | |
tiles = [id_to_coord(tile) for tile in p[::-1]] | |
s = sum([g[x[0]][x[1]] for x in tiles]) | |
# log all the solutions | |
solutions.append((s, len(tiles), tiles)) | |
# find the best | |
best = min(solutions, key=lambda s: (abs(s[0]), s[1])) | |
print('The best solution is a sum of', best[0], 'in', best[1], 'steps.') | |
sol = ' -> '.join([str(c) + ', tile ' + str(g[c[0]][c[1]]) for c in best[2]]) | |
print(sol) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment