Project Euler problems 18/67: maximum path sum

Question

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.io.FileReader;
import java.util.ArrayList;
public class EighteenNSixtyseven {
@SuppressWarnings("rawtypes")
public ArrayList<ArrayList> readFile() {
 ArrayList<ArrayList> nodeList = new ArrayList<ArrayList>();
 BufferedReader reader = null;
 try {
 reader = new BufferedReader(new FileReader("Triangle.txt"));
 String tmp = reader.readLine();
 while (tmp != null) {
 String[] nums = tmp.split("\\s+");
 ArrayList<Integer> nmb = new ArrayList<Integer>();
 for (int i = 0; i < nums.length; i++) {
 nmb.add(Integer.parseInt(nums[i]));
 }
 nodeList.add(nmb);
 // im adding an ArrayList to the ArrayList
 tmp = reader.readLine(); // where the first ArrayList index is the 
 } // the specific row and the other ArrayList
 // containing the numbers
 } catch (Exception e) {
 e.printStackTrace();
 } finally {
 try {
 reader.close();
 } catch (Exception e) {
 e.printStackTrace();
 }
 }
 return nodeList;
}
public static void main(String[] args) {
 EighteenNSixtyseven ad = new EighteenNSixtyseven();
 long start = System.currentTimeMillis(); // starting time
 @SuppressWarnings("rawtypes") // eclipse suggested this??? Why?
 ArrayList<ArrayList> list = ad.readFile(); // reading the file with numbers in triangle
 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!

Answer 1

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!

• martijnn2008: yup no DP but weighted shortest path :) The title says it all "path"

Answer 2

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.

readFile

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).

• Olba12: 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!
• Bobby: "It should be a fake class with only static methods..." The technical term is "(static) utility class".
• Anonymous: 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: @Bobby: I wanted to make it clear that it was a class serving as a module, not a class for utility purposes.