6
\$\begingroup\$

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 \le N \le 18\$.

First I tried to do it with recursion but that was taking way too long going through all the permutation. Then I tried to do is creating two arrays with odd and even numbers and going through them picking the number which will give me a prime when I add it to the last number picked and removing it from the array. The loop goes through all the numbers until it finds enough for a necklace or exits the loop.

Here is the code using NSMutableArray:

    BOOL isPrime(int number){
        for(int i = 2;i<(int)(number/2)+1;i++){
            if (number%i == 0) {
                return false;
            }
        }
        return true;
    }

    BOOL isEven(int number)
    {
        if(number%2==0){
            return true;
        }
        return false;
    }    
    NSUInteger count=0;    
        void calculateNumNecklaces(int numOfBeads, NSMutableArray *beadsArray, NSMutableArray *necklace)
            {

                if ([beadsArray count] == 1) {

                    if((isPrime([[necklace lastObject] intValue] + [[beadsArray lastObject] intValue]) && (isPrime([[necklace objectAtIndex:0] intValue] + [[beadsArray lastObject] intValue])))){
//comparing the last bead in beads array to last in necklace and to first in necklace
                        [necklace addObject:[beadsArray lastObject]];
                        count +=1;

                    }
                    //return 1;
                }else{
                    int previousNumber = [[necklace lastObject] intValue];
                    int startPos = 0;
                    for (int pos = startPos; pos < [beadsArray count]; pos+=1) {
                        if (isPrime(previousNumber  + [[beadsArray objectAtIndex:pos] intValue])) {
                            NSMutableArray *tempNecklace = [necklace mutableCopy];
                            [tempNecklace addObject:[beadsArray objectAtIndex:pos]];
                            NSMutableArray *tempArray = [beadsArray mutableCopy];
                            [tempArray removeObjectAtIndex:pos];
                            calculateNumNecklaces(numOfBeads, tempArray, tempNecklace);
                            tempNecklace = nil;
                            tempArray = nil;
                        }
                    }

                }


                //return 0;
            }
            -(void)primesMain
            {
                int input = 8;
                if (isEven(input)) {
                    NSMutableArray *beadsArray =[[NSMutableArray alloc] init];
                    for (int i = 2; i<=input; i++) {
                        [beadsArray addObject:[NSNumber numberWithInt:i]];
                    }
                    NSMutableArray *necklace = [[NSMutableArray alloc]init];
                    [necklace addObject:[NSNumber numberWithInt:1]];
                    calculateNumNecklaces(input, beadsArray, necklace);

                }
                NSLog(@"%d",count);
            }

The code using integer arrays:

        NSUInteger count=0;
        BOOL isPrime(int number){
            for(int i = 2;i<(int)(number/2)+1;i++){
                if (number%i == 0) {
                    return false;
                }
            }
            return true;
        }

        BOOL isEven(int number)
        {
            if(number%2==0){
                return true;
            }
            return false;
        }
            void calculateNumNecklacesC(int numOfBeads, int beadsArray[], int sizeBeadsArray, int necklace[], int sizeNecklaceArray)
    {

        if (sizeBeadsArray == 1) {
            if(isPrime(necklace[sizeNecklaceArray-1] + beadsArray[sizeBeadsArray-1]) && (isPrime(necklace[0] + beadsArray[sizeBeadsArray-1]))){
                necklace[sizeNecklaceArray+1] = beadsArray[sizeBeadsArray];
                count +=1;

            }
        }else{
            int previousNumber = necklace[sizeNecklaceArray-1];
            int startPos = 0;
            for (int pos = startPos; pos < sizeBeadsArray; pos++) {
                if (isPrime(previousNumber  + beadsArray[pos])) {

                    /*By getting rid of the copying to the temp array but just manipulating the position i was able to cut the run time by half
int tempNecklaceArray[sizeNecklaceArray+1];

                    for (int i = 0; i<sizeNecklaceArray; i++) {
                        tempNecklaceArray[i]=necklace[i];
                    }
                    tempNecklaceArray[sizeNecklaceArray] = beadsArray[pos];
                    int tempNecklaceSize = sizeNecklaceArray+1;*/

                    necklace[sizeNecklaceArray] = beadsArray[pos];
                    sizeNecklaceArray+=1;

                    int tempSizeBeadsArray = sizeBeadsArray-1;
                    int tempBeadsArray[tempSizeBeadsArray];
                    int tempPos = 0;
                    for (int i = 0; i<sizeBeadsArray; i++) {

                        if (i!=pos) {
                            tempBeadsArray[tempPos] = beadsArray[i];
                            tempPos+=1;
                        }
                    }
                    calculateNumNecklacesC(numOfBeads, tempBeadsArray, tempSizeBeadsArray, necklace, sizeNecklaceArray);
                    sizeNecklaceArray -=1; // brings back the size counter to the proper position for this loop.

                }
            }

        }

    }

            -(void)primesMainC
            {
                int input =18;
                count = 0;
                if (isEven(input)) {
                    int beadsArray[input-1];
                    int pos = 0;
                    while (pos<input-1) {
                        beadsArray[pos] = pos+2;
                        pos+=1;
                    }
                    int necklace[input];
                    necklace[0]=1;
                    calculateNumNecklacesC(input, beadsArray, input-1, necklace,1);

                }
                NSLog(@"answer: %d",count);
            }

I also copied the code and run it as C program but that still used too much time @ codeeval.com to get a score.

\$\endgroup\$
4
\$\begingroup\$

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 <stdbool.h> 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 = [beadsArray[fromPosition - 1] intValue];
    if (isPrime(previousNumber + [beadsArray[fromPosition] intValue])) {
        count += 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];
            count += calculateNumNecklaces(beadsArray, fromPosition + 1);
            [beadsArray exchangeObjectAtIndex:fromPosition withObjectAtIndex:pos];
        }
    }
    return count;
}

Is working with C arrays faster? Let's try it! The translation is now relatively easy:

int calculateNumNecklacesC(int *beads, int numBeads, int fromPosition) {

    if (fromPosition == numBeads ) {
        if (isPrime(beads[0] + beads[numBeads - 1])) {
            return 1;
        } else {
            return 0;
        }
    }

    int count = 0;
    int previousNumber = beads[fromPosition - 1];
    if (isPrime(previousNumber + beads[fromPosition])) {
        count += calculateNumNecklacesC(beads, numBeads, fromPosition + 1);
    }
    for (int pos = fromPosition + 1; pos < numBeads; ++pos) {
        if (isPrime(previousNumber + beads[pos])) {
            swap(beads, fromPosition, pos);
            count += calculateNumNecklacesC(beads, numBeads, fromPosition + 1);
            swap(beads, fromPosition, pos);
        }
    }

    return count;
}

with the utility function

void swap(int *array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
}

Usage:

int beads[numBeads];
for (int i = 0; i < numBeads; ++i) {
    beads[i] = i + 1;
}
count = calculateNumNecklacesC(beads, numBeads, 1);

Computation time: 0.03 s for 16 beads.


There is one more thing ...

This can still be improved by using the mathematical structure of the problem. All primes > 2 are odd, so the sum of two consecutive beads must be odd, i.e. the sum of an even and an odd bead. The bead #1 is fixed at the first position, therefore all beads at odd positions must be odd, and the beads at even positions must be even.

Or, putting it another way, a bead at position p must only be swapped with beads at position p+2, p+4, .... And that is now almost trivial to implement: Just replace the for-loop in calculateNumNecklacesC() by:

for (int pos = fromPosition + 2; pos < numBeads; pos += 2) { ...

Computation time: 0.02 s for 16 beads.

Total performance improvement: 1.5 s/0.02 s = 75 times faster!

\$\endgroup\$
  • \$\begingroup\$ Thank you very much for taking the time to reply! It makes a lot of sense. Doing it with one array is great idea. I really don't have to keep a necklace array going. I can't really use modern objective-c code because codeeval.com doesn't except it. If you don't mind i have a question about the code. Why do you need to do an if(isPrime ... before the for loop. Wouldn't be the same as just letting it go to the loop. Thanks again and have a great day! \$\endgroup\$ – Yan Apr 16 '15 at 21:29
  • \$\begingroup\$ @Yan: OK, I did not know that codeeval.com does not accept modern ObjC (perhaps they use GNUStep or something like that). – The isPrime() before the loop is a minor optimization, alternatively the for-loop could start at int pos = fromPosition instead of pos = fromPosition + 1. Then the first element would be swapped with itself. \$\endgroup\$ – Martin R Apr 16 '15 at 21:34
  • \$\begingroup\$ They use objective-c 2.0. I wonder what's the version objc in the new Xcode. Thanks again! \$\endgroup\$ – Yan Apr 16 '15 at 21:37
3
\$\begingroup\$

DISCLAIMER: I know no , so my answer will not cover any language and style-related recommendations!

First I tried to do it with recursion but that was taking way too long going through all the permutation.

And this exactly is the problem your code has. You first generated all permutations and then checked for their validity. It's unhelpful to do so, because permutations are many and almost all are wrong in your case.

The solution to this is easier when you generate valid permutations.

But let's start with first things first:

$$2\leq N\leq18$$

This tells you two things.

  1. It restricts the maximum prime you can attain through summing any of the 2 \$N\$'s. The maximum number you can obtain by summing any 2 \$N\$'s is: 35. The primes, smaller than 35 are:

    \$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31\$

    This means a few things that you can do to optimize your generation algorithm, but later more.

  2. The longest possible necklace (namely 18 beads)

The first thing you want to do is write these primes to some place, where you can easily check up on them. Probably the best solution would be some kind of static immutable collection or something.

The next thing you need is a way to decide whether two necklaces are "duplicates" or not. It's probably easiest to do with some circular-linked-list structure. Again, I don't know objective-c so, you're on your own.

And then you want to start generating valid necklaces. For that you need two things: What you have up to now, and what choices remain.

Now assuming that what we have until now is valid, there is one condition that makes a necklace a valid finished necklace (that we can store away somewhere), namely that the remaining single candidate sums up to a prime with the last and the first element of the chain we have until now.

This is what is commonly called the "special case" in recursive algorithms. These special cases terminate the current "chain" (either successfully or unsuccessfully). Let's call this special case: isValidFinishedNecklace (my java habits strike again)

The only thing remaining to be done for a finished recursive generation of valid chains is ensuring that the next call gets a valid "until now"-necklace

And then we're already... well finished? In pseudocode this looks as follows:

BEGIN generate_necklace ( until_now, remaining_beads )
  IF isValidFinishedNecklace THEN
    add necklace to some storage
  OTHERWISE
    FOREACH remaining_beads AS candidate
      IF until_now's last bead + candidate is prime THEN
        generate_necklace with until_now + candidate and remaining_beads - candidate
    END
END 

This approach eliminates a lot of extra work by cutting off huge edges from the permutation generation graph, and because of that probably is faster than both of your current solutions

\$\endgroup\$
  • \$\begingroup\$ Thank you very much for your detailed answer! Its a great idea to put the primes in a set so that i don't have to recalculate if it is a prime every time. As far as the duplicate necklaces, I am actually starting all necklaces with 1, that way i won't have any circular duplicates. I think that i am actually using your approach and only recursing when the next bead is found. This way it cuts off and goes back if no more beads is found for the level before it. This way it doesn't make all the permutations. Have a great day! \$\endgroup\$ – Yan Apr 16 '15 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.