Can you solve this problem using C++?

Pages: 12
Oct 25, 2017 at 10:40pm
Alright, I’ll bite.

Gets max gold only
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <ciso646>
#include <iostream>

constexpr int G_ROWS = 7;
constexpr int G_COLS = 8;
int G[7][8] = 
{
  { 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 }
};

int max_path( int row, int col )
{
  int up = G[ row ][ col ];
  int rt = G[ row ][ col ];
  
  if ((row == 0) and (col == G_COLS-1)) return G[ row ][ col ];
  
  if (row >        0) up += max_path( row-1, col );
  if (col < G_COLS-1) rt += max_path( row, col+1 );
  
  return up > rt ? up : rt;
}

int main()
{
  std::cout << "max gold = " << max_path( G_ROWS-1, 0 ) << "\n";
}


Get max gold and path taken
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <ciso646>
#include <iostream>
#include <string>

constexpr int G_ROWS = 7;
constexpr int G_COLS = 8;
int G[7][8] = 
{
  { 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 }
};

struct max_path_result
{
  int         gold;
  std::string path;
  max_path_result& operator += ( const max_path_result& that )
  {
    gold += that.gold;
    path += that.path;
    return *this;
  }
};

max_path_result
max_path( int row, int col )
{
  max_path_result up{ G[ row ][ col ], "U" };
  max_path_result rt{ G[ row ][ col ], "R" };
  
  if ((row == 0) and (col == G_COLS-1)) return { G[ row ][ col ], "" };
  
  if (row >        0) up += max_path( row-1, col );
  if (col < G_COLS-1) rt += max_path( row, col+1 );

  return (up.gold > rt.gold) ? up : rt;
}

int main()
{
  auto r = max_path( G_ROWS-1, 0 );
  std::cout << "max gold = " << r.gold << "\n";
  std::cout << "max path = " << r.path << "\n";
}

Simple recursive, non-dynamic, Dijkstra not needed.
Oct 25, 2017 at 11:10pm
Is it just me or does your second version return the path in reverse?
Oct 25, 2017 at 11:33pm
Look again. ;-)
Oct 26, 2017 at 1:09am
Ah, I see. It confused me that you both pass the coordinates in y-x order and start the recursion from the start point rather than the end point.
Both calls look identical if you ignore the variable names:
auto r = max_path( G_ROWS-1, 0 );

std::cout << get_best(w - 1, 0) << std::endl;
Last edited on Oct 26, 2017 at 1:09am
Oct 26, 2017 at 7:56am
@Helios and @Duthomas: thank-you for sharing those recursive codes.

Here's the best space-saving direct version I could come up with. The diagonal front and dependence of steps allows you to overwrite the original matrix. It saves having another array (or an equivalent amount of function pointers in memory for the recursive case). It doesn't store the route though.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
   const int IMAX = 7, JMAX = 8;
   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

   for ( int d = 1; d <= IMAX + JMAX - 2; d++ )            // d is diagonal (= number of steps here)
   {
      for ( int j = max(0,d+1-IMAX), i = IMAX-1-d+j; j <= min(JMAX-1,d); i++, j++ )
      {
         if      ( j == 0        ) A[i][j] += A[i+1][j];
         else if ( i == IMAX - 1 ) A[i][j] += A[i][j-1];
         else                      A[i][j] += max( A[i][j-1], A[i+1][j] );
      }
   }
   cout << "Most gold is " << A[0][JMAX-1] << '\n';
}


Most gold is 33
Oct 26, 2017 at 8:55am
Ooh! Fun!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <algorithm>

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
};

int main(){
#define f(z) ((y = x), (x += (i & (1 << j)) ? 1 : -z), y)
#define FOR for (int j = 0; j < m; j++)
	int w = 8, h = 7, m = w + h - 2, max = 0;
	for (int i = 0; i < (1 << m); i++){
		int x = 0, y;
		FOR f(1);
		if (x != w - h)
			continue;
		int accum = 0;
		x = (h - 1) * w;
		FOR accum += map[f(w)];
		max = std::max(accum, max);
	}
	std::cout << max << std::endl;
}
Topic archived. No new replies allowed.
Pages: 12