2D Array Row and Column Duplicate Checker

[Bizzy]

Hey guys, so continuing with my project, I was able to create two functions that determine if there are duplicate rows or columns in an array and they work perfectly. Now I have to try and put them together to determine if a full array has any duplicate rows or columns and I'm not sure how to do this. I'm sure my issue is how I'm using int i in the board_has_no_duplicates function. Any help?

bool rows_are_different(const int board[MAX_SIZE][MAX_SIZE],
                        int size,
                        int row1,
                        int row2) {

    for (int i = 0; board[row1 - 1][i] && board[row2 - 1][i]; i++) {
        if (board[row1 - 1][i] != board[row2 - 2][i]) {
            return false;
        }
    }
    return true;
}

bool cols_are_different(const int board[MAX_SIZE][MAX_SIZE],
                        int size,
                        int col1,
                        int col2) {

    for (int i = 0; board[i][col1 - 1] && board[i][col2 - 1]; i++) {
        if (board[i][col1 - 1] != board[i][col2 - 1]) {
            return false;
        }
    }
    return true;
}

bool board_has_no_duplicates(const int board[MAX_SIZE][MAX_SIZE], int size) {

    for (int i = 0; i < size; i++) {
        if (!rows_are_different(board, size, i, i) &&    //FIX???
            !cols_are_different(board, size, i, i)) {
            return false;
        }
    }
    return true;
}

[coder777]

Why this - 1 in row. - 1/col. - 1?

What is the data type of board?

This

board[row1 - 1][i] && board[row2 - 1][i]

returns true if both expressions are != 0. Is that your intention?

[fantomasAlbania]

Why have you put [row1-1] / [row2-2]?
I am not sure if I am wrong but this means , row1 = i , than i = 0 and 0-1 ?

it seems a bit wrong exception .

[Bizzy]

Okay, I apologize I switched around the "true" and "false" statements to make sense with what the functions were called. Also yes, I need to have row1 - 1 etc. in order for the inputs to find the proper array element. The inputs for my project start at 1, so to find [0] I need to subtract 1. It works as intended with my tests so that's not an issue.

So now I have the code below, and I 'm wondering what I need to do with the arguments row1, row2, col1, and col2, where I have i right here

if (rows_are_different(board, size, i, i) &&    //FIX???
            cols_are_different(board, size, i, i)) {
            return true;

Here's the full code updated.

bool rows_are_different(const int board[MAX_SIZE][MAX_SIZE],
                        int size,
                        int row1,
                        int row2) {

    for (int i = 0; board[row1 - 1][i] && board[row2 - 1][i]; i++) {
        if (board[row1 - 1][i] == board[row2 - 2][i]) {
            return false;
        }
    }
    return true;
}

bool cols_are_different(const int board[MAX_SIZE][MAX_SIZE],
                        int size,
                        int col1,
                        int col2) {

    for (int i = 0; board[i][col1 - 1] && board[i][col2 - 1]; i++) {
        if (board[i][col1 - 1] == board[i][col2 - 1]) {
            return false;
        }
    }
    return true;
}

bool board_has_no_duplicates(const int board[MAX_SIZE][MAX_SIZE], int size) {

    for (int i = 0; i < size; i++) {
        if (rows_are_different(board, size, i, i) &&    //FIX???
            cols_are_different(board, size, i, i)) {
            return true;
        }
    }
    return false;
}

[Bizzy]

Here's a test you can run if you want. Both boards return 0 when the first should return 1, since there is a duplicate column.

void test_board_has_no_duplicates() {
    int board[MAX_SIZE][MAX_SIZE];

    string test_board_1[] = { "X-X-",
                              "XOX-",
                              "O-O-",
                              "O-O-" };
    string test_board_2[] = { "OXXO",
                              "XOOX",
                              "OOXX",
                              "XXOO" };
    int size_1 = 4;

    read_board_from_string(board, test_board_1, size_1);
    cout << board_has_no_duplicates(board, size_1) <<
        " should be 1" << endl;
    read_board_from_string(board, test_board_2, size_1);
    cout << board_has_no_duplicates(board, size_1) <<
        " should be 0" << endl;
}

[mbozzi]

You need to check each row against every other row.
Use a nested loop.

for (int i = 0; i < board_size; ++i)
  for (int j = 0; j < board_size; ++j)
    if (i != j && !cols_are_different(board, board_size, i, j)) {
      // there is a duplicate column.  
    }
// there is no duplicate column 

[Bizzy]

Could you explain the purpose of i !=j ? Also I just tested your solution but it didn't seem to work

[mbozzi]

i != j prevents columns from being compared against themselves. This is required because any column is a duplicate of itself.

Don't forget that you need to do the similar process for rows. You can combine the two.

Your solution doesn't work

That's at least because cols_are_duplicate() && rows_are_duplicate() will end up accessing the -1st corresponding row or column of the array. Are you using one-indexed arrays? Why? (This sort of strange requirement should probably be documented somewhere.)

Can you please provide the definition of read_board_from_string() so I can run your test case?

[Bizzy]

Gotcha, okay. Also hmm, I'll keep trying to get it to work with your explanation. And I'm using 2D arrays, so board[i][j] is just an example. I really appreciate the help, btw

In the meantime, here's the function I was given to test with:

bool read_board_from_string(int board[MAX_SIZE][MAX_SIZE],
                            string board_string[MAX_SIZE],
                            int size) {
    for (int row = 0; row < size; row++) {
        string line = board_string[row];

        if (!line_is_valid(line)) {
            return false;
        }

        for (int col = 0; col < size; col++) {
            board[row][col] =  convert_char_to_color(line[col]);
        }
    }

    return true;
}

[mbozzi]

Thanks. Maybe this will help. You might want to double-check your first test case.

# include <iostream>

static constexpr int MAX_SIZE = 4;

// Just made up this defn. 
int convert_char_to_color(char c) { 
    switch (c) { case 'X': return 1; case 'O': return 2; default: return 0; };
}

bool read_board_from_string(int board[MAX_SIZE][MAX_SIZE],
                            std::string board_string[MAX_SIZE],
                            int size) {
    for (int row = 0; row < size; row++) {
        std::string line = board_string[row];


        for (int col = 0; col < size; col++) {
            board[row][col] =  convert_char_to_color(line[col]);
        }
    }

    return true;
}


bool rows_are_same(const int board[MAX_SIZE][MAX_SIZE],
                   int const r1, int const r2) {
    for (int i = 0; i < MAX_SIZE; ++i) 
        if (board[r1][i] != board[r2][i]) return false;
    return true;
}
bool cols_are_same(const int board[MAX_SIZE][MAX_SIZE], 
                   int const c1, int const c2) {
    for (int i = 0; i < MAX_SIZE; ++i) 
        if (board[i][c1] != board[i][c2]) return false;
    return true;
}
// both of these functions are almost identical. 
// Duplicate code is bad!  Is there a way to get rid of it? 

// no size parameter needed in this case
bool board_has_no_duplicates(const int board[MAX_SIZE][MAX_SIZE]) {

    for (int i = 1; i <= MAX_SIZE; ++i) {
        for (int j = 1; j <= MAX_SIZE; ++j) {
            if (i == j) continue; 
            if (cols_are_same(board, i, j) || rows_are_same(board, i, j)) 
                return false;
        }
    }
    return true;
}

void test_board_has_no_duplicates() {
    int board[MAX_SIZE][MAX_SIZE];

    /// FIXME: This board has duplicate rows.  
    std::string test_board_1[] = { "X-X-",
                              "XOX-",
                              "O-O-",
                              "O-O-" };
    std::string test_board_2[] = { "OXXO",
                              "XOOX",
                              "OOXX",
                              "XXOO" };
    int size_1 = 4;

    read_board_from_string(board, test_board_1, size_1);
    std::cout << board_has_no_duplicates(board) <<
        " should be 0 -- there are duplicate rows in the test case." << std::endl;
    read_board_from_string(board, test_board_2, size_1);
    std::cout << board_has_no_duplicates(board) <<
        " should be 0" << std::endl;
    // You can use the assert() macro from the <cassert> header to do these sorts of tests less painfully. 
    // e.g.: assert(! board_has_no_duplicates(board)); // assertion should always be true.
}

int main() {
    test_board_has_no_duplicates();
}

http://coliru.stacked-crooked.com/a/2dee078a128b291b

[Bizzy]

Thanks man, this works great. Also the first test board was to see if the function would return 0 as expected, since it does have a duplicate :)