3

Source: http://projecteuler.net/index.php?section=problems&id=11

Quick overview: Take a 20x20 grid of numbers and compute the largest product of 4 pairs of numbers in either horizontal, vertical, or diagonal.

My current approach is to divide the 20x20 grid up into single rows and single columns and go from there with a much more manageable grid. The code I'm using to divide the rows into rows is

void fillRows
    ( string::const_iterator& fieldIter, 
      list<int>& rowElements, 
      vector<list<int>>& rows )
{
    // fieldIter is already initialized.
    int count(0);
    for( ; fieldIter < field.end(); ++fieldIter )
    {
        if(isdigit(field[*fieldIter]))
        {           
            rowElements.push_back(toInt(field[*fieldIter]));
            ++count;
        }
        if(count == 40)
        {
            rows.push_back(rowElements);
            count = 0;
            rowElements.clear();
        }
    }
}

Short explanation: I have the field set as static const std::string field and I am filling a vector with lists of rows. Why a list? Because the queue doesn't have a clear function. Also practice using STL container lists and not ones I write myself.

However, this thing isn't working. Oftentimes I see it omitting a character( function toInt parses the const char as int ) and I end up with 18 rows, two rows short of the 20x20 grid. The length of the rows seem good.

Rows: 18

RowElements[0]: 40 (instead of pairs I saved each number individually. Will fix that later)

What am I doing wrong?

IAE
  • 2,213
  • 13
  • 37
  • 71
  • 1
    Why are you dividing the grid like that? You also have to take diagonals into consideration, which your solution doesn't seem to do. – IVlad Jun 15 '10 at 07:46
  • Because I thought that was a good answer? And I think diagonals could be done fine because it would simply be the pair to the right or left of the previous row, and so on. Not too hard imo, but I haven't tried it yet. – IAE Jun 15 '10 at 07:48
  • 1
    "4 pairs of numbers" - the problem is about 4 numbers, not 4 pair of numbers – adf88 Jun 15 '10 at 07:51
  • Sorry, they're all numbers. My horrible use of "pair" was regarding the fact that the number "26" is made up of two digits, so a pair." – IAE Jun 15 '10 at 07:55

3 Answers3

5

You know the grid is 20x20, so just paste it into a text file and read it like you would normally read a matrix:

for (int i = 0; i < 20; ++i)
    for (int j = 0; j < 20; ++j)
        inFile >> mat[i][j];

Then do the obvious: for each element [i][j], go 4 elements down, 4 to the right, 4 diagonally to the right and 4 diagonally to the left and find the product. If you can't get 4 elements because of boundaries, ignore those you can get.

There's no need to complicate this like you seem to be doing. Keep it simple, because this is a simple problem, and if you overthink it you will only make your life harder.

IVlad
  • 43,099
  • 13
  • 111
  • 179
  • The Euler project is not about brute force :) – badp Jun 15 '10 at 07:52
  • @bp - precisely, so you avoid lists and vectors if you can help it :). Saying to brute force it was an unfortunate choice of words, as you have to examine all the elements anyway, so there's no other solution. I'll edit that. – IVlad Jun 15 '10 at 07:55
  • 3
    It's a 20x20 grid... doing anything other than brute force would be a pointless waste of time, and the optimal way is only slightly faster anyway. – Peter Alexander Jun 15 '10 at 07:56
  • "If you can't get 4 elements because of boundaries, ignore those you can get." What??? Why does this have so many upvotes? That sentence makes no sense. Could you please elaborate on how you're supposed to handle the boundaries? This problem is far more challenging than everyone seems to claim. – Aleksandr Hovhannisyan Dec 21 '16 at 19:14
  • @AleksandrH 5 upvotes can't possibly qualify as "many". What about the sentence doesn't make sense? It means that if you are on `mat[i][j]`, and one of `mat[i][j+1], mat[i][j+2], mat[i][j+3]` (or one of the similar ones down and diagonally) is outside the bounds of the matrix, you should ignore even those that aren't outside and move on to the next position, and try to find 4 starting from there. Only compute the product if you can find 4 within the boundaries. – IVlad Dec 21 '16 at 19:27
  • Alternatively, start the nested `for` loops from `3` and end them at `20 - 4`. And for each `[i][j]`, go 4 left, right, up, down and diagonally. This way, the boundaries won't matter. – IVlad Dec 21 '16 at 19:28
  • With the second approach, you'd miss checking some horizontals and verticals. Still don't understand the first approach very well. Having a hard time picturing this, even on paper. – Aleksandr Hovhannisyan Dec 21 '16 at 19:36
  • @AleksandrH you'd miss some on the edges, true. You can consider those separately, by only starting one of the `for` loops from 3 to 16. For the first approach, imagine fixing a position `[i][j]`. Draw lines from it of length 4 diagonally, horizontally and vertically. Only consider the lines that do not go outside of the boundaries. Multiply each set of 4 cells that those cross. – IVlad Dec 21 '16 at 19:40
3

I have written this code. I hope it helps, though it is a long one....

#include <iostream>
#include <vector>
using namespace std;



void main() 
{

int num_container[20][20] = {
                            { 8,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91, 8},
                            {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, 8,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, 9,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, 9,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, 8,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, 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,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},
                                                                                        };


int test = num_container[6][8] * num_container[7][9] * num_container[8][10] * num_container[9][11];
cout<<test<<endl;
system("pause");

int start = 0;
int end = 3;
long long mul_result = 1;

vector<long long>final_results;

/////////////////////UP/DOWN/////////////////////
for(int k=0; k<20; k++)
{
    for(int i=0; i<=16; i++)
    {
        for(int j=start; j<=end; j++)
        {
            mul_result = mul_result * num_container[k][j];
            if (j == end)
                final_results.push_back(mul_result);
        }
        mul_result = 1;
        start++;
        end++;
    }
    start = 0;
    end = 3;

    for(int i=0; i<=16; i++)
    {
        for(int j=start; j<=end; j++)
        {
            mul_result = mul_result * num_container[j][k];
            if (j == end)
                final_results.push_back(mul_result);
        }
        mul_result = 1;
        start++;
        end++;
    }
    start = 0;
    end = 3;

}
/////////////////////UP/DOWN Ends here//////////////////////



///////////////////Both Ways Diagonal Starts here//////////////////////
int current_row = 0;

for(int i=0; i<=16; i++)
{
    for(int j=0; j<=16; j++)
    {
        current_row = i;
        for(int k=start; k<=end; k++)
        {
            mul_result = mul_result * num_container[current_row][k];
            current_row++;
            if (k==end)
                final_results.push_back(mul_result);
        }
        mul_result = 1;
        start++;
        end++;          
    }
    start = 0;
    end = 3;

    for(int j=0; j<=16; j++)
    {
        current_row = i+3;
        for(int k=start; k<=end; k++)
        {
            mul_result = mul_result * num_container[current_row][k];
            current_row--;
            if (k==end)
                final_results.push_back(mul_result);
        }
        mul_result = 1;
        start++;
        end++;          
    }
    start = 0;
    end = 3;
}
/////////////////////Both Ways diagonal ends here///////////////////


////////////////////Compare Thning Starts here//////////////////////

long long the_big_one = 0;
for(int i=0; i<final_results.size(); i++)
{
    if (final_results[i] > the_big_one)
        the_big_one = final_results[i];
}





cout<<endl<<endl<<"The big one is: "<<the_big_one<<endl;

system("pause");
}
Rafay
  • 6,108
  • 11
  • 51
  • 71
2

Why not use a std::vector instead of a list? Lists and queues are a bad choice for this question as you require random-access, for which you need a vector.

Why are you moving to the next row when count == 40? Shouldn't it be 20?

You are using iterators wrong. You don't use field[*fieldIter] to get the element at the iterator, you just use *fieldIter.

You should use fieldIter != field.end() instead of <. For a string, it's the same either way, but for other containers (such as a list), < won't work because the list nodes aren't ordered in memory.

Where is your toInt function?

Anyway, why make this so complicated?

int grid[20][20];

for (int i = 0; i < 20; ++i)
  for (int j = 0; j < 20; ++j)
    std::cin >> grid[i][j];
Peter Alexander
  • 53,344
  • 14
  • 119
  • 168
  • I had to make it a little complicated because the list is divided with spaces, like so = "20 14 55 00" and to simply grab the stuff like that wouldn't work too great. Thanks for setting me straight on the iterators! 40 because I'm not grabbing pairs, but single numbers. 20 pairs = 40 numbers. – IAE Jun 15 '10 at 07:55
  • Reading the integers like I have done works just fine. Try it. `std::cin` handles the spaces for you. Why do you keep mentioning pairs? There's no pairs in the question. It just wants products of individual numbers in a line. – Peter Alexander Jun 15 '10 at 08:04
  • Personally I just cut and pasted the numbers into the source and turned it into an array initialiser with a couple of search and replace commands. It's not like you're going to have to solve the problem for another set of numbers any time. – Pete Kirkham Jun 15 '10 at 08:32
  • @IAE [Why you should never, ever, EVER use linked-list in your code again](https://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/), [Bjarne Stroustrup says we must avoid linked lists](https://stackoverflow.com/q/34170566/995714) – phuclv Jul 29 '18 at 15:29