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!