Python - Gold Mine Problem

Python – Gold Mine Problem

The Gold Mine Problem is a classic dynamic programming challenge. Given a grid where each cell represents an amount of gold, the goal is to collect the maximum amount of gold by starting from any row in the first column and moving to the right. Allowed moves include moving right, right-up, or right-down.

Problem Statement

You are given a gold mine represented as a 2D grid of dimensions m x n where each cell gold_mine[i][j] contains a certain amount of gold. Starting from any row in the first column, you can move in one of the following ways:

Right: gold_mine[i][j+1]
Right-up: gold_mine[i-1][j+1] (if i-1 is within bounds)
Right-down: gold_mine[i+1][j+1] (if i+1 is within bounds)

Your task is to determine the maximum amount of gold that can be collected when moving through the grid according to these rules.

Sample Input and Output

Example 1:

</>

Copy

# Input: Gold mine grid (3x3)
gold_mine = [
    [1, 3, 3],
    [2, 1, 4],
    [0, 6, 4]
]

# Expected Output:
# Maximum gold collected: 12

Explanation: In this grid, the optimal path yields a maximum of 12 gold. For example, starting from the second row (value 2) in the first column, moving to the third row in the next column (value 6), and finally to the third row in the last column (value 4) gives 2 + 6 + 4 = 12.

Example 2:

</>

Copy

# Input: Gold mine grid (4x4)
gold_mine = [
    [1, 3, 1, 5],
    [2, 2, 4, 1],
    [5, 0, 2, 3],
    [0, 6, 1, 2]
]

# Expected Output:
# Maximum gold collected: 16

Explanation: In this 4×4 grid, dynamic programming is used to evaluate all possible paths. One optimal path yields a total of 16 gold. The algorithm examines the potential moves (right, right-up, and right-down) at each step, ultimately determining that the best achievable amount is 16.

Solution Approach

The problem can be solved using a bottom-up dynamic programming approach. We construct a DP table of the same dimensions as the grid. Each cell dp[i][j] in this table represents the maximum gold that can be collected starting from that cell and moving to the right.

To fill the DP table, start from the last column and move leftwards. For each cell dp[i][j], calculate the maximum gold collectable as:

dp[i][j] = gold_mine[i][j] + max(right, right-up, right-down)

Where:

right = dp[i][j+1]
right-up = dp[i-1][j+1] (if i-1 is valid)
right-down = dp[i+1][j+1] (if i+1 is valid)

Finally, the maximum gold that can be collected is the maximum value in the first column of the DP table, as the miner can start from any row in that column.

Python Program

</>

Copy

def max_gold(gold_mine):
    """
    Compute the maximum amount of gold that can be collected from the gold mine.
    
    Parameters:
    gold_mine (List[List[int]]): 2D list representing the gold mine grid.
    
    Returns:
    int: Maximum gold that can be collected.
    """
    if not gold_mine or not gold_mine[0]:
        return 0
    
    m = len(gold_mine)    # Number of rows
    n = len(gold_mine[0]) # Number of columns
    
    # Initialize DP table with zeros
    dp = [[0] * n for _ in range(m)]
    
    # Fill the last column with the values from the gold mine
    for i in range(m):
        dp[i][n - 1] = gold_mine[i][n - 1]
    
    # Fill the DP table from the second last column to the first
    for j in range(n - 2, -1, -1):
        for i in range(m):
            # Move right
            right = dp[i][j + 1]
            
            # Move right-up (if within bounds)
            right_up = dp[i - 1][j + 1] if i - 1 >= 0 else 0
            
            # Move right-down (if within bounds)
            right_down = dp[i + 1][j + 1] if i + 1 < m else 0
            
            # Update DP table for the current cell
            dp[i][j] = gold_mine[i][j] + max(right, right_up, right_down)
    
    # The answer is the maximum value in the first column of dp
    return max(dp[i][0] for i in range(m))

# Test examples
print("Example 1:")
gold_mine1 = [
    [1, 3, 3],
    [2, 1, 4],
    [0, 6, 4]
]
print("Maximum Gold Collected:", max_gold(gold_mine1))  # Expected output: 12

print("\nExample 2:")
gold_mine2 = [
    [1, 3, 1, 5],
    [2, 2, 4, 1],
    [5, 0, 2, 3],
    [0, 6, 1, 2]
]
print("Maximum Gold Collected:", max_gold(gold_mine2))  # Expected output: 16

Explanation: The function max_gold() computes the maximum gold that can be collected using a dynamic programming approach. It initializes a DP table with the values from the last column of the grid, then iteratively fills the table by considering the best move from each cell (right, right-up, or right-down). The final answer is the maximum value found in the first column of the DP table, which represents the best starting point.

Conclusion

This tutorial demonstrated the Gold Mine Problem, a well-known dynamic programming challenge. We discussed the problem statement, provided sample examples with explanations, and implemented a Python program using a bottom-up dynamic programming approach. This problem illustrates how dynamic programming can optimize decision-making in grid-based problems by breaking down the problem into smaller, manageable subproblems.

TutorialKart

Python – Gold Mine Problem