52 lines
1.5 KiB
Python
52 lines
1.5 KiB
Python
from functools import namedtuple
|
|
from lib_a_star import A_Star
|
|
from e081 import get_grid
|
|
|
|
|
|
def euler_083():
|
|
Node = namedtuple("Node", ["row", "col"])
|
|
|
|
def cost(grid):
|
|
n_rows = len(grid)
|
|
n_cols = len(grid[0])
|
|
start_node = Node(0, 0)
|
|
end_node = Node(n_rows - 1, n_cols - 1)
|
|
|
|
def h(node):
|
|
return (end_node.row - node.row) + (end_node.col - node.col)
|
|
|
|
def d(current_node, next_node):
|
|
return grid[next_node.row][next_node.col]
|
|
|
|
def neighbors(node):
|
|
neighbors = []
|
|
# right neighbor
|
|
if not node.col + 1 == n_cols:
|
|
neighbors.append(Node(node.row, node.col + 1))
|
|
# left neighbor
|
|
if not node.col == 0:
|
|
neighbors.append(Node(node.row, node.col - 1))
|
|
# down neighbor
|
|
if not node.row + 1 == n_rows:
|
|
neighbors.append(Node(node.row + 1, node.col))
|
|
# up neighbor
|
|
if not node.row == 0:
|
|
neighbors.append(Node(node.row - 1, node.col))
|
|
return neighbors
|
|
|
|
a = A_Star([start_node], [end_node], h, d, neighbors)
|
|
return a.cost
|
|
|
|
grid = [[131, 673, 234, 103, 18],
|
|
[201, 96, 342, 965, 150],
|
|
[630, 803, 746, 422, 111],
|
|
[537, 699, 497, 121, 956],
|
|
[805, 732, 524, 37, 331]]
|
|
assert(cost(grid) == 2297) # Example from problem statement.
|
|
return cost(get_grid())
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print("e083.py: " + str(euler_083()))
|
|
assert(euler_083() == 425185)
|