C++

Forum

 
Project Euler #1 Algorithm Question

picksomecardz (5)
Hello everyone,

First time poster here. I recently started learning C++ and have been doing some of the Project Euler problems for practice. I'm currently working on #11 and having some difficulty. The problem gives you a 20x20 grid of numbers and asks you to find the highest product of 4 numbers, either left, right, up, down, or diagonal.

As you see in my code below, instead of using individual arrays, I took the time to practice using a vector array and string manipulation. My current code outputs both the value of my array at [x] and x itself; it seems as though my array and string are set up properly, with each number in the 20x20 grid listed as 0-399.

My code successfully runs, and outputs a few very large products, but not the correct answer. This leads me to believe I have an error in my algorithms computing products. I've been over and over my code and can't figure out where I'm going wrong. Any help would be much appreciated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
 // Problem11.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <locale>
#include <vector>
#include <cstdint>

#define GRID_NUM "Num editted for forum size"
#define bigint uint64_t

int main()
{
	//Make a string for the number
	std::string numString = GRID_NUM;

	//Get rid of spaces, find out how many unique numbers are present
	numString.erase(std::remove(numString.begin(), numString.end(), ' '), numString.end());
	int strLength = numString.length();	
	
	//Create a dynamic array of integers and set each spot to a number in the list
	std::vector<int> numVector(strLength);	
	int arrayCounter = 0;
	for (int iii = 0; iii < numString.length(); iii+=2)
	{
		numVector[arrayCounter] = ((numString.at(iii) - '0') * 10) + (numString.at(iii + 1) - '0');
		arrayCounter++;
	}

	bigint maxLRProduct = 0, maxUDProduct = 0, maxLRDIAProduct = 0, maxRLDIAProduct = 0;

	//Find max product of left-right
	bigint currentProduct = 0;
	int rowCounter = 1;
	for (int iii = 0; iii <= (rowCounter * 16); iii++)
	{
		currentProduct = (numVector[iii] * numVector[iii+1] * numVector[iii+2] * numVector[iii+3]);
		if (currentProduct > maxLRProduct)
		{
			maxLRProduct = currentProduct;
		}
		if (iii == (rowCounter * 16))
		{
			iii+=3;
			rowCounter++;
		}
		if (rowCounter > 20)
		{
			break;
		}
	}

	//Find max product of up-down
	int columnCounter = 1, tempCounter = 0;
	currentProduct = 0;
	for (int iii = 0; columnCounter <= 19; iii+=20)
	{
		currentProduct = (numVector[iii] * numVector[iii+20] * numVector[iii+40] * numVector[iii+60]);
		tempCounter++;
		if (currentProduct > maxUDProduct)
		{
			maxUDProduct = currentProduct;
		}
		if (tempCounter == 16)
		{
			iii = columnCounter;
			columnCounter++;
			tempCounter = 0;
		}
	}

	//Find max product of LR diagonal
	currentProduct = 0, rowCounter = 1;
	for (int iii = 0; iii <= (rowCounter * 16); iii++)
	{
		currentProduct = (numVector[iii] * numVector[iii+21] * numVector[iii+42] * numVector[iii+63]);
		if (currentProduct > maxLRDIAProduct)
		{
			maxLRDIAProduct = currentProduct;
		}
		if (iii == (rowCounter * 16))
		{
			iii+=3;
			rowCounter++;
		}

		if (rowCounter > 16)
		{
			break;
		}
	}

	//Find max product of RL diagonal
	currentProduct = 0, rowCounter = 1;
	for (int iii = 19; iii >= (rowCounter * 3) && rowCounter <= 16; iii--)
	{
		currentProduct = numVector[iii] * numVector[iii+19] * numVector[iii+38] * numVector[iii+57];
		if (currentProduct > maxRLDIAProduct)
		{
			maxRLDIAProduct = currentProduct;
		}
		if (iii == (rowCounter * 3))
		{
			iii+=37;
			rowCounter++;
		}

		if (rowCounter > 16)
		{
			break;
		}
	}

	int counter = 0;

	for (int iii = 0; iii < 400; iii++)
	{
		std::cout << numVector[iii] << "," << iii << " ";
		counter ++;

		if (counter % 20 == 0)
		{
			std::cout << std::endl;
		}
	}

	std::cout << std::endl << maxLRProduct << "\t" << maxUDProduct << "\t" << maxLRDIAProduct <<  "\t" << maxRLDIAProduct << std::endl;

	system("PAUSE");

	return 0;
}
Last edited on
closed account (48T7M4Gy)
It's unreasonable to expect people to review 135 lines of code. If you believe it to be wrong please show us your test data, the expected result and what the program produces at each of the relevant stages.

The first stage would be to see whether the program is producing the correct matrix of numbers.
picksomecardz (5)
Sorry. This is the output of the program. First value is the number I'm storing, then comma, then array number. Bottom numbers are the products of Left-Right , Up-Down, Left-Right Diagonal, and Right-Left Diagonal.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
8,0 2,1 22,2 97,3 38,4 15,5 0,6 40,7 0,8 75,9 4,10 5,11 7,12 78,13 52,14 12,15 50,16 77,17 91,18 8,19 
49,20 49,21 99,22 40,23 17,24 81,25 18,26 57,27 60,28 87,29 17,30 40,31 98,32 43,33 69,34 48,35 4,36 56,37 62,38 0,39 
81,40 49,41 31,42 73,43 55,44 79,45 14,46 29,47 93,48 71,49 40,50 67,51 53,52 88,53 30,54 3,55 49,56 13,57 36,58 65,59 
52,60 70,61 95,62 23,63 4,64 60,65 11,66 42,67 69,68 24,69 68,70 56,71 1,72 32,73 56,74 71,75 37,76 2,77 36,78 91,79 
22,80 31,81 16,82 71,83 51,84 67,85 63,86 89,87 41,88 92,89 36,90 54,91 22,92 40,93 40,94 28,95 66,96 33,97 13,98 80,99 
24,100 47,101 32,102 60,103 99,104 3,105 45,106 2,107 44,108 75,109 33,110 53,111 78,112 36,113 84,114 20,115 35,116 17,117 12,118 50,119 
32,120 98,121 81,122 28,123 64,124 23,125 67,126 10,127 26,128 38,129 40,130 67,131 59,132 54,133 70,134 66,135 18,136 38,137 64,138 70,139 
67,140 26,141 20,142 68,143 2,144 62,145 12,146 20,147 95,148 63,149 94,150 39,151 63,152 8,153 40,154 91,155 66,156 49,157 94,158 21,159 
24,160 55,161 58,162 5,163 66,164 73,165 99,166 26,167 97,168 17,169 78,170 78,171 96,172 83,173 14,174 88,175 34,176 89,177 63,178 72,179 
21,180 36,181 23,182 9,183 75,184 0,185 76,186 44,187 20,188 45,189 35,190 14,191 0,192 61,193 33,194 97,195 34,196 31,197 33,198 95,199 
78,200 17,201 53,202 28,203 22,204 75,205 31,206 67,207 15,208 94,209 3,210 80,211 4,212 62,213 16,214 14,215 9,216 53,217 56,218 92,219 
16,220 39,221 5,222 42,223 96,224 35,225 31,226 47,227 55,228 58,229 88,230 24,231 0,232 17,233 54,234 24,235 36,236 29,237 85,238 57,239 
86,240 56,241 0,242 48,243 35,244 71,245 89,246 7,247 5,248 44,249 44,250 37,251 44,252 60,253 21,254 58,255 51,256 54,257 17,258 58,259 
19,260 80,261 81,262 68,263 5,264 94,265 47,266 69,267 28,268 73,269 92,270 13,271 86,272 52,273 17,274 77,275 4,276 89,277 55,278 40,279 
4,280 52,281 8,282 83,283 97,284 35,285 99,286 16,287 7,288 97,289 57,290 32,291 16,292 26,293 26,294 79,295 33,296 27,297 98,298 66,299 
88,300 36,301 68,302 87,303 57,304 62,305 20,306 72,307 3,308 46,309 33,310 67,311 46,312 55,313 12,314 32,315 63,316 93,317 53,318 69,319 
4,320 42,321 16,322 73,323 38,324 25,325 39,326 11,327 24,328 94,329 72,330 18,331 8,332 46,333 29,334 32,335 40,336 62,337 76,338 36,339 
20,340 69,341 36,342 41,343 72,344 30,345 23,346 88,347 34,348 62,349 99,350 69,351 82,352 67,353 59,354 85,355 74,356 4,357 36,358 16,359 
20,360 73,361 35,362 29,363 78,364 31,365 90,366 1,367 74,368 31,369 49,370 71,371 48,372 86,373 81,374 16,375 23,376 57,377 5,378 54,379 
1,380 70,381 54,382 71,383 83,384 51,385 54,386 69,387 16,388 92,389 33,390 48,391 61,392 43,393 52,394 1,395 89,396 19,397 67,398 48,399 

48477312	51267216	32719995	41076896


Edit : the goal is to find the highest of those 4 products. The answer should be 70600674. My magnitude seems right but the value is off.
Last edited on
closed account (48T7M4Gy)
Well, your first problem is to print out the matrix to look exactly the same as that given in the original problem instead of just a pile of comma delimited 'stuff'.


Forget the rest until you can do that. What it will mean when you do that is that you will have control over addressing each element. This doesn't mean throw out your code - just get to an intermediate and manageable step first!
picksomecardz (5)
I think my output made it seem like something it's not. The output was simply so I could match values with array number, make sure everything was ok on that end. The array I created numArray[] stores only the left hand value above; the comma was put in myself and the right hand value is the number of the array.
closed account (48T7M4Gy)
Try doing it the way I suggest. Your output is no use in debugging because it clouds the issues.

In line 1 of your number array what does "0 2," mean after the first comma? What's the space all about?

[I think you have overcomplicated things by storing the numbers as strings and further compounded this by not just using a simple 2-d array of integers. (long or otherwise) Vectors are OK if you must I but you should 'automate' the 2d indexing :) ]
picksomecardz (5)
I don't think you're understanding what my output is, and I'm not making it very clear. The first number (8) is the value of numArray[0]; this corresponds to the first number on the list. For ease of anyone reading the output, I included a cout of the number of the array. So when you read 8,0, it means numArray[0] = 8. The space is there for legibility. numArray[1] = 2, numArray[2] = 22, etc.

I know I overcomplicated things a bit, and a 2d array would be easier, but I wanted practice with automated string manipulation. If I had done a 2d array, I would have had to go through the entire list of 400 numbers and format it a, b, c, d, ...etc. By using strings, I was able to simply copy-paste a huge block of numbers and work with it.

Edit : it looks like even though I didn't end up using 2d arrays, your suggestion helped. I started thinking about how my code would work if it were constructed in that manner instead, and noticed a couple big, hard to notice math errors. I was running if tests on incorrect values in my loops. It was causing the loops to stop calculating values too early. I fixed it up and got the answer. Code is below for anyone interested. Thanks for the help.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
 
// Problem11.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <locale>
#include <vector>
#include <cstdint>
#include <fstream>

#define GRID_NUM "Number removed for size"
#define bigint uint64_t

int main()
{
	//Make a string for the number
	std::string numString = GRID_NUM;

	//Get rid of spaces, find out how many unique numbers are present
	numString.erase(std::remove(numString.begin(), numString.end(), ' '), numString.end());
	int strLength = numString.length();	
	
	//Create a dynamic array of integers and set each spot to a number in the list
	std::vector<int> numVector(strLength);	
	int arrayCounter = 0;
	for (int iii = 0; iii < numString.length(); iii+=2)
	{
		numVector[arrayCounter] = ((numString.at(iii) - '0') * 10) + (numString.at(iii + 1) - '0');
		arrayCounter++;
	}

	//Some variables for product testing
	bigint maxLRProduct = 0, maxUDProduct = 0, maxLRDIAProduct = 0, maxRLDIAProduct = 0, absMaxProduct = 0;

	//Find max product of left-right
	bigint currentProduct = 0;
	int rowCounter = 1;
	for (int iii = 0; iii <= (rowCounter * 16); iii++)
	{
		currentProduct = (numVector[iii] * numVector[iii+1] * numVector[iii+2] * numVector[iii+3]);
		if (currentProduct > maxLRProduct)
		{
			maxLRProduct = currentProduct;
		}
		if (iii == (16 + ((rowCounter - 1) * 20)))
		{
			iii+=3;
			rowCounter++;
		}
		if (rowCounter >= 20)
		{
			break;
		}
	}
	//See if its the max product
	if (maxLRProduct > absMaxProduct)
	{
		absMaxProduct = maxLRProduct;
	}

	//Find max product of up-down
	int columnCounter = 1, tempCounter = 0;
	currentProduct = 0;
	for (int iii = 0; columnCounter <= 19; iii+=20)
	{
		currentProduct = (numVector[iii] * numVector[iii+20] * numVector[iii+40] * numVector[iii+60]);
		tempCounter++;
		if (currentProduct > maxUDProduct)
		{
			maxUDProduct = currentProduct;
		}
		if (tempCounter == 16)
		{
			iii = columnCounter;
			columnCounter++;
			tempCounter = 0;
		}
	}
	//See if its the max product
	if (maxUDProduct > absMaxProduct)
	{
		absMaxProduct = maxUDProduct;
	}

	//Find max product of LR diagonal
	currentProduct = 0, rowCounter = 1;
	for (int iii = 0; iii <= (rowCounter * 16); iii++)
	{
		currentProduct = (numVector[iii] * numVector[iii+21] * numVector[iii+42] * numVector[iii+63]);
		if (currentProduct > maxLRDIAProduct)
		{
			maxLRDIAProduct = currentProduct;
		}
		if (iii == (16 + ((rowCounter - 1) * 20)))
		{
			iii+=3;
			rowCounter++;
		}

		if (rowCounter > 16)
		{
			break;
		}
	}
	//See if its the max product
	if (maxLRDIAProduct > absMaxProduct)
	{
		absMaxProduct = maxLRDIAProduct;
	}

	//Find max product of RL diagonal
	currentProduct = 0, rowCounter = 1;
	for (int iii = 19; iii >= (rowCounter * 3) && rowCounter <= 16; iii--)
	{
		currentProduct = numVector[iii] * numVector[iii+19] * numVector[iii+38] * numVector[iii+57];
		if (currentProduct > maxRLDIAProduct)
		{
			maxRLDIAProduct = currentProduct;
		}
		if (iii == (((rowCounter - 1) * 20) + 3))
		{
			iii+=37;
			rowCounter++;
		}

		if (rowCounter > 16)
		{
			break;
		}
	}
	//See if its the max product
	if (maxRLDIAProduct > absMaxProduct)
	{
		absMaxProduct = maxRLDIAProduct;
	}	

	std::cout << "The max product is " << absMaxProduct << std::endl;

	system("PAUSE");

	return 0;
}


Last edited on
closed account (48T7M4Gy)
OK. I now see what you are doing with strings and vectors. Very complicated but it's your call of course. Good luck with it.

PS Glad to be of indirect help, especially that you solved it yourself.
Last edited on
Topic archived. No new replies allowed.