Just a hint, so you don’t go down the wrong path. You probably won’t, but if you don’t want any hints, stop reading this article!
PS If you don’t know what Project Euler is, I recommend having a look at their website, or just getting an idea from the problems themselves.
What is Project Euler?
Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
Now problem / puzzle 11:
In the 2020 grid below, four numbers along a diagonal line have been marked in red.
(snip)
The product of these numbers is 26 63 78 14 = 1788696.
What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 2020 grid?
Just a hint for those of you who spent too long on this like me: it’s essentially a word search. One of these but with numbers.
You see, when I got the wrong answer a couple times I reread the question, and figure “adjacent” just meant anywhere beside each other – eg a square of four numbers, a t-shape. This is not the case! You don’t need to develop a path-finding bot that navigates 4 numbers, looking for the best options! Although, having done that, it’s actually quite fun! In python, at least, it’s quite concise and the code is pretty-looking.
Bonus points (or a packet of chocolate-coated raisins) to the first person who does implement such an algorithm. The answer I’m looking for is the highest product of the resulting 4 numbers, and leave it in the comments.
Bet I won’t get an answer!
I have looked
I have looked through the first few pages of hits on google and have yet to find a post of the actual answer to this problem. I can only find different codes people have written to find it. It’s starting to get on my nerves. No offense to fellow beginner coders out there, but I don’t really care how you got your answer because I already wrote my own code for it. I just want to know if my answer is correct for verification. So here is my code (which I doubt addresses the problem in the form you were looking for) followed by the absolutely necessary info of what answer my code outputs (for those of you, like me, who have been unable to find it).
#include
using namespace std;
int grid [400] = {
8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8,
49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0,
81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65,
52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 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, 3, 45, 2, 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, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21,
24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72,
21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95,
78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92,
16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57,
86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58,
19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40,
4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66,
88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69,
4, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 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, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54,
1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48};
int across (int x) {
int product;
product = grid[x]*grid[x+1]*grid[x+2]*grid[x+3];
return product;}
int down (int x) {
int product;
product = grid[x]*grid[x+20]*grid[x+40]*grid[x+60];
return product;}
int diagonalf (int x) {
int product;
product = grid[x]*grid[x+21]*grid[x+42]*grid[x+63];
return product;}
int diagonalb (int x) {
int product;
product = grid[x]*grid[x+19]*grid[x+38]*grid[x+57];
return product;}
int main () {
int pos=0, hia=0, storea, hid=0, stored, hidf=0, storedf, hidb=0, storedb;
for (; pos<400; pos++) {
int y;
y=pos%20;
if (y<19) {cout << grid[pos] << " ";}
if (y==19) {cout << grid[pos] << endl;}
}
cout << "The greatest product of 4 adjacent numbers is ";
pos=0;
for (; pos<400; pos++) {
int y, v;
y=pos%20;
if (yhia) {hia = v; storea = pos;}}
}
pos=0;
for (; poshid) {hid=v; stored=pos;}
}
pos=0;
for (; pos<340; pos++) {
int y, v;
y=pos%20;
if (yhidf) {hidf=v; storedf=pos;}}
}
pos=0;
for (; pos2) {v = diagonalb(pos);
if (v>hidb) {hidb=v; storedb=pos;}}
}
if (hia>hid && hia>hidf && hia>hidb) {cout << hia << "." << endl << "Starting at position "
<< storea << " and moving across (to the right)." << endl;
cout << "Values of " << grid[storea] << ", " << grid[storea+1] << ", " << grid[storea+2]
<< ", and " << grid[storea+3] <hia && hid>hidf && hid>hidb) {cout << hid << "." << endl << "Starting at position "
<< stored << " and moving down." << endl;
cout << "Values of " << grid[stored] << ", " << grid[stored+20] << ", " << grid[stored+40]
<< ", and " << grid[stored+60] <hia && hidf>hid && hidf>hidb) {cout << hidf << "." << endl << "Starting at position "
<< storedf << " and moving diagonally forward." << endl;
cout << "Values of " << grid[storedf] << ", " << grid[storedf+21] << ", " << grid[storedf+42]
<< ", and " << grid[storedf+63] <hia && hidb>hid && hidb>hidf) {cout << hidb << "." << endl << "Starting at row "
<< storedb/20+1 << ", column " << storedb%20+1 << " and moving diagonally backward." << endl;
cout << "Values of " << grid[storedb] << ", " << grid[storedb+19] << ", " << grid[storedb+38]
<< ", and " << grid[storedb+57] << endl;}
}
Answer (still unverified): 70,600,674
It was found starting at row 13, column 7 and moves diagonally down right to left from there. Values 89, 94, 97, and 87.
Hi Austin++, thanks for your contribution! I agree it’s frustrating to not find what you’re looking for, but PE does verification for you does it not? In case it doesn’t, the answer you have is correct.
The reason I put up a general guide of how it is solved is so that there is a hint for people with no idea of how to go about it! It’s like many problems in maths – the answer itself is (relatively) uninteresting, it’s the work to get there that’s the useful bit 🙂
Perhaps having both answer and working available would be most useful? If it was me, I’d be tempted to just put the answer in without doing the working which is why I omitted the answer. No harm done either way 🙂
Lastly, if you’ve no objections, I’ll package your code up into a text file and link that for download, or put it in the body of the post in a collapsible <div> ? The theme I’m using doesn’t seem to be great for code snippets unfortunately!