HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Consecutive Primes challenge at CodeEval.com and memory allocation issue

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
combinatoricscodereviewrecursionobjective-cstackoverflowalgorithmprogramming-challenge
codeevalprimeschallengeissuememoryandcomallocationconsecutive

Problem

I finally solved this challenge with using recursion and figured out why the automatic scorer wasn't passing my previous solutions. I was using NSMutableArray to store the numbers and with N=18 I was running out of allowed memory by codeeval.com. I rewrote the code using integer arrays and I received 100% but still the answer is not being rank because it is using too much time and memory to solve it. Please let me know if this a viable solution and how I can improve speed and memory allocation.

With integer array solution I was using a for loop to copy data from array to another array. There might be a better solution by using memcpy but I was not able to make it work.

I just changed the solution to get rid of one of the copying loops and instead just move the counter back which cut the run time in half and it I did get ranked. I did the same with NSArray solution and it is still using too much memory.

One of the things that I don't like about the solution is using a global variable for count. I have to figure out how to count within the recursion code and not use global variables.

Here is the assignment:

Consecutive Primes Challenge @ codeeval.com


Alice has an even number of N beads, and each bead has a number from 1 to N painted on it. She would like to make a necklace out of
all the beads, with a special requirement: any two beads next to each
other on the necklace must sum to a prime number. Alice needs your
help to calculate how many ways it is possible to do so.


For example:


N = 4


There are two possible ways to build the necklace. Note that the last bead connects to the first bead.

1 2 3 4
1 4 3 2




Note: The necklace should be unique.
For example: 1 2 3 4 is the same as 2 3 4 1 and 3 4 1 2 and 4 1 2 3.

To solve if first tried recursion but that was running very slowly because of going through all the permutations. The inputs consists of one even integer on a line. Each integer \$N\$ is \$2

Solution

Review of your existing code:

The spacing is not consistent, generally there should be more space (as in }else{). Some lines are too long.

You are completely ignoring the "Modern Objective-C" syntax such as properties, object literals, and array/dictionary subscripting:

  • [NSNumber numberWithInt:i] can simply be written as @(i),



  • [beadsArray objectAtIndex:pos] is beadsArray[pos],



  • [beadsArray lastObject] is beadsArray.lastObject.



Xcode can assist you in the conversion (Edit > Refactor > Convert to Modern Objective-C Syntax.)

BOOL isEven(int number)
{
  if(number%2==0){
      return true;
  }
  return false;
}


The body can be simplified to

return (number % 2 == 0);


And you should decide which type of boolean variable you want to use:

  • The Objective-C BOOL with values NO and YES, or



  • C's bool from ` with values false and true.



Moreover, isEven() is called only once in your program, so you may
eliminate it altogether.

In calculateNumNecklaces(), the numOfBeads parameter is unused
and the local startPos not really needed. Setting the temporary arrays
to nil inside the loop is not necessary.

Possible improvements:

For 16 beads, your Objective-C code runs in 1.50 s on my computer (Release configuration).

As @Vogel612 already said, the isPrime() function can be optimized by using a fixed array of primes in the needed range.
As possible implementation is

const int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
const int numPrimes = sizeof(primes)/sizeof(primes[0]);

bool isPrime(int number){
    for (int i = 0; i < numPrimes; i++) {
        if (number == primes[i]) {
            return true;
        }
    }
    return false;
}


Interestingly, the impact is not too big: the computation time
reduces to 1.45 s.

The repeated creation of mutable arrays consumes much time. This can
be avoided by modifying the existing arrays (necklace and beadsArray)
before entering the recursive step, and undoing the modification on
return. For the beads array, you can remove the first element and later
add it at the end, so that it is not chosen again:

void calculateNumNecklaces(NSMutableArray *beadsArray, NSMutableArray *necklace)
{
    if (beadsArray.count == 1) {
        if ((isPrime([necklace.lastObject intValue]) + [beadsArray.lastObject intValue])
            && (isPrime([necklace.firstObject intValue]) + [beadsArray.lastObject intValue])) {
            count +=1;
        }
    } else {
        int previousNumber = [necklace.lastObject intValue];
        for (int pos = 0; pos < beadsArray.count; ++pos) {
            NSNumber *bead = beadsArray.firstObject;
            [beadsArray removeObjectAtIndex:0];
            if (isPrime(previousNumber + bead.intValue)) {
                [necklace addObject:bead];
                calculateNumNecklaces(beadsArray, necklace);
                [necklace removeObjectAtIndex:necklace.count - 1];
            }
            [beadsArray addObject:bead];
        }
    }
}


Computation time now: 0.28 s for 16 beads.

This can further be improved by working on a single array only, and
just exchanging the beads:

void calculateNumNecklaces(NSMutableArray *beadsArray, int fromPosition)
{
    if (fromPosition == beadsArray.count) {
        // All beads chosen, check if valid:
        if (isPrime([beadsArray.lastObject intValue] + [beadsArray.firstObject intValue])) {
            count += 1;
        }
        return;
    }

    // Is the bead at `fromPosition` a valid choice?
    int previousNumber = [beadsArray[fromPosition - 1] intValue];
    if (isPrime(previousNumber + [beadsArray[fromPosition] intValue])) {
        calculateNumNecklaces(beadsArray, fromPosition + 1);
    }

    for (int pos = fromPosition + 1; pos < beadsArray.count; ++pos) {
        // Is the bead at `pos` a valid choice?
        if (isPrime(previousNumber + [beadsArray[pos] intValue])) {
            // Yes. Swap with `fromPosition`, recurse, and swap back:
            [beadsArray exchangeObjectAtIndex:fromPosition withObjectAtIndex:pos];
            calculateNumNecklaces(beadsArray, fromPosition + 1);
            [beadsArray exchangeObjectAtIndex:fromPosition withObjectAtIndex:pos];
        }
    }
}


This function has to be called as

calculateNumNecklaces1(beadsArray, 1);


where beadsArray is an initial mutable array with the numbers
1, ..., N.

Computation time now: 0.14 s for 16 beads.

Finally, the global variable count can also be eliminated by
changing the function to

`
int calculateNumNecklaces(NSMutableArray *beadsArray, int fromPosition)
{
if (fromPosition == beadsArray.count) {
// All beads chosen, check if valid:
if (isPrime([beadsArray.lastObject intValue] + [beadsArray.firstObject intValue])) {
return 1;
} else {
return 0;
}
}

int count = 0;
// Is the bead at fromPosition` a valid choice?
int previousNumber = [bead

Code Snippets

BOOL isEven(int number)
{
  if(number%2==0){
      return true;
  }
  return false;
}
return (number % 2 == 0);
const int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
const int numPrimes = sizeof(primes)/sizeof(primes[0]);

bool isPrime(int number){
    for (int i = 0; i < numPrimes; i++) {
        if (number == primes[i]) {
            return true;
        }
    }
    return false;
}
void calculateNumNecklaces(NSMutableArray *beadsArray, NSMutableArray *necklace)
{
    if (beadsArray.count == 1) {
        if ((isPrime([necklace.lastObject intValue]) + [beadsArray.lastObject intValue])
            && (isPrime([necklace.firstObject intValue]) + [beadsArray.lastObject intValue])) {
            count +=1;
        }
    } else {
        int previousNumber = [necklace.lastObject intValue];
        for (int pos = 0; pos < beadsArray.count; ++pos) {
            NSNumber *bead = beadsArray.firstObject;
            [beadsArray removeObjectAtIndex:0];
            if (isPrime(previousNumber + bead.intValue)) {
                [necklace addObject:bead];
                calculateNumNecklaces(beadsArray, necklace);
                [necklace removeObjectAtIndex:necklace.count - 1];
            }
            [beadsArray addObject:bead];
        }
    }
}
void calculateNumNecklaces(NSMutableArray *beadsArray, int fromPosition)
{
    if (fromPosition == beadsArray.count) {
        // All beads chosen, check if valid:
        if (isPrime([beadsArray.lastObject intValue] + [beadsArray.firstObject intValue])) {
            count += 1;
        }
        return;
    }

    // Is the bead at `fromPosition` a valid choice?
    int previousNumber = [beadsArray[fromPosition - 1] intValue];
    if (isPrime(previousNumber + [beadsArray[fromPosition] intValue])) {
        calculateNumNecklaces(beadsArray, fromPosition + 1);
    }

    for (int pos = fromPosition + 1; pos < beadsArray.count; ++pos) {
        // Is the bead at `pos` a valid choice?
        if (isPrime(previousNumber + [beadsArray[pos] intValue])) {
            // Yes. Swap with `fromPosition`, recurse, and swap back:
            [beadsArray exchangeObjectAtIndex:fromPosition withObjectAtIndex:pos];
            calculateNumNecklaces(beadsArray, fromPosition + 1);
            [beadsArray exchangeObjectAtIndex:fromPosition withObjectAtIndex:pos];
        }
    }
}

Context

StackExchange Code Review Q#87097, answer score: 5

Revisions (0)

No revisions yet.