How to compare whole 2D array rows not elements

user_12157404 0
Viewed 645

For a function of the form.

bool contains_equal_rows(int height, int width, const int ar[height][width])

How do I find if a row is repeated? I can see how you can set a bool to true if a row is repeated, but how do you avoid returning false too early?

Problem description:

Write a function that gets a 2-d array of given dimensions of ints.
It returns true if the array contains two rows with exactly the same values in the same order, and returns false otherwise.

bool contains_equal_rows( int height, int width, const int ar[height][width])

Examples:

On input

{{1,2,3,4},
{2,3,4,1},
{1,2,3,4}}

it returns true.

On input

{{1,2,3,4},
{2,3,4,5},
{3,4,5,6}}

it returns false.

On input

{{1,1,1,1},
{2,2,2,2},
{1,1,1,6}}

it returns false.

My attempt so far:

bool contains_equal_rows(int height, int width, const int array[height][width])
{
  int w = width;
  int h = height;
  bool test = false;
  bool matchedRow = false;

  for(int m = 0; m < h; m++)
  {
    for(int n = 0; n < w; n++)
    {
        if( array[m][n] == array[m][n-1] )
        {
            test = true;
        }
        else
        {
            test = false;
        }
    }

    if(test == true)
    {
        matchedRow = true;
    }
  }
  return matchedRow;
}

The problem with my code is that I'm only comparing a row with the one before it, and can't figure out how to compare one row with all.

Expected results as shown in description.

c
5 Answers

You should start your outer loop from 1.
And in your inner loop compare array[0] against array[m],
before entering into the inner most loop set test to false
as soon as test is true you can break out of both loops and return true.

user_37338010

You could add another for-loop: 

For each row `i`:  
    For every other row `j`:  
        For each column `k` compare `array[i][k]` and `array[j][k]`

Something like this for example:

int w = width;
int h = height;
boolean test = false;

for(int i = 0; i < h; i++)
{
    for(int j = i+1; j < h; j++) {
        test = true;
        for(int k = 0; k < w; k++)
        {
            if( array[i][k] != array[j][k] )
            {
                test = false;
            }
        }
        if(test == true)
        {
            return true;
        }
    }
}
return false;
user_54576430

Perhaps the clearest way to do this is to break down the task, by creating a separate function to compare two rows; then run through the array, checking each row against all others:

bool rows_are_equal(int width, const int row1[], const int row2[])
{
    for (int i = 0; i < width; ++i) if (row1[i] != row2[i]) return false;
    return true;
}

bool contains_equal_rows(int height, int width, const int *array[])
{
    for (int row = 0; row < height; ++row) { // Check each row ...
        for (int test = row + 1; test < height; ++test) { // ... against all the others:
            if (rows_are_equal(width, array[row], array[test])) return true;
        }
    }
    return false;
}

Notice that I've changed the format of the last argument to your contains_equal_rows function, as the way you had it written is not standard C.

Feel free to ask for further clarification and/or explanation.

user_108710730

try this:

bool contains_equal_rows(int height, int width, const int array[][])
{
int horizontalItr = 0;
int verticalItr = 0;
int verticalItrItrUtility = 0;

bool testIfRowIsRepeated = true;
bool foundAtLeastOneRowIsRepeated = false;
bool finalAnswerRowIsRepeated = false;

for (verticalItr; verticalItr < height - 1; verticalItr++)
{
    for (verticalItrItrUtility = verticalItr; verticalItrItrUtility < height - 1 ; verticalItrItrUtility++)
    {
        testIfRowIsRepeated = true

        for (horizontalItr; horizontalItr < width; horizontalItr++)
        {
            if (array[verticalItrItrUtility][horizontalItr] != array[verticalItrItrUtility + 1][horizontalItr])
            {
                testIfRowIsRepeated = false;
                horizontalItr = 0;
                break;
            }
        }

        if (testIfRowIsRepeated == true)
        {
            foundAtLeastOneRowIsRepeated = true;
            break;
        }
    }

    if (foundAtLeastOneRowIsRepeated)
    {
        finalAnswerRowIsRepeated = true;
        break;
    }
}

return finalAnswerRowIsRepeated;

}

didn't tested it, but it seems fine to me, couple of things, 1. i changed your variables name, to more clear names. 2. the check is supposed to be against the next rows, not the preveious ones. 3. the concept is that i assume each row is the repeated one, until the loop proves me otherwise. enjoy! :)

user_120974890

This code works only for your test cases specs i.e, with width=4. You can create an outer for loop for the current row to compare it's elements with every row, notice that when it compares with itself flag would be equal to width hence you should avoid comparing it with itself using "continue", if at anytime all 4 elements of our current row are same to any other row then flag becomes equal to width(i.e, 4) and we return true immediately, if we come out of the outer loop having counter "k" then none of the 2 rows are same and we return false 

bool contains_equal_rows(int height, int width, const int array[][4])
{
int flag = 0;

for (int k = 0;k < height;k++)
    for (int m = 0; m < height; m++)
    {
        if (m == k)
            continue;
        for (int n = 0; n < width; n++)
            if (array[k][n] == array[m][n])
                flag++;
            else
                break;
        if (flag == width)
            return true;
        else
            flag = 0;
    }
return false;
}
user_55037530
Related