Triangle problem

Question

Hey!!

I am trying to resolve Euler Problem 18 -> http://projecteuler.net/index.php?section=problems&id=18

I am trying to do this with c++ (I am relearning it and euler problems make for good learning/searching material)

#include <iostream>

using namespace std;

long long unsigned countNums(short,short,short array[][15],short,bool,bool);

int main(int argc,char **argv) {

    long long unsigned max = 0;
    long long unsigned sum;


    short piramide[][15] = {{75,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
                            {95,64,0,0,0,0,0,0,0,0,0,0,0,0,0},
                            {17,47,82,0,0,0,0,0,0,0,0,0,0,0,0},
                            {18,35,87,10,0,0,0,0,0,0,0,0,0,0,0},
                            {20,4,82,47,65,0,0,0,0,0,0,0,0,0,0},
                            {19,1,23,75,3,34,0,0,0,0,0,0,0,0,0},
                            {88,2,77,73,7,63,67,0,0,0,0,0,0,0,0},
                            {99,65,4 ,28,6,16,70,92,0,0,0,0,0,0,0},
                            {41,41,26,56,83,40,80,70,33,0,0,0,0,0,0},
                            {41,48,72,33,47,32,37,16,94,29,0,0,0,0,0},
                            {53,71,44,65,25,43,91,52,97,51,14,0,0,0,0},
                            {70,11,33,28,77,73,17,78,39,68,17,57,0,0,0},
                            {91,71,52,38,17,14,91,43,58,50,27,29,48,0,0},
                            {63,66,4,68,89,53,67,30,73,16,69,87,40,31,0},
                            {4,62,98,27,23,9,70,98,73,93,38,53,60,4,23}};

    for (short i = 0;i<15;i++) {
        for (short m=0;m<15;m++) {
            if (piramide[i][m] == 0)
                break;
            sum = countNums(i,m,piramide,15,true,true);
            if (sum > max)
                max = sum;
            sum = countNums(i,m,piramide,15,true,false);
            if (sum > max)
                max = sum;
            sum = countNums(i,m,piramide,15,false,true);
            if (sum > max)
                max = sum;
            sum = countNums(i,m,piramide,15,false,false);
            if (sum > max)
               max = sum;

        }

    }
    cout << max;
    return 0;
}


long long unsigned countNums(short start_x,short start_y,short array[][15],short size, bool goright,bool goright2) {
    long long unsigned currentSum;

    currentSum = array[start_x][start_y];

    if (goright) { //go right
        if ((start_x + 1) < size)
            start_x++;
        if ((start_y + 1) < size)
            start_y++;
    }
    else //go down
        if ((start_x + 1) < size)
            start_x++;

    if (goright2) { //still going right
        for (short i = start_x, m = start_y;i< size && m < size;i++,m++) {
            currentSum += array[i][m];         
        }
    }
    else { //still going down
        for (short i = start_x;i<size;i++) {
            currentSum += array[i][start_y];            
        }
    }

    return currentSum;
}

The countNums function is used to go either down or diagonally. I have tested this function like so:

short a = 0;
short b = 0;
cout << countNums(a,b,piramide,15,true,true) << endl;
cout << countNums(a,b,piramide,15,true,false) << endl;
cout << countNums(a,b,piramide,15,false,true) << endl;
cout << countNums(a,b,piramide,15,false,false) << endl;
return 0;

And it does work (I also changed the function a little so it would print every number it was going through)

But I still don't get the right result. This goes down and to the right and still goes right (adjacent numbers to the right), goes down and keeps going down (adjacent number to the left). What am I doing wrong here, anyone???

Answer 1

Ok so first off, I'm a little unclear as to what you think the problem is. I can't parse that second-last sentence at all...

Secondly you might want to re-think your design here. Think about functions that perform a single discrete task and are not intertwined with the rest of the application (ie read up on "tightly coupled and loosely bound"). For me a big warning bell here is the presence of a overly-generic function name countNums with a long list of arguments.

I think if you were to divide the problem into smaller, more easily comprehensible, chunks you might find the problems a lot easier to find. I know the approach that I would take here but I'm assuming the whole point of the exercise is to help you practice your programming skills, so I'll just leave it at that...

Answer 2

Alastair: It's simple

long long unsigned countNums(short start_x,short start_y,short array[][15],short size, bool goright,bool goright2);

start_x and start_y are the coords of the array array is the reference to the array size is just the size of the array (it's always 15) goright is to know if I am going to go down and right or just down goright2 is to know if I am going to continue to go down or going left

Answer 3

I'm a little confused by the problem..
I'd start by cleaning up your code.

long long unsigned countNums(short x,
                             short y,
                             short array[][15],
                             short size, 
                             bool goright,
                             bool goright2) 
{
    long long unsigned currentSum;
    currentSum = array[x][y];

    if ((x + 1) < size)    x++; //this happened in both your if cases

    if (goright && ((y + 1) < size)      y++; 

    if (goright2)
    { 
        for (;x< size && y< size;x++,y++)
         currentSum += array[x][y];         

    }
    else 
    {
        for (;x<size;x++) 
      currentSum += array[x][y];            
    }
    return currentSum;
 }

Now I read the question and I'm not sure it's doing what you want. Since this isn't what you want I'd suggest psudo-code the answer first. Forget the code.. What is the answer in sudo code.
Oh and for the love of all that is holy. Don't put more then one initializer in the for loop. I know I'm going to get flak for that, but it's messy and really not needed. Something you might consider is a recusive function. Seems ideal for this problem.

Answer 4

The main function checks that an entry isn't zero, but the other function it calls doesn't check for that even though it changes the index again. I don't know, I don't really understand what you are trying to do.

I see array size 15 for 15 elements, would the index for declaration also start at 0? Let me check for a sec. Just making sure, declared with size but accessed based off 0. Good.

Why did you use a nested for statements one place but a compunded-condition for statement later on? Better check that the && doesn't have higher precedence than the <. Group 8 beats out group 13 here. Increment operator not used multiple times in a statement, that's good.

It sounds like you've done this problem before in another language, could you do a trace on that too and find the place your new program first differs?

The other guys are right, the question is confusing. I would first try to solve the problem buy building up subscores in another matrix giving the highest score if the pyramid started at that point and build it up from the bottom row to the top.

Answer 5

I've solved this problem. Given the nature of Project Euler is to solve the problem on your own ("photocopying a solved crossword puzzle doesn't mean you solved it") and that I don't want to ruin this for someone else, all I can really say is that your solution looks overly complex.

You can, however, solve this problem as you're reading the file. Solve it this way and problem #69 will be a breeze!

Good luck!

Answer 6

The above code seems to aim for the brute force approach.

Anyone knows the solution for the "clever" approach?

Maybe just pointing out the general idea behind the algorithm might help

Answer 7

Well thanks for trying to help anyway.. I guess