Project Euler Problem #11

Question

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?

Answer 1

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];

Answer 2

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.