Project Euler Problem 67 : Maximum Path Sum 2

In the name of Allah.

Thanks to zariman, he helped me on file i/o. I really don't remember that part of programming. From a scribble of program code he wrote in the class, I take the shot of Problem 67 by modifying solution18_manualinput.java.

^^^^^^^^^^^^^^^^^^^^^^
Maximum Path Sum 2 (Project Euler Problem 67)

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2⁹⁹ altogether! If you could check one trillion (10¹²) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

^^^^^^^^^^^^^^^^^^^^^^

First, it is in text file. So, we need to use file input technique. There is too much to hardcoded in our program. A simple way would be just accept it using FileReader and nextInt(). There is space and lines, so it will be automatically taken separately.

E.g:
Scanner  in = new Scanner(new FileReader(".txt"));
ArrayList list = new ArrayList();
while(in.hasNext())
     list.add(in.nextInt());

Then, because I want it to be inputted in triangle array of number:
int num[] = new int[list.size()];
for( int i=0; i<list.size(); i++
{
    num[i] =(int)list.get(i);
}

Why (int)? If I am not mistaken, because it was stored in list as object, or binary data, or string. I cant remember. >_<

But, my algorithm used 2D array of integers. Therefore, I had to change it to act as such. Pull out a 100gsm of A4 paper and I scribble these. First, create a sample of list that was taken from text file. The index number is because i use list.get(i).

From here, we create the triangle of numbers to see how the pattern works.

Well, we only can see how it looks like, but how in the programming world we gonna make it looks like that? That is the use of using array, because it have index. and then, compared to my idea of 2D array in Problem 18 solution:

Look like from these
   list[0] => triangle[0][0]
   list[1] => triangle[1][0]
   list[2] => triangle[1][1]
   list[3] => triangle[2][0]
   list[4] => triangle[2][1]
   list[5] => triangle[2][2]
   list[6] => triangle[3][0]
   list[7] => triangle[3][1]
   list[8] => triangle[3][2]
   list[9] => triangle[3][3]

Patterns that I can see is, whenever we insert, i should increase the counter pointing to list index by 1 at any time. While to look for the row and column, using the usual i and j, I take that I can do the usual for(i=0;i<max;i++), while j=0, j<=i. Because the maximum column number is same as row number. But, because these are 2D array, the size are different. To avoid OutOfBoundException thingy, the max need to be counter pointing to index. I use variable name count, where it always increase everytime I assign value, and it is the stopping counter for both for loop.

Then, using the same algorithm from solution18, taddaa!

Though, because I assign final MAX <= list.size(), there are waste of space in memory. If there are other algorithm to know the maximum row and column quickly, let me know. I don't feel like looking for it. In my mind, I also thinking about using graph or trees as data representation, but it may be more difficult. Keep it simple.

See ya later! :)


=

=