51 lines
1.5 KiB
Python
51 lines
1.5 KiB
Python
from functools import namedtuple
|
|
from lib_a_star import A_Star
|
|
from e081 import get_grid
|
|
|
|
|
|
def euler_082():
|
|
Node = namedtuple("Node", ["row", "col"])
|
|
|
|
def cost(grid):
|
|
n_rows = len(grid)
|
|
n_cols = len(grid[0])
|
|
start_nodes = [Node(row, 0) for row in range(n_rows)]
|
|
end_nodes = [Node(row, n_cols - 1) for row in range(n_rows)]
|
|
|
|
def h(node):
|
|
c_self = grid[node.row][node.col]
|
|
c_steps = n_cols - node.col
|
|
return c_self + c_steps
|
|
|
|
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))
|
|
# 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_nodes, end_nodes, 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) == 994) # Example from problem statement.
|
|
return cost(get_grid())
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print("e082.py: " + str(euler_082()))
|
|
assert(euler_082() == 260324)
|