Project Euler, Problem 17
18 Nov 2010After my success on getting unittest to work on the iPhone, I thought I should try it out some more. It’s been a while since last time I solved an Euler Problem, so maybe this would be a good excuse to solve another one? The last problems involved a lot of math, so this time I found something completely different:
If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 3 5 4 4 = 19 letters used in total. If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
Well, lets see, then…
We would need a class that can convert an integer into written words. I will call it WrittenNumber, and give it a class method (NSString *)fromInt:(int) to do the work.
@interface WrittenNumber : NSObject {
}
(NSString *) fromInt:(int)number;
@end
Now, that I got my basic interface in place, I tried it out with the most basic test:
- (void)testSingleDigitOne {
GHAssertEqualStrings([WrittenNumber fromInt:1], @"one", nil);
}
As expected, it failed :
euler17/testSingleDigitOne ✘ 0.00s
Name: GHTestFailureException
File: /../euler17.m
Line: 40
Reason: '' should be equal to 'one'.
I will not take you through every single step I took, including returning ‘one’, writing a new test and realize that returning ‘one’ didn’t work for other cases and so on… What we need, is to identify every word that we need to build up every number from one to 1000. Up to nineteen, there are all unique words. From there, most written numbers are combined by two or more words. So I put these words into a couple of static arrays:
static NSString * simpleNumbers[] = {
@"", @"one", @"two", @"three", @"four", @"five", @"six", @"seven", @"eight", @"nine",
@"ten", @"eleven", @"twelve", @"thirteen", @"fourteen", @"fifteen", @"sixteen", @"seventeen", @"eighteen", @"nineteen"
};
static NSString *tens[] = {
@"", @"", @"twenty", @"thirty", @"forty", @"fifty", @"sixty", @"seventy", @"eighty", @"ninety"
};
I have padded the ‘tens’-array to make indexing a little easier. tens2 = “twenty”, tens[8] = “eighty” and so on. Now, the algorithm that I ended up with, was to start with the larger part of the number, converting it into text, and then handle the rest in the same way. Peele away the larger part, convert it to text, and repeat.
(NSString *) processSimpleNumbers:(int)number
{
return simpleNumbers[number];
}
(NSString *) processTens:(int)number
{
if (number < 20) {
return [self processSimpleNumbers:number];
}
int div = number / 10;
int rest = number % 10;
NSString *tmp = tens[div];
if (rest > 0){
return [NSString stringWithFormat:@"%@-%@", tmp, [self processSimpleNumbers:rest]];
} else{
return tmp;
}
}
(NSString *) processHundreds:(int)number;
{
if (number < 100) {
return [self processTens:number];
}
int div = number / 100;
int rest = number % 100;
NSString *tmp = [NSString stringWithFormat:@"%@ hundred", simpleNumbers[div]];
if (rest > 0){
return [NSString stringWithFormat:@"%@ and %@", tmp, [self processTens:rest] ];
} else {
return tmp;
}
}
(NSString *) processThousands:(int)number;
{
if (number < 1000){
return [self processHundreds:number];
}
int div = number / 1000;
int rest = number % 1000;
NSString *tmp = [NSString stringWithFormat:@"%@ thousand", [self processHundreds:div]];
if (rest > 0) {
if (rest < 100) {
return [NSString stringWithFormat:@"%@ and %@", tmp, [self processTens:rest]];
} else {
return [NSString stringWithFormat:@"%@ %@", tmp, [self processHundreds:rest]];
}
} else{
return tmp;
}
}
(NSString *) fromInt:(int)number
{
return [self processThousands:number];
}
I’m sure there are prettier ways of solving this, but it works. The remaining task, is trivial. Convert each number and accumulate the length of the strings after removing hyphens and spaces. Of cause, we could get rid of these characters right away by not returning them in the first place, but then again, I did not…
I have uploaded the source to my svn repository if you want to take a look. You’ll find the WrittenNumber class in the iPhone/src folder, and the unittests in the iPhone/tests folder.