52 lines
1.5 KiB
Python
52 lines
1.5 KiB
Python
from functools import namedtuple
|
|
from lib_a_star import A_Star
|
|
|
|
|
|
def get_grid():
|
|
with open("../txt/e081.txt", "r") as f:
|
|
grid = list(map(lambda line: list(map(int, line.split(","))),
|
|
f.readlines()))
|
|
return grid
|
|
|
|
|
|
def euler_081():
|
|
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))
|
|
# down neighbor
|
|
if not node.row + 1 == n_rows:
|
|
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) == 2427) # Example from problem statement.
|
|
return cost(get_grid())
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print("e081.py: " + str(euler_081()))
|
|
assert(euler_081() == 427337)
|