Project Euler#18: Maximum Paths I: Brute Forced Depth First Search

Question

Problem: enter image description here Data:

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

Here is my code:

String[] s = getText(18).split("\\s");
 int[] a = stringArraytoIntArray(s);
 Stack<Integer> stackOfindices = new Stack<Integer>();
 // stack of indices (actually the path of indices)
 final int maxdepth = 15;
 final int size = maxdepth * (maxdepth + 1) / 2;
 boolean[] treaded = new boolean[size];
 // treaded or not?
 Arrays.fill(treaded, false);// not travelled anywhere, this could be avoided since default values and all that, but for clearance I wrote it
 int max = 1;// maximum is greater than 1
 int depth = 0;// depth to which we have reached
 int sum = a[0];// present sum
 stackOfindices.push(0);// pushing the index 0
 treaded[0] = true;// travelled index 0
 boolean shouldadd = true;// used whether to return or whether add to sum
 // the present number
 // loop:
 do {
 ++depth;// enter a depth
 if (depth != maxdepth) {
 // choose an undiscovered branch and add to sum while pushing to
 // stack
 // two paths possible 0,+1
 for (int i = 0; i <= 2; i++) {// trying children
 if (i == 2) {// if last children
 if (stackOfindices.peek() == size) {
 return max;
 }
 // clearing mechanism which clears treaded array for
 // entries children since we would be reaching some of
 // these children maybe
 // later through different paths and we then want these
 // to be treated as untreaded
 for (int j = 0; j <= 1; j++) {// clear each index of
 // children
 int clearindex = stackOfindices.peek() + depth + j;
 treaded[clearindex] = false;
 }
 depth -= 2;// now move 2 steps up (since we will dive a
 // step at the start so total -1)
 sum -= a[stackOfindices.peek()];// subtract from sum
 stackOfindices.pop();// remove current index
 shouldadd = false;// do not add but return
 break;
 }
 int tryindex = stackOfindices.peek() + depth + i;
 // try these index if not the last one
 if (!treaded[tryindex]) {
 stackOfindices.push(tryindex);// push
 treaded[stackOfindices.peek()] = true;// traversed
 shouldadd = true;// add the number
 break;
 // if found a treadable branch exit checking for a new
 // index
 }
 }
 // add to sum
 if (shouldadd) {
 sum += a[stackOfindices.peek()];
 }
 } else {
 if (stackOfindices.peek() == (size - 1)) {
 break;
 }
 // when no further check with max
 if (sum > max) {
 // System.out.println("="+max);
 max = sum;
 }
 // step back and subtract
 depth -= 2;
 // since it is going to be increased by one at the start of loop
 sum -= a[stackOfindices.peek()];
 stackOfindices.pop();
 }
 } while (true);
 return max;

It is/was actually my first DFS implementation. I am unhappy with:

• Large Size of code. I've seen smaller and concise similar approaches.
• Confusing, even after adding comments.
• Code speed is fine, you can improve it if you want
• Other possible improvements you think could be done.
• Don't try to switch it to another algorithm (the reverse working one)

• rolfl: Seriously: Don't try to switch it to another algorithm (the reverse working one) ??? You know, if you use a different algorithm it will solve a bunch of other problems.... including speed, etc.
• RE60K: @rolfl speed is no problem and I have already implemented the reverse working algorithm in problem 67.
• rolfl: While you are correct that speed may not be the problem, the truth is that the algorithm you chose affects more than just the speed, but the code size, the confusions, and other improvements..... what you are saying is: I have driven this race course with my eyes open, so now I want to drive it with my eyes closed.... what can I do to improve my driving style (but don't tell me to open my eyes because I have done that before!)
• rolfl: See rags-to-riches version.

Answer 1

String[] s = getText(18).split("\\s");
int[] a = stringArraytoIntArray(s);
Stack<Integer> stackOfindices = new Stack<Integer>();
// stack of indices (actually the path of indices)
final int maxdepth = 15;
final int size = maxdepth * (maxdepth + 1) / 2;
boolean[] treaded = new boolean[size];
// treaded or not?
Arrays.fill(treaded, false);// not travelled anywhere, this could be avoided since default values and all that, but for clearance I wrote it
int max = 1;// maximum is greater than 1
int depth = 0;// depth to which we have reached
int sum = a[0];// present sum
stackOfindices.push(0);// pushing the index 0
treaded[0] = true;// travelled index 0
boolean shouldadd = true;// used whether to return or whether add to sum
 // the present number

In that lot I see the following variables s and a, neither of which is commented.... but then also I see max, depth and sum ... which are commented. Why comment the things which don't need it, and not comment the things which do need it?.

In addition, your comments are inconsistent. Sometimes they are on a new line, sometimes they are not. Regardless, where they are at the moment makes the code harder to read, not easier.

Your stackOfIndices is an overkill situation as well... Stack is a synchronized collection (it extends Vector) and as a result carries unnecessary overhead. In addition, the conversion to/from Integer for the indices is awkward. The autoboxing helps, but not much.

It would be much better to simply have an int[] array as a stack.

Your parsing of the Triangle in to a 1D array (int[]) also makes the remaining code cumbersome. Using an int[][] instead would help a lot.

Finally, why do you hard-code the max depth at 15? Whenever you find yourself coding in constants like that you know you have made a mistake somewhere....

The algorithm is not great either, and that affects pretty much everything else.