C++

Forum

 
Project euler problem 11

closed account (ETAkoG1T)
You need to look at this page to see what i am working at:
http://projecteuler.net/problem=11
I compile the program but the answer my program tells is the biggest isn't correct according to the website. Can you help me spot mistakes that can be the cause?
Than you!



My code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;
void show_arr(const int *arr);
int main()
{
	ifstream in;
	in.open("numb.txt");
	int arr[20][20];
	for(int i = 0;i < 20;++i)
	{
		for(int o = 0;o < 20;o++)
			in >> arr[i][o];
	}
	long long max = 0;
	int o = 0;
	for(int i = 0;i < 20;i++)
	{
		cout << " Start ";
		o = 0;
		for(; o < 20; o++)
		{
			cout << " * ";
			//four in a row, in line
			if(o < 17 && arr[i][o] * arr[i][o + 1] * arr[i][o + 2] * arr[i][o + 3] > max)
				max = arr[i][o] * arr[i][o + 1] * arr[i][o + 2] * arr[i][o + 3];

			if(o > 2 && i < 17 && arr[i][o] * arr[i+1][o-1] * arr[i+2][o-2] * arr[i+3][o-3] > max)
				max = arr[i][o] * arr[i+1][o-1] * arr[i+2][o-2] * arr[i+3][o-3];

			if(o < 17 && i < 17 &&  i < 17 && arr[i][o] * arr[i+1][o+1] * arr[i+2][o+2] * arr[i+3][o+3] > max)
				max = arr[i][o] * arr[i+1][o+1] * arr[i+2][o+2] * arr[i+3][o+3];

			if(i < 17 && arr[i][o] * arr[i-1][o] * arr[i-2][o] * arr[i-3][o] > max)
				max = arr[i][o] * arr[i-1][o] * arr[i-2][o] * arr[i-3][o];
			
		}
		cout << " Fin ";
		cout << "\nMax: " << max << endl;
	}
	cout << "The biggest number is: " << max;
	in.close();
	cin.get();
	cin.get();
	return 0;
}

void show_arr(const int *arr)
{
	for(int i = 0;i < 20;++i)
	{
		for(int o = 0;o < 20;++o)
		{
			cout << *arr << " ";
			arr++;
		}
		cout << endl;
	}
}
closed account (ETAkoG1T)
I don't use the show_arr function in this program I just made it so that I could test if everything worked fine. This is what the numb.txt file contains:

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


coder777 (8444)
why do you think you need - for the index? Esp. the last if (on line 35) is wrong.

Multiplicating left with right is the same as right with left.

try this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
			if(o < 17)
			{
				const long long value = arr[i][o] * arr[i][o + 1] * arr[i][o + 2] * arr[i][o + 3]; // Horizontally
				if(value > max)
					max = value
				if(i < 17)
				{
					const long long value = arr[i][o] * arr[i + 1][o + 1] * arr[i + 2][o + 2] * arr[i + 3][o + 3] // Diagonally
					if(value > max)
						max = value
				}
			}
			if(i < 17)
			{
				const long long value = arr[i][o] * arr[i + 1][o] * arr[i + 2][o] * arr[i + 3][o]; // Vertically
				if(value > max)
					max = value
			}
Not tested!
closed account (ETAkoG1T)
I think this is basically almost the same as I did it just neater, still doesn't give me the correct answer :/ does this cover all the different combinations? This does not cover backward diagonal. If I am thinking right backward and forward is the same but not when it comes to diagonally.


EDIT:
Still not working even when I added that...
Last edited on
coder777 (8444)
Your right it does not cover all diagonals. Currently \ only but / is missing:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
			if(o < 17)
			{
				const long long value = arr[i][o] * arr[i][o + 1] * arr[i][o + 2] * arr[i][o + 3]; // Horizontally
				if(value > max)
					max = value
				if(i < 17)
				{
					const long long value = arr[i][o] * arr[i + 1][o + 1] * arr[i + 2][o + 2] * arr[i + 3][o + 3] // Diagonally: \
					if(value > max)
						max = value
					const long long value = arr[i][o + 3] * arr[i + 1][o + 3] * arr[i + 2][o + 1] * arr[i + 3][o] // Diagonally: /
					if(value > max)
						max = value
				}
			}
			if(i < 17)
			{
				const long long value = arr[i][o] * arr[i + 1][o] * arr[i + 2][o] * arr[i + 3][o]; // Vertically
				if(value > max)
					max = value
			}


If I am thinking right backward and forward is the same but not when it comes to diagonally.
It is the same. line 29 and 32 are calculating the same value just at another time.

Another issue is: what happens at the egdes (i.e. o/i >= 17)?
closed account (ETAkoG1T)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
if(o < 17)
			{
				const long long value = arr[i][o] * arr[i][o + 1] * arr[i][o + 2] * arr[i][o + 3]; // Horizontally
				if(value > max)
					max = value;
				if(i < 17)
				{
					const long long value = arr[i][o] * arr[i + 1][o + 1] * arr[i + 2][o + 2] * arr[i + 3][o + 3]; // Diagonally
					if(value > max)
						max = value;
				}
			}
			if(i < 17)
			{
				const long long value = arr[i][o] * arr[i + 1][o] * arr[i + 2][o] * arr[i + 3][o]; // Vertically \
				if(o > 2)
				{
				const long long value2 = arr[i][o] * arr[i][o - 1] * arr[i][o - 2] * arr[i][o - 3]; // Vertically /
				if(value2 > max)
					max = value2;
				}
				if(value > max)
					max = value;
			}


This should work but I still get my answer as wrong!?
Last edited on
closed account (ETAkoG1T)
I think the program covers everywere : up, down, left, right, or diagonally
but it doesn't give me the right answer so maybe the answer to making it work lies somewhere else..
closed account (ETAkoG1T)
Please can anyone help? I need help no way I can do this alone. I thought people at c++ forum would be able to help with things like this...
closed account (D80DSL3A)
I'm not sure what's wrong with your code.

I got the right answer with this code.
It brute-forced the answer in 0.062 sec.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
#include <iostream>
#include <fstream>
using namespace std;

const unsigned int size = 20;
unsigned int M[size][size] = {0};

int main()
{
    unsigned int r=0, c=0;// for looping

    // init array
    ifstream fin("numb.txt");// ATTENTION: This file must exist.
    if( fin )
    {
        for( r=0; r < size*size; ++r )
            fin >> M[r/size][r%size];

        fin.close();
    }
    else
    {
        cout << "fileopenfail!!" << endl;
        return 1;
    }

    unsigned int prod = 1;
    unsigned int maxProd = prod;

    // vertical products
    for( c=0; c < size; ++c )
        for( r=0; r < size-3; ++r )
        {
            prod = M[r][c]*M[r+1][c]*M[r+2][c]*M[r+3][c];
            if( prod > maxProd )
                maxProd = prod;
        }

    // horizontal products
    for( r=0; r < size; ++r )
        for( c=0; c < size-3; ++c )
        {
            prod = M[r][c]*M[r][c+1]*M[r][c+2]*M[r][c+3];
            if( prod > maxProd )
                maxProd = prod;
        }

    // diagonal products - \
    for( c=0; c < size-3; ++c )
        for( r=0; r < size-3; ++r )
        {
            prod = M[r][c]*M[r+1][c+1]*M[r+2][c+2]*M[r+3][c+3];
            if( prod > maxProd )
                maxProd = prod;
        }

    // diagonal products - /
    for( c=3; c < size; ++c )
        for( r=0; r < size-3; ++r )
        {
            prod = M[r][c]*M[r+1][c-1]*M[r+2][c-2]*M[r+3][c-3];
            if( prod > maxProd )
                maxProd = prod;
        }

    cout << "maxProd = " << maxProd << endl;

    cout << endl;
    return 0;
}

I assumed the output was wrong when the program finished so fast, but it was right!

EDIT: Was this line (line 18 above) for finding products on the / diagonals?
const long long value2 = arr[i][o] * arr[i][o - 1] * arr[i][o - 2] * arr[i][o - 3]; // Vertically /
You needed to increase row also:
const long long value2 = arr[i][o] * arr[i + 1][o - 1] * arr[i + 2][o - 2] * arr[i + 3][o - 3]; // Vertically /

About the data type needed for this problem.
I see you played it safe and went with long long int.
You can tell that an integer would do fine by looking at the largest value the product of 4 numbers<100 could be.

max product < 100*100*100*100 < 10^8 and so a regular int will suffice.
Last edited on
coder777 (8444)
Well Filiprei, I really don't know what you're trying to do?

You copied the line for calculating horizontally (and change + to -) and claim it is vertically?
line 3 and 18 produce the same result. Just that line 18 will produce less.

you may write all results for the different calculation in different files. Then compare the results. if the results of one calculation is equal or a subset of the other calculation you did something wrong.

Lets reduce complexity (to 2):
1
2
3
4
 
arr[i + 0][o + 0] * arr[i + 0][o + 1]
arr[i + 0][o + 0] * arr[i + 1][o + 1]
arr[i + 0][o + 3] * arr[i + 1][o + 2]
arr[i + 0][o + 0] * arr[i + 1][o + 0]
The important thing is the the content of [] is in fact different. The problem is to find any existing combination.
The nature of multiplication is that e.g.
arr[i][o] * arr[i][o + 1]
produces the same result as
arr[i][o] * arr[i][o - 1]
That's not a true difference!

I made a little mistake on line 11:
const long long value = arr[i][o + 3] * arr[i + 1][o + 3] * arr[i + 2][o + 1] * arr[i + 3][o] // Diagonally: /

Corrected:
const long long value = arr[i][o + 3] * arr[i + 1][o + 2] * arr[i + 2][o + 1] * arr[i + 3][o] // Diagonally: /
Last edited on
closed account (ETAkoG1T)
what fun2code had worked, ty for the time anyways, in the beginner forum I have another project euler thread, it would be nice if you helped with that one to :)
Topic archived. No new replies allowed.