Skip to content

Instantly share code, notes, and snippets.

@jtpio
Last active August 29, 2015 14:22
Show Gist options
  • Save jtpio/f4175e0c38d2be4b44c9 to your computer and use it in GitHub Desktop.
Save jtpio/f4175e0c38d2be4b44c9 to your computer and use it in GitHub Desktop.
Solving the math puzzle of the Schönbrunn maze in Vienna
5 5
4 2
2 2
2 -2 4 -1 3
-3 3 -1 3 -2
1 -2 0 -2 3
-3 2 -3 2 -4
4 -2 1 -3 2
# 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