What is an efficient way to REPLACE repeated elements within 2D(10x10) int array

[Arkalian]

I have a question for you guys. My Bro is working on this for a project and this problem came up. I want to surprise him with the answer. I figured if anyone could deal with it, you guys could. I had to copy and paste it and I am not much of a programmer so if there are any mistakes, I apologize. Any ideas or insight would be great. Thanks in advance! Ark

"I have generated a 10x10 integer matrix, by way of a 2 dimensional array, the elements are randomly generated and lie on

Code: [Select]

1 <= z <= 5
I am in need of an efficient method of setting all adjacent "duplicates" (repeating elements), along any row or column (not diagonally), of length 3 or greater to the integer six (6). The source for the brute method follows for clarity.

Code: [Select]

for(row=0;row<10;row++)
{
    for(col=0;col<10;col++)
    {
        board[row][col]=rand()%4+1; //filling matrix here
    }
}
print_board(board, row, col);

printf("Switch: ROW COLUMN\n ");
scanf("%hu %hu", &x1, &y1);
printf("With: ROW COLUMN\n");
scanf("%hu %hu", &x2, &y2);
swap(board, x1, y1,x2, y2);  //stdrd for loop no good b/c of
                             //below <-this->below   
if(board[0][0]==board[0][1] && board[0][1]==board[0][2] && board[0][2]==board[0][3])
{
    board[0][0]=6;
    board[0][1]=6; 
    board[0][2]=6;
    board[0][3]=6;   // brute force would require many more to complete
}
I know there must exist a much more elegant approach than listing out all permutations. If you have seen this and recall the technique I would very much appreciate your assistance."

[Deque]

Well, you can count, can't you?
So you can count the number of equal adjacent elements and set them to 6 if the count is equal or greater than 3 instead of "bruteforcing" them.

[Arkalian]

Well, you can count, can't you?
So you can count the number of equal adjacent elements and set them to 6 if the count is equal or greater than 3 instead of "bruteforcing" them.

First, Clearly you can't. A counting loop CLEARLY will not work because if and when you learn to count you will realize that there the middle cells of the 2 dimensional array have to appear in BOTH binary AND operators.

Code: (c) [Select]

#include <emmintrin.h>

int main(){
    int board[10][10];
    int row, col;
    for(row=0;row<10;row++){
        for(col=0;col<10;col++){
            board[row][col]=rand()%2+1; //filling matrix here
            printf("%d ", board[row][col]);
        }
        printf("\n");
    }
    printf("\n");
    for(row=0;row<10;row++){
        col = 0;
        while(col <= 10 - 4){
            __m128i xmm0 = _mm_loadu_si128((__m128i*)&board[row][col]);
            __m128i xmm1 = _mm_set1_epi32(board[row][col]);
            __m128i xmm2;
            __m128i xmm6 = _mm_set1_epi32(6);
            __m128i xmmn = _mm_set1_epi32(-1);
            unsigned long c;
            int mask;

            xmm0 = _mm_xor_si128(_mm_cmpeq_epi32( xmm0, xmm1 ), xmmn);
            mask = _mm_movemask_epi8(xmm0);
            if (!mask){
                _mm_storeu_si128( (__m128i*)&board[row][col], xmm6 );
                col += 4;
                do{
                    if (col > 10 - 4) col = 10 - 4;
                    xmm0 = _mm_loadu_si128((__m128i*)&board[row][col]);
                    xmm2 = _mm_or_si128( _mm_cmpeq_epi8( xmm0, xmm1 ), _mm_cmpeq_epi8( xmm0, xmm6 ) );
                    xmm0 = _mm_xor_si128(xmm2, xmmn);
                    xmm0 = _mm_or_si128(_mm_slli_si128(xmm0, 4), xmm0);
                    xmm0 = _mm_or_si128(_mm_slli_si128(xmm0, 8), xmm0);
                    xmm2 = _mm_xor_si128(xmm0, xmmn);
                    _mm_maskmoveu_si128( _mm_set1_epi32(6), xmm2 , (char*)&board[row][col] );
                    mask = _mm_movemask_epi8(xmm0);
                    if (col == 10 - 4){
                        col++;
                        break;
                    }
                    c = __builtin_ctz(mask);/* In MSVC: _BitScanForward(mask, &c); */
                    c >>= 2;
                    col += c;
                }while(mask);
            }else{
                col += __builtin_ctz(mask) >> 2;
            }
        }
    }
    for(row=0;row<10;row++){
        for(col=0;col<10;col++){
            printf("%d ", board[row][col]);
        }
        printf("\n");
    }

    return 1;
}
This has to be taken care of with intrinsic's.

Now that that is cleared up.

I simply came on here to ask for advice. I said, right of the bat, that it might have mistakes and I apologized for not knowing more about it. But, that's why I asked for the help in the first place. I surely didn't ask so I could get hit with a smart ass insult. Especially, one that doesn't even help. It doesn't send a great message to the community when someone honestly and humbly comes on here to ask for help and they get nothing more out of it than an argument. Things change, I guess.

[Hermit]

I think you can solve it with Dynamic Programming

Code: [Select]

for (int i=0;i<10;i++){
count[0][i].top=1;
}

for (int i=0;i<10;i++){
count[i][0].left=1;
}

for (int i=0;i<10;i++){
for (int j=0;j<10;j++){
if (i-1>=0){
if (board[i][j]==board[i-1][j]){
count[i][j].top=count[i-1][j].top+1;
}
else{
count[i][j].top=1;
}
}
if (j-1>=0){
if (board[i][j]==board[i][j-1]){
count[i][j].left=count[i][j-1].left+1;
}
else{
count[i][j].left=1;
}
}
}
}

for (int i=10;i>=0;i--){
for (int j=10;j>=0;j--){
if (count[i][j].top>=3){
for (int k=0;k<count[i][j].top;k++){
board[i-k][j]=6;
}
for (int k=0;k<count[i][j].left;k++){
board[i][j-k]=6;
}
}
}
}
for each block there is two field, namely top and left. This field save how many adjacent number from top and left that has the same value with the current block. if the value of current block is the same with the value of the block above, then it means the current top value is one plus the above block top value

[lucid]

I simply came on here to ask for advice. I said, right of the bat, that it might have mistakes and I apologized for not knowing more about it. But, that's why I asked for the help in the first place. I surely didn't ask so I could get hit with a smart ass insult. Especially, one that doesn't even help. It doesn't send a great message to the community when someone honestly and humbly comes on here to ask for help and they get nothing more out of it than an argument. Things change, I guess.

Dude woah. I really think you might have misunderstood the tone of Deque's post. I highly doubt she was trying to be rude or throw "smart ass insults" at you. Right Deque?

So let's move on and pretend this never happened. Quit being so sensitive

[bluechill]

Well, you can count, can't you?
So you can count the number of equal adjacent elements and set them to 6 if the count is equal or greater than 3 instead of "bruteforcing" them.

What Deque means is something like this:

Code: (C++) [Select]

#include <iostream>
#include <vector>
#include <random>
#include <sstream>

using namespace std;

typedef vector<vector<int>> matrix;

void check(matrix &board);
void check(matrix::iterator board);

int main(int argc, char** argv)
{
int size = 10;

if (argc == 2)
{
stringstream ss;
ss << argv[1];
ss >> size;
}

matrix board(size, vector<int>(size));

random_device generator;
uniform_int_distribution<int> distribution(1,5);

for (auto it = board.begin(),end = board.end();it != end;++it)
for (auto jt = it->begin(), end = it->end();jt != end;++jt)
*jt = distribution(generator);

for (auto i : board)
{
for (int &j : i)
cout << j << ' ';

cout << endl;
}

cout << endl;

check(board);

for (int i = 0;i < size;i++)
for (int j = 0;j < size;j++)
{
if (i < j)
swap(board[i][j], board[j][i]);
}

check(board);

for (int i = 0;i < size;i++)
for (int j = 0;j < size;j++)
{
if (i < j)
swap(board[i][j], board[j][i]);
}

for (auto i : board)
{
for (int &j : i)
cout << j << ' ';

cout << endl;
}

return 0;
}

void check(matrix &board)
{
for (auto it = board.begin(),end = board.end();it != end;++it)
check(it);
}

void check(matrix::iterator it)
{
int count = 1;
int element = *(it->begin());

vector<int>::iterator jt, end;
for (jt = it->begin()+1, end = it->end();jt != end;++jt)
{
if (element == *jt)
count++;
else
{
if (count >= 3)
{
for (auto ft = jt-1,end = ft-count;ft != end;ft--)
*ft = 6;
}

element = *jt;
count = 1;
}
}

if (count >= 3)
{
for (auto ft = it->end()-1,end = ft-count;ft != end;ft--)
*ft = 6;
}
}

C++11 ftw

[Deque]

First, Clearly you can't. A counting loop CLEARLY will not work because if and when you learn to count you will realize that there the middle cells of the 2 dimensional array have to appear in BOTH binary AND operators.

Code: (c) [Select]

#include <emmintrin.h>

int main(){
    int board[10][10];
    int row, col;
    for(row=0;row<10;row++){
        for(col=0;col<10;col++){
            board[row][col]=rand()%2+1; //filling matrix here
            printf("%d ", board[row][col]);
        }
        printf("\n");
    }
    printf("\n");
    for(row=0;row<10;row++){
        col = 0;
        while(col <= 10 - 4){
            __m128i xmm0 = _mm_loadu_si128((__m128i*)&board[row][col]);
            __m128i xmm1 = _mm_set1_epi32(board[row][col]);
            __m128i xmm2;
            __m128i xmm6 = _mm_set1_epi32(6);
            __m128i xmmn = _mm_set1_epi32(-1);
            unsigned long c;
            int mask;

            xmm0 = _mm_xor_si128(_mm_cmpeq_epi32( xmm0, xmm1 ), xmmn);
            mask = _mm_movemask_epi8(xmm0);
            if (!mask){
                _mm_storeu_si128( (__m128i*)&board[row][col], xmm6 );
                col += 4;
                do{
                    if (col > 10 - 4) col = 10 - 4;
                    xmm0 = _mm_loadu_si128((__m128i*)&board[row][col]);
                    xmm2 = _mm_or_si128( _mm_cmpeq_epi8( xmm0, xmm1 ), _mm_cmpeq_epi8( xmm0, xmm6 ) );
                    xmm0 = _mm_xor_si128(xmm2, xmmn);
                    xmm0 = _mm_or_si128(_mm_slli_si128(xmm0, 4), xmm0);
                    xmm0 = _mm_or_si128(_mm_slli_si128(xmm0, 8), xmm0);
                    xmm2 = _mm_xor_si128(xmm0, xmmn);
                    _mm_maskmoveu_si128( _mm_set1_epi32(6), xmm2 , (char*)&board[row][col] );
                    mask = _mm_movemask_epi8(xmm0);
                    if (col == 10 - 4){
                        col++;
                        break;
                    }
                    c = __builtin_ctz(mask);/* In MSVC: _BitScanForward(mask, &c); */
                    c >>= 2;
                    col += c;
                }while(mask);
            }else{
                col += __builtin_ctz(mask) >> 2;
            }
        }
    }
    for(row=0;row<10;row++){
        for(col=0;col<10;col++){
            printf("%d ", board[row][col]);
        }
        printf("\n");
    }

    return 1;
}
This has to be taken care of with intrinsic's.

Now that that is cleared up.

I simply came on here to ask for advice. I said, right of the bat, that it might have mistakes and I apologized for not knowing more about it. But, that's why I asked for the help in the first place. I surely didn't ask so I could get hit with a smart ass insult. Especially, one that doesn't even help. It doesn't send a great message to the community when someone honestly and humbly comes on here to ask for help and they get nothing more out of it than an argument. Things change, I guess.

I don't know what you read in my post that infuriated you. I didn't say anything about a for-loop.

I will try again and rephrase.
You can often write algorithms if you think about the way you would solve a problem like this if you do it manually. Like if you have an 2D-array on paper in front of you, and all the time you cover all elements except for one (e.g. using a paper with a window to cover the matrix except for one element); and you have to replace all adjacent duplicates of length 3 or greater by using a pencil. Think about that or even do it for a sample matrix.
What you will do is going through the columns and rows and count. E.g. you see the number 1. You move your window to the right and see number 1 again. So in your head you note that there are at least two adjacent elements that are the same, your internal counter is 2. You move the cover paper to the right again and see the element 4. So no need to do something, you start counting by 1 again. This goes on and on until your counter is greater than 2, then you have to find all adjacent duplicate numbers to the current number (also the ones you might not have looked at by now) and replace them with 6.
You stop with the whole procedure if you reach the end of your matrix.

What I described above is an algorithm. It's one way how you can find a solution in your head. That algorithm is the one you can use as well for your implementation and that doesn't need any bruteforcing like you described.
bluechill already gave you example code for it, but it is important that you get a feeling about how to solve this yourself. How to get the idea of the solution.
I actually wanted to lead to you to that solution step by step in such a way that you find the solution yourself instead of others giving it to you. But there is no sense in doing that anymore, so I still hope my description is of any help for the next time you need to create an algorithm.

[Arkalian]

Ahhhh, I see. I thought your response to my post was to ask me if I was able to "count". Like, if I had the ability to count (i.e. 1,2,3,4), then, I would be able to solve my problem...lol. I was like damn what a low blow. I apologize for misunderstanding you. But, I am sure you can see how that could be misinterpreted. I will try to ease off of the trigger a bit. Thanks to everyone for trying to help.

Sincerely,
Ark

[bluechill]

Ahhhh, I see. I thought your response to my post was to ask me if I was able to "count". Like, if I had the ability to count (i.e. 1,2,3,4), then, I would be able to solve my problem...lol. I was like damn what a low blow. I apologize for misunderstanding you. But, I am sure you can see how that could be misinterpreted. I will try to ease off of the trigger a bit. Thanks to everyone for trying to help.

Sincerely,
Ark

Whenever a programmer says, "could you count it" or "can you count" they almost always mean can you count the thing you are trying to replace/count/etc.

[Arkalian]

Cool deal.