Can you solve this problem using C++?

[Xenophobe]

Greetings fellow programmers. I would like to share a problem with you. There is a 7x8 grid that has gold coins in it. Each number represents the number of gold coins in each cell. The rules of the game are:
1) You must start at the bottom left corner and end up at the top right
corner
2) You can only move up and to the right

What is the maximum possible number of gold you can end up with by the time you get to the top right corner? Show a nice C++ code that solves the problem.

5 1 0 4 1 1 2 0
0 3 2 1 0 3 0 1
4 3 0 6 5 0 1 0
3 1 0 3 4 0 1 3
0 5 2 0 1 1 5 1
2 1 6 1 6 0 2 1
0 0 4 3 2 3 0 2

[jonnin]

that sounds like a fun exercise. Can you show us your attempt and ask a question?

[lastchance]

Any advances?

Most gold is 33
Route is RRURRUUURUURR

[Duthomhas]

Also valid:

RRURRUUUURURR

(There’s a zero either way from the 5 to the 3.)

I had written my algorithm like lastchance, and got the same result has he, but then I swapped my test to prefer right over up to get the other possibility.


Either way you get a maximum gold of 33. Your assignment does not appear to require you to return the path taken like lastchance and I did.

This is a very simple recursive function. Consider the simplest case:

  2 0
  0 1
 
If I go up and recurse, do I wind-up with more gold than if I go right and recurse?

Finally, how do I know when to stop?

Good luck!

[Xenophobe]

@jonnin, here is my code, but it still has problems. I'm having a bad time trying to figure out a good way to check array boundaries. Check the comment at the very end of the code.

#include <iostream>
#include <vector>

using namespace std;

// Declare the dimensions of the array with in an 'enum'
enum {ROW = 7, COLUMN = 8};

// Declare a global variable 'totalGold'
// Declare a vector to record the path of numbers taken
int totalGold = 0;
vector<int> path;

// struct used to store position in the array
struct position
{
	int x;
	int y;

	position(){}
	position(int a, int b):x(a), y(b) {}
	void setPosition(position);
	void setPosition(int, int);
};

void position::setPosition(position sample){
	x = sample.x;
	y = sample.y;
}

void position::setPosition(int a, int b){
	x = a;
	y = b;
}
// ========================================= //

// ** Declaration of functions used in program ** //

// Check if position co-ordinates are out of bound
int indexOutOfBound(position);
// Compare the immideately above and right values and return the
// position of the bigger value
void compare(position&, int matrix[][COLUMN]);
// When position is at the very right column
void addAllAlongColumn(position, int matrix[][COLUMN]);
// When position is at the very top row
void addAllAlongRow(position, int matrix[][COLUMN]);
// Display vector
void show(vector<int>);
// ========================================= //
int main(){

	position checker(6, 0);
	int maze[ROW][COLUMN] = {  
                                                     {5, 1, 0, 4, 1, 1, 2, 0},
            				 	     {0, 3, 2, 1, 0, 3, 0, 1},
						     {4, 3, 0, 6, 5, 0, 1, 0},
           					     {3, 1, 0, 3, 4, 0, 1, 3},
 						     {0, 5, 2, 0, 1, 1, 5, 1},
            					     {2, 1, 6, 1, 6, 0, 2, 1},
            					     {0, 0, 4, 3, 2, 3, 0, 2}
           				 	 };

    while(true){
    	if(indexOutOfBound(checker) == checker.x + checker.y)
    		break;
    	else if(indexOutOfBound(checker) == checker.x){
    		addAllAlongColumn(checker, maze);
    		break;
    	}
    	else if (indexOutOfBound(checker) == checker.y){
    		addAllAlongRow(checker, maze);
    		break;
    	}

    	else
    		compare(checker, maze);

    }

    show(path);
    cout << endl << "Total gold coins = " << totalGold << endl;

    return 0;
}

// Function Declarations

int indexOutOfBound(position sample){
	// Beware that sample.x only goes upwards hence decreases
	if((sample.x < 0) && (sample.y >= COLUMN))
		return sample.x + sample.y;
	else if (sample.x < 0)
		return sample.y;
	else if(sample.y >= COLUMN)
		return sample.x;
	else
		return -2;
}
// =============================================================

void compare(position &sample, int matrix[][COLUMN]){
    // Number above is greater
	if(matrix[sample.x - 1][sample.y] > matrix[sample.x][sample.y + 1]){
		totalGold += matrix[sample.x - 1][sample.y];
		sample.setPosition(sample.x - 1, sample.y);
		path.push_back(matrix[sample.x][sample.y]);
	}
    // Number to the right is greater
	else if (matrix[sample.x][sample.y + 1] > matrix[sample.x - 1][sample.y]){
		totalGold += matrix[sample.x][sample.y + 1];
		sample.setPosition(sample.x, sample.y + 1);
		path.push_back(matrix[sample.x][sample.y]);
	}
    // Both numbers are equal
    // Restructure the next 'else if' condidition in a way that gives the 'offset' problem a solution
    // The 'offset' problem is listed on the very end of this page
	else if (matrix[sample.x - 1][sample.y] == matrix[sample.x][sample.y + 1]){
		if(matrix[sample.x - 2][sample.y] > matrix[sample.x][sample.y + 2]){
			totalGold += matrix[sample.x - 1][sample.y];
			sample.setPosition(sample.x - 1, sample.y);
			path.push_back(matrix[sample.x][sample.y]);
		}

		else if (matrix[sample.x][sample.y + 2] > matrix[sample.x - 2][sample.y]){
			totalGold += matrix[sample.x][sample.y + 1];
			sample.setPosition(sample.x, sample.y + 1);
			path.push_back(matrix[sample.x][sample.y]);
		}
	}
}
// =============================================================

void addAllAlongColumn(position sample, int matrix[][COLUMN]){
	for(int i = sample.x; i > -1; --i){
		totalGold += matrix[i][sample.y - 1];
		path.push_back(matrix[i][sample.y - 1]);
	}
}
// =============================================================

void addAllAlongRow(position sample, int matrix[][COLUMN]){
	for(int i = sample.y; i < COLUMN; ++i){
		totalGold += matrix[sample.x - 1][i];
		path.push_back(matrix[sample.x - 1][i]);
	}
}
// =============================================================

void show(vector<int> sample){
	for(unsigned int i = 0; i < sample.size(); ++i)
		cout << "[" << sample[i] << "]" << " ";
}

/* ===================================================
OFFSET PROBLEM:
	Assume the conditions where current position is at
	3 rows down and 1 column from the right (the cell
        that contains 3):
		int maze[3][4] = {
							{1,  2, 4, 5},
							{4,  5, 2, 0},
							{87, 5, 3, 2}
						 };
	After comparing 2 and 2 the program finds out that
	it needs to do further comparisons to figure out
	which the best path is. But it can't do a comparison
        between 4 and a non-existent number. What's the solution here?

	================================================== */

[Xenophobe]

@Duthomhas and @lastchance, how is going 'Right' the first best move? Because starting at 0 you should first go up (because 2 > 0).

P.S. It's not an assignment, it's one of the many 'Computer Science' problems I found on brilliant.org. You guys should check that website out. It's packed with many interesting problems.

[Duthomhas]

Just because 2 > 0 does not make up correct. Your goal is to find the maximal path.

You must think in terms of recursion. I’ve already given you a big hint. The function that does your recursion should be less than ten lines long (not counting spaces, etc).

[lastchance]

Actually, I did it directly, without recursion.

Analogy: imagine you are supplying an army along an ADVANCING FRONT.

Precisely 55 if...else tests, so very fast.
One extra 7x8 int array ... updated in careful order (or you could overwrite the original).
(Plus one 7x8 string array if you want the route).

Direct and explicit, can be done without recursion in 7x8-1 = 55 steps.


Give it a bit of time to run, then we can all swap codes!!


As @Duthomas notes there can be more than one maximal route. Here, there appear to be two. With a bit of code-jiggling:

Most gold is 33
Route is  ( RRURRUUURU || RRURRUUUUR ) URR

Here's one route:

.....120
.....3..
....50..
....4...
....1...
..616...
004.....

Thank-you for posting the challenge, @Xenophobe. It's a nice puzzle, and a good diversion from some recent heated threads (which I'm mortified to have joined).

[keskiverto]

I have seen something similar along with term dynamic programming.


You have your data matrix A.
Let there be score matrix B with same dimensions.
Lets call the lower left element (0,0) and upper right (n,m).

Fill the B with B(r,c) = A(r,c) + max( B(r-1,c), B(r,c-1) )
Now B(n,m) contains the maximal running sum of the matrix.

There are at least two approaches for the "missing boundaries".
1. Make the max(...) above test for it every time.
2. Fill the left column and bottom row of B with simplified equation(s), because you know that you are at boundary. You also know that other elements of B are not in boundary.


You can, if you want, trace a maximal path (or all of them) from B(n,m) to B(0,0). Recursion might be appropriate for getting all the paths.

P.S. It's not an assignment, it's one of the many 'Computer Science' problems I found on

Do you claim that you did not assign this problem for you to tinker with? If nobody makes you do it, then ...

[lastchance]

Give or take the row-column notation, @Keskiverto's much more succinct explanation exactly describes that in my code, although I still think of it as "moving front".

I also keep a running sum of the route in a parallel string array (so I use explicit if...else... rather than max(), as there are two arrays to update; also, boundaries are just part of the if ... else if ... options). In a bells-and-whistles version it adds to the string sum the alternative previous routes (as in my previous post).

I didn't have to use recursion anywhere.

[helios]

lastchance: Did you use Dijkstra's? Your solution sounds more complicated than Duoas' suggestion.

[lastchance]

Your solution sounds more complicated

Well, maybe ...
Anyway, it's not many lines of code. I've got a bells-and-whistles version that does all the maximal routes and draws pictures, but that is a bit longer.

My moving front is diagonal since that seemed more natural here (to me, anyway) as every step takes you onto the next diagonal.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
   const int IMAX = 7, JMAX = 8;
   const int STEPS = IMAX + JMAX - 2;                      // Number of steps from bottom left to top right

   int A[IMAX][JMAX] = { { 5, 1, 0, 4, 1, 1, 2, 0 },       // Indexing orientation:
                         { 0, 3, 2, 1, 0, 3, 0, 1 },       //      +--------> j         0,0 -------- 0,JMAX-1
                         { 4, 3, 0, 6, 5, 0, 1, 0 },       //      |                     |
                         { 3, 1, 0, 3, 4, 0, 1, 3 },       //      |                     |
                         { 0, 5, 2, 0, 1, 1, 5, 1 },       //      |                     |
                         { 2, 1, 6, 1, 6, 0, 2, 1 },       //     \|/                    |
                         { 0, 0, 4, 3, 2, 3, 0, 2 } };     //      i                 IMAX-1,0

   int best[IMAX][JMAX] = { 0 };
   string route[IMAX][JMAX];


   best[IMAX-1][0] = A[IMAX-1][0];                         // Start at bottom-left corner

   for ( int diag = 1; diag <= STEPS; diag++ )             // Each step takes you onto a new diagonal line (my MOVING FRONT)
   {
      for ( int j = max( 0, diag + 1 - IMAX ); j <= min( JMAX - 1, diag ); j++ )      // Values on diagonal
      {
         int i = IMAX - 1 - diag + j;

         if ( j == 0 )                                     // On left, must come from below; i.e. move is UP
         {
            best [i][j] = best [i+1][j] + A[i][j] ;
            route[i][j] = route[i+1][j] + "U"     ;
         }
         else if ( i == IMAX - 1 )                         // On bottom, must come from left; i.e. move is RIGHT
         {
            best [i][j] = best [i][j-1] + A[i][j];
            route[i][j] = route[i][j-1] + "R"    ;
         }
         else if ( best[i][j-1] > best[i+1][j] )           // Maximal if comes from left; i.e. move is RIGHT
         {
            best [i][j] = best [i][j-1] + A[i][j];
            route[i][j] = route[i][j-1] + "R"    ;
         }
         else                                              // Maximal if comes from below; i.e. move is UP
         {
            best [i][j] = best [i+1][j] + A[i][j] ;
            route[i][j] = route[i+1][j] + "U"     ;
         }
      }
   }

   cout << "Most gold is " << best [0][JMAX-1] << '\n';    // Finish at top-right corner
   cout << "Route is "     << route[0][JMAX-1] << '\n';
}

Most gold is 33
Route is RRURRUUURUURR

[helios]

Yeah, that's Dijkstra's with a modification to obviate the queue, which is possible because the "robot" can only be in one of a few possible cells at each step in the simulation.
It's clever, but IMO overkill for this problem. A backtracking solution is more space-efficient and possibly even more time-efficient.

[lastchance]

and possibly even more time-efficient

Well, I did try clocking it - but couldn't get anything above 0 ms with std::clock()! It's only a single update for 55 points after all.

However, I do, embarassingly, have to admit to first trying the brute-force search through all ¹³C₇ possible routes which took ... er ... rather a long time.

You'd have to direct me to good learning resources for backtracking - I never did a programming or computer-science course in my life.

[helios]

13 pick 7 is only 1716. And the number of possible routes is 8192. So I have no idea what you did.

[lastchance]

The route has to take 6 'ups' and 7 'rights' so I reckon it is defined by the number of ways you can choose 7 (or 6) things from 13; i.e. ¹³C₇. Actually, I've now realised that my earlier brute force method was worse than that, since I started out by repeatedly using next_permutation on {1,1,1,1,1,1,1,0,0,0,0,0,0} - there's a mere 13! of those - and most are just repeats. No wonder it took some time! Truly embarassing!

Anyway, my ad hoc solution as posted did a satisfactory job, so I'll stick with it and see what others come up. I'd be interested in the recursive ones.

[keskiverto]

One should obviously test with input matrix, where each cell has same value and therefore all possible paths are maximal paths.

[lastchance]

One should obviously test with input matrix, where each cell has same value and therefore all possible paths are maximal paths.

A matrix of 1's gives

Most gold is 14
Route is RRRRRRRUUUUUU

Starts at 1, then 13 steps each picking up another 1. Seems OK.

My code favours R over U (equality == covered by the else on line 46) until it gets to the right boundary.

[HArray]

You need recursive MinMax algorithm with Alpha/Beta optimization.
The same what applied in Chess/Checkers games.

[helios]

Ah, you're right. Going 13 times up would be invalid.

#include <iostream>
#include <vector>
#include <string>

int map[] = {
    5, 1, 0, 4, 1, 1, 2, 0,
    0, 3, 2, 1, 0, 3, 0, 1,
    4, 3, 0, 6, 5, 0, 1, 0,
    3, 1, 0, 3, 4, 0, 1, 3,
    0, 5, 2, 0, 1, 1, 5, 1,
    2, 1, 6, 1, 6, 0, 2, 1,
    0, 0, 4, 3, 2, 3, 0, 2
};

const int w = 8;
const int h = 7;

int get_best(int x, int y){
    int current = map[x + y * w];
    int ret = -1;
    if (x)
        ret = get_best(x - 1, y);
    if (y != h - 1)
        ret = std::max(ret, get_best(x, y + 1));
    if (ret < 0)
        return current;
    return ret + current;
}

void extend(std::vector<std::string> &routes, char c){
    if (!routes.size())
        routes.resize(1);
    for (size_t i = 0; i < routes.size(); i++)
        routes[i] += c;
}

int get_best_routes(int x, int y, std::vector<std::string> &routes){
    int current = map[x + y * w];
    int ret = -1;
    routes.clear();
    if (x){
        ret = get_best_routes(x - 1, y, routes);
        extend(routes, 'R');
    }
    if (y != h - 1){
        std::vector<std::string> routes2;
        int candidate = get_best_routes(x, y + 1, routes2);
        extend(routes2, 'U');
        if (candidate > ret){
            ret = candidate;
            routes = routes2;
        }else if (candidate == ret){
            for (size_t i = 0; i < routes2.size(); i++)
                routes.push_back(routes2[i]);
        }
    }
    if (ret < 0)
        return current;
    return ret + current;
}

std::vector<std::string> get_best_routes(int x, int y){
    std::vector<std::string> ret;
    get_best_routes(x, y, ret);
    return ret;
}

void print(const std::vector<std::string> &routes){
    for (size_t i = 0; i < routes.size(); i++)
        std::cout << routes[i] << std::endl;
}

int main(){
    std::cout << get_best(w - 1, 0) << std::endl;
    print(get_best_routes(w - 1, 0));
}