Skip to content

Instantly share code, notes, and snippets.

@DavidDexterCharles

DavidDexterCharles/treasure.c

Created December 9, 2016 02:50
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save DavidDexterCharles/5d1a2da6b55208163571b56aa590f93d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save DavidDexterCharles/5d1a2da6b55208163571b56aa590f93d to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. David Charles created this gist Dec 9, 2016.
    194 changes: 194 additions & 0 deletions treasure.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,194 @@
    /* 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);
    }
    }