1
\$\begingroup\$

I am working through a new challenge on CodeEval.com and I think I am getting a correct result but I can't get through their grader. I am not exactly sure where error is. I didn't post this on stack overflow because I also would like to get your opinion on the code and the algorithm that I came up to solve this.

This is the assignment: Consecutive Primes Challenge

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 <= N <= 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.

    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;
    }


    NSMutableArray *  createEvenNumbersArray(int num)
    {
        NSMutableArray *evenNumArray = [[NSMutableArray alloc]initWithCapacity:num];
        for (int i=2; i<=num; i+=2) {
            [evenNumArray addObject:[NSNumber numberWithInt:i]];
        }
        return evenNumArray;
    }

    NSMutableArray * createOddNumbersArray(int num)
    {
        NSMutableArray *oddNumArray = [[NSMutableArray alloc]initWithCapacity:num];
        for (int i=3; i<=num; i+=2) {
            [oddNumArray addObject:[NSNumber numberWithInt:i]];
        }
        return oddNumArray;
    }



    int calculateConsecutive(int input)
    {
        int count = 0;
        BOOL evenFound = NO;
        BOOL oddFound = NO;
        NSMutableArray *oddNumArray = createOddNumbersArray(input); //creates odd number array with all the possiblities
        NSMutableArray *evenNumArray = createEvenNumbersArray(input); // create even number array with all the possibilities
        NSMutableArray *necklace = [[NSMutableArray alloc]init];
        [necklace addObject:[NSNumber numberWithInt:1]]; // start the necklace with 1 to get rid of duplicate necklaces
        for (int i = 2; i<=input; i+=2) { // goes through all the possibilities for the second bit to create the necklase
            NSMutableArray *tempOddNumArray = [oddNumArray mutableCopy]; // populate odd number array
            NSMutableArray *tempEvenNumArray = [evenNumArray mutableCopy]; // puplate even number array
            if(isPrime([[necklace lastObject] intValue] + i)){
                [tempEvenNumArray removeObject:[NSNumber numberWithInt:i]]; //remove number that we added to the necklase
                [necklace addObject:[NSNumber numberWithInt:i]];
                while ([necklace count]<=input) { // start creating the necklace after two numbers were added
                    oddFound = NO;
                    evenFound = NO;
                    for(NSNumber *oddNumber in tempOddNumArray){ // find the odd number possibility from the numbers that are left in the array
                        if(isPrime([[necklace lastObject] intValue] + oddNumber.intValue)){
                            [necklace addObject:oddNumber];
                            oddFound = YES;
                            break;
                        }
                    }
                    if (!oddFound) {
                        break;
                    }else{
                        [tempOddNumArray removeObject:[necklace lastObject]];
                    }
                    for(NSNumber *evenNumber in tempEvenNumArray){ // find the odd number possibility from the numbers that are left in the array
                        if(isPrime([[necklace lastObject] intValue] + evenNumber.intValue)){
                            [necklace addObject:evenNumber];
                            evenFound = YES;
                            break;
                        }
                    }
                    if (!evenFound) {
                        break;
                    }else{
                        [tempEvenNumArray removeObject:[necklace lastObject]];
                    }
                    if (([tempOddNumArray count] == 0) || ([tempEvenNumArray count] == 0) ){
                        break;
                    }

                }
            }
            if (([necklace count] == input) && (isPrime([[necklace lastObject] intValue]+[[necklace firstObject] intValue]))) {
                // check to make sure that the necklace is full and if the sum of the last number and first number is prime
                count= count + 1;
            }
            NSLog(@"%@",necklace);

            [necklace removeAllObjects];
            [necklace addObject:[NSNumber numberWithInt:1]];
        }
        return count;
    }

    -(void)primesMain
    {
        int necklaceCount = 0;
        int input = 18;
        if (isEven(input)) {
            necklaceCount = calculateConsecutive(input);
        }
        NSLog(@"%d",necklaceCount);
    }

-(void)viewDidLoad
{
     [self primesMain];
}

Here is the revised code with a solution as a new question.

\$\endgroup\$
3
\$\begingroup\$

Unfortunately, I've never handled objective-c code, but your algorithm is pretty convoluted and hard to analyse if you're missing any use-cases. It would be best for you and others if you could split some code fragments into smaller chuncks named appropriatelly.

Also, it might not be accepted as a solution because you don't return 0 if input is not even.

On the algorithm front - the most general solution to this kind of problem is backtracking. This way you don't miss solutions and the steps - incrementation and validation - are clearly visible in a brief inspection. Added benefit is that the code writes as a mirrot to the requirements for the problem. Other small optimizations to your code you could do:

    BOOL isPrime(int number){
        int max = (int)(number/2) + 1;//you skip calculating the division at each iteration
        for(int i = 2; i < max; i++){
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }

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

Not really applicable here, but there more efficient ways to calculate primality

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to CodeReview, Marius Lazin. I hope you enjoy the site. \$\endgroup\$ – Legato Apr 14 '15 at 11:52
  • \$\begingroup\$ Thank you very much for your response. I am going to try to split it up to make it more readable. The version that i submit i do return 0 if not even. I do NSLog on all the possible answers and the chains seem correct. With the smaller number like 2 and 4 the algorithm does give me the right results. I read the backtracking link. As far as i understand i would to create all the possibilities first and then check if they fit the solution? Please let me know if that's correct. Have a good day! \$\endgroup\$ – Yan Apr 14 '15 at 16:31
  • \$\begingroup\$ I updated the answer a little bit. \$\endgroup\$ – Yan Apr 14 '15 at 16:34
  • \$\begingroup\$ Not that much create all posibilities as slowly going through all of them and keeeping only the ones you validate. The first optimisation would be in each iteration to try to add only the odd/even numbers not previously used in the current array. \$\endgroup\$ – Marius Lazin Apr 14 '15 at 20:35
  • \$\begingroup\$ Did not know of 5 minute comment editing limitation... :) Example of the algorithm for N=6, and the array: "1 2 3" the next extension can be only [4 or 6]. We choose 4 => 1 2 3 4 => next we must choose 5(only remaining) which is invalid (4+5=9) so we go back and replace 4 with 6 now we have 1 2 3 6 - also invalid => 1 2 5 => 1 2 5 4 => 1 2 5 6 => 1 2 5 6 3 => 1 4 => ... Check out also courses.cs.washington.edu/courses/cse143/12su/lectures/07-16/12-recursive-backtracking.pdf \$\endgroup\$ – Marius Lazin Apr 14 '15 at 20:49

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.