# Project Euler problems 18/67: maximum path sum

I recently solved problems 18/67 in Project Euler. My code is long and I think it could be more effective. I solved the problem with dynamic programming and am new to it, so I want to improve my dynamic programming. I think my running time is acceptable: 0.214 seconds.

import java.io.BufferedReader;
import java.util.ArrayList;

public class EighteenNSixtyseven {
@SuppressWarnings("rawtypes")
ArrayList<ArrayList> nodeList = new ArrayList<ArrayList>();
try {
while (tmp != null) {
String[] nums = tmp.split("\\s+");
ArrayList<Integer> nmb = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
}
// im adding an ArrayList to the ArrayList
}                                // the specific row and the other ArrayList
// containing the numbers
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
} catch (Exception e) {
e.printStackTrace();
}
}
return nodeList;
}
public static void main(String[] args) {
long start = System.currentTimeMillis();  // starting time
@SuppressWarnings("rawtypes")               // eclipse suggested this??? Why?
int size = list.size() - 1;
int calc = 0;
int otherCalc = 0;
int q = 0;
ArrayList<Integer> temp1 = new ArrayList<Integer>();
ArrayList<Integer> temp2 = new ArrayList<Integer>();
while (size >= 1) {
temp1 = list.get(size);
temp2 = list.get(size - 1);
q = 0;
if (temp2.size() != 1) {
while (q < temp2.size() - 1) {
for (int k = 0; k < temp2.size(); k++) {    // checking which
calc = temp1.get(q) + temp2.get(k);        // sum gives the bigger on
otherCalc = temp1.get(q + 1) + temp2.get(k); // adding numbers
if (calc > otherCalc) {                        // in the lower line
temp2.set(k, calc);                    // with the ones in the line
} else {                                // over to the right and left
temp2.set(k, otherCalc);
}
q++;
}
size--;
}
} else {
calc = temp1.get(0) + temp2.get(0);            // had to add this or the
otherCalc = temp1.get(1) + temp2.get(0);    // array is outOufBounds
if (calc > otherCalc) {
temp2.set(0, calc);
size--;
} else {
temp2.set(0, otherCalc);
size--;
}
}
}

System.out.println("\nThe sum total is = " + temp2.get(0));
long elapsedTimeMillis = System.currentTimeMillis() - start;
float elapsedTimeSec = elapsedTimeMillis / 1000F;
System.out.println("Tid " + elapsedTimeSec);
}
}


As you can see, the code is a bit messy! Any suggestions will be highly appreciated!

-

Even before starting the review I have to disappoint you. The problem has nothing to do with the dynamic programming. Now let's go.

1. Naming: Avoid meaningless names, such as q, temp1, temp2, calc and otherCalc.

2. Responsibilities: You correctly separated IO in a method of its own. The actual calculations also deserve to be separated.

3. Algorithm: A triple nesting loop is an immediate red flag. In fact, you don't need to iterate over q (which is the index into the bottom row, right? - it took me a while to figure it out) at all: the kth element of the upper row can be only influenced by kth and k+1th of the bottom one. Taking it into consideration, you'd eliminate one level of nesting as well as a really ugly special case of temp2.size() == 1.

The core loop should look like

    for (k = 0; k < upperRow.size(); k++)
upperRow[k] += max(bottomRow[k], bottomRow[k+1]);


That said, let me reiterate a very important rule of no raw loops: for every loop you write, think of it as a standalone method and figure out a meaningful name for it. If you can't than you effectively don't know what it is doing!

-
yup no DP but weighted shortest path :) The title says it all "path" – martijnn2008 May 19 '14 at 7:25

## Architecture

Instances of this class don't represent anything, so there shouldn't be any. It should be a fake class with only static methods, like java.Math.

## Variables

Many variable scopes are too large. Variables should be declared where they're initialized, not declared in one place and initialized later.

Variable names should indicate their meaning:

• nodeList and list are the triangle.
• temp1 is nextRow, and temp2 is currentRow.
• calc and otherCalc are the costs of the left and right paths from this node. (But they should both go away.)
• size is currentDepth or the y coordinate.

Several while loops could be written as for loops to make the initialization and updating of their loop variables obvious.

Don't suppress the rawtypes warning — it's telling you something! nodeList should be an ArrayList<ArrayList<Integer>>.

You only need one call to readLine: while ((line = reader.readLine()) != null) is the idiomatic way to read lines in Java.

The string-parsing loop can be over elements, not indexes: for (String s : nums).

Don't catch Exception. Catch only the exception you expect, in this case java.io.IOException. (Ideally you shouldn't catch any exception you can't handle — just let them propagate to the caller — but Java forces you to catch some exceptions. Fortunately in this case you only need one catch, not two.)

## main

Overwriting the triangle with its maximum path costs is confusing, because it changes the meaning of the data structure partway through. It would be cleaner to use a separate data structure for the path costs.

There's no reason to duplicate the section that adds path costs.

The nested loops on k and q do the same thing. You probably only want one of them. (I think this causes a bug, too.)

The if (calc > otherCalc) ... calc ... else otherCalc pattern can be written more simply as Math.max(calc, otherCalc).

-
First of all big thank you! You said i could write for (String s : nums) instead of for (int i = 0; i < nums.length; i++) { rowNmbs.add(Integer.parseInt(nums[i])); but when i dont have my i how do i tell what index to add? what do i typ in the "box" in nums[]? What is the difference between java.io.IOException and Exception? The other things i understand! – Olba12 May 18 '14 at 9:49
"It should be a fake class with only static methods..." The technical term is "(static) utility class". – Bobby May 18 '14 at 10:47
You don't need an index when you already have the element: for (String s : nums) { row.add(Integer.parseInt(s)); }. IOException is the subclass of Exception for I/O failures; catching it avoids catching other exceptions you didn't expect, like NumberFormatException from parseInt. – Anonymous May 18 '14 at 15:12
@Bobby: I wanted to make it clear that it was a class serving as a module, not a class for utility purposes. – Anonymous May 18 '14 at 15:41