Project Euler : Objc - 2

E013.m

// 큰 수 더하기
// 앞의 10자리를 구할 것
#import <Foundation/Foundation.h>

const char *values[] = {"37107287533902102798797998220837590246510135740250",
"46376937677490009712648124896970078050417018260538",
"74324986199524741059474233309513058123726617309629",
"91942213363574161572522430563301811072406154908250",
"23067588207539346171171980310421047513778063246676",
"89261670696623633820136378418383684178734361726757",
"28112879812849979408065481931592621691275889832738",
"44274228917432520321923589422876796487670272189318",
"47451445736001306439091167216856844588711603153276",
"70386486105843025439939619828917593665686757934951",
"62176457141856560629502157223196586755079324193331",
"64906352462741904929101432445813822663347944758178",
"92575867718337217661963751590579239728245598838407",
"58203565325359399008402633568948830189458628227828",
"80181199384826282014278194139940567587151170094390",
"35398664372827112653829987240784473053190104293586",
"86515506006295864861532075273371959191420517255829",
"71693888707715466499115593487603532921714970056938",
"54370070576826684624621495650076471787294438377604",
"53282654108756828443191190634694037855217779295145",
"36123272525000296071075082563815656710885258350721",
"45876576172410976447339110607218265236877223636045",
"17423706905851860660448207621209813287860733969412",
"81142660418086830619328460811191061556940512689692",
"51934325451728388641918047049293215058642563049483",
"62467221648435076201727918039944693004732956340691",
"15732444386908125794514089057706229429197107928209",
"55037687525678773091862540744969844508330393682126",
"18336384825330154686196124348767681297534375946515",
"80386287592878490201521685554828717201219257766954",
"78182833757993103614740356856449095527097864797581",
"16726320100436897842553539920931837441497806860984",
"48403098129077791799088218795327364475675590848030",
"87086987551392711854517078544161852424320693150332",
"59959406895756536782107074926966537676326235447210",
"69793950679652694742597709739166693763042633987085",
"41052684708299085211399427365734116182760315001271",
"65378607361501080857009149939512557028198746004375",
"35829035317434717326932123578154982629742552737307",
"94953759765105305946966067683156574377167401875275",
"88902802571733229619176668713819931811048770190271",
"25267680276078003013678680992525463401061632866526",
"36270218540497705585629946580636237993140746255962",
"24074486908231174977792365466257246923322810917141",
"91430288197103288597806669760892938638285025333403",
"34413065578016127815921815005561868836468420090470",
"23053081172816430487623791969842487255036638784583",
"11487696932154902810424020138335124462181441773470",
"63783299490636259666498587618221225225512486764533",
"67720186971698544312419572409913959008952310058822",
"95548255300263520781532296796249481641953868218774",
"76085327132285723110424803456124867697064507995236",
"37774242535411291684276865538926205024910326572967",
"23701913275725675285653248258265463092207058596522",
"29798860272258331913126375147341994889534765745501",
"18495701454879288984856827726077713721403798879715",
"38298203783031473527721580348144513491373226651381",
"34829543829199918180278916522431027392251122869539",
"40957953066405232632538044100059654939159879593635",
"29746152185502371307642255121183693803580388584903",
"41698116222072977186158236678424689157993532961922",
"62467957194401269043877107275048102390895523597457",
"23189706772547915061505504953922979530901129967519",
"86188088225875314529584099251203829009407770775672",
"11306739708304724483816533873502340845647058077308",
"82959174767140363198008187129011875491310547126581",
"97623331044818386269515456334926366572897563400500",
"42846280183517070527831839425882145521227251250327",
"55121603546981200581762165212827652751691296897789",
"32238195734329339946437501907836945765883352399886",
"75506164965184775180738168837861091527357929701337",
"62177842752192623401942399639168044983993173312731",
"32924185707147349566916674687634660915035914677504",
"99518671430235219628894890102423325116913619626622",
"73267460800591547471830798392868535206946944540724",
"76841822524674417161514036427982273348055556214818",
"97142617910342598647204516893989422179826088076852",
"87783646182799346313767754307809363333018982642090",
"10848802521674670883215120185883543223812876952786",
"71329612474782464538636993009049310363619763878039",
"62184073572399794223406235393808339651327408011116",
"66627891981488087797941876876144230030984490851411",
"60661826293682836764744779239180335110989069790714",
"85786944089552990653640447425576083659976645795096",
"66024396409905389607120198219976047599490197230297",
"64913982680032973156037120041377903785566085089252",
"16730939319872750275468906903707539413042652315011",
"94809377245048795150954100921645863754710598436791",
"78639167021187492431995700641917969777599028300699",
"15368713711936614952811305876380278410754449733078",
"40789923115535562561142322423255033685442488917353",
"44889911501440648020369068063960672322193204149535",
"41503128880339536053299340368006977710650566631954",
"81234880673210146739058568557934581403627822703280",
"82616570773948327592232845941706525094512325230608",
"22918802058777319719839450180888072429661980811197",
"77158542502016545090413245809786882778948721859617",
"72107838435069186155435662884062257473692284509516",
"20849603980134001723930671666823555245252804609722",
"53503534226472524250874054075591789781264330331690"};

NSArray *arrayWithValue() 
{
	NSArray *result;
	@autoreleasepool {

		NSMutableArray *rows = [[NSMutableArray alloc] init];
		int i;
		for(i=0;i<sizeof(values)/sizeof(char*);i++) {
			NSString *aRow = [NSString stringWithUTF8String:values[i]];
			[rows addObject:aRow];
		}
		result = [rows copy];
		[rows release];
	}
	return [result autorelease];
}

NSString* rjust(NSString *str, NSUInteger length)
{
	NSString *newStr = @"";
	int i;
	for(i=0;i<(length - [str length]);i++) {
		newStr = [newStr stringByAppendingString:@"0"];
	}
	newStr = [newStr stringByAppendingString:str];
	return newStr;
}


NSString* stringWithReversedArray(NSArray* reversedArray)
{
	NSString *string;
	@autoreleasepool {
		int i;
		NSString *temp = @"";
		for(id num in reversedArray) {
			temp = [NSString stringWithFormat:@"%i%@", [num intValue], temp];
		}
		string = [temp copy];
	}
	return [string autorelease];
}

NSString* ltrim(NSString *string, unichar ch)
{
	int i=0;
	while(ch == [string characterAtIndex:i]) {
		i++;
	}
	return [string substringFromIndex:i];
}


NSString* addStringValue(NSString *str1, NSString *str2)
{
	NSUInteger len = ([str1 length] > [str2 length]) ? [str1 length] + 1 : [str2 length] + 1;
	NSString *v1 = rjust(str1, len);
	NSString *v2 = rjust(str2, len);
	NSMutableArray *reversedAnswer = [NSMutableArray array];
	int c1, c2, sum;
	int temp=0,i;
	for(i=len;i>0;i--) {
		c1 = (int)[v1 characterAtIndex:i-1] - 48;
		c2 = (int)[v2 characterAtIndex:i-1] - 48;
		sum = c1 + c2 + temp;
		if(sum > 9) {
			temp = 1;
			sum = sum - 10;
		} else {
			temp = 0;
		}
		[reversedAnswer addObject:@(sum)];
	}
	return ltrim(stringWithReversedArray(reversedAnswer),'0');
}

int main(int argc, char const *argv[])
{
	@autoreleasepool {
		NSArray *numbers = arrayWithValue();
		NSString *sum = @"0";
		for(NSString *row in numbers) {
			sum = addStringValue(sum, row);
		}
		NSLog(@"%@", [sum substringWithRange:NSMakeRange(0,10)]);
	}
	return 0;
}

// 2013-04-19 14:43:02.984 E013[9828] 5537376230
// [Finished in 0.4s]

E014.m

#import <Foundation/Foundation.h>
// N is even : --> N/2
// N is odd : --> 3N + 1

NSUInteger travel(double num)
{
	NSUInteger hit = 0;
	while(num != 1) {
		if(fmod(num, 2)){
			num = 3* num + 1;
			hit ++;
		}
		num = num / 2;
		hit++;
	}
	return hit;
}

int main(int argc, char const *argv[])
{
	double num = 1000000;
	int maxhit = 0, hit, longtravelingNumber;
	while(num > 1) {
		hit = travel(num);
		if(maxhit < hit) {
			maxhit = hit;
			longtravelingNumber = num;
		}
		num--;
	}
	NSLog(@"%d by %d", maxhit, longtravelingNumber);
	return 0;
}

// 2013-04-19 15:35:25.268 E014[8728] 524 by 837799
// [Finished in 4.7s]

E015.m

#import <Foundation/Foundation.h>

int main(int argc, char const *argv[])
{
	@autoreleasepool {
		double grid[20][20];
		int i,j;
		for(i=0;i<20;i++) grid[0][i] = 1;
		for(i=1;i<20;i++) {
			for(j=0;j<20;j++) {
				if(j==0) grid[i][j] = 1;
				else {
					grid[i][j] = grid[i-1][j] + grid[i][j-1];
				}
			}
		}

		NSLog(@"%.0f", grid[19][19]);
	}
	return 0;
}

// 2013-04-20 00:07:54.642 E015[87512:707] 35345263800
// [Finished in 0.0s]

E015.py

#python 2.7
import math
print "%.0f" % (math.factorial(40) / math.factorial(20)**2)
# 137846528820
# [Finished in 0.5s]

E016.m

#import <Foundation/Foundation.h>

NSString *stringWithReversedArray(NSArray *reversedArray);
NSString *ltrim(NSString *str, unichar ch);
NSString *rjust(NSString *str, NSUInteger length, unichar ch);
NSString *addStrings(NSString *str1, NSString *str2);

NSString *rjust(NSString *str, NSUInteger length, unichar ch)
{
	unichar *prefix = (unichar *)malloc((length - [str length]+1) * sizeof(unichar));
	NSUInteger i=0;
	while(i<(length - [str length])) {
		*(prefix+i) = ch;
		i++;
	}
	*(prefix+i) = 0;
	NSString *nsPrefix = [NSString stringWithCharacters:prefix length:(length - [str length])];
	NSString *result = [NSString stringWithFormat:@"%@%@", nsPrefix, str];
	free(prefix);
	return result;
}

NSString *ltrim(NSString *str, unichar ch)
{
	NSUInteger i = 0;
	while(i < [str length] && [str characterAtIndex:i] == ch ) i++;
	return [str substringFromIndex:i];
}

NSString *stringWithReversedArray(NSArray *reversedArray)
{
	NSUInteger i;
	unichar *string = (unichar *)calloc([reversedArray count] , sizeof(unichar));
	for(i=0;i<[reversedArray count];i++) {
		*(string+i) = (unichar)([[reversedArray objectAtIndex:([reversedArray count]-i-1)] charValue] + 48);
	}
	// printf("%s\n", string);
	NSString *result = [NSString stringWithCharacters:string length:[reversedArray count]];
	free(string);
	return result;
}


NSString *addStrings(NSString *str1, NSString *str2)
{
	NSUInteger len = ([str1 length] > [str2 length]) ? [str1 length]+1 : [str2 length]+1;
	NSString *v1 = rjust(str1, len, '0');
	NSString *v2 = rjust(str2, len, '0');
	NSMutableArray *reversed = [NSMutableArray array];
	int i;
	int a,b,k=0,temp;;
	for(i=len;i>0;i--) {
		a = [v1 characterAtIndex:i-1] - 48;
		b = [v2 characterAtIndex:i-1] - 48;
		temp = a+b+k;
		if(temp > 9) {
			k = 1;
			temp = temp - 10;
		}else{
			k=0;
		}
		[reversed addObject:@(temp)];
	}
	return ltrim(stringWithReversedArray(reversed), '0');
}


int main(int argc, char const *argv[])
{
	@autoreleasepool {
		int i;
		NSString *s = @"1";
		for(i=0;i<1000;i++) {
			s = addStrings(s,s);
		}

		double sum=0;
		for(i=0;i<[s length];i++) {
			sum += [s characterAtIndex:i] - 48;
		}
		NSLog(@"%.0f", sum);
	}
	return 0;
}

// 2013-04-20 00:19:04.946 E016[87590:707] 1366
// [Finished in 0.0s]

E017.m

#import <Foundation/Foundation.h>

NSString* wordsForNumber (NSUInteger number)
{
	NSString *result;
	@autoreleasepool {
		NSMutableString *string = [NSMutableString string];
		NSDictionary *words = @{@1:@"one", @2:@"two", @3:@"three", @4:@"four", @5:@"five", @6:@"six", @7:@"seven", @8:@"eight", @9:@"nine", @10:@"ten", @11:@"eleven", @12:@"twelve", @13:@"thirteen", @14:@"fourteen", @15:@"fifteen", @16:@"sixteen", @17:@"seventeen", @18:@"eighteen", @19:@"nineteen", @20:@"twenty", @30:@"thirty", @40:@"forty", @50:@"fifty", @60:@"sixty", @70:@"seventy", @80:@"eighty", @90:@"ninety", @100:@"hundred", @1000:@"thousand"};
		NSUInteger count;
		NSUInteger level = 1000;
		while(number) {
			if(number >= level) {
				if(number < 20) {
					[string appendString:[words objectForKey:@(number)]];
					number = 0;
				} else {
					if(level == 10) {
						count = (number / level) * 10;
						number = number % 10;
					} else {count = number / level; }
					[string appendString:[words objectForKey:@(count)]];
					if(level != 10) [string appendString:[words objectForKey:@(level)]];
					if(level == 100 && number % 100) { [string appendString:@"and"]; }
					number = number % level;
				}
			}
			level = level / 10;
		}
		result = [string copy];
	}
	return [result autorelease];
}



int main(int argc, char const *argv[])
{
	@autoreleasepool {
		NSUInteger i, len=0;
		for(i=1;i<1001;i++) {len += [wordsForNumber(i) length]; }
		NSLog(@"%d", len);
	}
	return 0;
}

// 2013-04-24 23:53:41.535 E017[14220] 21124
// [Finished in 0.2s]

E019.m

// Project Euler 19
// Firtst day of a month 
// Compiled on ARC. 
// !!! GNUSTEP's buggy NSCalendar can't make correct date, so this file doesn't work with GNUSTEP.
#import <Foundation/Foundation.h>

int main(int argc, char const *argv[])
{
	@autoreleasepool {
		NSCalendar *g = [[NSCalendar alloc] initWithCalendarIdentifier:NSGregorianCalendar];
		NSUInteger count = 0;
		NSDateComponents *comps = [[NSDateComponents alloc] init];
		NSDateComponents *weekdayComps;
		NSUInteger year, month;
		for(year=1901;year<2001;year++) {
			month=1;
			while(month < 13) {
				comps.year = year;
				comps.month = month;
				comps.day = 1;
				NSDate *oneDay = [g dateFromComponents:comps];
				weekdayComps = [g components:(NSWeekdayCalendarUnit) fromDate:oneDay];
				if(weekdayComps.weekday == 1) count++;
				month++;
			}
		}
		NSLog(@"%ld", count);
	}
	return 0;
}

E020.m

#import <Foundation/Foundation.h>

NSString *mutipliyStrings(NSString *str1, NSString *str2);
NSString *stringWithReversedArray(NSArray *reversedArray);
NSString *ltrim(NSString *str, unichar ch);
NSString *rjust(NSString *str, NSUInteger length, unichar ch);
NSString *addStrings(NSString *str1, NSString *str2);
NSString *factorial(NSString *str);

NSString *rjust(NSString *str, NSUInteger length, unichar ch)
{
	unichar *prefix = (unichar *)malloc((length - [str length] + 1) * sizeof(unichar));
	NSUInteger i=0;
	while(i<(length - [str length])) {
		*(prefix+i) = ch;
		i++;
	}
	*(prefix+i) = 0;
	NSString *result = [[NSString stringWithCharacters:prefix length:(length - [str length])] stringByAppendingString:str];
	free(prefix);
	return result;
}

NSString *ltrim(NSString *str, unichar ch)
{
	NSUInteger i = 0;
	while(i < [str length] && [str characterAtIndex:i] == ch ) i++;
	return [str substringFromIndex:i];
}

NSString *stringWithReversedArray(NSArray *reversedArray)
{
	NSUInteger i;
	unichar *string = (unichar *)calloc([reversedArray count] , sizeof(unichar));
	for(i=0;i<[reversedArray count];i++) {
		*(string+i) = (unichar)([[reversedArray objectAtIndex:([reversedArray count]-i-1)] charValue] + 48);
	}
	// printf("%s\n", string);
	NSString *result = [NSString stringWithCharacters:string length:[reversedArray count]];
	free(string);
	return result;
}


NSString *addStrings(NSString *str1, NSString *str2)
{
	NSUInteger len = ([str1 length] > [str2 length]) ? [str1 length]+1 : [str2 length]+1;
	NSString *v1 = rjust(str1, len, '0');
	NSString *v2 = rjust(str2, len, '0');
	NSMutableArray *reversed = [NSMutableArray array];
	int i;
	int a,b,k=0,temp;;
	for(i=len;i>0;i--) {
		a = [v1 characterAtIndex:i-1] - 48;
		b = [v2 characterAtIndex:i-1] - 48;
		temp = a+b+k;
		if(temp > 9) {
			k = 1;
			temp = temp - 10;
		}else{
			k=0;
		}
		[reversed addObject:@(temp)];
	}
	return ltrim(stringWithReversedArray(reversed), '0');
}

NSString *mutipliyStrings(NSString *str1, NSString *str2)
{
	NSMutableArray *rows = [NSMutableArray array];
	NSMutableArray *reversedRow = [NSMutableArray array];
	NSUInteger rowIndex, colIndex;
	int a,b,c,temp=0;
	for(rowIndex=[str1 length];rowIndex > 0;rowIndex--) {
		[reversedRow removeAllObjects];
		int k;
		for(k=0;k<[str1 length]-rowIndex;k++) {
			[reversedRow addObject:@(0)];
		}
		a = [str1 characterAtIndex:rowIndex-1] - 48;
		for(colIndex=[str2 length];colIndex>0;colIndex--) {
			b = [str2 characterAtIndex:colIndex-1] - 48;
			c = a*b+temp;
			if(c > 9) {
				temp = (c / 10);
				c = c - temp*10;
			} else {
				temp = 0;
			}
			[reversedRow addObject:@(c)];
		}
		if(temp) {
			if(temp > 0) {
				[reversedRow addObject:@(temp)];
				temp = 0;
			}
		}
		[rows addObject:ltrim(stringWithReversedArray(reversedRow),'0')];
	}
	NSString *allSum = @"0";
	for(NSString *row in rows) {
		allSum = addStrings(row, allSum);
	}
	[rows removeAllObjects];
	return allSum;
}

NSString *factorial(NSString *str)
{
	NSUInteger k = [str integerValue];
	NSString *f = @"1";
	while(k>1) {
			NSString *kstring = [NSString stringWithFormat:@"%ld", k];
			f = mutipliyStrings(f, kstring);
			k--;	
	}
	return f;
}



int main(int argc, char const *argv[])
{
	@autoreleasepool {
		NSString *f100 = factorial(@"100");
		int sum = 0, i;
		for(i=0;i<[f100 length];i++) {
			sum += [f100 characterAtIndex:i] - 48;
		}
		NSLog(@"%d", sum);
		//93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
	}
	return 0;
}

// 2013-04-20 01:49:00.603 E020[18774:707] 648
// [Finished in 0.3s]

E023.m

#import <Foundation/Foundation.h>


BOOL isPrime(int num)
{
	if(num == 1) return NO;
	if( num==2 || num==3 || num==5 || num==7 || num==11 || num==13 || num==17 || num==19) return YES;
	if(!(num % 2 && num % 3 && num % 5 && num % 7 && num % 11 && num % 13 && num % 17 && num % 19)) return NO;
	NSUInteger temp = 23;
	double sqrn = sqrt(num);
	while(temp <= sqrn) {
		if(num % temp == 0) return NO;
		temp += 2;
	}
	return YES;
}

int nextPrime(int num)
{
	int n = (num % 2) ? num+2 : num+1;
	while(!isPrime(n)) {
		n += 2;
	}
	return n;
}

int sumOfFactors(int num)
{
	int u = 2;
	int primes[100];
	int idx=0, count;
	int sum = 1;
	while(num != 1) {
		if(num % u == 0) {
			primes[idx] = u;
			idx++;
			num = num / u;
		} else {
			u = nextPrime(u);
		}

	}
	count = idx;
	idx = 0;
	int temp=2, s=0;
	int psum = 1;
	while(idx < count) {
		if(temp == primes[idx]) {
			s++;
			psum += (int)pow(primes[idx], s);
			idx++;
		} else {
			temp = primes[idx];
			sum *= psum;
			psum = 1;
			s = 0;
		}
	}
	sum *= psum;
	return sum;
}

BOOL isAbundant(int num)
{
	if (num * 2 < sumOfFactors(num)) return YES;
	else return NO;
}

int main(int argc, char const *argv[])
{
	double sum = 0;
	int limit = 28123;
	int *arr = (int*)malloc(sizeof(int)*5000);
	int *two = (int*)malloc(sizeof(int)*9000000);
	int temp = limit;
	int index = 0;
	int count;
	int i,j;
	int searchindex = 0;
	BOOL shouldAdd = NO;
	while(temp>11) {
		if(isAbundant(temp)) {
			arr[index] = temp;
			index++;
		}
		temp--;
	}
	count = 0;
	for(i=12;i<index;i++) {
		for(j=12;j<index;j++) {
			if(arr[i]+arr[j] <= limit) {
				searchindex = 0;
				while(searchindex < count) {
					if(two[searchindex] == arr[i]+arr[j]) {
						shouldAdd = NO;
						break;
					}
				}
				if(shouldAdd) {
					two[count] = arr[i] + arr[j];
					count++;
				}
			}
		}
	}
	NSLog(@"%d", index);
	for(i=0;i<count;i++) {
		sum += two[i];
	}
	NSLog(@"%.f", sum);
	return 0;
}

E013.m

50개의 50자리 수 덧셈

C의 타입으로는 인식할 수 없는 큰 수이기 때문에 문자열로 보고, 수작업으로 계산하는 것과 동일한 방법을 사용합니다.

자리수를 맞추고 맨 앞에 0을 하나 붙입니다. (혹시 올림되어 한 자리 올라갈 수 있으니)
뒤에서부터 각 자리 숫자를 char 값으로 바꾸어 더합니다. 더한 값이 9보다 크면 1을 올림합니다. 이렇게 구한 각 자리 값은 배열에 넣습니다.

배열을 뒤집어서 문자열로 만들어주는 함수를 추가했고, 끝으로 맨 왼쪽에 0이 붙어있는 경우에 이를 제거하는 함수를 하나 만들었습니다. 이렇게 해서 긴 문자열로 된 숫자 (소수점은 고려하지 않음)를 더할 수 있게 됩니다.

E014.m

100만 이하의 우박수 중 1까지 가장 긴 경로를 거치는 숫자.

충분히 긴 경로를 거친 숫자에 대해서는 그 수와 경로를 저장해두면, 이 숫자가 중간에 등장할 때 바로 써먹을 수 있습니다. 그렇지만, 이 방법은 꽤 많은 메모리를 사용할 수도 있어서....

그냥 일일이 찾도록 했습니다. 짝수일 때 2로 나누면 다음수는 짝수일지 홀수 일지 모르지만, 홀수의 다음수는 항상 짝수가 되므로 홀수인지를 먼저 검사하면 루프 횟수를 줄일 수 있습니다. (2초 가량 단축됩니다.)

E015.py

20X20 격자를 오른쪽 대각선 방향으로 건너가는 경우의 수

가로20개, 세로 20개 총 40개의 루트를 거쳐가는데,
가로길과 세로길 끼리의 순서는 정해져 있으므로
40! / (20! * 20!) 을 계산하면 되므로 파이썬에서는 아주 간단히 구할 수 있어요. (파이썬은 큰 수를 지원합니다.)

E015.m

20X20 격자를 건너는 경우의 수

역시나 계산 방법은 같은데, 큰 수의 나눗셈은 엄두가 안나서 배열에 넣고 약분해가는 식으로 처리하면
간신히(?) double 형 타입에 담을 수 있는 수로 계산됩니다.

다른 풀이

가로방향의 점마다 1을 지정하고
세로방향의 점마다 1을 지정합니다.
만나는 지점은 출발한 두 점의 값을 더합니다.
이런식으로 20X20배열을 채워나가면...구할 수 있습니다.

... 이 풀이는 초등학생들 수학책에 나오는데. 코드가 훨씬 간단하네요 ㅠㅠ.