Skip to main content

Gold Mine Problem

The Gold Mine Problem is a classic dynamic programming problem where we are given a 2D matrix representing a gold mine. Each cell in the matrix contains a certain amount of gold. The objective is to find the maximum amount of gold that can be collected by starting at any column of the first row and moving only right, right-up, or right-down in subsequent columns until reaching the last column. In this article, we will explain the problem statement and provide a Java solution using dynamic programming.

Problem Statement:

Given a 2D matrix representing a gold mine, we need to find the maximum amount of gold that can be collected by starting at any column of the first row and moving only right, right-up, or right-down in subsequent columns until reaching the last column.

Code Solution:

To solve this problem efficiently, we can use dynamic programming. The idea is to calculate the maximum amount of gold that can be collected at each cell in the matrix by considering the maximum amount of gold that can be collected from the neighboring cells in the previous column. We will iterate column-wise from left to right, updating the values in the matrix.

// Java Program 
// Gold Mine Problem
public class GoldMineProblem
{
    public void maxGold(int[][] goldMine)
    {
        int row = goldMine.length;
        int col = goldMine[0].length;
        int max = 0;
        for (int i = 1; i < col; ++i)
        {
            for (int j = 0; j < row; ++j)
            {
                max = Integer.MIN_VALUE;
                if (goldMine[j][i - 1] + goldMine[j][i] > max)
                {
                    // Left
                    max = goldMine[j][i - 1] + goldMine[j][i];
                }
                if (j - 1 >= 0 && goldMine[j - 1][i - 1] + goldMine[j][i] > max)
                {
                    // Top Left
                    max = goldMine[j - 1][i - 1] + goldMine[j][i];
                }
                if (j + 1 < row && goldMine[j + 1][i - 1] + goldMine[j][i] > max)
                {
                    // Botoom Left
                    max = goldMine[j + 1][i - 1] + goldMine[j][i];
                }
                goldMine[j][i] = max;
            }
        }
        // Check result in last column
        max = goldMine[0][col - 1];
        for (int i = 1; i < row; ++i)
        {
            if (max < goldMine[i][col - 1])
            {
                max = goldMine[i][col - 1];
            }
        }
        System.out.println(max);
    }
    public static void main(String[] args)
    {
        GoldMineProblem task = new GoldMineProblem();
        int[][] matrix = {
            {
                14 , 5 , 6 , 9 , 3
            },
            {
                12 , 9 , 7 , 10 , 2
            },
            {
                15 , 6 , 8 , 3 , 1
            },
            {
                13 , 8 , 9 , 4 , 2
            }
        };
        // [15 + 9 + 8 + 10 + 3] = 45
        task.maxGold(matrix);
    }
}

Output

45
// Include header file
#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;
// C++ Program 
// Gold Mine Problem
class GoldMineProblem
{
    public: void maxGold(vector < vector < int >> goldMine)
    {
        int row = goldMine.size();
        int col = goldMine[0].size();
        int max = 0;
        for (int i = 1; i < col; ++i)
        {
            for (int j = 0; j < row; ++j)
            {
                max = INT_MIN;
                if (goldMine[j][i - 1] + goldMine[j][i] > max)
                {
                    // Left
                    max = goldMine[j][i - 1] + goldMine[j][i];
                }
                if (j - 1 >= 0 && goldMine[j - 1][i - 1] + goldMine[j][i] > max)
                {
                    // Top Left
                    max = goldMine[j - 1][i - 1] + goldMine[j][i];
                }
                if (j + 1 < row && goldMine[j + 1][i - 1] + goldMine[j][i] > max)
                {
                    // Botoom Left
                    max = goldMine[j + 1][i - 1] + goldMine[j][i];
                }
                goldMine[j][i] = max;
            }
        }
        // Check result in last column
        max = goldMine[0][col - 1];
        for (int i = 1; i < row; ++i)
        {
            if (max < goldMine[i][col - 1])
            {
                max = goldMine[i][col - 1];
            }
        }
        cout << max << endl;
    }
};
int main()
{
    GoldMineProblem *task = new GoldMineProblem();
    vector < vector < int >> matrix
    {
        {
            14 , 5 , 6 , 9 , 3
        } , {
            12 , 9 , 7 , 10 , 2
        } , {
            15 , 6 , 8 , 3 , 1
        } , {
            13 , 8 , 9 , 4 , 2
        }
    };
    // [15 + 9 + 8 + 10 + 3] = 45
    task->maxGold(matrix);
    return 0;
}

Output

45
// Include namespace system
using System;
// Csharp Program 
// Gold Mine Problem
public class GoldMineProblem
{
    public void maxGold(int[,] goldMine)
    {
        int row = goldMine.GetLength(0);
        int col = goldMine.GetLength(1);
        int max = 0;
        for (int i = 1; i < col; ++i)
        {
            for (int j = 0; j < row; ++j)
            {
                max = int.MinValue;
                if (goldMine[j,i - 1] + goldMine[j,i] > max)
                {
                    // Left
                    max = goldMine[j,i - 1] + goldMine[j,i];
                }
                if (j - 1 >= 0 && goldMine[j - 1,i - 1] + goldMine[j,i] > max)
                {
                    // Top Left
                    max = goldMine[j - 1,i - 1] + goldMine[j,i];
                }
                if (j + 1 < row && goldMine[j + 1,i - 1] + goldMine[j,i] > max)
                {
                    // Botoom Left
                    max = goldMine[j + 1,i - 1] + goldMine[j,i];
                }
                goldMine[j,i] = max;
            }
        }
        // Check result in last column
        max = goldMine[0,col - 1];
        for (int i = 1; i < row; ++i)
        {
            if (max < goldMine[i,col - 1])
            {
                max = goldMine[i,col - 1];
            }
        }
        Console.WriteLine(max);
    }
    public static void Main(String[] args)
    {
        GoldMineProblem task = new GoldMineProblem();
        int[,] matrix = {
            {
                14 , 5 , 6 , 9 , 3
            },
            {
                12 , 9 , 7 , 10 , 2
            },
            {
                15 , 6 , 8 , 3 , 1
            },
            {	
                13 , 8 , 9 , 4 , 2
            }
        };
        // [15 + 9 + 8 + 10 + 3] = 45
        task.maxGold(matrix);
    }
}

Output

45
package main
import "math"
import "fmt"
// Go Program 
// Gold Mine Problem
type GoldMineProblem struct {}
func getGoldMineProblem() * GoldMineProblem {
    var me *GoldMineProblem = &GoldMineProblem {}
    return me
}
func(this GoldMineProblem) maxGold(goldMine[][] int) {
    var row int = len(goldMine)
    var col int = len(goldMine[0])
    var max int = 0
    for i := 1 ; i < col ; i++ {
        for j := 0 ; j < row ; j++ {
            max = math.MinInt64
            if goldMine[j][i - 1] + goldMine[j][i] > max {
                // Left
                max = goldMine[j][i - 1] + goldMine[j][i]
            }
            if j - 1 >= 0 && goldMine[j - 1][i - 1] + goldMine[j][i] > max {
                // Top Left
                max = goldMine[j - 1][i - 1] + goldMine[j][i]
            }
            if j + 1 < row && goldMine[j + 1][i - 1] + goldMine[j][i] > max {
                // Botoom Left
                max = goldMine[j + 1][i - 1] + goldMine[j][i]
            }
            goldMine[j][i] = max
        }
    }
    // Check result in last column
    max = goldMine[0][col - 1]
    for i := 1 ; i < row ; i++ {
        if max < goldMine[i][col - 1] {
            max = goldMine[i][col - 1]
        }
    }
    fmt.Println(max)
}
func main() {
    var task * GoldMineProblem = getGoldMineProblem()
    var matrix = [][] int   {
        { 14 , 5 , 6 , 9 , 3 },
        { 12 , 9 , 7 , 10 , 2 },
        { 15 , 6 , 8 , 3 , 1 },
        { 13 , 8 , 9 , 4 , 2 },
    }
    // [15 + 9 + 8 + 10 + 3] = 45
    task.maxGold(matrix)
}

Output

45
<?php
// Php Program 
// Gold Mine Problem
class GoldMineProblem
{
    public	function maxGold($goldMine)
    {
        $row = count($goldMine);
        $col = count($goldMine[0]);
        $max = 0;
        for ($i = 1; $i < $col; ++$i)
        {
            for ($j = 0; $j < $row; ++$j)
            {
                $max = -PHP_INT_MAX;
                if ($goldMine[$j][$i - 1] + $goldMine[$j][$i] > $max)
                {
                    // Left
                    $max = $goldMine[$j][$i - 1] + $goldMine[$j][$i];
                }
                if ($j - 1 >= 0 && $goldMine[$j - 1][$i - 1] + 
                    $goldMine[$j][$i] > $max)
                {
                    // Top Left
                    $max = $goldMine[$j - 1][$i - 1] + $goldMine[$j][$i];
                }
                if ($j + 1 < $row && $goldMine[$j + 1][$i - 1] + 
                    $goldMine[$j][$i] > $max)
                {
                    // Botoom Left
                    $max = $goldMine[$j + 1][$i - 1] + $goldMine[$j][$i];
                }
                $goldMine[$j][$i] = $max;
            }
        }
        // Check result in last column
        $max = $goldMine[0][$col - 1];
        for ($i = 1; $i < $row; ++$i)
        {
            if ($max < $goldMine[$i][$col - 1])
            {
                $max = $goldMine[$i][$col - 1];
            }
        }
        echo($max.
            "\n");
    }
}

function main()
{
    $task = new GoldMineProblem();
    $matrix = array(
        array(14, 5, 6, 9, 3), 
        array(12, 9, 7, 10, 2), 
        array(15, 6, 8, 3, 1), 
        array(13, 8, 9, 4, 2)
    );
    // [15 + 9 + 8 + 10 + 3] = 45
    $task->maxGold($matrix);
}
main();

Output

45
// Node JS Program 
// Gold Mine Problem
class GoldMineProblem
{
    maxGold(goldMine)
    {
        var row = goldMine.length;
        var col = goldMine[0].length;
        var max = 0;
        for (var i = 1; i < col; ++i)
        {
            for (var j = 0; j < row; ++j)
            {
                max = -Number.MAX_VALUE;
                if (goldMine[j][i - 1] + goldMine[j][i] > max)
                {
                    // Left
                    max = goldMine[j][i - 1] + goldMine[j][i];
                }
                if (j - 1 >= 0 && goldMine[j - 1][i - 1] + goldMine[j][i] > max)
                {
                    // Top Left
                    max = goldMine[j - 1][i - 1] + goldMine[j][i];
                }
                if (j + 1 < row && goldMine[j + 1][i - 1] + goldMine[j][i] > max)
                {
                    // Botoom Left
                    max = goldMine[j + 1][i - 1] + goldMine[j][i];
                }
                goldMine[j][i] = max;
            }
        }
        // Check result in last column
        max = goldMine[0][col - 1];
        for (var i = 1; i < row; ++i)
        {
            if (max < goldMine[i][col - 1])
            {
                max = goldMine[i][col - 1];
            }
        }
        console.log(max);
    }
}

function main()
{
    var task = new GoldMineProblem();
    var matrix = [
        [14, 5, 6, 9, 3],
        [12, 9, 7, 10, 2],
        [15, 6, 8, 3, 1],
        [13, 8, 9, 4, 2]
    ];
    // [15 + 9 + 8 + 10 + 3] = 45
    task.maxGold(matrix);
}
main();

Output

45
import sys
#  Python 3 Program 
#  Gold Mine Problem
class GoldMineProblem :
    def maxGold(self, goldMine) :
        row = len(goldMine)
        col = len(goldMine[0])
        max = 0
        i = 1
        while (i < col) :
            j = 0
            while (j < row) :
                max = -sys.maxsize
                if (goldMine[j][i - 1] + goldMine[j][i] > max) :
                    #  Left
                    max = goldMine[j][i - 1] + goldMine[j][i]
                
                if (j - 1 >= 0 and goldMine[j - 1][i - 1] + 
                    goldMine[j][i] > max) :
                    #  Top Left
                    max = goldMine[j - 1][i - 1] + goldMine[j][i]
                
                if (j + 1 < row and goldMine[j + 1][i - 1] + 
                    goldMine[j][i] > max) :
                    #  Botoom Left
                    max = goldMine[j + 1][i - 1] + goldMine[j][i]
                
                goldMine[j][i] = max
                j += 1
            
            i += 1
        
        #  Check result in last column
        max = goldMine[0][col - 1]
        i = 1
        while (i < row) :
            if (max < goldMine[i][col - 1]) :
                max = goldMine[i][col - 1]
            
            i += 1
        
        print(max)
    

def main() :
    task = GoldMineProblem()
    matrix = [
        [14, 5, 6, 9, 3],
        [12, 9, 7, 10, 2],
        [15, 6, 8, 3, 1],
        [13, 8, 9, 4, 2]
    ]
    #  [15 + 9 + 8 + 10 + 3] = 45
    task.maxGold(matrix)

if __name__ == "__main__": main()

Output

45
#  Ruby Program 
#  Gold Mine Problem
class GoldMineProblem 
    def maxGold(goldMine) 
        row = goldMine.length
        col = goldMine[0].length
        max = 0
        i = 1
        while (i < col) 
            j = 0
            while (j < row) 
                max = -(2 ** (0. size * 8 - 2))
                if (goldMine[j][i - 1] + goldMine[j][i] > max) 
                    #  Left
                    max = goldMine[j][i - 1] + goldMine[j][i]
                end

                if (j - 1 >= 0 && goldMine[j - 1][i - 1] + 
                    goldMine[j][i] > max) 
                    #  Top Left
                    max = goldMine[j - 1][i - 1] + goldMine[j][i]
                end

                if (j + 1 < row && goldMine[j + 1][i - 1] + 
                    goldMine[j][i] > max) 
                    #  Botoom Left
                    max = goldMine[j + 1][i - 1] + goldMine[j][i]
                end

                goldMine[j][i] = max
                j += 1
            end

            i += 1
        end

        #  Check result in last column
        max = goldMine[0][col - 1]
        i = 1
        while (i < row) 
            if (max < goldMine[i][col - 1]) 
                max = goldMine[i][col - 1]
            end

            i += 1
        end

        print(max, "\n")
    end

end

def main() 
    task = GoldMineProblem.new()
    matrix = [
        [14, 5, 6, 9, 3],
        [12, 9, 7, 10, 2],
        [15, 6, 8, 3, 1],
        [13, 8, 9, 4, 2]
    ]
    #  [15 + 9 + 8 + 10 + 3] = 45
    task.maxGold(matrix)
end

main()

Output

45
// Scala Program 
// Gold Mine Problem
class GoldMineProblem()
{
    def maxGold(goldMine: Array[Array[Int]]): Unit = {
        var row: Int = goldMine.length;
        var col: Int = goldMine(0).length;
        var max: Int = 0;
        var i: Int = 1;
        while (i < col)
        {
            var j: Int = 0;
            while (j < row)
            {
                max = Int.MinValue;
                if (goldMine(j)(i - 1) + goldMine(j)(i) > max)
                {
                    // Left
                    max = goldMine(j)(i - 1) + goldMine(j)(i);
                }
                if (j - 1 >= 0 && goldMine(j - 1)(i - 1) + 
                    goldMine(j)(i) > max)
                {
                    // Top Left
                    max = goldMine(j - 1)(i - 1) + goldMine(j)(i);
                }
                if (j + 1 < row && goldMine(j + 1)(i - 1) + 
                    goldMine(j)(i) > max)
                {
                    // Botoom Left
                    max = goldMine(j + 1)(i - 1) + goldMine(j)(i);
                }
                goldMine(j)(i) = max;
                j += 1;
            }
            i += 1;
        }
        // Check result in last column
        max = goldMine(0)(col - 1);
        i = 1;
        while (i < row)
        {
            if (max < goldMine(i)(col - 1))
            {
                max = goldMine(i)(col - 1);
            }
            i += 1;
        }
        println(max);
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var task: GoldMineProblem = new GoldMineProblem();
        var matrix: Array[Array[Int]] = Array(
            Array(14, 5, 6, 9, 3), 
            Array(12, 9, 7, 10, 2), 
            Array(15, 6, 8, 3, 1), 
            Array(13, 8, 9, 4, 2)
        );
        // [15 + 9 + 8 + 10 + 3] = 45
        task.maxGold(matrix);
    }
}

Output

45
import Foundation;
// Swift 4 Program 
// Gold Mine Problem
class GoldMineProblem
{
    func maxGold(_ goldMine: inout[[Int]])
    {
        let row: Int = goldMine.count;
        let col: Int = goldMine[0].count;
        var max: Int = 0;
        var i: Int = 1;
        while (i < col)
        {
            var j: Int = 0;
            while (j < row)
            {
                max = Int.min;
                if (goldMine[j][i - 1] + goldMine[j][i] > max)
                {
                    // Left
                    max = goldMine[j][i - 1] + goldMine[j][i];
                }
                if (j - 1 >= 0 && goldMine[j - 1][i - 1] + 
                    goldMine[j][i] > max)
                {
                    // Top Left
                    max = goldMine[j - 1][i - 1] + goldMine[j][i];
                }
                if (j + 1 < row && goldMine[j + 1][i - 1] + 
                    goldMine[j][i] > max)
                {
                    // Botoom Left
                    max = goldMine[j + 1][i - 1] + goldMine[j][i];
                }
                goldMine[j][i] = max;
                j += 1;
            }
            i += 1;
        }
        // Check result in last column
        max = goldMine[0][col - 1];
        i = 1;
        while (i < row)
        {
            if (max < goldMine[i][col - 1])
            {
                max = goldMine[i][col - 1];
            }
            i += 1;
        }
        print(max);
    }
}
func main()
{
    let task: GoldMineProblem = GoldMineProblem();
    var matrix: [[Int]] = [
        [14, 5, 6, 9, 3],
        [12, 9, 7, 10, 2],
        [15, 6, 8, 3, 1],
        [13, 8, 9, 4, 2]
    ];
    // [15 + 9 + 8 + 10 + 3] = 45
    task.maxGold(&matrix);
}
main();

Output

45
// Kotlin Program 
// Gold Mine Problem
class GoldMineProblem
{
    fun maxGold(goldMine: Array < Array < Int >> ): Unit
    {
        val row: Int = goldMine.count();
        val col: Int = goldMine[0].count();
        var max: Int;
        var i: Int = 1;
        while (i < col)
        {
            var j: Int = 0;
            while (j < row)
            {
                max = Int.MIN_VALUE;
                if (goldMine[j][i - 1] + goldMine[j][i] > max)
                {
                    // Left
                    max = goldMine[j][i - 1] + goldMine[j][i];
                }
                if (j - 1 >= 0 && goldMine[j - 1][i - 1] + 
                    goldMine[j][i] > max)
                {
                    // Top Left
                    max = goldMine[j - 1][i - 1] + goldMine[j][i];
                }
                if (j + 1 < row && goldMine[j + 1][i - 1] + 
                    goldMine[j][i] > max)
                {
                    // Botoom Left
                    max = goldMine[j + 1][i - 1] + goldMine[j][i];
                }
                goldMine[j][i] = max;
                j += 1;
            }
            i += 1;
        }
        // Check result in last column
        max = goldMine[0][col - 1];
        i = 1;
        while (i < row)
        {
            if (max < goldMine[i][col - 1])
            {
                max = goldMine[i][col - 1];
            }
            i += 1;
        }
        println(max);
    }
}
fun main(args: Array < String > ): Unit
{
    val task: GoldMineProblem = GoldMineProblem();
    val matrix: Array < Array < Int >> = arrayOf(
        arrayOf(14, 5, 6, 9, 3), 
        arrayOf(12, 9, 7, 10, 2), 
        arrayOf(15, 6, 8, 3, 1), 
        arrayOf(13, 8, 9, 4, 2)
    );
    // [15 + 9 + 8 + 10 + 3] = 45
    task.maxGold(matrix);
}

Output

45

Explanation:

  1. We start by defining the maxGold method that takes a 2D array goldMine as input. This method will calculate and output the maximum amount of gold that can be collected.

  2. We retrieve the number of rows and columns in the goldMine matrix using goldMine.length and goldMine[0].length, respectively.

  3. We initialize a variable max to store the maximum amount of gold.

  4. We iterate column-wise from the second column (index 1) to the last column. Inside this loop, we iterate row-wise.

  5. For each cell, we initialize max to Integer.MIN_VALUE, which is the smallest possible integer value. This ensures that any gold amount will be greater than the initial value of max.

  6. We consider three possible paths to reach the current cell: from the left, top-left, or bottom-left cell.

  7. We compare the sum of the gold amount in the previous column's cell and the current cell with the current maximum (max). If it is greater, we update max accordingly.

  8. Similarly, we check the top-left and bottom-left cells if they exist and update max if the sum of their gold amounts and the current cell's gold amount is greater.

  9. Once we have determined the maximum amount of gold that can be collected at the current cell, we update the value of that cell in the goldMine matrix.

  10. After completing the column-wise iteration, we need to find the maximum value in the last column. We initialize max with the value of the first cell in the last column.

  11. We iterate over the remaining cells in the last column and update max if a larger value is found.

  12. Finally, we output the value of max, which represents the maximum amount of gold that can be collected.

Example Output:

In the given example, the maximum amount of gold that can be collected is 45. The path that yields this maximum value is [15, 9, 8, 10, 3].

The Gold Mine Problem can be efficiently solved using dynamic programming techniques. By breaking down the problem into subproblems and calculating the maximum amount of gold at each cell, we can find the overall maximum amount of gold that can be collected. The Java implementation provided in this article demonstrates the step-by-step process of solving the problem. By understanding the problem statement and the corresponding solution, you can apply similar techniques to solve other dynamic programming problems efficiently.





Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment