Gold Mine Problem In C++

The Gold Mine Challenge introduces core concepts essential to the principles learned through dynamic programming, encompassing optimization, decision-making, and state transition principles. In practical scenarios, the grid structure and movement constraints of the challenge facilitate its application in activities like strategic resource allocation and navigating constrained options at various decision junctures.

There is a concept known as the Gold Mine Problem, which is a dynamic programming problem that deals with accumulation in a two-dimensional grid in my world. They have designed the mine in the form of an n x m grid, with each cell holding a specified quantity of gold. They differ in the sense that in the matrix , you do not always start from the first row, and you get gold from any row of the first column. The target is to get to the last column, and the more gold you collect as you traverse the field, the better. However, movement is restricted to three directions at each step:

• ✅ Right (→): One can transition from a cell (i, j) to (i, j+1), that is, directly to the right.
• ✅ Right-up diagonal (↗): You can go from cell (i, j) to (i-1, j+1), right and up (except if it is the first row).
• ✅ Right-down diagonal (↘): From a cell (i,j), one may go to (i+1, j+1), rightward and downward if not at the bottommost row.

In practical scenarios, the Gold Mine Problem serves as a representation of various real-world challenges. The utilization of grid-based movements finds relevance in sectors necessitating strategic resource allocation, operational coordination, and navigation within confined spaces. For instance, it finds application in mapping optimal delivery routes for companies, as certain paths yield higher resource or financial returns compared to others.

Besides providing a comprehensive demonstration of breaking down a complex issue into smaller, solvable sub-problems, a fundamental tenet of dynamic programming, it introduces a universal method for addressing optimization challenges across various disciplines like economics, operations research, and computer science. The Gold Mine Problem serves as a prominent example of how theoretical methodologies intersect with practical decision-making in real-world scenarios.

Problem Overview

The grid for the mine contains gold in different cells, with the quantity of gold collected determined by the path taken through the grid. The task involves determining the most profitable path from the initial column to the final column, considering specific movement constraints. Players have the flexibility to start from any row in the initial column and conclude in any row of the final column.

The challenge arises in optimizing the route through the mine due to the various options at each move: you can choose to move right, upwards diagonally, or downwards diagonally. When dealing with larger grids, computing all potential paths through the mine would involve evaluating an exponential number of possibilities, making it impractical. This is where the concept of dynamic programming becomes essential.

Dynamic Programming Approach

Ultimately, a dynamic programming (DP) approach is employed to tackle the issue with greater efficiency. In this scenario, a DP table is generated where each cell, denoted as dpi, holds the highest gold quantity achievable upon reaching that specific cell (i, j). The calculation for each cell involves determining the maximum gold accumulation from the three adjacent cells: the one on the right, the one on the right diagonal, and the one directly above. Consequently, the problem at hand is broken down into multiple interconnected subproblems, which are then resolved in a sequential manner.

The final result is derived from the initial column in the dynamic programming table once it has been populated with the highest values. This figure represents the maximum quantity of gold that can be gathered by commencing at any row in the initial column and concluding at any column in the final row.

Program:

Let's consider a C++ code example to demonstrate the Gold-Mine Problem.

#include <iostream>
#include <vector>
#include <algorithm> // For std::max
using namespace std;
// Function to calculate the maximum gold collectible in the gold mine
int getMaxGold(vector<vector<int>>& goldMine, int n, int m) {
    // Create a DP table to store the maximum gold collectible at each cell
    vector<vector<int>> dp(n, vector<int>(m, 0));
    // Iterate over the grid starting from the last column and work backward
    for (int col = m - 1; col >= 0; col--) {
        for (int row = 0; row < n; row++) {
            // Gold collected from the current cell
            int currentGold = goldMine[row][col];
            // Three possible directions to move to the next column:
            // 1. Right (same row)
            // 2. Right-up diagonal (previous row)
            // 3. Right-down diagonal (next row)
            // Handle edge cases to ensure we don't go out of bounds
            int goldRight = (col == m - 1) ? 0 : dp[row][col + 1]; // Move to the right
            int goldRightUp = (row == 0 || col == m - 1) ? 0 : dp[row - 1][col + 1]; // Move to the right-up diagonal
            int goldRightDown = (row == n - 1 || col == m - 1) ? 0 : dp[row + 1][col + 1]; // Move to the right-down diagonal
            // Take the maximum gold that can be collected from the next column
            dp[row][col] = currentGold + max({goldRight, goldRightUp, goldRightDown});
        }
    }
    // Find the maximum gold collectible from any row in the first column
    int maxGold = dp[0][0];
    for (int i = 1; i < n; i++) {
        maxGold = max(maxGold, dp[i][0]);
    }
    // Return the maximum gold collectible
    return maxGold;
}
// Function to print the gold mine matrix
void printGoldMine(const vector<vector<int>>& goldMine, int n, int m) {
    cout << "Gold Mine Grid:" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << goldMine[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
// Main function to run multiple test cases
int main() {
    // Example 1
    vector<vector<int>> goldMine1 = {
        {1, 3, 1, 5},
        {2, 2, 4, 1},
        {5, 0, 2, 3},
        {0, 6, 1, 2}
    };
    int n1 = goldMine1.size();    // Number of rows in the first gold mine
    int m1 = goldMine1[0].size(); // Number of columns in the first gold mine
    // Print gold mine 1
    printGoldMine(goldMine1, n1, m1);
    // Get and print the maximum gold collectible for Example 1
    int maxGold1 = getMaxGold(goldMine1, n1, m1);
    cout << "Maximum gold collectible in gold mine 1: " << maxGold1 << endl;
    // Example 2
    vector<vector<int>> goldMine2 = {
        {10, 33, 13, 15},
        {22, 21, 4, 1},
        {5, 0, 2, 3},
        {0, 6, 14, 2}
    };
    int n2 = goldMine2.size();    // Number of rows in the second gold mine
    int m2 = goldMine2[0].size(); // Number of columns in the second gold mine
    // Print gold mine 2
    printGoldMine(goldMine2, n2, m2);
    // Get and print the maximum gold collectible for Example 2
    int maxGold2 = getMaxGold(goldMine2, n2, m2);
    cout << "Maximum gold collectible in gold mine 2: " << maxGold2 << endl;
    // Example 3: Larger gold mine
    vector<vector<int>> goldMine3 = {
        {1, 3, 1, 5, 9, 2},
        {2, 2, 4, 1, 8, 6},
        {5, 0, 2, 3, 7, 4},
        {0, 6, 1, 2, 5, 8},
        {4, 2, 1, 9, 10, 3}
    };
    int n3 = goldMine3.size();    // Number of rows in the third gold mine
    int m3 = goldMine3[0].size(); // Number of columns in the third gold mine
    // Print gold mine 3
    printGoldMine(goldMine3, n3, m3);
    // Get and print the maximum gold collectible for Example 3
    int maxGold3 = getMaxGold(goldMine3, n3, m3);
    cout << "Maximum gold collectible in gold mine 3: " << maxGold3 << endl;
    // Example 4: Gold mine with minimal values
    vector<vector<int>> goldMine4 = {
        {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0},
        {0, 0, 0, 0}
    };
    int n4 = goldMine4.size();    // Number of rows in the fourth gold mine
    int m4 = goldMine4[0].size(); // Number of columns in the fourth gold mine
    // Print gold mine 4
    printGoldMine(goldMine4, n4, m4);
    // Get and print the maximum gold collectible for Example 4
    int maxGold4 = getMaxGold(goldMine4, n4, m4);
    cout << "Maximum gold collectible in gold mine 4: " << maxGold4 << endl;
    // Example 5: Larger gold mine with random values
    vector<vector<int>> goldMine5 = {
        {4, 5, 8, 9, 3, 1, 2},
        {6, 7, 1, 4, 9, 5, 8},
        {9, 3, 6, 2, 5, 7, 4},
        {2, 4, 7, 8, 1, 6, 9},
        {8, 6, 3, 1, 2, 4, 5},
        {5, 9, 4, 6, 7, 3, 2}
    };
    int n5 = goldMine5.size();    // Number of rows in the fifth gold mine
    int m5 = goldMine5[0].size(); // Number of columns in the fifth gold mine
    // Print gold mine 5
    printGoldMine(goldMine5, n5, m5);
    // Get and print the maximum gold collectible for Example 5
    int maxGold5 = getMaxGold(goldMine5, n5, m5);
    cout << "Maximum gold collectible in gold mine 5: " << maxGold5 << endl;
    return 0;
}

Output:

Gold Mine Grid:
1 3 1 5 
2 2 4 1 
5 0 2 3 
0 6 1 2 
Maximum gold collectible in gold mine 1: 16
Gold Mine Grid:
10 33 13 15 
22 21 4 1 
5 0 2 3 
0 6 14 2 
Maximum gold collectible in gold mine 2: 83
Gold Mine Grid:
1 3 1 5 9 2 
2 2 4 1 8 6 
5 0 2 3 7 4 
0 6 1 2 5 8 
4 2 1 9 10 3 
Maximum gold collectible in gold mine 3: 39
Gold Mine Grid:
0 0 0 0 
0 0 0 0 
0 0 0 0 
0 0 0 0 
Maximum gold collectible in gold mine 4: 0
Gold Mine Grid:
4 5 8 9 3 1 2 
6 7 1 4 9 5 8 
9 3 6 2 5 7 4 
2 4 7 8 1 6 9 
8 6 3 1 2 4 5 
5 9 4 6 7 3 2 
Maximum gold collectible in gold mine 5: 58

Explanation:

• ✅ Libraries and Namespace: The code begins by including standard libraries such as <iostream>, <vector>, and <algorithm>. These libraries provide basic input-output functionalities, container management (2D vectors in this case), and algorithmic utilities like std::max for finding the maximum value among multiple numbers. The use of namespace std is declared to simplify code by avoiding prefixing std:: before standard library functions.
• ✅ Function getMaxGold: This is the main function that calculates the maximum amount of gold collectible in the gold mine. Let's break it down: Input: The function takes a 2D vector goldMine representing the gold mine grid and two integers n and m, representing the number of rows and columns, respectively. Dynamic Programming (DP) Table: A 2D DP table dpn is initialized to store the maximum gold collectible from each cell in the mine. Each entry dpi will hold the maximum amount of gold that can be collected, starting from the cell (i, j) and moving toward the right. Iterate Backward: The algorithm iterates from the last column (right-most) to the first column (left-most), calculating the maximum gold collectible at each cell based on the three possible moves: Right: Moving right to the same row. Right-up diagonal: Moving right and up (previous row). Right-down diagonal: Moving right and down (next row).
• ✅ Input: The function takes a 2D vector goldMine representing the gold mine grid and two integers n and m, representing the number of rows and columns, respectively.
• ✅ Dynamic Programming (DP) Table: A 2D DP table dpn is initialized to store the maximum gold collectible from each cell in the mine. Each entry dpi will hold the maximum amount of gold that can be collected, starting from the cell (i, j) and moving toward the right.
• ✅ Iterate Backward: The algorithm iterates from the last column (right-most) to the first column (left-most), calculating the maximum gold collectible at each cell based on the three possible moves:
• ✅ Right: Moving right to the same row.
• ✅ Right-up diagonal: Moving right and up (previous row).
• ✅ Right-down diagonal: Moving right and down (next row).

For each cell (i, j), the algorithm computes the maximum of these three moves and adds the current cell's gold (goldMinei) to it. The three possible values are:

• ✅ goldRight: Gold is collected by moving to the right (same row).
• ✅ goldRightUp: Gold is collected by moving right up (one row up, if not out of bounds).
• ✅ goldRightDown: Gold is collected by moving right-down (one row down, if not out of bounds).

To handle edge cases, like the first row where moving up is not possible or the last row where moving down is out of bounds, the code uses conditional statements to avoid accessing invalid indices.

• ✅ Final Result: Once the DP table is fully populated, the solution to the problem is found by selecting the maximum value from the first column. The goal is to start from any row in the first column and move to the last column. The function then returns this maximum value.
• ✅ Helper Function printGoldMine: This function takes the goldMine grid and prints it in a readable format. It's used in the main function to display the gold mine before calculating the maximum gold collectible.
• ✅ Main Function: The main function is where multiple test cases are executed to demonstrate how the solution works on different inputs. Five example gold mines are provided, each with different configurations: GoldMine1 and GoldMine2: These are simple test cases with different grid sizes and values. GoldMine3: This example uses a larger gold mine with 5 rows and 6 columns. GoldMine4: This is a test case with all zero values in the grid, representing an empty gold mine. GoldMine5: A more complex test case with random values to further test the robustness of the solution.
• ✅ GoldMine1 and GoldMine2: These are simple test cases with different grid sizes and values.
• ✅ GoldMine3: This example uses a larger gold mine with 5 rows and 6 columns.
• ✅ GoldMine4: This is a test case with all zero values in the grid, representing an empty gold mine.
• ✅ GoldMine5: A more complex test case with random values to further test the robustness of the solution.

For every gold mine, the software displays the grid, computes the highest attainable gold amount by utilizing the getMaxGold method, and then exhibits the outcomes on the console.

Complexity Analysis:

Time Complexity

The time complexity of the given C++ implementation for the Gold Mine Problem can be dissected by examining the primary stages of the algorithm: setup and populating the dynamic programming (DP) array.

Initialization of the DP Table:

The process begins by setting up a dynamic programming (DP) table, represented as a 2D array, with a size of n x m. Here, n corresponds to the total rows (indicating the height of the gold mine) and m represents the total columns (representing the width of the gold mine). The initialization of the table entails constructing a grid with n rows and m columns, where each cell is initially assigned a value of zero.

The time complexity of this stage scales in direct proportion to the quantity of items in the table, represented by n m. Consequently, the time complexity for initializing the DP table is O(n m).

Filling the DP Table:

Following the initialization of the dynamic programming (DP) table, the process entails iterating through each cell within the gold mine to populate the DP table with the highest amount of gold that can be collected at that specific location. This process is accomplished through the utilization of two nested loops:

The external loop cycles through every column, beginning from the rightmost column and progressing towards the leftmost one. This process entails m iterations, with m representing the overall count of columns within the grid.

The nested loop iterates over every row within the current column, resulting in n cycles per column, where n signifies the overall row count.

For each cell (i, j), the algorithm evaluates up to three possible movement options:

• ✅ Right (→): Transitioning to the same row in the next column.
• ✅ Right-up diagonal (↗): Moving to the previous row in the next column (if not in the first row).
• ✅ Right-down diagonal (↘): Moving to the next row in the next column (if not in the last row).

Each validation necessitates retrieving precalculated data from the DP table, which entails performing operations with constant time complexity. As a result, the calculation for each individual cell is O(1), resulting in an aggregate time complexity of O(n * m) for populating the complete DP table.

Given the presence of n rows and m columns, the computation involves handling n m cells. Each cell undergoes operations with constant time complexity for updating the DP table. Consequently, the overall time complexity for populating the DP table amounts to O(n m).

Finding the Maximum Value:

Once the dynamic programming (DP) table is populated, the next step in the algorithm is to determine the highest amount of gold that can be collected. This is achieved by examining the values in the initial column of the DP table. This process entails scanning through all n rows of the first column, resulting in n evaluations. Consequently, the computational complexity for this concluding phase is O(n).

Space Complexity

The space complexity of the algorithm is defined by the quantity of extra memory allocated for the DP table and any additional storage required.

DP Table:

The primary factor that impacts space usage is the dynamic programming (DP) table, which is a two-dimensional array with dimensions n x m. This array holds the highest amount of gold that can be collected from each cell as the algorithm navigates through the grid. Every cell in the table reflects the best solution achievable for that particular position, taking into account values calculated earlier. The space complexity of the DP table is O(n * m).

Auxiliary Variables:

In conjunction with the dynamic programming table, the procedure utilizes several integer variables like goldRight, goldRightUp, goldRightDown, and maxGold, to retain interim outcomes while processing. These variables serve as containers for temporary data throughout the process of determining the maximum amount of gold that can be gathered from each cell. Notably, the storage space needed for these additional variables stays consistent, irrespective of the dimensions of the input grid. As a result, the spatial demand for these variables is O(1).

The primary factor influencing space complexity is the storage required for the dynamic programming (DP) table, which scales at O(n * m). Conversely, the additional space (O(1)) plays a minor role in the overall comparison.

Therefore, the overall space complexity of the algorithm amounts to O(n * m).