Thursday, April 4, 2013

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 299 altogether! If you could check one trillion (1012) 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! :)


=

=

Tuesday, April 2, 2013

Project Euler Problem 18 : Maximum Path Sum 1

In the name of Allah.

For those who loves programming challenges, can look at this link for a list.

Phew. Finally finish writing a program for Problem 18 Project Euler.

#########################################


Maximum Path Sum 1 (Project Euler Problem 18)

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 of the triangle below:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o) 

#########################################

At first, I thought it just look going to max adjacent below row route. But after trying the triangle posted by them, it is about the maximum sum of a path of numbers. Therefore, I thought that it might be good to look it up from the bottom.

But I can't think of a way.

So first, how would I stored the data? I thought of 2D array, binary tree and graph. Graph won't work, binary tree may show a fast speed, but it doesn't seems to have any way of storing 0 (or I just didn't see it). Therefore, the overused array are used.

Second,question to see how they are adjacent to each others. Third, how to know it is a maximum path from top to bottom. I read an interesting thing that max f(x) = -min[f(x)]. But, my imagination see no specific function for this, and then I guess it is not needed when I finally found the one-line function.

<_< >_>

Alright, after 30 minutes of thinking, I just google it. -.-" But, I only read the C# program explanation, then I use that 'inspiration' to build it on my own. Cheating? Yeah, I still noob. T_T.

First, I used this algorithm/pseduocode.

1. Read input from input.txt.
2. Store into 2D array integer.
3. Do the triangle function thingy.
4. Display last triangle function OR display the [0][0] element.
5. Eat supper.

Okay, ignore that number 5. I am currently in hyper mode from listening to Vocaloid songs.

And the triangle Function thingy I got:

for (i=SIZE-1; i>=0; i--)
for (j=0; i<SIZE;j++)
[i-1] [j] = [i-1][j] + max([i][j],[i][j+1]

where SIZE is the number of lines in text files. Or, size of row/column of the array.

So, how in the heaven and on earth I got that?

First, the data representation, as mentioned, is done by putting into 2D array. The empty part is filled with zeros. Because I don't really remember how to file input, I use manual array initialisation now. Therefore, it is in form of

If we find the maximum between 2 lowest row, then add to the higher row adjacent element, it create some sort of triangle maximum summation. So, Uh, continue doing so until the top making the top having the maximum sum path thing. (Getting hard to explain).

I tried some trial and error to see the pattern as I usually do.
2 + max(8,5) <=> [2][0]+max([3][0],[3][1]);
4 + max(5,9) <=> [2][1]+max([3][1],[3][2]);
6 + max(9,3) <=> [2][2]+max([3][2],[3][3]); 
-----------------------------------------------------
[i-1] [j] = [i-1][j] + max([i][j],[i][j+1] 
-----------------------------------------------------

So, collapsing triangle like recursively:

3
7 4
2 4 6
8 5 9 3

3
7 4
10 13 15

3
20 19

23
You can see that the operation reduce the triangle to the answer. But, my function seems to meet with the boundary. So, re-adjust them:

 for (i=SIZE-2; i>=0; i--)
for (j=0; i<=1;j++)
[i-1] [j] += max([i+1][j],[i+1][j+1]