Problem 011

[Bruceleet]

I was looking for a bit of clarification on problem 11. I'm gonna try get to it tonight but I already looked it over and I was wondering about something:

What is the greatest product of four numbers in any direction (up, down, left, right, or diagonally) in the 20 x 20 grid?

9 8 5 2 1 3 4 7 6 // example cube

Would the solution in this cube (line) be:
a) 720
b) 3024

I'm assuming people won't consider this a spoiler or hint in anyway. If they do i'm very sorry and i'll ofcourse remove the post.

[quilan]

If memory serves, a) 720 would be considered the correct answer for that line.

[Bruceleet]

Your memory served you well, thanks alot for the clarification. Problem solved.

[PO8]

Problem 11 has a specification ambiguity which kind of worried me. Nothing in the problem description states that the numbers in the product have to be adjacent, although they happen to be in the example. Turns out they do, but it should probably be spelled out.

The other version of the problem is at least as interesting, BTW.

[euler]

That's a fair point. I've changed it to: "What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20 x 20 grid?"
http://projecteuler.net/index.php?secti ... lems&id=11

[bryan4tw]

I am having quite a bit of trouble with this problem. I keep coming to the same, incorrect answer. I am not sure how much information I should post; I do not want give it away for someone else, but I need help.

----

Hah! Never mind, while I was writing this I had flash back to Algebra 101. Needless to day, I feel dumb now, but I'm glad I solved it!

[TheRatKing]

I'm a bit confused by this question, does "four adjacent numbers in any direction (up, down, left, right, or diagonally) " mean something like this is possible?

1 2 3 4
5 6 7 8
9 1 4 5
5 7 3 1

Or do ALL of the numbers have to be in the same direction (as in the example)?

edit: I figured it out, the above example is definitely not a possible solution, although it would make for a harder and more interesting problem.

[daniel.is.fischer]

All in the same direction.

[MoHSalim]

My code runs fine but I keep getting the wrong answer:


I was wondering what is wrong here or am I missing some direction?

[elendiastarman]

You may want to snip out that code to avoid possibly posting a spoiler. I will tell you though, that your number is much too low.

[MoHSalim]

I got why it isn't giving me the right answer. I didn't include the 16 numbers in the bottom left and bottom right numbers because of OutOfBoundExceptions.

[knicknic]

I made the mistake of earlier people seeing that the number should be just touching one another in a chain, not all in the same line. You should fix the problem's wording because I feel it is incorrect. BTW I think both problems are the same hardness, but it should be clarified.

[JerBear]

Hi,
Problem 11 if you've forgotten it.

Do the four numbers have to be all in 'the same' direction (ie, like connect 4)?
Or would a 2x2 block count as four adjacent numbers?
Cheers

[harryh]

@JerBear:
Your question has already been answered as you can see.
If only you had looked at the previously existing topic for this problem...

[Seahawk]

This is kind of like my intro to the forum and also a question on problem number 11. I am Matt. I am 13 years old and started coding in VB.Net then I moved on to C#. I am also picking up PHP/HTML/MySQL now. But anyways on to the question.

Ok I made an array of arrays (Multidimensional I think is what it is called) of the numbers. Then I am using variables (X and Y) respecitively for the index like so: thegrid[5][0]. That will go down to the 6th array in the array and then access the first element of that. Ok but I made 5 or 6 helper methods to get the product of 4 numbers diagonal and so on. And the thing is, is that I have to start at the bounds 3,3 and then stop at 16,16 or I will get index out of range exception. I have also tested all of my helper methods to see if they work and they do what they are supposed to do so just give some advice please peoples!

[hk]

That isn't so strange, isn't it?
If you are multiplying for numbers on that diagonal and you would start at (17,17) those numbers would be at
(17,17) (18,18), (19,19) and (20,20)
However, the largest x and y in your array are 19.
So if either x+3 or y+3 would exceed 19 you're in trouble.

[Seahawk]

That isn't so strange, isn't it?
If you are multiplying for numbers on that diagonal and you would start at (17,17) those numbers would be at
(17,17) (18,18), (19,19) and (20,20)
However, the largest x and y in your array are 19.
So if either x+3 or y+3 would exceed 19 you're in trouble.

When I was talking about 3,3 and 16,16 I was talking about a zero based index. Sorry if I didn't make it clear enough.

[hk]

I understood that and my answer was also directed at zero based arrays.
To make it more clear:
with "So if either x+3 or y+3 would exceed 19 you're in trouble."
I mean
So if either x+3 >19 or y+3>19 you're in trouble.
With x and y I mean the leftmost and the topmost element of you four numbers.

[Seahawk]

Oh sorry! I must be confusing my self. Can you explain this problem a little more to me because this has been the hardest one yet for me.

[hk]

Take it easy. Working in a twodimensional array is something to get accustomed with.
So you are walking on the line with points (0,0)(1,1) ....(19,19).
First you take the points (0,0)..(3,3) and multiply them
then the points (1,1)...(4,4) and so on.
So you get something like:
for x=0 to 19
{y=x
h=a[x,y]*a[x+1,y+1]*a[x+2,y+2]*a[x+3,y+3]
{and do something with h}}

But there are also other straight lines parallel to that straight line aren't there?
E.g. the line with y=x+1.
How would things go then?
What would be thestarting point with the largest x?