Mapping matrix with index values (IMPROVEMENT)

[Grime]

This is not homework. I have already solved the problem. But I want help to see whether there can be a better way to do this.

Given M and N the height and width of a MATRIX which follows a particular pattern, and being given that pattern and not the MATRIX, I am supposed to convert any number into its respective index.

Consider this.

1 2 3
6 5 4
7 8 9

where order is (3,3)

The pattern is that the line increments from left to right and then on the next line it swaps to go from right to left and so on..

The below,

1 2 3
6 5 4
7 8 9
(with height and width being variables) is all what I was given (on paper and not on program). I converted that into this problem demonstrated above.

Basically those integers represent address. I input the location of bombs in maze using this address system. But then I need to convert it back to index system so I can do my maze magic.

Get what I'm saying right?

I came up with this:

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

struct coordinate {
	int x;
	int y;
};

int main() {

	int M, N;
	cout << "Enter order of 2D array";
	cin >> M >> N;

	map<int, coordinate> int_and_coordinate;

	for (int k = 0; k < M; k++) {

		for (int i = 0, j = N * k + 1; i < N; i++, j++) {
			int_and_coordinate.insert(pair<int, coordinate>(j, { i, k }));
		}

		k++;
		if (!(k < M))
			break;

		for (int i = 0, j = N * (k + 1); i < N; i++, j--) {
			int_and_coordinate.insert(pair<int, coordinate>(j, { i, k }));
		}
	}

	for (int i = 1; i <= M*N; i++) {
		cout << i << ":\t" << int_and_coordinate[i].x << ", " << int_and_coordinate[i].y<< '\n';
	}

	system("pause");
	return 0;
}

But there are two drawbacks for this.

1) Cannot convert indexes back to integer value.
-> How to do this? *scratches head*

2) Isn't there a better easier method?
Because I am preparing for a future CS competition. They will give problems like that so I need to be able to convert such a matrix into indexes. And Doing all of that is TIME CONSUMING and hard to REMEMBER. It took me very long to come up with the logic for that.


Is it a bad idea to use C++ for competitive programming? Well it's the only thing I know so far..

[jonnin]

if I understood your question, this is about as fast as it gets.

vector <double> m(rows*cols);
m[desiredrow*maxcols+desiredcol] = value;

you can wrap that up so it isn't a burden in the code, of course.

maps are slower than they should be. I have had zero luck with them in ultra high performance code.

C++ is one of the fastest languages available for anything. You almost have to write assembly language to beat it, for most tasks. A tiny number of things are faster in pure C, which can be mixed into c++ at will. You need to understand the costs of memory allocation and release, and cost of copying things unnecessarily, at the very least.

[dutch]

Your method is extremely inefficient. How about something like this:

#include <iostream>
#include <iomanip>

// row and col are 0-based
struct Coord {
    int row, col;
    Coord(int row, int col) : row(row), col(col) { }
};

std::ostream& operator<<(std::ostream& os, const Coord& coord) {
    return os << '(' << coord.col << ',' << coord.row << ')';
}

int to_int(int row, int col, int cols) {
    int row_start = row * cols;
    return row % 2 ? row_start + cols - col : row_start + col + 1;
}

Coord to_coord(int i, int cols) {
    int row = (i - 1) / cols;
    int col = (i - 1) % cols;
    return Coord(row, row % 2 ? cols - col - 1: col );
}

void display_grid(int rows, int cols) {
    for (int row = 0; row < rows; ++row) {
        for (int col = 0; col < cols; ++col)
            std::cout << std::setw(2) << to_int(row, col, cols) << ' ';
        std::cout << '\n';
    }
    std::cout << '\n';
}

void display_coords(int rows, int cols) {
    for (int i = 1; i <= rows * cols; ++i)
        std::cout << std::setw(2) << i << ' ' << to_coord(i, cols) << '\n';
    std::cout << '\n';
}

int main() {
    int rows = 3, cols = 4;  // even number of cols
    display_grid(rows, cols);
    display_coords(rows, cols);

    cols = 5;  // odd number of cols
    display_grid(rows, cols);
    display_coords(rows, cols);
}

Output:

 1  2  3  4 
 8  7  6  5 
 9 10 11 12 

 1 (0,0)
 2 (1,0)
 3 (2,0)
 4 (3,0)
 5 (3,1)
 6 (2,1)
 7 (1,1)
 8 (0,1)
 9 (0,2)
10 (1,2)
11 (2,2)
12 (3,2)

 1  2  3  4  5 
10  9  8  7  6 
11 12 13 14 15 

 1 (0,0)
 2 (1,0)
 3 (2,0)
 4 (3,0)
 5 (4,0)
 6 (4,1)
 7 (3,1)
 8 (2,1)
 9 (1,1)
10 (0,1)
11 (0,2)
12 (1,2)
13 (2,2)
14 (3,2)
15 (4,2)

to_int still looks a little over-complicated but I'm not sure how to simplify it. And now that I think about it, it should probably take a Coord instead of row and col!

And obviously a proper C++ program would wrap up some of these details so, for example, you wouldn't have to pass cols around like that.

EDIT: I've incorporated JLBorges simplification to the to_int calculation above. It was originally:

int to_int(int row, int col, int cols) {
    int val = row * cols + col + 1;
    return row % 2 ? (2 * row + 1) * cols - val + 1 : val;
}

[JLBorges]

> Cannot convert indexes back to integer value. How to do this?
> Isn't there a better easier method?

Both conversions (coordinates => value and value => coordinates) can be computed;
there is no need to store the entire matrix.

For example:

#include <iostream>
#include <iomanip>
#include <string>

struct coordinates { int row ; int col ; };

std::ostream& operator<< ( std::ostream& stm, coordinates coord ) {

    return stm << " (" << coord.row << ',' << coord.col << ')' ;
}

struct matrix {

    matrix( int height, int width ) : nrows(height), ncols(width)
    { /* assert( nrows > 0 && ncols > 0 ) ; */ }

    int value( coordinates coord ) const { // convert coordinates => value

        if( coord.row >= nrows || coord.col >= ncols ) return -1 ; // invalid coordinates

        const int v = coord.row * ncols ;
        if( coord.row %2 == 0 ) return v + coord.col + 1 ; // even row
        else return v + ncols - coord.col ; // odd row
    }

    coordinates coord( int value ) const { // convert value => coordinates

        if( value < 1 || value > (nrows*ncols) ) return { nrows, ncols } ; // invalid

        const int row = (value-1) / ncols ;

        if( row%2 == 0 ) return { row, value - row*ncols - 1 } ; // even row
        else return { row, ncols - (value-1)%ncols - 1 } ; // odd row
    }

    std::ostream& print( std::ostream& stm = std::cout ) const {

        const int width = int( std::to_string( nrows * ncols ).size() ) + 2 ;

        for( int row = 0 ; row < nrows ; ++row ) {

            for( int col = 0 ; col < ncols ; ++col )
                stm << std::setw(width) << value( { row, col } ) ;
            stm << '\n' ;
        }
        return stm << '\n' ;
    }

    int nrows ;
    int ncols ;
};

int main() {

    std::cout << "enter #rows and #cols: " ;
    int M, N ;
    std::cin >> M >> N ;
    std::cout << M << 'x' << N << "\n\n" ;

    const matrix m( M, N ) ;
    m.print() ;

    int cnt = 0 ;
    for( int val = 1 ; val <= M*N ; ++val ) {

        if( cnt++%N == 0 ) std::cout << '\n' ;
        std::cout << "value: " << val << "  coordinates: " << m.coord(val) << '\n' ;
    }
}

http://coliru.stacked-crooked.com/a/321ccdb3076da71e

[Grime]

JLBorges I'm not able to understand what is there inside the struct matrix(). Can you give me keywords so I can google & understand?

Especially
matrix( int height, int width ) : nrows(height), ncols(width)
What is that!

coordinates coord( int value ) const
What is const doing outside the function declaration?

std::ostream& print( std::ostream& stm = std::cout ) const
what is this?

I did not even know you could do all of this inside structures.. Thought they were just group of datatypes.


I appreciate all the help. But I want to mention that this competition is not based on how good the program is. It's just that they give you problems and you have to solve them just so that they work. No need to make very efficient program.

So I need to be able to solve this by typing and thinking quickly.

Maybe I can simplify your examples by looking at the logic I will post later after I've analyzed properly when I have time.

[JLBorges]

> matrix( int height, int width ) : nrows(height), ncols(width)
> What is that!

In matrix( int height, int width ) : nrows(height), ncols(width) { /* ... */ }.
the bolded part is the member initializer list
Initialise member nrows with height and the member ncols with width
More information: https://www.learncpp.com/cpp-tutorial/8-5a-constructor-member-initializer-lists/


> What is const doing outside the function declaration?

See: https://isocpp.org/wiki/faq/const-correctness#const-member-fns


> std::ostream& print( std::ostream& stm = std::cout ) const
> what is this?

Member function print which takes an argument of type std::ostream&
There is a default argument; if the function is called without providing an argument, the std::cout would be used.
https://en.cppreference.com/w/cpp/language/default_arguments