10 replies to this topic

[Liatula]

Hi,
I have a 2 dimentional array for 3x3 with numbers.
I need to check that it contains all numbers between 1-9.
Any idea what's the most efficient way to do it?
Cheers
L

[WingedPanther]

There are a lot of ways to do it. An array of bools comes to mind.

[ZekeDragon]

Just make an implementation that works and is simple. That's usually the best, and worry about efficiency if it becomes a constraint. I'd do this:

boolean isOneThruNine(int[][] twoDArray)
{
    boolean retVal = false;
    // Unfortunately Java doesn't seem to have a convenient way to do this...
    boolean[] checkArray = { false, false, false, false, false,
                             false, false, false, false };

    if (twoDArray.length != 3) return false;

    for (int iii = 0; iii < 3; ++iii)
    {
        if (twoDArray[iii].length != 3) return false;
    }

    for (int iii = 0; iii < 9; ++iii)
    {
        int val = twoDArray[iii / 3][iii % 3] - 1;

        if (val >= 8 || val < 0) return false;
        if (checkArray[val]) return false;

        checkArray[val] = true;
    }

    return true;
}

Edited by ZekeDragon, 06 December 2009 - 03:34 AM.
Added val check.

[Liatula]

I don't really understand what this line is meant to be doing:

int val = twoDArray[iii / 3][iii % 3];

[ZekeDragon]

If you learn what the modulus operator does, it should make more sense. Also remember that integer division simply cuts off the values after the decimal, so 2 / 3 = 0.

Edited by ZekeDragon, 06 December 2009 - 02:08 PM.

[chili5]

You could use a boolean array to keep track of whether or not the number exists. So arbNums[1] = true, if 1 is found in the matrix, false otherwise.

Then if you find a false entry in the array, then the matrix does not contain all the numbers from 0 to 9.

#include <iostream>
#include <fstream>

using namespace std;

bool arbNums[10];

bool isOneToNine() {
    for (int x=1;x<10;x++) {
        if (arbNums[x] == false) {
            return false;
        }
    }
    return true;
}

int main()
{
    ofstream out("out.txt");

    int arnNums[3][3];

    int a[] = {1,2,3,4,3,6,7,8,9};
    int nCount = 0;

    for (int x=0;x<3;x++) {
        for (int y=0;y<3;y++) {
            arnNums[x][y] = a[nCount++];
        }
    }




    for (int x=0;x<10;x++) arbNums[x] = false;

    for (int x=0;x<3;x++) {
        for (int y=0;y<3;y++) {
            arbNums[arnNums[x][y]] = true;
        }
    }

    if (isOneToNine()) {
        out << "Contains 1 to 9\n";
    } else {
        out << "Does not contain 1 to 9\n";
    }

    out.close();

    return 0;
}

ZekeDragon said:

Just make an implementation that works and is simple. That's usually the best, and worry about efficiency if it becomes a constraint. I'd do this:

boolean isOneThruNine(int[][] twoDArray)
{
    boolean retVal = false;
    // Unfortunately Java doesn't seem to have a convenient way to do this...
    boolean[] checkArray = { false, false, false, false, false,
                             false, false, false, false };

You don't even have to do that, it floods the array with false values to begin with.

So:

boolean[] checkArray = new boolean[10];

But, just for the record you could do:

java.util.Arrays.fill(checkArray,false);

:)

[ZekeDragon]

Why the use of C++? This is a Java question. :P

Anyway, thanks for that Arrays tip, I'll remember that you can do that. And yes, I used to always assigning a value to everything I make, in the C++ world it's "If you don't assign it a value, it's undefined!"

Also, if you're writing in C++, it's generally a good idea to avoid globals. You could very easily have declared that array locally and sent it to "isOneToNine()" as a parameter.

[chili5]

ZekeDragon said:

Why the use of C++? This is a Java question. :P

Code::Blocks is faster than Netbeans. :P But, the idea remains the same.

Quote

Anyway, thanks for that Arrays tip, I'll remember that you can do that. And yes, I used to always assigning a value to everything I make, in the C++ world it's "If you don't assign it a value, it's undefined!"

Quote

Also, if you're writing in C++, it's generally a good idea to avoid globals. You could very easily have declared that array locally and sent it to "isOneToNine()" as a parameter.

And, thanks for that tip. I wrote it quickly so wasn't paying attention to that. =)

[Shaddix]

edit: never mind

[chili5]

Actually a HashSet isn't a bad idea. If you add all the numbers in the matrix to the set and at the end the set has a size of 9 then the array contains all the numbers to 1-9.

HashSet<Integer> nums = new HashSet<Integer>();


for (int x=0;x<3;x++) {

     for(int y=0;y<3;y++) {

          nums.add(matrix[x][y]);

     }

}


if (nums.size() == 9) {

       System.out.println("The matrix contains the numbers 1-9");

} else {

       System.out.println("The matrix does not contain the numbers 1-9");

}

This eliminates the need for an 0(n) iteration through the boolean array, so it probably is better.

[ZekeDragon]

chili5 said:

This eliminates the need for an 0(n) iteration through the boolean array, so it probably is better.

Given, and Shaddix's idea wasn't a bad one, but I think this would still be less efficient. However which way you look at it, you're going to end up needing to package each of the int's into Integer objects. Done transparently sure, but not for free. Performing nine if checks on booleans should be cheaper than packaging nine static ints into dynamically declared Integer objects. Also if you look at my implementation it performs the check on each of those booleans along with adding them to the array itself, so you aren't having a separate check of the array anyway.

And yes, you have to check the size of the matrix, if you don't you could end up throwing an ArrayIndexOutOfBoundsException, so you'll probably have two for loops either way.