# Transforming elements of std containers from other std containers

### Problem

In this HackerRank problem we are asked to rotate the elements of a matrix in the following way:

### Example Input and Output

First and second entry specify the size of the matrix and third entry how many times it has to be rotated. As an example, the following input:

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


would produce the following output:

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


### Solution

My idea was to rotate these rings.

#include <vector>
#include <iostream>
#include <algorithm>

using Matrix = std::vector<std::vector<int>>;

void rotate_mat (Matrix &mat, int r){
auto m = mat.size(); // Number of rows
auto n = mat[0].size(); // Number of columns
auto n_rings = std::min(m,n)/2; // Number of rings
for(auto ring_i=0; ring_i<n_rings; ++ring_i){
// The elements of the ring are stored sequentially
// in v_ring so it can be rotated with std::rotate
std::vector<int>  v_ring;
// v_ring_ptr points to the original places in the matrix,
// so the rotation of v_ring can be assigned back to the matrix
std::vector<int*> v_ring_ptr;
// Top side of the ring
for(auto j=ring_i; j<=(n-1)-ring_i; ++j) {
v_ring.push_back(mat[ring_i][j]);
v_ring_ptr.push_back(&mat[ring_i][j]);
}
// Right side of the ring
for(auto i=ring_i+1; i<=(m-1)-ring_i; ++i) {
v_ring.push_back(mat[i][(n-1)-ring_i]);
v_ring_ptr.push_back(&mat[i][(n-1)-ring_i]);
}
// Bottom size of the ring
for(auto j=(n-1)-ring_i-1; j>ring_i; --j) {
v_ring.push_back(mat[(m-1)-ring_i][j]);
v_ring_ptr.push_back(&mat[(m-1)-ring_i][j]);
}
// Left size of the ring
for(auto i=(m-1)-ring_i; i>ring_i; --i) {
v_ring.push_back(mat[i][ring_i]);
v_ring_ptr.push_back(&mat[i][ring_i]);
}

std::rotate(v_ring.begin(),v_ring.begin()+r%v_ring.size(),v_ring.end());
// Update the rotated values in the original matrix
for (auto i=0; i<v_ring.size(); ++i){
*v_ring_ptr[i] = v_ring[i];
}
}
};

Matrix read_matrix(int m, int n) {
Matrix mat;
mat.reserve(m);
for(auto i=0; i<m; ++i) {
mat.push_back(std::vector<int>{});
mat[i].reserve(n);
for(auto j=0; j<n; ++j) {
int x; std::cin >> x;
mat[i].push_back(x);
}
}
return mat;
};

void print_matrix(Matrix &mat){
for (auto& i : mat){
for (auto& j : i) {
std::cout << j << " ";
}
std::cout << "\n";
}
};

int main() {
int m,n; std::cin >> m >> n;
int r; std::cin >> r;

rotate_mat(mat,r);
print_matrix(mat);

return 0;
}


### Questions

My main problem is that I would like to avoid having the v_ring copy and this part:

for (auto i=0; i<v_ring.size(); ++i){
*v_ring_ptr[i] = v_ring[i];
}


Is there a way to store references to the content of the original matrix so the transformation in the constructed rings would automatically be reflected? I tried with std::reference_wrapper. It almost works with that, I can modify the elements in the ring for example with ++ operator, but I cannot make assigments, nor std::rotate has any effect on them.

Any ideas? I'm also interested in any other approach that could come to your mind! I thought this way was easy to express in code

• what do you want to improve in this code ? do you want a better algorithm ? The same algorithm with better performance? a clearer algo ? etc... Because there are many approaches actually. Jan 25, 2018 at 12:47
• I couldn't express what I really wanted and I had to end up having two vectors, one for the values v_ring and another pointing to the values v_ring_ptr. I would like to be able to have a container that doesn't have the values, but the referenes to the values in the matrix so I can just modify them and the changes get reflected in the matrix. Jan 25, 2018 at 12:49
• update with executable code (c++11 minimum) Jan 26, 2018 at 1:23

Some things to note :

• As you said there are std::min(m,n)/2; rings.
• the ring R(r, p) has 2*(r+p-2) elements.
• the top left of the ring has always coordinates (x,x). This is visible in your code :) j = ring_i; v_ring.push_back(mat[ring_i][j]);
• Your code is using a relatively efficient amount of memory for the in-place transformation, and running in O(m*n) time, which is the best possible.
• A performance improvement will be to use a single vector for the data in the matrix such that m(x,y) = m.data[x * cols + y]

Can we do it differently ?

Given the local coordinates system where (0, 0) is the top left of the ring

A coordinate (i,j), 0<=i<w, 0<=j<h, j == 0 || i == 0 on a side of a ring, can be moved by one position using the function

std::pair<int, int>
rotated_local_next(int i, int j, int w, int h)
{
if(j == 0) //top , special case top-right
{
return i == w-1 ? std::make_pair(i, ++j) : std::make_pair(++i, j);
}
if(i == w-1) //right, special case bottom-right
{
return j == h-1 ? std::make_pair(--i, j) : std::make_pair(i, ++j);
}
if(j == h-1) //bottom, special case bottom-left
{
return i == 0 ? std::make_pair(i, --j) : std::make_pair(--i, j);
}
if(i == 0) //left, special case top-left
{
return j == 0 ? std::make_pair(++i, j): std::make_pair(i, --j);
}

// cannot happen
throw std::exception{};
}


You can now implement in matrix coordinates

std::pair<int, int>
rotated_matrix_next(int x, int y, int ring_i, int height, int width )
{
auto local_point = rotated_local_next(x-ring_i, y-ring_i, width-2*(ring_i), height-2*(ring_i));
return std::make_pair(local_point.first + ring_i, local_point.second + ring_i);
}


All you need to do now is to implement iterators satisfying MoveAssignable and MoveConstructible. The beginning of your ring is the element at positing ring, ring, which is also the end of the ring.

struct RingView
{
//ring start at 0
RingView(std::vector<std::vector<int>>& mat, int ringnumber)
: matrix(mat)
, rows(mat.size())
, cols(mat[0].size())
, ring(ringnumber)
{}

std::vector<std::vector<int>>& matrix;
int rows;
int cols;
int ring;

class ring_iterator : public std::iterator<std::forward_iterator_tag, int>
{
public:

ring_iterator(RingView* v = nullptr, int xpos = 0, int ypos = 0)
: view(v)
, x(xpos)
, y(ypos)
{}

ring_iterator(const ring_iterator& other) = default;
ring_iterator(ring_iterator&& other) = default;
ring_iterator& operator =(ring_iterator const&) = default;
ring_iterator& operator=(ring_iterator&&) = default;
virtual ~ring_iterator() = default;

RingView* view;
int x;
int y;

// Forward
ring_iterator& operator++() {
auto posnext = rotated_matrix_next(x, y, view->ring, view->cols, view->rows);

x = posnext.first;
y = posnext.second;
return *this;
}

ring_iterator operator++(int) {
auto posnext = rotated_matrix_next(x, y, view->ring, view->cols, view->rows);
ring_iterator next_iter = *this;
next_iter.x = posnext.first;
next_iter.y = posnext.second;
return next_iter;
}

bool operator==(const ring_iterator& other) const {
if(view == nullptr ){
return other.view == nullptr;
}
return view->ring == other.view->ring && x == other.x && y == other.y;
}

bool operator!=(const ring_iterator& other) const {
return !(*this == other);
}

// usually required
int& operator*() {
return view->matrix[x][y];
}
int* operator->() {
return &(view->matrix[x][y]);
}
};

ring_iterator begin()
{
return ring_iterator(this, ring, ring);
}

ring_iterator end()
{
return begin();
}

int size() const
{
return 2*(rows+cols -2) - 4 * ring;
}
};


Now you can rotate the matrix using the view. To be able to rotate in both directions (positive for clockwise, negative counter-clockwise) we use

r' = (r % view.size() + view.size()) % view.size();

void rotate_mat (Matrix &mat, int r){
auto n_rings = std::min(mat.size(),mat[0].size())/2; // Number of rings
for(auto ring_i=0; ring_i<n_rings; ++ring_i){
RingView view(mat,ring_i);
int r_modulo = (r % view.size() + view.size()) % view.size();
auto next_location = view.begin();
std::rotate(view.begin(),next_location,view.end());
}
}


Full code : https://ideone.com/I3vg5v

I got the solution I was looking for from stackoverflow (check it here). Now it doesn't need the extra copy. I was expecting that this wouldn't be as verbose. I think being able to use the algorithms over a vector of references can be an useful feature.

#include <vector>
#include <iostream>
#include <algorithm>

using Matrix = std::vector<std::vector<int>>;

/**
* Class implementing std::reference_wrapper that
* cannot be rebound after creation.
**/
template <class T>
class single_bind_reference_wrapper {

// pointer to the original element
T *p_;

public:

// typedefs
using type = T;

// Construct/Copy/Destroy
single_bind_reference_wrapper(T& ref) noexcept : p_(std::addressof(ref)) {}
single_bind_reference_wrapper(T&&) = delete;

// Enable implicit convertsion from ref<T> to ref<const T>,
// or ref<Derived> to ref<Base>
template <class U, std::enable_if_t<std::is_convertible<U*, T*>{}, int> = 0>
single_bind_reference_wrapper(const single_bind_reference_wrapper<U>& other) noexcept :
p_(&other.get()) { }

// Assignment
template <class U>
decltype(auto) operator=(U &&u) const
noexcept(std::is_nothrow_assignable<T, U>{}) {
return get() = std::forward<U>(u);
}

decltype(auto) operator=(const single_bind_reference_wrapper& other) const
noexcept(std::is_nothrow_assignable<T, T>{}) {
return get() = other.get();
}

// Access
operator T& () const noexcept { return *p_; }
T& get() const noexcept { return *p_; }
};

template <class T>
void swap(single_bind_reference_wrapper<T> &lhs,
single_bind_reference_wrapper<T> &rhs)
noexcept(std::is_nothrow_move_constructible<T>::value &&
std::is_nothrow_move_assignable<T>::value){
auto tmp = std::move(lhs.get());
lhs = std::move(rhs.get());
rhs = std::move(tmp);
}

void rotate_mat (Matrix &mat, int r){
auto m = mat.size(); // Number of rows
auto n = mat[0].size(); // Number of columns
auto n_rings = std::min(m,n)/2; // Number of rings
for(auto ring_i=0; ring_i<n_rings; ++ring_i){
// The elements of the ring are stored sequentially
// in v_ring so it can be rotated with std::rotate
std::vector<single_bind_reference_wrapper<int>>  v_ring;
// Top side of the ring
for(auto j=ring_i; j<=(n-1)-ring_i; ++j) {
v_ring.push_back(mat[ring_i][j]);
}
// Right side of the ring
for(auto i=ring_i+1; i<=(m-1)-ring_i; ++i) {
v_ring.push_back(mat[i][(n-1)-ring_i]);
}
// Bottom size of the ring
for(auto j=(n-1)-ring_i-1; j>ring_i; --j) {
v_ring.push_back(mat[(m-1)-ring_i][j]);
}
// Left size of the ring
for(auto i=(m-1)-ring_i; i>ring_i; --i) {
v_ring.push_back(mat[i][ring_i]);
}
std::rotate(v_ring.begin(),v_ring.begin()+r%v_ring.size(),v_ring.end());
}
};

Matrix read_matrix(int m, int n) {
Matrix mat;
mat.reserve(m);
for(auto i=0; i<m; ++i) {
mat.push_back(std::vector<int>{});
mat[i].reserve(n);
for(auto j=0; j<n; ++j) {
int x; std::cin >> x;
mat[i].push_back(x);
}
}
return mat;
};

void print_matrix(Matrix &mat){
for (auto& i : mat){
for (auto& j : i) {
std::cout << j << " ";
}
std::cout << "\n";
}
};

int main() {
int m,n; std::cin >> m >> n;
int r; std::cin >> r;

rotate_mat(mat,r);
print_matrix(mat);

return 0;
}

• @papagaga Just for reference, this was what I was trying to achieve. Jan 26, 2018 at 12:34
• @UmNyobe Just for reference, this was what I was trying to achieve. Jan 26, 2018 at 12:35
• Ranges are specifically designed to pipe from one algorithm to another. The only question is when they will arrive. For now you can try ranges-v3 by Eric Niebler. Jan 26, 2018 at 14:11
• @Incomputable wao, that's really cool. I'm checking it out Jan 26, 2018 at 14:14
• @Incomputable mmm but from what I reading that wouldn't solve my problem right? How would ranges solve my problem? What I want is what I had to implement, a container of references, so I can run the algorithm on the selected elements as if they were in a container, but so that the effect get's reflected in their original positions in the original container. Jan 26, 2018 at 14:24

"I thought this way was easy to express in code". Sadly, what's easy to write isn't always what's easy to read. Six loops, six one-letter variables, no comments... Frankly I can't follow (meaning I won't try to follow unless I really have to) and I'm not sure you'll be able to understand it yourself in two weeks from now.

You should try to better document your code, either through comments or, better, through variable and type names.

Another -arguably simpler- approach would be to create a function modifying the index by which the matrix is accessed. For example, if you want the element (0,0) of a matrix which has been rotated once, you need the element (0,1) of the underlying matrix.

Here's my take (I haven't put much time in the algorithm but tried to make it easy to read):

struct Coordinates {int row=0, col=0; };
using Matrix_size = Coordinates;

// determine the ring to which those coordinates belongs
int ring_number(Coordinates coord, Matrix_size m_size, int offset=0) {
if  (  coord.row == 0+offset
|| coord.col == 0+offset
|| coord.row == m_size.row-1-offset
|| coord.col == m_size.col-1-offset
) return 0;
return 1 + ring_number(coord, m_size, offset+1);
}

// return the coordinates of north-west and southwest angles of the ring
std::pair<Coordinates, Coordinates> ring_coordinates(Coordinates coord, Matrix_size m_size) {
auto rn = ring_number(coord, m_size);
return { Coordinates{rn, rn}, Coordinates{m_size.row-rn-1, m_size.col-rn-1} };
}

Coordinates rotate_coordinates(Coordinates c, Matrix_size m_size, int step=1) {
auto [min, max] = ring_coordinates(c, m_size);
step %= 2*(max.row-min.row+max.col-min.col); // number of elements in the ring;
for (int i = 0; i < step; ++i) {
if (c.row == min.row && c.col < max.col) ++c.col;
else if (c.col == max.col && c.row < max.row) ++c.row;
else if (c.row == max.row && c.col > min.col) --c.col;
else --c.row;
}
return c;
}


Then you can use it to output a rotated matrix that way:

#include <iostream>
#include <vector>

int main() {
std::vector<std::vector<int>> data = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16} };
Matrix_size msz = {4, 4};
for (int row = 0; row < msz.row; ++row) {
for (int col = 0; col < msz.col; ++col) {
auto rc = rotate_coordinates(Coordinates{row, col}, msz, 1);
std::cout << data[rc.row][rc.col] << " ";
}
std::cout << '\n';
}
}

• Oh, I didn't put any comments because I thought it was very simple. The loops are just to build the ring, the ring is a square with four sides, each loop saves the values in a vector, and then I rotate it with std rotate. I'll put comments to make it clear. My problem is that I need to make a copy v_ring and then have v_ring_ptr. It can be done without v_ring but I don't know how. Thanks for your approach, for me the one letter variable names n,m i,j have meaning, but I understand it can be difficult to read. Jan 25, 2018 at 13:43
• I've added the comments, I don't know if its clearer now. Jan 25, 2018 at 13:49
• I agree with the name variable x, it didn't have meaning, but it was because I didn't know how to name it. It's the ring that it's being built, I've renamed ring_i Jan 25, 2018 at 13:53
• @papagaga WooWapDaBug has a better time complexity than your solution (if he was not using pushback) Jan 25, 2018 at 14:31
• @UmNyobe what do you mean with "if he was not using pushback", what should I use and what would that change? Jan 26, 2018 at 7:38

Full code:

really main task and algorithm for rotate indices: convert (i, j) -> (_i, _j) by given matrix dimension MxN and R. also important condition is min(M, N) % 2 == 0.

so need first build array of permutations by M, N, R, for this we not need matrix itself.

#include <malloc.h>
#include <cstring>

typedef unsigned int UINT;

struct S
{
UINT i, j;
};

void rotate(UINT M, UINT N, UINT R, S* u)
{
u += M*N;
bool f = M > N;

UINT i = M, _i = 0;

do
{
--i; // i + _i == M - 1;

UINT j = N, _j = 0;

do
{
--j; // j + _j == N - 1;

UINT s; // side in {0,1,2,3}

if (f)
{
// (N < M) => (min(M, N)==N) => (j != _j)
// (j == _j) => (2*j == N - 1) => (min(M, N) == 2*j+1)

if (j > _j)
{
if (_i < _j) s = 2;
else if (i <= _j) s = 0;
else s = 3;

// (_i < _j) && (i <= _j) && (_j < j) =>
// (_i < _j) && (i <  j) =>
// (i+_i < j+_j)
// (M < N)
}
else // j < _j
{
if (_i <= j) s = 2;
else if (i < j) s = 0;
else s = 1;

// (_i <= j) && (i < j) && (j < _j) =>
// (_i < _j) && (i <  j) =>
// (i+_i < j+_j)
// (M < N)
}
}
else
{
// (M <= N) => (min(M, N)==M) => (i!=_i)
// (i==_i) => (2*i==M-1) => (min(M, N)==2*i+1)

if (i > _i)
{
if (_i >= _j) s = 3;
else if (_i > j) s = 1;
else s = 2;

// (_i >= _j) && (_i > j) && (i > _i) =>
// ( i > _j)  && (_i > j) =>
// (i+_i > j+_j)
// (M > N)
}
else // i < _i
{
if (i > _j) s = 3;
else if (i >= j) s = 1;
else s = 0;

// (i > _j) && ( i >= j) && (_i > i) =>
// (i > _j) && (_i >  j) =>
// (i+_i > j+_j)
// (M > N)
}
}

UINT r, Di, Dj, L, l;

switch (s)
{
case 0:
r = i;
l = j;
break;
case 1:
r = j;
l = _i;
break;
case 2:
r = _i;
l = _j;
break;
case 3:
r = _j;
l = i;
break;
// default: __assume(false);
}

l -= r, r <<= 1, Di = M - r - 1, Dj = N - r - 1;

L = R % ((Di + Dj) << 1);

UINT ii = i, jj = j;

switch (s)
{
for (;;)
{
case 0:
if (L <= l)
{
jj -= L;
goto __end;
}
jj -= l, L -= l, l = Di;
case 1:
if (L <= l)
{
ii += L;
goto __end;
}
ii += l, L -= l, l = Dj;
case 2:
if (L <= l)
{
jj += L;
goto __end;
}
jj += l, L -= l, l = Di;
case 3:
if (L <= l)
{
ii -= L;
goto __end;
}
ii -= l, L -= l, l = Dj;
}
// default: __assume(false);
}

__end:
u--, u->i = ii, u->j = jj;

} while (_j++, j);

} while (_i++, i);
}


this is O(M*N) - we have loop by M and inside it loop for N. but for R we have maximum 5 iterations. for every point (i,j) we calculate it side (0,1,2,3) and ring. and shift.

function for visualize permutation:

void PrintPermutation(UINT M, UINT N, UINT R)
{
S* u = new S[M*N];

rotate(M, N, R, u);

UINT i = 0;

do
{
UINT j = 0;

do
{
printf("(%u,%u)->(%u, %u) ", i+1, j+1, 1+u->i, 1+u->j);
u++;
} while (++j<N);

printf("\n");

} while (++i<M);

delete [] (u - M*N);
}


say for

PrintPermutation(4, 5, 1);


we got

(1,1)->(2, 1) (1,2)->(1, 1) (1,3)->(1, 2) (1,4)->(1, 3) (1,5)->(1, 4)
(2,1)->(3, 1) (2,2)->(3, 2) (2,3)->(2, 2) (2,4)->(2, 3) (2,5)->(1, 5)
(3,1)->(4, 1) (3,2)->(3, 3) (3,3)->(3, 4) (3,4)->(2, 4) (3,5)->(2, 5)
(4,1)->(4, 2) (4,2)->(4, 3) (4,3)->(4, 4) (4,4)->(4, 5) (4,5)->(3, 5)


what is correspond to

with this function implement matrix rotation already easy:

void RotateMatrix(UINT M, UINT N, UINT R, UINT mtx[])
{
UINT mn = M * N;

S* u = new S[mn];

UINT* _mtx = new UINT[mn];

std::memcpy(_mtx, mtx, mn * sizeof(UINT));

rotate(M, N, R, u);

UINT i = 0, j;

do
{
j = 0;

do
{
mtx[N * u->i + u->j] = *_mtx++;
u++;
} while (++j<N);

} while (++i<M);

delete [] (_mtx - mn);
delete [] (u - mn);
}

void PrintMatrix(UINT M, UINT N, const UINT mtx[])
{
UINT i = M, j;

do
{
j = N;
do
{
printf("%02u ", *mtx++);
} while (--j);

printf("\n");

} while (--i);
}

void RotateAndPrintMatrix(UINT M, UINT N, UINT R, UINT mtx[])
{
printf("\n===============\n");
PrintMatrix(M, N, mtx);
printf("---------------\n");
RotateMatrix(M, N, R, mtx);
PrintMatrix(M, N, mtx);
}


first we allocate and build array of permutations u than make copy of matrix _mtx and finally do in loop

    mtx[N * u->i + u->j] = *_mtx++;
u++;


test#1:

UINT mtx[] = {
1,  2,  3,  4,
5,  6,  7,  8,
9,  10, 11, 12,
13, 14, 15, 16
};
RotateAndPrintMatrix(4, 4, 2, mtx);


and result:

01 02 03 04
05 06 07 08
09 10 11 12
13 14 15 16
=============
03 04 08 12
02 11 10 16
01 07 06 15
05 09 13 14


test#2: (Sample Input #02)

UINT mtx[]= {
1,  2,  3,  4,
7,  8,  9, 10,
13, 14, 15, 16,
19, 20, 21, 22,
25, 26, 27, 28
};
RotateAndPrintMatrix(5, 4, 7, mtx);


and result:

01 02 03 04
07 08 09 10
13 14 15 16
19 20 21 22
25 26 27 28
=============
28 27 26 25
22 09 15 19
16 08 21 13
10 14 20 07
04 03 02 01


for RotateAndPrintMatrix(5, 4, 14*6, mtx); 14*6=((4+3)*2)*((2+1)*2) matrix how and must be unchanged

01 02 03 04
07 08 09 10
13 14 15 16
19 20 21 22
25 26 27 28
=============
01 02 03 04
07 08 09 10
13 14 15 16
19 20 21 22
25 26 27 28