Given 4 objects, how to figure out whether exactly 2 have a certain property

Question

Hi guys! I have another question on how to make most elegant solution to this problem, since I cannot afford to go to computer school right so my actual "pure programming" CS knowledge is not perfect or great. This is basically an algorhythm problem (someone please correct me if I am using that wrong, since I don't want to keep saying them and embarass myself)

I have 4 objects. Each of them has an species property that can either be a dog, cat, pig or monkey. So a sample situation could be:

object1.species=pig object2.species=cat object3.species=pig object4.species=dog

Now, if I want to figure out if all 4 are the same species, I know I could just say:

if  ( (object1.species==object2.species) 
    && (object2.species==object3.species)
    && (object3.species==object4.species)
) {
    // They are all the same animal (don't care WHICH animal they are)
}

But that isn't so elegant right? And if I suddenly want to know if EXACTLY 3 or 2 of them are the same species (don't care WHICH species it is though), suddenly I'm in spaghetti code.

I am using Objective C although I don't know if that matters really, since the most elegant solution to this is I assume the same in all languages conceptually? Anyone got good idea?

Thanks!!

Answer 1

You can use a hash table (or dictionary in objective-C) with the key on the species, incrementing the count every time.

For clarity (pseudo-code):

// N is 4 for your particular case
for ( int i = 0; i < N; i++ )
   hashtable[ object[i].species ]++;

hashtable[ Species.PIG ]; // number of pigs (constant)

or if you want to unroll it manually:

hashtable[ object1.species ]++;
hashtable[ object2.species ]++;
hashtable[ object3.species ]++;
hashtable[ object4.species ]++;

now you can check through the species to see the count:

for each key in hashtable
    if ( hashtable[ key ] == 3 ) // species "key" has 3 items
        /* Code */

of course, "hashtable" can be just a simple array if species is just a simple enum/integer. The above should be the same theory in either case.

Answer 2

You can count how many comparisons match of all possible comparisons. If exactly 1 comparison is true, then exactly 2 items are the same, if 3 comparisons match, exactly 3 items are the same. This example is in C, you'll have to convert it to objective-C on your own.

int count = 0;
count += object1.species == object2.species;
count += object1.species == object3.species;
count += object1.species == object4.species;
count += object2.species == object2.species;
count += object2.species == object3.species;
count += object3.species == object4.species;
// count 0 - all different
// count 1 - exactly 2 are the same
// count 2 - two pairs of 2
// count 3 - exactly 3 are the same
// count 6 - all are the same

The counting can also be implemented as a loop:

for (int i = 0; i < 4; i++)
    for (int j = i + 1; j < 4; j++)
        count += objects[i].species == objects[j].species;

This approach only works if the amount of objects is 5 or less. Because of this and the fact that the amount of comparisons scales quadratically, it's better to use a hashtable if the amount of objects is larger.

Answer 3

This is precisely what sets and counted sets are for.

BOOL allSameSpecies(NSArray *animals) {
    NSSet *speciesSet = [NSSet setWithArray:[animals valueForKey:@"species"]];
    return [[speciesSet] count] == 1;
}

BOOL sameSpeciesNumber(NSArray *animals, NSUInteger targetCount) {
    NSCountedSet *speciesCounts = [NSCountedSet setWithArray:[animals valueForKey:@"species"]];
    for (id species in speciesCounts) {
        if ([speciesCounts countForObject:species] == targetCount)
            return YES;
    }
    return NO.
}