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?
Here is my solution in C++ to this project euler problem; not the most elegant method, and the verbosity was just kind of tacked on. But it works fairly quickly, at .024 seconds including file reading and parsing.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <vector>
#include <fstream>
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define VERBOSE 0
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
unsigned long long calculateDiagonals(std::vector<std::vector<int>> passedLines, int lineIndex, int linePos);
unsigned long long calculateHorizontal(std::vector<std::vector<int>> passedLines, int lineIndex, int linePos);
unsigned long long calculateVerticals(std::vector<std::vector<int>> passedLines, int lineIndex, int linePos);
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main(void)
{
std::ifstream inFile("input.txt");
std::string sbuff;
std::size_t found;
std::vector<std::vector<int>> theLines;
int lineIndex = 0, intBuff;
unsigned long long greatestMultiple = 0, multipleBuff;
while(getline(inFile, sbuff))
{
theLines.push_back(std::vector());
if(VERBOSE)
{
std::cout << sbuff << "\n";
}
while((found = sbuff.find(" ")) != std::string::npos)
{
if(VERBOSE)
{
std::cout << sbuff << "\n";
}
theLines.back().push_back(stoi(sbuff.substr(0, found)));
sbuff.erase(0, found + 1);
}
theLines.back().push_back(stoi(sbuff));
}
while(lineIndex < 20)
{
for(int linePos = 0; linePos < 20; linePos++) { multipleBuff = calculateHorizontal(theLines, lineIndex, linePos); if(multipleBuff > greatestMultiple)
{
greatestMultiple = multipleBuff;
if(VERBOSE)
{
std::cout << "[+]New greatest multiple found: " << greatestMultiple << "\n"; } } multipleBuff = calculateVerticals(theLines, lineIndex, linePos); if(multipleBuff > greatestMultiple)
{
greatestMultiple = multipleBuff;
if(VERBOSE)
{
std::cout << "[+]New greatest multiple found: " << greatestMultiple << "\n"; } } multipleBuff = calculateDiagonals(theLines, lineIndex, linePos); if(multipleBuff > greatestMultiple)
{
greatestMultiple = multipleBuff;
if(VERBOSE)
{
std::cout << "[+]New greatest multiple found: " << greatestMultiple << "\n";
}
}
}
++lineIndex;
}
std::cout << "Greatest multiple found: " << greatestMultiple << "\n";
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
unsigned long long calculateHorizontal(std::vector<std::vector<int>> passedLines, int lineIndex, int linePos)
{
unsigned long long leftBuff = passedLines[lineIndex][linePos];
unsigned long long rightBuff = leftBuff;
if(linePos >= 3)
{
for(int i = (linePos - 1); i > linePos - 4; i--)
{
leftBuff *= passedLines[lineIndex][i];
}
if(VERBOSE)
{
std::cout << "[*] Left horizontal is: " << leftBuff << "\n";
}
}
if(linePos <= 16)
{
for(int i = (linePos + 1); i < linePos + 4; i++)
{
rightBuff *= passedLines[lineIndex][i];
}
if(VERBOSE)
{
std::cout << "[*] Right horizontal is: " << rightBuff << "\n"; } } if(leftBuff > rightBuff)
{
return leftBuff;
}
else
{
return rightBuff;
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
unsigned long long calculateVerticals(std::vector<std::vector<int>> passedLines, int lineIndex, int linePos)
{
unsigned long long upBuff = passedLines[lineIndex][linePos];
unsigned long long downBuff = upBuff;
if(lineIndex >= 3)
{
for(int i = (lineIndex - 1); i > lineIndex - 4; i--)
{
upBuff *= passedLines[i][linePos];
}
if(VERBOSE)
{
std::cout << "[*] Up vertical is: " << upBuff << "\n";
}
}
if(lineIndex <= 16)
{
for(int i = (lineIndex + 1); i < lineIndex + 4; i++)
{
downBuff *= passedLines[i][linePos];
}
if(VERBOSE)
{
std::cout << "[*] Down vertical is: " << downBuff << "\n"; } } if(upBuff > downBuff)
{
return upBuff;
}
else
{
return downBuff;
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
unsigned long long calculateDiagonals(std::vector<std::vector<int>> passedLines, int lineIndex, int linePos)
{
unsigned long long seedVal = passedLines[lineIndex][linePos];
unsigned long long leftBuff = seedVal;
unsigned long long rightBuff = seedVal;
unsigned long long returnBuff;
unsigned long long posBuff = linePos;
if(lineIndex >= 3 && linePos >= 3)
{
for(int i = (lineIndex - 1); i > lineIndex - 4; i--)
{
leftBuff *= passedLines[i][--posBuff];
}
if(VERBOSE)
{
std::cout << "[*] Up-left diagonal is: " << leftBuff << "\n"; } } posBuff = linePos; if(lineIndex >= 3 && linePos <= 16) { for(int i = (lineIndex - 1); i > lineIndex - 4; i--)
{
rightBuff *= passedLines[i][++posBuff];
}
if(VERBOSE)
{
std::cout << "[*] Up-right diagonal is: " << rightBuff << "\n"; } } if(rightBuff > leftBuff)
{
returnBuff = rightBuff;
}
else
{
returnBuff = leftBuff;
}
posBuff = linePos;
leftBuff = seedVal;
rightBuff = seedVal;
if(lineIndex <= 16 && linePos >= 3)
{
for(int i = (lineIndex + 1); i < lineIndex + 4; i++)
{
leftBuff *= passedLines[i][--posBuff];
}
if(VERBOSE)
{
std::cout << "[*] Down-left diagonal is: " << leftBuff << "\n";
}
}
posBuff = linePos;
if(lineIndex <= 16 && linePos <= 16)
{
for(int i = (lineIndex + 1); i < lineIndex + 4; i++)
{
rightBuff *= passedLines[i][++posBuff];
}
if(VERBOSE)
{
std::cout << "[*] Down-right diagonal is: " << rightBuff << "\n"; } } if(leftBuff > returnBuff)
{
returnBuff = leftBuff;
}
if(rightBuff > returnBuff)
{
returnBuff = rightBuff;
}
return returnBuff;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////