Transforming elements of std containers from other std containers

Question

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;

    auto mat = read_matrix(m,n);
    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

Answer 1

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::advance(next_location, r_modulo);
        std::rotate(view.begin(),next_location,view.end());
    }
}

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

Answer 2

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;

    auto mat = read_matrix(m,n);
    rotate_mat(mat,r);
    print_matrix(mat);

    return 0;
}

Answer 3

"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';
    }
}

Answer 4

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