Using a greedy algorithm to find the best path in a 2D array

Here is a short write-up of things I noticed while reading the code. Please excuse the missing structure, I might restructure it properly later. Please ask if the reasoning behind points is unclear.

1. Instead of build-in arrays use std::array. Then you will not need to pass rowCount and colCount. It is also much safer, because you cannot pass std::arrays with wrong sizes.

2. Use MAX_ROW and MAX_COL everywhere where they are actually meant, i.e. also in Map[100][100], so that you can change the value without having to check your code correctness afterwards.

3. If your functions are supposed to take arrays of varying sizes, than you should pass as int** Map instead of int Map[100][100]. If only arrays of dimensions MAX_ROWxMAX_COL are supposed to be allowed, then it is unnecessary to pass rowCount and colCount because they are required to be MAX_ROW and MAX_COL.

4. Don't declare all local variables at the beginning of functions. That is only (somewhat) required in old versions of C and has never been required in C++. Declare variables at the point where they are initialized or first used and in the narrowest scope that they are required. For example:

   int max = findMax(Map, MAX_ROW, MAX_COL);
   

   There is no reason to have int max; declared beforehand. It is just more code and risking usage of max before initialization.

   Another example:

   int elevChange2 = abs(Map[currentRow][currentCol] - Map[currentRow][currentCol + 1]);
   

   elevChange2 needs not be retained outside the if-block. Therefore its scope should also be limited to it, making the code more readable, reducing probability of unintended misuse (equal names, etc.) outside the intended scope and allowing for easier optimization by the compiler.

5. Move the file name mapdata.txt either to a constant global string or better read it from argv and pass it to mapData. This might be beyond your intended scope, because you don't want the file name to change, but hardcoded file names are usually problematic (need to recompile just to change some file names).

6. I think the name mapData is not really saying what the function does readMap or similar seems more appropiate.

7. ifstream has a constructor from file names. That means that you can write

   ifstream myIn("mapdata.txt");
   

   with the same effect, reducing code and making it impossible to use myIn before actually opening the file.

8. myIn is the only variable you prefix with my. That is inconsitent. Use a better name like inFile or something.

9. Using output parameters is not really good C++ style if return values could be used instead. If you used std::array as I mentioned, then you could create the array in mapData and return it after filling with the file data instead of passing an array pointer from the caller.

10. Your loop in main could be written shorter. You use an endless loop while(true) which runs until a break; statement. The break; statement happens exactly if the condition startingRow < 0 || startingRow > 99 is not satisfied. Or expressed a bit differently, the loop continues as long as startingRow < 0 || startingRow > 99. Therefore you can just write (and much more readable):

    while(startingRow < 0 || startingRow > 99)
    {
        cout << "That is not a valid row. Try again.";
        cin >> startingRow;
    }
    

11. Use while(startingRow < 0 || startingRow >= MAX_ROW) for the same reason as 2. because otherwise changing MAX_ROW will break your code unless you can find all numbers actually referring to it semantically.

12. You might want to have error handling in your input code. As is trying to input a string instead of a valid number during cin >> startingRow; will result in an uncaught exception crashing your program. If you haven't yet learned about exception you probably shouldn't bother yet, but otherwise put a try/catch block arround it and give proper error messages.

13. elevChange = drawLowestElevPath(Map, MAX_ROW, MAX_COL, startingRow);: Here you are setting elevChange, but it is not actually used afterwards anymore. That is unnecessary. In fact that is the only use of elevChange, so it is not needed at all.

14. In drawLowestElevPath you should not reuse Map to draw the path. The caller passes Map into the function and the function is modifying it. I don't think this is expected. Instead create a new int[MAX_ROW][MAX_COL] and use it to write to, leaving Map unmodified.

15. In drawLowestElevPath you are repeating code unnecessarily. For example Map[currentRow][currentCol] = 1; will be executed no matter which if/else branch is executed. Therefore you could simply put it at the end of the for-block (at least if you followed my point 14., otherwise you might have to restructure your code, i.e. first calculate all elevChanges allowed, then set =1 and then check the next step).

    Another example is currentCol++ which is repeated in every branch. Put it at the end of the for-block once instead.

16. I think you did not properly explain what path your code is supposed to find. Is the greedy walker allowed to take direct as well as diagonally adjacent tiles? It also seems to be constraint to having to move towards increasing column number. (i.e. not backwards in columns). Is that correct? Otherwise your code is not doing the correct thing.

17. In fact currentCol and i seem to be always equal because in each step currentCol and i need to be incremented. Therefore you could just use currentCol as the loop counter instead of i.

18. There is no need to differ between elevChange2 == elevChange3 and elevChange2 < elevChange3 because you are doing the same thing in both branches, you are handling the equal case as if it was smaller (supposedly that was the behavior requested in the assignment). Just use something like:

    if (elevChange2 <= elevChange3) {
        currentCol++;
        totalElevChange += elevChange2;
    } else {
        currentRow++;
        currentCol++;
        totalElevChange += elevChange3;
    }
    

    The same applies to the other such branches.

19. if ( currentRow == 99) should be if ( currentRow == rowCount-1).

20. elevChange1/elevChange2/elevChange3 should have more descriptive names, i.e. elevChangeMid/elevChangeUp/elevChangeDown.

21. Here:

    int randNum = rand() % 2;
    if (randNum == 0)
    

    This could be shortened to if(rand()%2 == 0). But might be personal preference.

22. totalElevChange is actually not needed at all. The total change in elevation is the final (after the loop) value of Map[currentRow][colCount-1] minus Map[0][0].

23. Probably not relevant for your case, but for more computationally intensive cases: If you switched rows and columns everywhere then cache access would be much more local, because in each step of the for loop you are accessing the next column only. Currently you are jumping between rows which are far away in memory.

24. The output loop in drawLowestElevPath is wrong (probably an oversight by your teacher). If the input array has a 1 somewhere it will be handled as part of the calculated path even if it wasn't chosen before. You can only fix this reliably (if inputs are allowed to be arbitary integers) by following my point 14)

25. I think it is not good that drawLowestElevPath is calculating the path as well as printing it. It seems more logical to have one function calculating the path and one drawing it, like you did for mapData and drawMap. In fact you could just reuse drawMap.

26. findMax and findMin do not actually modify Map. Therefore they should be passed as const pointers:

    int findMax(const int Map[100][100], int rowCount, int colCount);
    

27. If you want to allow variable-size input files, then std::vector should replace std::array, but then you also need to read in the correct dimensions from the input file.