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

I'm a student and this is one of my assignments. My professor basically confirmed that my code is correct but all he grades on is if I finished the assignment correctly but not the coding style. I think I did poorly in terms of code style and implementation. I'm very frustrated and would like some guidance on how to improve and think about problems in a better way.

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cmath>

using std::cout;
using std::cin;
using std::ifstream;
using std::endl;

const int MAX_ROW = 100;
const int MAX_COL = 100;

//Function Prototypes
void mapData(int Map[100][100], int rowCount, int colCount);
int findMax(int Map[100][100], int rowCount, int colCount);
int findMin(int Map[100][100], int rowCount, int colCount);
void drawMap(int Map[100][100], int rowCount, int colCount);
int drawLowestElevPath(int Map[100][100], int rowCount, int colCount, int startingRow);

int main() {
int Map[100][100];
int startingRow, max, min, elevChange;

mapData(Map, MAX_ROW, MAX_COL);
max = findMax(Map, MAX_ROW, MAX_COL);
min = findMin(Map, MAX_ROW, MAX_COL);
drawMap(Map, MAX_ROW, MAX_COL);

// Taking the starting row input from the user
cout << "What is the starting row? 0-99" << " ";
cin >> startingRow;

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

elevChange = drawLowestElevPath(Map, MAX_ROW, MAX_COL, startingRow);

return 0;

}

// Inputs a list of integers from a text file into a 2D array in row major
void mapData(int Map[100][100], int rowCount, int colCount)
{
ifstream myIn;
myIn.open("mapdata.txt"); //opening the text file

for (int i = 0; i < rowCount; i++)
{
for (int j = 0; j < colCount; j++)
{
myIn >> Map[i][j]; //reading each integer into an index in the array
}
}
}

// Determines the largest integer in the array
int findMax(int Map[100][100], int rowCount, int colCount)
{
int max = Map[0][0];
for (int i = 0; i < rowCount; i++)
{
for (int j = 0; j < colCount; j++)
{
if (Map[i][j] > max)
{
max = Map[i][j];
}
}
}

return max;
}

// Determines the smallest integer in the array
int findMin(int Map[100][100], int rowCount, int colCount)
{
int min = Map[0][0];
for (int i = 0; i < rowCount; i++)
{
for (int j = 0; j < colCount; j++)
{
if (Map[i][j] < min)
{
min = Map[i][j];
}
}
}

return min;
}

// Prints each integer in the array creating a map
void drawMap(int Map[100][100], int rowCount, int colCount)
{
for (int i = 0; i < rowCount; i++)
{
for (int j = 0; j < colCount; j++)
{
cout << Map[i][j] << " ";
}
cout << endl;
}
}

int drawLowestElevPath(int Map[100][100], int rowCount, int colCount, int startingRow)
{
int elevChange1, elevChange2, elevChange3, currentRow, currentCol, totalElevChange = 0;

currentRow = startingRow;
currentCol = 0;

for (int i = 0; i < colCount; i++)
{
if (currentRow == 0)
{
elevChange2 = abs(Map[currentRow][currentCol] - Map[currentRow][currentCol + 1]);
elevChange3 = abs(Map[currentRow][currentCol] - Map[currentRow + 1][currentCol + 1]);
Map[currentRow][currentCol] = 1;

if (elevChange2 == elevChange3)
{
currentCol++;
totalElevChange += elevChange2;
} else if (elevChange2 < elevChange3)
{
currentCol++;
totalElevChange += elevChange2;
} else {
currentRow++;
currentCol++;
totalElevChange += elevChange3;
}
} else if ( currentRow == 99)
{
elevChange1 = abs(Map[currentRow][currentCol] - Map[currentRow - 1][currentCol + 1]);
elevChange2 = abs(Map[currentRow][currentCol] - Map[currentRow][currentCol + 1]);
Map[currentRow][currentCol] = 1;

if (elevChange1 == elevChange2)
{
currentCol++;
totalElevChange += elevChange2;
} else if (elevChange1 < elevChange2)
{
currentCol++;
currentRow--;
totalElevChange += elevChange1;
} else {
currentCol++;
totalElevChange += elevChange2;
}
} else {
elevChange1 = abs(Map[currentRow][currentCol] - Map[currentRow - 1][currentCol + 1]);
elevChange2 = abs(Map[currentRow][currentCol] - Map[currentRow][currentCol + 1]);
elevChange3 = abs(Map[currentRow][currentCol] - Map[currentRow + 1][currentCol + 1]);
Map[currentRow][currentCol] = 1;

if (elevChange1 == elevChange2 && elevChange2 == elevChange3)
{
currentCol++;
totalElevChange += elevChange2;
} else if (elevChange2 == elevChange1 && elevChange2 < elevChange3)
{
currentCol++;
totalElevChange += elevChange2;
} else if (elevChange2 == elevChange3 && elevChange2 < elevChange1)
{
currentCol++;
totalElevChange += elevChange2;
} else if (elevChange1 == elevChange3 && elevChange1 < elevChange2)
{
int randNum = rand() % 2;
if (randNum == 0)
{
currentRow--;
currentCol++;
totalElevChange += elevChange1;
} else
{
currentRow++;
currentCol++;
totalElevChange += elevChange3;
}
} else if (elevChange1 < elevChange2 && elevChange1 < elevChange3)
{
currentRow--;
currentCol++;
totalElevChange += elevChange1;
} else if (elevChange2 < elevChange1 && elevChange2 < elevChange3)
{
currentCol++;
totalElevChange += elevChange2;
} else if (elevChange3 < elevChange1 && elevChange3 < elevChange2)
{
currentRow++;
currentCol++;
totalElevChange += elevChange3;
}
}

}

for (int i = 0; i < rowCount; i++)
{
for (int j = 0; j < colCount; j++)
{
if (Map[i][j] != 1)
{
Map[i][j] = 0;
}
cout << Map[i][j] << " ";
}
cout << endl;
}

}


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.

• Thank you very much for all your detailed answers. Yes, the algorithm has to start at column 0 and make its way across the 2D array to the end. As far as declaring all my variables at the beginning of the function, the professor specifically wanted us to declare them there and said we would lose points otherwise. I also agree with the drawLowestElevPath function shouldn't be calculating path and printing the path but I can't figure out how to have my program remember what the path that was chosen was outside the function. Also, what do you mean the output loop in drawLowestElevPath is wrong? – Bishoy Boktor Sep 25 '16 at 22:54
• @BishoyBoktor I cannot see any good reason to declare local variables at the top of functions, especially in C++ it can even easily be semantically wrong. But of course you shouldn't jeopardize your grades for this, just keep it in mind for later. For point 24 consider an input matrix having 1 everywhere in the first column. Your drawLowestElevPath will then also print 1 in all rows of the first column, although only the first row element of the first column belongs to the path. – user4407569 Sep 25 '16 at 23:00
• How exactly would you have done it then? I can't think of a way to pull that off with my implementation. – Bishoy Boktor Sep 26 '16 at 15:49
• @BishoyBoktor In drawLowestElevPath you declare a new std::array<std::array<bool, MAX_ROW>,MAX_COL> Path{}; (note that {} initializes it to zero everywhere) and then you put the ones representing the path in there and leave Map unmodified. Afterwards you return Path by value. In fact because there can only be one element per column in the path, you can also use an std::array<int, MAX_COL> which just saves the row chosen for each column. If you keep using built-in arrays for some reason, then provide an additional int Path[MAX_ROW][MAX_COL] as output parameter instead. – user4407569 Sep 26 '16 at 15:58
• I'm sorry if this is very noobie but I'm not sure what a built-in arrays are or how they're different from std::array. – Bishoy Boktor Sep 26 '16 at 16:01

I think there is indeed room for improvement.

1. If you define global variables make them #define or constexpr

2. You should use stl std::vector container here, or better std::vector<std::vector<int> >. This would allow you to use range based loops, which are more descriptive.

typedef std::vector<std::vector<int>> array2D;
void mapData(array2D &array) {
ifstream myIn("mapdata.txt");
if (!myIn) {
throw std::runtime_error("Cannot open file");
}
for (auto &rows : array) {
for (auto &elem : rows) {
myIn >> elem;
}
}
myIn.close();
}

int findMax(const array2D &array) {
int max = array[0][0];
for (auto &rows : array) {
for (auto &elem : rows) {
if (elem > max) {
max = elem;
}
}
}
return max;
}

int findMin(const array2D &array) {
int min = array[0][0];
for (auto &rows : array) {
for (auto &elem : rows) {
if (elem < min) {
min = elem;
}
}
}
return min;
}

void drawMap(const array2D &array) {
for (auto &rows : array) {
for (auto &elem : rows) {
std::cout << elem << " ";
}
std::cout << "\n";
}
}

3. I would strongly recommend to refactor your monster function into smaller subfunctions.

• Thank you for the comment. I was mostly wondering about my drawLowestElevPath() function implementation. Something about it leaves a sour taste in my mouth. I know there has to be a better way to do things than a giant mass of if-else statements but I don't know what. – Bishoy Boktor Sep 25 '16 at 19:15
• Often using std::vector<cell_type> for 2D array is better (with index mapping function z = y*columns + x;), at least from performance point of view (having whole array as single continuous block of memory, improving locality), and with proper getter/setter functions wrapping that index mapping, it's still readable enough at source level. – Ped7g Sep 26 '16 at 13:42

This is a minimum optimisation problem. Generally there is a lot to be gained from restructuring data to minimise comparisons in tight loops.

In the source posted I buffered data on on the top and bottom with maximum signed integer (32bit) values, note that this will not work if the maximum integer value appears in data set (I think it is unlikely for elevation though), this removes the need for bound checking on the map array which may lead to tricky nested if statements. I also used only one dimensional arrays which tends to be more cache-able.

It is always good to find optimal ways of writing algorithms but don't sweat the small stuff; optimisation comes at a cost of time and sometimes ease of maintainability.

To write the best kind of code it is important to understand the machine it runs on :)

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cmath>
#include <string.h>

using std::cout;
using std::cin;
using std::ifstream;
using std::endl;

/*[CONSTANTS]----------------------------------------------------------------------------*/

#define MAP_ROW       100
#define MAP_COL       100
#define MAP_OFFSET    100
#define MAP_ROW_X_COL 10000

#define MAX_INT       0x7FFFFFFF // assuming int is 32 bits :)
#define HALF_RAND_MAX 16384      // max number produced by rand() -> RAND_MAX = 32767

/*[MACROS]-------------------------------------------------------------------------------*/

#define ROW_COL_TO_IDX(ROW,COL) MAP_OFFSET + (ROW*MAP_ROW + COL)
#define SWOP(A,B) A=A+B;B=A-B;A=A-B
#define TEST_SWOP(ARR,IDX,I1,I2) if(ARR[I1]>ARR[I2]){SWOP(ARR[I1],ARR[I2]);SWOP(IDX[I1],IDX[I2]);}

/*[ENUMS]---------------------------------------------------------------------------------*/

enum dir_idx
{
NE, // North East
E,  // East
SE, // South East
NUM_DIRS
};

enum map_legend
{
LOW,
MED,
HIGH,
NUM_LEGEND = 3
};

/*[CONSTANT VARIABLES]---------------------------------------------------------------------*/

static char map_legend_char[NUM_LEGEND] = {'l','m','h'};
static int dir_offset[NUM_DIRS] = {-99,1,101};

/*[VARIABLES]------------------------------------------------------------------------------*/

static char print_map[MAP_ROW_X_COL] = {0};

static int  sol_path[MAP_COL];
static int  sol_elev_change;
static int  map_elev_range;

static int min_elev;
static int max_elev;

/*[STATIC FUNCTIONS]------------------------------------------------------------------------*/

static inline int GetNextMinIdx(int curr_idx)
{
int elevs[NUM_DIRS] = {map[curr_idx-99],map[curr_idx+1],map[curr_idx+101]};
int eidx[NUM_DIRS]  = {NE,E,SE};

// bubble sort
TEST_SWOP(elevs,eidx,NE,E);
TEST_SWOP(elevs,eidx,E ,SE);
TEST_SWOP(elevs,eidx,NE,E);

// choose random dir if NE and SE is Equal and smaller than E
if ((eidx[0]+eidx[1] == 2) && (elevs[0] == elevs[1]))
{
if (rand() < 16384)   // propability of 50 %
SWOP(eidx[0],eidx[1]);
}

return curr_idx + dir_offset[eidx[0]];
}

/*--------------------------------------------------------------------------------------------*/

static int FindBestPath(int start)
{
int c_col     = 0;
int c_idx     = ROW_COL_TO_IDX(start,0);
int elev_diff = map[c_idx];

sol_path[c_col]             = c_idx;
print_map[c_idx-MAP_OFFSET] = '*';

while(++c_col < MAP_COL)
{
c_idx                       = GetNextMinIdx(c_idx);
sol_path[c_col]             = c_idx;
print_map[c_idx-MAP_OFFSET] = '*';
}

elev_diff = elev_diff - map[c_idx];

return elev_diff;
}

/*--------------------------------------------------------------------------------------------*/

static void Printmap()
{
int  pm_offset;
char ch_p;
int  l_sel;

for (pm_offset = 0 ;pm_offset < MAP_ROW_X_COL; pm_offset++)
{
if (pm_offset % 100 == 0) cout << '\n';
l_sel = (int)(((float)map[pm_offset+MAP_OFFSET]/(float)map_elev_range)*(float)NUM_LEGEND);
ch_p  = map_legend_char[l_sel];
ch_p  = (print_map[pm_offset]) == 0 ? ch_p - 32 : ch_p;
cout << ch_p;
}
}

/*[MAIN]---------------------------------------------------------------------------------*/

int main()
{
int      m_offset;
ifstream my_in;
bool     input_valid = false;
int      start_row;

my_in.open("mapdata.csv");

for (m_offset = 0; m_offset < MAP_OFFSET; m_offset++)
{
map[m_offset] = MAX_INT;
map[MAP_ROW_X_COL+MAP_OFFSET+ m_offset] = MAX_INT;
}

my_in >> min_elev;
max_elev        = min_elev;
map[m_offset++] = min_elev;

for (;m_offset < MAP_ROW_X_COL+MAP_OFFSET; m_offset++)
{
my_in >> map[m_offset];
min_elev = (min_elev > map[m_offset]) ? map[m_offset] : min_elev;
max_elev = (max_elev < map[m_offset]) ? map[m_offset] : max_elev;
}

map_elev_range = max_elev - min_elev;

while (!input_valid)
{
cout << "Enter Start Row(0-99):";
cin >> start_row;
input_valid = ((start_row >= 0) && (start_row <= 99));
}

sol_elev_change = FindBestPath(start_row);
Printmap();
}