-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathprojectEuler011.cpp
More file actions
159 lines (132 loc) · 6.01 KB
/
Copy pathprojectEuler011.cpp
File metadata and controls
159 lines (132 loc) · 6.01 KB
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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/* Problem 11
Largest Product in a Grid
In the 20×20 grid below, four numbers along a diagonal line have been
marked with underscores.
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?
*/
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <string>
using namespace std;
int main () {
string sGrid =
"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 00 00 00"
"49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 00 00 00"
"81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 00 00 00"
"52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 00 00 00"
"22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 00 00 00"
"24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 00 00 00"
"32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 00 00 00"
"67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 00 00 00"
"24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 00 00 00"
"21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 00 00 00"
"78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 00 00 00"
"16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 00 00 00"
"86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 00 00 00"
"19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 00 00 00"
"04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 00 00 00"
"88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 00 00 00"
"04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 00 00 00"
"20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 00 00 00"
"20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 00 00 00"
"01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 00 00 00"
"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00"
"00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00";
double largestProduct = 0;
// Remove whitespace
sGrid.erase(remove_if(sGrid.begin(), sGrid.end(), isspace), sGrid.end());
int rowModulus = 23;
double dGrid [23][23] = { };
// Each "row" should have a length of 46: 20 2-digit numbers and 3 00.
for (int row = 0; row < rowModulus; row++) {
for (int col = 0; col < rowModulus; col++) {
int tensPlace = (sGrid [0] - 48) * 10;
int onesPlace = sGrid [1] - 48;
int gridCell = tensPlace + onesPlace;
dGrid [row][col] = double(gridCell);
sGrid.erase (sGrid.begin (), sGrid.begin () + 2);
}
}
// cout << dGrid [0][0] << endl << dGrid [0][1] << endl << dGrid [0][2] << endl << dGrid [0][3] << endl;
// Check sequences in the right direction.
for (int chunkRow = 0; chunkRow < rowModulus - 3; chunkRow++) {
for (int chunkCol = 0; chunkCol < rowModulus - 3; chunkCol++) {
double rightDirSeq =
dGrid [chunkRow] [chunkCol + 0] *
dGrid [chunkRow] [chunkCol + 1] *
dGrid [chunkRow] [chunkCol + 2] *
dGrid [chunkRow] [chunkCol + 3];
// if ((chunkRow == chunkCol) && chunkRow == 0) {
// cout << rightDirSeq << endl;
// }
if (rightDirSeq > largestProduct) {
largestProduct = rightDirSeq;
}
}
}
// Check sequences in the down direction.
for (int chunkRow = 0; chunkRow < rowModulus - 3; chunkRow++) {
for (int chunkCol = 0; chunkCol < rowModulus - 3; chunkCol++) {
double downDirSeq =
dGrid [chunkRow + 0] [chunkCol] *
dGrid [chunkRow + 1] [chunkCol] *
dGrid [chunkRow + 2] [chunkCol] *
dGrid [chunkRow + 3] [chunkCol];
if (downDirSeq > largestProduct) {
largestProduct = downDirSeq;
}
}
}
// Check sequences in the diagonalUp direction.
for (int chunkRow = 0; chunkRow < rowModulus - 3; chunkRow++) {
for (int chunkCol = 0; chunkCol < rowModulus - 3; chunkCol++) {
double diagUpDirSeq =
dGrid [chunkRow + 0] [chunkCol + 3] *
dGrid [chunkRow + 1] [chunkCol + 2] *
dGrid [chunkRow + 2] [chunkCol + 1] *
dGrid [chunkRow + 3] [chunkCol + 0];
if (diagUpDirSeq > largestProduct) {
largestProduct = diagUpDirSeq;
}
}
}
// Check sequences in the diagonalDown direction.
for (int chunkRow = 0; chunkRow < rowModulus - 3; chunkRow++) {
for (int chunkCol = 0; chunkCol < rowModulus - 3; chunkCol++) {
double diagDownDirSeq =
dGrid [chunkRow + 0] [chunkCol + 0] *
dGrid [chunkRow + 1] [chunkCol + 1] *
dGrid [chunkRow + 2] [chunkCol + 2] *
dGrid [chunkRow + 3] [chunkCol + 3];
if (diagDownDirSeq > largestProduct) {
largestProduct = diagDownDirSeq;
}
}
}
cout << setprecision (0) << fixed;
cout << largestProduct << endl;
}