1
\$\begingroup\$

So in this problem I am given an NxN matrix, in which each value of the matrix represents an altitude. I need to find the best path from the top-left corner to the bottom-right one, my moves being limited to down and right. Also, the path needs to be chosen in such way that the differences in altitude are the smallest, basically finding the path that has the smallest sum of differences in altitude. I think I am using dynamic programming in my solution.(I am still a beginner, I am not so sure of this)

First I begin by creating another matrix that has the sums of the differences in altitude of the edges of the matrix, being the easiest to calculate because there is a single way that those sums can be computed. (S is the new matrix, while A is the matrix that is given)

 S[0][0]=0;
 for(int i=1;i<=n-1;i++)
        {S[0][i]=S[0][i-1]+abs(A[0][i]-A[0][i-1]);
        S[i][0]=S[i-1][0]+abs(A[i][0]-A[i-1][0]);}

Secondly, I am traversing the matrix by comparing the sums of the already calculated paths(the edges at first)+ the two ways (up or down). Whichever one is smallest, will be put in the new matrix.

for(int i=1;i<=n-1;i++)
    for(int j=1;j<=n-1;j++)
        if(S[i-1][j]+abs(A[i][j]-A[i-1][j])<S[i][j-1]+abs(A[i][j]-A[i][j-1]))
                S[i][j]=S[i-1][j]+abs(A[i][j]-A[i-1][j]);
        else
                S[i][j]= S[i][j-1]+abs(A[i][j]-A[i][j-1]);

This problem worked for the examples that I tried, but I am wondering if there is a more efficient way. Also, i could have made a mistake (or many :) ), so please feel free to tell me if you think it is a good solution, a bad one and if you have any advice for me.

Thank you for the attention anyways!

The complete code:

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("data.in");
ofstream fout("data.out");

int A[21][21],n,S[21][21],D[42][4];

int main()
{   //reading the matrix
    fin>>n;
    for(int i=0;i<=n-1;i++)
        for(int j=0;j<=n-1;j++)
            fin>>A[i][j];
    //computing the edges of the new matrix
    S[0][0]=0;
    for(int i=1;i<=n-1;i++)
        {S[0][i]=S[0][i-1]+abs(A[0][i]-A[0][i-1]);
        S[i][0]=S[i-1][0]+abs(A[i][0]-A[i-1][0]);}
    //comparing the sums
    for(int i=1;i<=n-1;i++)
        for(int j=1;j<=n-1;j++)
            if(S[i-1][j]+abs(A[i][j]-A[i-1][j])<S[i][j-1]+abs(A[i][j]-A[i][j-1]))
                S[i][j]=S[i-1][j]+abs(A[i][j]-A[i-1][j]);
            else
                S[i][j]= S[i][j-1]+abs(A[i][j]-A[i][j-1]);

//a new matrix to identify the path and memorize the down/right moves
    int i,j,x;
    i=n-1;
    j=n-1;
    x=1;
    D[0][0]=A[n-1][n-1];
    while(i!=0&&j!=0)
    {if(S[i-1][j]<S[i][j-1])
        {
        D[x][0]=A[i-1][j];
        D[x][1]=1;   //1 for down
        x++;
        i=i-1;}
    else
    {
        D[x][0]=A[i][j-1];
        D[x][1]=2;    //2 for right
        x++;
        j=j-1;
    }}
    if(S[1][0]>S[0][1])
        D[x][1]=2;
    else
        D[x][1]=1;
    D[x][0]=A[0][0];

 //showing the path
fout<<"The path:"<<endl;
    for(i=x;i>=0;i--)
        { fout<<endl<<D[i][0];
        if(i!=0)
           {if(D[i][1]==1)
                fout<<endl<<"down";
            else
                if(D[i][1]==2)
                fout<<endl<<"right";}
        }

    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review. Are you aware the code in your question is absolutely terrible with regards to readability? Do you have tests written for this verifying it works? \$\endgroup\$ – Mast Apr 27 at 11:16
  • \$\begingroup\$ @Mast Hello! Yes, I have tried a few matrices and so far they worked fine. I am sorry for the readability, as I said I am new to this and I try to improve. I wish I knew how I could make it better. Do you have any advice for me? \$\endgroup\$ – Andrei Saulea Apr 27 at 13:17
1
\$\begingroup\$

Don't take this the wrong way, but my first thought when I looked at your code was "ugh do I really want to read this?" You have (probably) been thinking a lot about A, S, n, and D over the last few hours, but if you look at this again in 2 years, it will look like nonsense. So your number one goal should be to fix readability. Then you can start thinking about correctness and performance.

I would recommend reading through a C++ style guide for general tips. Here is one, but there are many others. I'll still list a few of the biggest mistakes:

  • You should avoid single letter variable names
  • Try to express your logic in functions
  • Don't use global variables
  • Indent consistently (or better yet, automatically with help from your IDE)

All of these have been written about extensively in style guides, programming manuals, other code reviews, etc...


fin>>n;

What if n > 21? If you have some reason to believe it cannot be, then you should assert(n < 22). But in this case, it's easy enough to support any n with std::vector.


i<=n-1

The canonical way to write this is i < n.


`S[i-1][j]+abs(A[i][j]-A[i-1][j])`

I think this section is correct, but I have more style comments!

  1. This is complicated looking for no reason. You're making yourself think harder than you have to which means you will accomplish less stuff with your mental bandwidth. How about something like costOfStep(i-1, j)?

  2. This gets exactly repeated twice and a very similar statement is also repeated twice. That's a telltale sign you should at least use a variable or better yet write a function to compute this.

Isn't the snipped below easier to read?

for(int i = 1; i < n; i++) {
    for(int j = 1; j < n; j++) {
        int costOfStepDown = costOfStep(i - 1, j);
        int costOfStepRight = costOfStep(i, j - 1);
        minCosts[i - 1][j] = std::min(costOfStepDown, costOfStepRight);
    }
}

//a new matrix to identify the path and memorize the down/right moves
int i,j,x;
i=n-1;
j=n-1;
x=1;

From this point on, I think you are using more time/memory than necessary. I believe you can refactor your code so that you only store one matrix for both the input array and one for the cumulative array (or two matrices if it's clearer, but not more). And you can store your path as a 1D vector. Doing two passes leads to unnecessary code which leads to pointless bugs and wasted time. Keep it minimal! You were following a decently minimal algorithm until this part...

Also, here are my thoughts while reading this snippet:

  1. Nice a comment... Where is the new matrix?

  2. Oh some single named variables. No idea what these do. Hopefully I can figure it out.

  3. Huh they are not initialized. I hope the author was careful not to use uninitialized values.

That's a lot of thinking for not very much action. How about this:

Matrix path;
path[0][0] = inputMatrix[size - 1][size - 1];
for (int i = 0, j = 0; i < size && j < size; /*increment in body*/) {
    ...

This is more of a general tip than a specific comment. I hope you find it useful.

Many dynamic programming problems are easy to solve with recursion. Here's some pseudo-code for this problem:

// return the min cost of traveling from pos to the bottom-right of inputMatrix
int minCost(Matrix const& input, Position const pos = top-left) {
    if (pos == bottom-right) {
        return 0;
    }
    return std::min(minCost(input, pos.right), minCost(input, pos.down));
}

Position could be std::pair<int, int> and Matrix could be std::vector<std::vector<int>>.

This function will calculate the correct answer, but it is slow because it repeatedly calculates the min cost of the same position many times. Fix that:

int minCostHelper(Matrix const& input, Position const pos, Cache cache) {
    if (cache.hasSeen(pos)) {
        return cache.valueOf(pos);
    }
    if (pos == bottom-right) {
        return 0;
    }
    auto result = std::min(minCost(input, pos.right), minCost(input, pos.down));
    cache.insert(pos, result);
    return result;
}

int minCost(Matrix const& input) {
    Cache cache;
    return minCostHelper(input, top-left, cache);
}

Cache could be an std::map.

The technical term for "fix" in this case is "memoize." I think this style is easier to read/debug than manually creating arrays. It's a question of personal preference though.

Here is a challenge: can you write a function that will memoize another function?

template <typename Function>
Function memoize(Function);
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.