5
\$\begingroup\$

I'm a newbie in programming. Could you please check my code and give any refactoring ideas, tips, etc... how it can be improved.

I wrote a code to perform the following task:

Find in randomly filled square matrix M x M max element which located in given sector, where M - is matrix size.

Here is the image of how sectors are located.

sectors

You should print the matrix, max element and it's position(if there are several of them all of which equal to max, print all their positions in given sector)

!Important: elements located on diagonals(both principal and secondary) shouldn't be taken into account!.

2 Examples of program working:

first example second example

Here goes the code:

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <cstdint>
#include <iomanip>

//    Sectors
//      \1/
//     2 X 3
//      /4\

void ShowIntro(const std::vector<std::vector<int>>& matrix);
int RestrictInput(int lowerBound, int upperBound);

std::vector<std::vector<int>> CreateMatrix(int rows, int columns);
void FillMatrixWithRandom(std::vector<std::vector<int>>& matrix);
void PrintAllElements(const std::vector<std::vector<int>>& matrix);
void PrintMaxElements(const std::vector<std::vector<int>>& matrix, int sector);

int main() {
    int M, sector;
    M = RestrictInput(3, 100);

    auto matrix = CreateMatrix(M, M);

    FillMatrixWithRandom(matrix);

    ShowIntro(matrix);

    sector = RestrictInput(1, 4);
    PrintMaxElements(matrix, sector);

    return 0;
}

std::vector<std::vector<int>> CreateMatrix(int rows, int columns) {
    std::vector<std::vector<int>> matrix = std::vector<std::vector<int>>(rows, std::vector<int>(columns));
    return matrix;
}

void FillMatrixWithRandom(std::vector<std::vector<int>>& matrix) {
    srand( (unsigned int) time(0)); //Init Random Number Generator(RNG)
    //row ~ y axis
    for (int row = 0; row < matrix.size(); ++row) { 
        // column ~ x
        for (int column = 0; column < matrix[row].size(); ++column) { 
            matrix[row][column] = rand() % 10; // [0; 99]
        }
    }
}

void PrintAllElements(const std::vector<std::vector<int>>& matrix) {
    for (const auto& v : matrix) {
        for (const auto& elem : v) {
            //setw(2) for better look
            std::cout << std::setw(2) << elem << ' ';
        }
        std::cout << '\n';
    }
}

void PrintMaxElements(const std::vector<std::vector<int>>& matrix, int sector) {
    int currentMax = INT_MIN;

    //Iterate through matrix and 
    //find max element in given sector
    auto rows = matrix.size();
    auto columns = matrix[0].size();
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < columns; ++j) {
            switch (sector) {
            case 1:
                if (i < rows / 2 && i < j && j + i < rows - 1) {
                    if (matrix[i][j] > currentMax) {
                        currentMax = matrix[i][j];
                    }
                }
                break;
            case 2:
                if (j < rows / 2 && i > j && j + i < rows - 1) {
                    if (matrix[i][j] > currentMax) {
                        currentMax = matrix[i][j];
                    }
                }
                break;
            case 3:
                if (i > rows / 2 && i > j && j + i > rows - 1) {
                    if (matrix[i][j] > currentMax) {
                        currentMax = matrix[i][j];
                    }
                }
                break;
            case 4:
                if (j >  rows / 2 && i < j && j + i > rows - 1) {
                    if (matrix[i][j] > currentMax) {
                        currentMax = matrix[i][j];
                    }
                }
                break;
            }
        }
    }

    std::cout << "Max element: " << currentMax << '\n';
    std::cout << "Positions(x, y): ";
    
    //Depending on sector print all positions where max element is
    for (int y = 0; y < rows; ++y) {
        for (int x = 0; x < columns; ++x) {
            switch (sector) {
            case 1:
                if (y < rows / 2 && y < x && x + y < rows - 1) {
                    if (matrix[y][x] == currentMax) {
                        std::cout << "(" << x << ", " << y << ")\n";
                    }
                }
                break;
            case 2:
                if (x < rows / 2 && y > x && x + y < rows - 1) {
                    if (matrix[y][x] == currentMax) {
                        std::cout << "(" << x << ", " << y << ")\n";
                    }
                }
                break;
            case 3:
                if (y > rows / 2 && y > x && x + y > rows - 1) {
                    if (matrix[y][x] == currentMax) {
                        std::cout << "(" << x << ", " << y << ")\n";
                    }
                }
                break;
            case 4:
                if (x > rows / 2 && y < x && x + y > rows - 1) {
                    if (matrix[y][x] == currentMax) {
                        std::cout << "(" << x << ", " << y << ")\n";
                    }
                }
                break;
            }
        }
    }
}


void ShowIntro(const std::vector<std::vector<int>>& matrix) {
    std::cout << "Generated random matrix " << matrix.size() << "X" << matrix[0].size() << " :\n";
    PrintAllElements(matrix);
    std::cout << '\n';
    std::cout << "Choose sector in which max element will be found:\n";
    std::cout << " \\1/ \n" 
              << "2 X 4 \n" 
              << " /3\\ \n";
    std::cout << "Sector: \n";
}

int RestrictInput(int lowerBound, int upperBound) {
    //Read value until it's >= lowerBound AND <= upperBound
    int inputValue;
    do {
        std::cout << "Enter value [" << lowerBound << ":" << upperBound << "]: \n";
        std::cin >> inputValue;
    } while (inputValue < lowerBound || inputValue > upperBound);
    return inputValue;
}

Especially, in function PrintMaxElements() there is a chunk of code, where switch(sector) and it is responsible for checking if element belongs to a given sector. I believe, this part can be rewriten in more intelligent or pretty way.

Here go 2 images how if condition works in this switch part.

first draw

In switch we have if conditions. Explanation for looking for a max element in section #1.

  1. We get randomly filled matrix.
  2. Remember we don't count diagonal elements.
  3. In if's first part we have y < rows / 2 which is shown as green rectangle.
  4. In if's second part we have y < x which means that elements must be above the main(principal) diagonal as orange triangle.
  5. Then in third(last) if's part we have x + y < rows - 1 which means that elements must be under secondary diagonal.

Having 3, 4, 5 points united in one if statement we get the area which marked as cyan triangle where we should be looking for max element(red circle).

Thanks in advance:) Everybody have a great day.

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

Create a class Matrix

Instead of passing around vectors of vectors, consider creating a class Matrix. That makes the code much more readable. Also consider adding a function to access an element at a given row and column, this way you can change the way the matrix is stored internally without having to change any of the code that uses it.

Store the matrix as a one-dimensional vector

Vectors of vectors are not very efficient. Consider storing the matrix elements in a single, one-dimensional std::vector. Create a function to access elements, that will take a row and column and will convert that into an index into the vector.

Use C++'s random number generators

Instead of using srand() and rand(), I recommend that you use random number generation functions from C++'s standard library.

You only need to check two triangles

From your own diagrams it is clear that you only need to check if a given element is in the overlapping region of two triangles, the rectangle is redundant. However:

It's faster to directly construct the triangle of interest

Your solution visit every element of the matrix, but less than a quarter will be in the desired region. So a lot of CPU time is wasted checking elements you are not interested in. But it's actually quite easy to just visit those elements that are in the desired triangle. For example, for the top triangle, you just need to look at all rows with indices < rows / 2 (the rectangle from diagram 3). Furthermore, for the first row in that region, you start at column 1 up until column columns - 1, then for the second row it's starting from column 2 up to columns - 2, and so on:

switch (sector) {
case 1:
    for (i = 0; i < rows / 2; ++i) {
        for (j = i + 1; j < columns - i - 1; ++j) {
            currentMax = std::max(currentMax, matrix[i][j]);
        }
    }
    break;
...
}

Going further

Even nicer would be to have a Matrix class with a function to return a pair of iterators or perhaps even a std::ranges::view that represents a sector. That way, you can pass the iterators or view to existing standard library functions that return the max element or find all elements matching a given value. That way you could write something like:

auto range = matrix.getSector(sector);
auto currentMax = *std::ranges::max_element(range);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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