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 2Note: The necklace should be unique. For example:
1 2 3 4is the same as2 3 4 1and3 4 1 2and4 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.
