Skip to content

Instantly share code, notes, and snippets.

@DavidDexterCharles

DavidDexterCharles/treasure.c

Created December 9, 2016 02:50
Show Gist options
  • Save DavidDexterCharles/5d1a2da6b55208163571b56aa590f93d to your computer and use it in GitHub Desktop.
Save DavidDexterCharles/5d1a2da6b55208163571b56aa590f93d to your computer and use it in GitHub Desktop.
Download ZIP
Raw
treasure.c
/* December 2005 Question 3 */
/* (b) In a treasure hunt, a retangular field is divided into m rows and n */
/* columns. Starting from a square in the left column, a player must move */
/* to a square in the right column, collectine 'treasure' as he moves from*/
/* square to square. At each step, a player can move diagonally to: */
/* the square to his left in the next column provided he is not */
/* already in the top row */
/* or to his right in the next column, provided he is not already in */
/* the bottom row. */
/* */
/* Each square is assign a treasure point value, p, 0<=p<=50. When a player */
/* move to a square, he must add its point value to his score. */
/* You are required to determine the maximum score a player can get as he */
/* move from any square in the left column to a square in the right column. */
/* */
/* Assume that the rows of the field are numbered 1 to m, going from the */
/* top to bottom and the column are numbered 1 to n, from left to right.T[i,j]*/
/* contains the treasure point value of the square in the ith row and the jth */
/* column. */
/* */
/* (i) Write code which uses a recursive algorithm to solve this prolem. Print*/
/* the maximum score obtainable and the starting row to obtain this */
/* maximum. What is the order of your algorithm? */
/* */
/* (ii) Write code which uses an efficient algorithm to solve this problem. */
/* What is the order of your algorithm. */
/* */
/* (iii) What does it means to memoize an algorithm? Rewrite the recursive */
/* routine from (i) using memoization so that the algorithm runs more */
/* quickly. */
/* */
/* (d) Given the completed table of memoized values such that M[i, j] contains*/
/* the highest score obtainable starting at row i, column j) and ending in*/
/* the rightmost column. Given M amd a starting row r, in the first */
/* column, write code to print the coordinates of the square visited in */
/* obtaining the maximum score starting from [r,1]. */
/******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 100
int maxPoints(int T[][MaxSize + 1], int i, int j, int m, int n);
int maxPointsMemoize(int T[][MaxSize + 1], int i, int j, int m, int n, int M[][MaxSize + 1]);
void maxPointEfficient(int T[][MaxSize + 1], int m, int n, int best[][MaxSize + 1]);
void printPath(int r, int M[][MaxSize + 1], int m, int n);
main()
{
FILE* in = fopen("input.txt", "r");
if(in == NULL) exit(1);
int i, j, m, n;
if(fscanf(in, "%d%d", &m, &n) != 2) exit(2);
int T[MaxSize + 1][MaxSize + 1], best[MaxSize + 1][MaxSize + 1];
int M[MaxSize + 1][MaxSize + 1];
/* Store data in array T */
for(i = 1; i <= m; i++)
{
for(j = 1; j <= n; j++)
{
if(fscanf(in, "%d", &T[i][j]) != 1) exit(2);
}
}
fclose(in);
/*Initilize array best and M */
for(i = 1; i <= m; i++)
{
for(j = 1; j < n; j++)
{
M[i][j] = -1;
}
}
for(i = 1; i <= m; i++) best[i][n] = M[i][n] = T[i][n];
/*brute force method */
int startSquare = 1;
int thisScore, max = -1;
for(i = 1; i <= m; i++)
{
thisScore = maxPoints(T, i, 1, m, n);
if(thisScore > max)
{
max = thisScore;
startSquare = i;
}
}
printf("The maximum point which can be obtained are: %d\n\n", max);
printf("The position of the start square is: (%d, 1)\n\n", startSquare);
printf("\n\n===========================================================\n\n");
/*efficient method */
maxPointEfficient(T, m, n, best);
max = best[1][1];
startSquare = 1;
for(i = 2; i <= m; i++)
{
if(best[i][1] > max)
{
max = best[i][1];
startSquare = i;
}
}
printf("The maximum point which can be obtained are: %d\n\n", max);
printf("The position of the start square is: (%d, 1)\n\n", startSquare);
printf("\n\n===========================================================\n\n");
/*memoize method */
startSquare = 1;
max = -1;
for(i = 1; i <= m; i++)
{
thisScore = maxPointsMemoize(T, i, 1, m, n, M);
if(thisScore > max)
{
max = thisScore;
startSquare = i;
}
}
printf("The maximum point which can be obtained are: %d\n\n", max);
printf("The position of the start square is: (%d, 1)\n\n", startSquare);
printf("\n\n===========================================================\n\n");
printPath(3, M, m, n);
printf("\n\n===========================================================\n\n");
system("pause");
}
int maxPoints(int T[][MaxSize + 1], int i, int j, int m, int n)
{
if(i < 1 || j < 1 || i > m || j > n) return 0;
if(j == n) return T[i][j];
if(i == 1) return T[i][j] + maxPoints(T, i+1, j+1, m, n);
if(i == m) return T[i][j] + maxPoints(T, i-1, j+1, m, n);
int left = maxPoints(T, i-1, j+1, m, n);
int right = maxPoints(T, i+1, j+1, m, n);
if(left > right) return T[i][j] + left;
return T[i][j] + right;
}
void maxPointEfficient(int T[][MaxSize + 1], int m, int n, int best[][MaxSize + 1])
{
int i, j;
for(j = n - 1; j > 0; j--)
{
best[1][j] = T[1][j] + best[2][j+1];
best[m][j] = T[m][j] + best[m-1][j+1];
for(i = 2; i < m; i++)
{
if(best[i-1][j+1] > best[i+1][j+1]) best[i][j] = T[i][j] + best[i-1][j+1];
else best[i][j] = T[i][j] + best[i+1][j+1];
}
}
}
int maxPointsMemoize(int T[][MaxSize + 1], int i, int j, int m, int n, int M[][MaxSize + 1])
{
if(i < 1 || j < 1 || i > m || j > n) return 0;
if(M[i][j] != -1) return M[i][j];
if(i == 1) return M[i][j] = T[i][j] + maxPointsMemoize(T, i+1, j+1, m, n, M);
if(i == m) return M[i][j] = T[i][j] + maxPointsMemoize(T, i-1, j+1, m, n, M);
int left = maxPointsMemoize(T, i-1, j+1, m, n, M);
int right = maxPointsMemoize(T, i+1, j+1, m, n, M);
if(left > right) return M[i][j] = T[i][j] + left;
return M[i][j] = T[i][j] + right;
}
void printPath(int r, int M[][MaxSize + 1], int m, int n)
{
if(r < 1 || r > m) return;
int j = 1;
printf("The path taken to obtain maximum sum is: (%d, 1)", r);
while(j < n)
{
j++;
if(r == 1) r = 2;
else if(r == m) r = m - 1;
else if(M[r-1][j] > M[r+1][j]) r -= 1;
else r += 1;
printf(" -> (%d, %d)", r, j);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment