Project Euler: Problem 11 - Largest product in a grid using Objective-C

August 14, 2015

Hi guys,

I’m back with a new interesting problem. That is currently, I’m following a website named Project Euler, which contains a lots of pratices for algorithm training with many different levels. And today, I’m gonna pick one of them to solve and present to the wolrd my solution is. Let’s do this.

Largest product in a grid

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

SOLUTION

First, with a very long requirement above, the best solution that I think is saving all in a file, such as .txt file, and call it when we need. With xCode, it’s very easy to do this.

// get string from file.
NSError *error;
NSString *strFileContent = [NSString stringWithContentsOfFile:[[NSBundle mainBundle]
pathForResource: @"Problem11" ofType: @"txt"] encoding:NSUTF8StringEncoding error:&error];

As we can see, I have saved the string in file named Problem11.txt and added it into project. Next step, we need to generate from string of the file into 2 dimentional array.

// seprate string from file into components with \n beetwen
NSArray* lines = [strFileContent componentsSeparatedByString:@"\n"];

NSMutableArray *mainArray = [NSMutableArray array];
for (NSString *eachLine in lines) {
    NSArray *elements = [eachLine componentsSeparatedByString:@" "];

    NSMutableArray *elementsTmp = [NSMutableArray array];
    for (NSString *aNumber in elements) {
        [elementsTmp addObject:[NSNumber numberWithInt:[aNumber intValue]]];
    }

    [mainArray addObject:elementsTmp];
}

And the last, we run our code, I have ran with 4 ways, these are: Vertical, Horizontal, Diagonally - down to the right , Diagonally - down to the left.

int numberOfRows = 20;
int numberOfColumns = 20;

int greatest = 0;

NSMutableArray *resultsArray = [NSMutableArray array];

for (int row = 0; row < numberOfRows; row++) {
	for (int col =0; col < numberOfColumns; col++) {

		if (col < numberOfColumns - 3) {
		// right and left
		greatest = MAX(greatest, [mainArray[row][col] intValue]*[mainArray[row][col+1] intValue]*[mainArray[row][col+2] intValue]*[mainArray[row][col+3] intValue]);
		}

		if (row < numberOfRows - 3) {
		// down and up
		greatest  = MAX(greatest, [mainArray[row][col] intValue]*[mainArray[row+1][col] intValue]*[mainArray[row+2][col] intValue]*[mainArray[row+3][col] intValue]);

		// Diagonally, down to the right
		if (col < numberOfColumns - 3) {
		greatest = MAX(greatest, [mainArray[row][col] intValue]*[mainArray[row+1][col+1] intValue]*[mainArray[row+2][col+2] intValue]*[mainArray[row+3][col+3] intValue]);
		}

		// Diagonally, down to the left
		if (col > 3) {
		greatest = MAX(greatest, [mainArray[row][col] intValue]*[mainArray[row+1][col-1] intValue]*[mainArray[row+2][col-2] intValue]*[mainArray[row+3][col-3] intValue]);
		}
	}

}
	[resultsArray addObject:[NSNumber numberWithInt:greatest]];

}

NSArray *sortedResults = [resultsArray sortedArrayUsingSelector:@selector(compare:)];
NSLog(@"result: %d", [[sortedResults lastObject]  intValue]);

So 70600674 is the final result.

Hope you found interesting in this post, I hope next time, it will be more interested and attractived. If there is anything that you need to add, pleas feel free to send me a mail.

Happy coding.