Project Euler Problem 83 Solution

Project Euler Problem 83 Statement

In the matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297. $$ \begin{pmatrix} \color{darkred}{131} & 673 & \color{darkred}{234} & \color{darkred}{103} & \color{darkred}{18}\\ \color{darkred}{201} & \color{darkred}{96} & \color{darkred}{342} & 965 & \color{darkred}{150}\\ 630 & 803 & 746 & \color{darkred}{422} & \color{darkred}{111}\\ 537 & 699 & 497 & \color{darkred}{121} & 956\\ 805 & 732 & 524 & \color{darkred}{37} & \color{darkred}{331} \end{pmatrix} $$

Find the minimum path sum in given matrix.

Solution

Project Euler Problem 83 asks us to find the minimal path sum in a square matrix from the top-left corner $ (0,0) $ to the bottom-right corner $ (n-1, n-1) $. Unlike earlier matrix path problems (like Problem 81), we are allowed to move in four directions: up, down, left, and right.

The code below implements a version of Dijkstra's Algorithm for grid-based pathfinding. Here's how it works step by step:

1. Reading and Storing the Matrix

n = int(input())
grid = [list(map(int, input().split())) for _ in range(n)]

• We first read an integer n which specifies the size of the square matrix.
• We then read each row using list(map(int, input().split())) and store these rows in the list of lists grid.
• After this, grid[x][j] represents the integer value in row x, column y.

2. Initializing the Distance Matrix

dist = [[float('inf')] * n for _ in range(n)]
dist[0][0] = grid[0][0]

• We create a 2D list dist[][] to track the minimal cost to reach each cell (x, y) from (0, 0).
• Each entry is initialized to float('inf') (infinity).
• We set dist[0][0] = grid[0][0] because the cost to start at $(0, 0)$ is just the value of that cell.

3. Using a Min-Heap (Priority Queue)

from heapq import heappush, heappop
heap = [(grid[0][0], 0, 0)]

• We import heappush and heappop from heapq to maintain a priority queue.
• The heap stores tuples (cost, x, y), where:
  • current_cost is the minimal cost to reach (x, y).
  • x, y are coordinates of that cell.
• We initialize the heap with (grid[0][0], 0, 0), indicating the cost of the top-left cell.

4. Exploring Neighboring Cells

while heap:
    cost, x, y = heappop(heap)
    for nx, ny in [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]:
        if 0 <= nx < n and 0 <= ny < n:
            new_cost = cost + grid[nx][ny]
            if new_cost < dist[nx][ny]:
                dist[nx][ny] = new_cost
                heappush(heap, (new_cost, nx, ny))

1. Pop from the heap: We take the tuple (cost, x, y) with the smallest cost so far.
2. Explore neighbors: We look at the four possible moves: (x+1, y), (x-1, y), (x, y+1), and (x, y-1). For each neighbor (nx, ny), we ensure it's within the grid boundaries.
3. Relaxation step: We compute new_cost = cost + grid[nx][ny]. If new_cost < dist[nx][ny], we have found a better path to (nx, ny). We update dist[nx][ny] = new_cost and push (new_cost, nx, ny) onto the heap.

This process repeats, updating the distances until we've found the minimal cost path to every reachable cell.

5. Final Answer

print(dist[-1][-1])

• After the loop finishes, dist[n-1][n-1] holds the minimal cost to reach the bottom-right corner (n-1, n-1) from (0, 0) by moving in four possible directions.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 83

HackerRank Project Euler 83: the matrix size is increased to 700 × 700.