Project Euler : Objc - 4

E037.m

#import <Foundation/Foundation.h>	

BOOL isPrime(unsigned int num)
{
	if(num<2) return NO;
	if(num==2||num==3||num==5) return YES;
	if(!(num%2&&num%3&&num%5)) return NO;
	int temp=7, sq=(int)sqrt(num);
	while(temp <= sq+1) {
		if(!(num%temp)) return NO;
		temp += 2;
	}
	return YES;
}

unsigned int nextPrime(unsigned int num)
{
	if(num < 2) return 0;
	unsigned int temp=(num%2) ? num + 1 : num + 2;
	while(!isPrime(temp)) {
		temp += 2;
	}
	return temp;
}


BOOL checkNumber(unsigned int i)
{
	BOOL result = YES;
	if(i<10) return NO;
	if(!isPrime(i)) return NO;
	@autoreleasepool {
		NSString *string = [NSString stringWithFormat:@"%i", i];
		NSUInteger l = [string length], i;
		if([string characterAtIndex:l-1] != '3' && [string characterAtIndex:l-1] != '7' ) result = NO;
		if(result) {
			for(i=0;i<l-1;i++) {
				NSString *temp = [string substringWithRange:NSMakeRange(i+1, l-i-1)];
				if(!isPrime([temp intValue])) {
					result = NO;
					break;
				}
			}
		}
		if(result) {
			for(i=0;i<l-1;i++) {
				NSString *temp = [string substringWithRange:NSMakeRange(0, l-i-1)];
				if(!isPrime([temp intValue])) {
					result = NO;
					break;
				}
			}
		}
	}
	return result;
}


int main(int argc, char const *argv[])
{
	@autoreleasepool{
		NSMutableArray *arr = [NSMutableArray array];
		int i=11;
		while([arr count] < 11) {
			if(checkNumber(i)) {
				[arr addObject:@(i)];
				NSLog(@"%i", i);
			}
			i += 2;
		}
		NSLog(@"sum : %@", [arr valueForKeyPath:@"@sum.intValue"]);
	}
	return 0;
}

// 2013-04-29 16:57:49.454 E037[2064] sum : 748317
// [Finished in 0.8s]

E038.m

#import <Foundation/Foundation.h>

BOOL isPandigital(NSString *str)
{
	NSString *m = @"123456789";
	NSMutableArray *chars = [NSMutableArray array];
	int i;
	for(i=0;i<[str length];i++) {
		[chars addObject:[str substringWithRange:NSMakeRange(i,1)]];
	}
	NSSortDescriptor *sd = [[NSSortDescriptor alloc] initWithKey:@"intValue" ascending:YES];
	NSArray *sortedchars = [chars sortedArrayUsingDescriptors:@[sd]];
	[sd release];
	NSString *sortedString = [sortedchars componentsJoinedByString:@""];
	if([sortedString isEqualToString:m]) return YES;
	return NO;
}

unsigned int panMultiply(int num)
{
	int result = 0;
	@autoreleasepool{
		NSMutableString *string = [NSMutableString string];
		[string appendString:[NSString stringWithFormat:@"%i", num]];
		int i = 2;
		while([string length] < 9) {
			[string appendString:[NSString stringWithFormat:@"%i", num*i]];
			i++;
			// NSLog(@"%@", string);
		}
		if([string length] > 9) return 0;
		if(isPandigital(string)) result = [string intValue];
	}
	return result;
}

int main(int argc, char const *argv[])
{
	@autoreleasepool{
		unsigned int max = 0, temp;
		int i=1;
		while(i<9877) {
			temp = panMultiply(i);
				// NSLog(@"%i", temp);
			if(max < temp) {
				max = temp;
			}
			i++;
		}
		NSLog(@"%i", max);
	}
	return 0;
}

// 2013-04-29 17:29:47.156 E038[2944] 932718654

E040.m

#import <Foundation/Foundation.h>

int main(int argc, char const *argv[])
{
	@autoreleasepool{
		NSMutableString *str = [NSMutableString string];
		[str appendString:@"0."];
		int i=1;
		while([str length] < 1000003) {
			[str appendString:[@(i) stringValue]];
			i++;
		}
		int k=1;
		int r = 1;
		while(k<10000000) {
			r = r * ([str characterAtIndex:k+1] - '0');
			k = k * 10;
		}
		NSLog(@"%i", r);
	} 
	return 0;
}

// 2013-04-29 17:41:01.443 E040[4796] 210

E041-2.m

#import <Foundation/Foundation.h>


BOOL isPrime(double num)
{
	if(num < 2) return NO;
	if(num == 2 || num == 3 || num == 5 || num == 7) return YES;
	if(!(fmod(num,2) && fmod(num,3) && fmod(num,5) && fmod(num,7))) return NO;
	double temp = 11;
	double sqrn = sqrt(num);
	while(temp < sqrn) {
		if(fmod(num, temp) == 0) return NO;
		temp+=2;
	}
	return YES;
}

NSString *sortedString(NSString *string)
{
	NSString *result;
	@autoreleasepool{
		NSMutableArray *chArray = [NSMutableArray array];
		NSString *sortedString;
		NSUInteger i;
		for(i=0;i<[string length];i++) {
			[chArray addObject:[string substringWithRange:NSMakeRange(i,1)]];
		}
		NSSortDescriptor *sd = [[NSSortDescriptor alloc] initWithKey:@"description" ascending:YES];
		NSArray *sortedArray = [chArray sortedArrayUsingDescriptors:@[sd]];
		[sd release];
		sortedString = [sortedArray componentsJoinedByString:@""];
		result = [sortedString copy];
	}
	return [result autorelease];
}

BOOL isPanDigit(double num)
{
	BOOL isPanDigit = NO;
	@autoreleasepool{
		NSString *maxPanDigit = @"1234567";
		NSString *numberString = sortedString([NSString stringWithFormat:@"%.f", num]);
		if([[maxPanDigit substringWithRange:NSMakeRange(0, (int)[numberString length])] isEqualToString:numberString]) {
			isPanDigit = YES;
		}
	}
	return isPanDigit;
}


int main(int argc, char const *argv[])
{
	@autoreleasepool{
		double k = 7654321;
		while(k > 100) {
			if(isPanDigit(k)) {
				if(isPrime(k)) break;
			}
			k--;
		}
		NSLog(@"%.f", k);
	}
	return 0;
}

E041.m

// maximun pandigital prime number.
// sum(1~9) = 45 -> no prime.
// sum(1~8) = 36 -> no prime. 
// try only 7 digit pandigital number.

#import <Foundation/Foundation.h>

BOOL isPrime(double num)
{
	if(num < 2) return NO;
	if(num == 2 || num == 3 || num == 5 || num == 7) return YES;
	if(!(fmod(num,2) && fmod(num,3) && fmod(num,5) && fmod(num,7))) return NO;
	double temp = 11;
	double sqrn = sqrt(num);
	while(temp < sqrn) {
		if(fmod(num, temp) == 0) return NO;
		temp+=2;
	}
	return YES;
}

NSMutableArray *lexicalList(NSMutableArray *elements)
{
	NSMutableArray *result = [NSMutableArray array];
	if([elements count] == 1) {
		[result addObject:elements];
		return result;
	}
	@autoreleasepool{
		int i;
		for(i=0;i<[elements count];i++) {
			NSMutableArray *subArray = [elements mutableCopy];
			id anElement = [[subArray objectAtIndex:i] retain];
			[subArray removeObjectAtIndex:i];
			NSMutableArray *subLexicalArray = lexicalList(subArray);
			for(NSMutableArray *base in subLexicalArray) {
				[base insertObject:anElement atIndex:0];
				[result addObject:base];
			}
		}
	}
	return result;
}

int main(int argc, char const *argv[])
{
	@autoreleasepool{
		NSMutableArray *numbers = [[NSMutableArray alloc] initWithArray:@[@7, @6, @5, @4, @3, @2, @1]];
		BOOL found = NO;
		int i;
		for(i=0;i<[numbers count];i++) {
			NSMutableArray *subNumbers =[[[numbers subarrayWithRange:NSMakeRange(i,[numbers count]-i)] mutableCopy] autorelease];
			NSMutableArray *lexicalArray = lexicalList(subNumbers);
			for(id anArray in lexicalArray) {
				double value = [[anArray componentsJoinedByString:@""] doubleValue];
				if(isPrime(value)) {
					NSLog(@"%.f", value);
					found = YES;
					break;
				}
			}
			if(found) break;
		}
		[numbers release];
	}
	return 0;
}

// 2013-04-25 13:41:34.799 E041-2[5040] 7652413
// [Finished in 0.3s]

E042.m

#import <Foundation/Foundation.h>


int valueOfWord(NSString *word)
{
	int result=0;
	int i;
	for(i=1;i<[word length]-1;i++) {
		result += [word characterAtIndex:i] - 'A' + 1;
	}
	return result;
}

int main(int argc, char const *argv[])
{
	@autoreleasepool{
		int count=0;
		NSString *filename = @"words.txt";
		NSFileManager *fileManager = [NSFileManager defaultManager];
		NSString *pathString = [fileManager currentDirectoryPath];
		NSString *filepath = [pathString stringByAppendingPathComponent:filename];
		NSString *rawString = [NSString stringWithContentsOfFile:filepath];
		NSArray *allWordsArray = [rawString componentsSeparatedByString:@","];

		int maxLimit = ([[allWordsArray valueForKeyPath:@"@max.length"] intValue] -2)*26;
		int tv=0, i=1;
		NSMutableArray *triangleNumbers = [NSMutableArray array];
		while(tv <= maxLimit) {
			tv = i * (i+1) / 2;
			[triangleNumbers addObject:@(tv)];
			i++;
		}

		for(NSString *aWord in allWordsArray) {
			if([triangleNumbers containsObject:@(valueOfWord(aWord))]) {
				count ++;
			}
		}

		NSLog(@"%i", count);

	}
	return 0;
}

E043-2.m

#import <Foundation/Foundation.h>

BOOL numberTest(NSString *str)
{
	NSArray *primes = @[@2, @3, @5, @7, @11, @13, @17];
	BOOL result = YES;
		NSUInteger i;
		for(i=0;i<7;i++) {
			@autoreleasepool{
				if([[str substringWithRange:NSMakeRange(i+1, 3)] intValue] % [[primes objectAtIndex:i] intValue] != 0) {
					result = NO;
					break;
				}
			}
		}
	return result;
}

double lexicalTest(NSString *str, NSArray *arr) {
	double result = 0;
	if([arr count] == 1) {
		@autoreleasepool{
			NSString *rString = [str stringByAppendingString:[[arr objectAtIndex:0] stringValue]];
			if(numberTest(rString)) {
				result += [rString doubleValue];
			}
		}
		return result;
	}
		for(id i in arr) {
			@autoreleasepool{
				NSMutableArray *subArr = [arr mutableCopy];
				[subArr removeObject:i];
				NSString *rString = [str stringByAppendingString:[i stringValue]];
				result += lexicalTest(rString, subArr);
				[subArr release];
			}
		}
	return result;
}

int main(int argc, char const *argv[])
{
	@autoreleasepool{
		NSMutableArray *temp = [NSMutableArray arrayWithArray:@[@0, @1, @2, @3, @4, @5, @6, @7, @8, @9]];
		NSString *str = @"";
		double result = lexicalTest(str, temp);
		NSLog(@"%.0f", result);
	}
	return 0;
}

// 2013-04-29 18:49:09.589 E043[2432] 16695334890

E043.m

// 부분열의 규칙
#import <Foundation/Foundation.h>

NSMutableArray *lexicalList(NSMutableArray *arr) {
	NSMutableArray *result = [NSMutableArray array];
	if([arr count] == 1) {
		[result addObject:arr];
		return result;
	}
	@autoreleasepool{
		for(id s in arr) {
			NSMutableArray *subArr = [arr mutableCopy];
			[subArr removeObject:s];
			NSMutableArray *subResult = lexicalList(subArr);
			for(id k in subResult) {
				[k insertObject:s atIndex:0];
				[result addObject:k];
			}
		}
	}
	return result;
}

BOOL numberTest(NSString *str)
{
	NSArray *primes = @[@2, @3, @5, @7, @11, @13, @17];
	BOOL result = YES;
	@autoreleasepool{
		NSUInteger i;
		for(i=0;i<7;i++) {
			if([[str substringWithRange:NSMakeRange(i+1, 3)] intValue] % [[primes objectAtIndex:i] intValue] != 0) {
				result = NO;
				break;
			}
		}
	}
	return result;
}


int main(int argc, char const *argv[])
{
	@autoreleasepool{
		NSMutableArray *temp = [NSMutableArray arrayWithArray:@[@0, @1, @2, @3, @4, @5, @6, @7, @8, @9]];
		NSMutableArray *total = lexicalList(temp);
		NSLog(@"%d", [total count]);
		NSMutableArray *targets = [NSMutableArray array];
		for(id i in total) {
			@autoreleasepool{
				NSString *str = [i componentsJoinedByString:@""];
				if(numberTest(str)) {
					[targets addObject:str];
					NSLog(@"%@", str);
				}
			}
		}
		NSLog(@"%@", [targets valueForKeyPath:@"@sum.doubleValue"]);
	}
	return 0;
}

E044.m

#import <Foundation/Foundation.h>	


BOOL isPent(double k)
{
	double n = (sqrt(24*k + 1) + 1)/6;
	if(n == floor(n)) return YES;
	return NO;
}

double pentNumber(double k)
{
	return k * (3*k -1) / 2;
}

int main(int argc, char const *argv[])
{
	double a, b, pentA, pentB;
	double dist=DBL_MAX, temp_dist;
	double near_dist;
	BOOL complete = NO;
	a = 1;
	pentA = pentNumber(a);
	while(!complete) {
		b = a;
		pentB = pentA;
		a++;
		pentA = pentNumber(a);
		near_dist = pentA - pentB;
		while(b>0) {
			if(isPent(pentA-pentB) && isPent(pentA+pentB)) {
				temp_dist = pentA - pentB;
				dist = (temp_dist < dist) ? temp_dist : dist;
				NSLog(@"%.f : a=%.f, b=%.f", dist, pentA, pentB);
				complete=YES;
				break;
			}
			b--;
			pentB = pentNumber(b);
		}
	}
	return 0;
}

E045.m

 #import <Foundation/Foundation.h>

BOOL isTriNum(double num)
{
	double k = (sqrt(8*num+1)+1)/2;
	if(k == floor(k)) return YES;
	return NO;
}

BOOL isPentNum(double num)
{
	double k = (sqrt(24*num + 1) +1)/6;
	if(k == floor(k)) return YES;
	return NO;
}


double  hexNum(double num)
{
	return (double)num * (2*num - 1);
}

int main(int argc, char const *argv[])
{
	@autoreleasepool{
		double k = 143;
		double p;
		BOOL found = NO;
		while(!found) {
			k++;
			p = hexNum(k);
			if(isPentNum(p)&&isTriNum(p)) found = YES;
		}
		NSLog(@"%.0f", p);
	}
	return 0;
}

// 2013-04-30 01:02:54.431 E045[96054:707] 1533776805
// [Finished in 0.0s]

E41.m

1. 123456789 로 구성된 9자리 팬디지털 숫자는 자리수 합이 45이므로 3의 배수. 따라서 소수가 아니다.
2. 8자리 팬디지털의 경우에도 36이 합으로 소수가 나올 수 없다.
3. 소수가 나올 수 있는 팬디지털 숫자는 7자리부터 생각할 수 있다.
4. 1~7로 구성된 배열을 만들고, 이 배열의 각 원소를 사전순으로 배치하여 팬디지털 숫자를 만든다. (이 편이 경우의 수는 훨씬 적음)
5. 그런다음 만들어진 팬디지털 숫자가 소수인지 검사한다.

사전식 순열 만들기

중복된 원소가 없다는 가정하에, 배열에서 하나씩 원소를 뺀 다음, 남은 숫자들로 사전식 순열을 만든다. 그런 다음 만들어진 각 순열의 숫자에 대해 첫 번째 자리 숫자를 빼두었던 숫자를 붙인다.

위의 과정은 재귀함수를 사용해서 비교적 간단히 구현한다. 이 문제에서는 9개의 숫자에 대해 사전식 순열을 구성하므로, 스택은 최대 9단계까지 늘어나므로 stack overflow가 발생할 염려는 없다.

다만, 모든 사전식 순열의 경우 (7!)을 모두 배열에 저장하여 탐색하므로 메모리는 좀 많이 쓸 수 도 있겠다.

E41-2.m

9자리숫자부터 시작해서 계산해 들어가면 경우의 수가 너무 많아지므로, (홀수만 검토시 4.5억회의 가능성) 일반 계산은 불가능한데, 7자리로 범위를 좁히면 4백5십만 정도의 경우의 수가 있고, 그 중에 역으로 계산하다 소수가 나오는 첫번 째 케이스가 구하고자 하는 답이므로 그냥 무식하게 계산해도 상관 없음.

팬디지털 숫자 검사하기

다음과 같은 방법들을 사용할 수 있음.

1. 숫자를 문자열로 변환한다음, 각 자리 문자가 그 다음자리에 같은 것이 있는지 검사.
2. 전체를 다 검사하여 중복되는 숫자가 없으면 팬디지털임

이렇게 생각할 수 있는데 만약 8자리나 7자리 인 경우에는 1345678도 위의 로직을 통과하게 된다. 따라서 다음의 로직으로 변경

1. 문자열로 변환하고 각 글자를 정렬
2. @"123456789"에서 문자열의 길이만큼 잘라 비교.

문자열 정렬하기

문자열을 정렬하는 방법으로 처음에는 NSMutableArray에 한글자 씩 잘라 붙여 넣고 이를 정렬한 다음, 이를 다시 NSMuatbleString에 하나씩 붙여넣는 방법을 사용했는데 배열과 문자열은 components... 메소드를 통해 상호 변환이 가능하다.

-componentsSeparatedByString:@"" // --> String --> Arary
-componentsJoinedByString:@"" // ==> Array --> String

정렬은 파운데이션의 경우 sortedArrayUsingComparator:를 사용하면 코드블럭을 통해 깔끔하게 처리할 수 있는데, GNUStep은 이 메소드가 sortedArrayUsingFunction:context:로 다소 다르다. 아마 gcc가 코드 블럭 문법을 아직 처리하지 못해서 함수 포인터를 사용하고 있는 듯. 대신에 정렬 디스크립터를 사용하는 방법은 두 플랫폼 모두에서 정상적으로 컴파일됨.

E042.m

텍스트 파일 내의 이름의 단어값이 삼각수가 되는 경우가 몇 개인지 찾기

삼각수는 1~N까지의 합이 되는 수로 N*(N+1)/2로 구할 수 있다. 매 단어 값에 대해 이 값을 비교하기 보다는 미리 배열에 만들어놓고 비교하는게 나을 것 같아서 그렇게 처리했다. 단어값의 최대 치는 '가장 긴단어가 ZZZZ... 로 된 경우' 이니 단어 길이의 최대값 * 26으로 최대치가 구해진다.

• NSFileManager를 통해 현재 디렉토리의 words.txt 파일을 찾고
• 이 파일을 읽어서 NSString으로 만든다.
• 이 문자열을 컴마를 기준으로 쪼개서 배열을 만든 다음,
• 배열의 각 원소는 따옴표로 둘러져 있으므로 substring으로 빼와서 단어 값 계산.
• 계산한 단어 값이 미리 생성한 삼각수 배열에 들어 있는지 확인하여 있으면 체크.

단어의 최대 길이 구하기

일일이 루프를 돌지 않고 collection의 KVC 연산자 @max를 사용한다. [배열 valueForKeyPath:@"@max.length"]는 각 원소의 길이가 가장 긴 값을 NSNumber로 돌려준다. (물론 내부적으로는 루프를 돌면서 탐색하겠지만)

배열에 이 값이 있는지 검사하기

-containsObject:를 사용하면 된다. 이 메서드는 배열내의 원소와 주어진 객체의 포인터를 비교하는 것이 아니라, 그 두 객체의 내용이 서로 같은지 (-isEqualTo:를 사용함) 비교한다. 만약 어떤 비교 연산에서 "obj1 == obj2"로 비교하는 것은 두 변수가 가리키는 포인터가 같은 것인지를 비교하는데, 이는 동일한 한 개 객체를 가리키는 두 포인터가 있을 때만 참인 것이며, [obj1 isEqualTo:obj2]는 두 객체의 값이 서로 같으면 참으로 간주하게 된다.