Problem:Data:7595 6417 47 8218 35 87 1020 04 82 47 6519 01 23 75 03 3488 02 77 73 07 63 6799 65 04 28 06 16 70 9241 41 26 56 83 40 80 70 3341 48 72 33 47 32 37 16 94 2953 71 44 65 25 43 91 52 97 51 1470 11 33 28 77 73 17 78 39 68 17 5791 71 52 38 17 14 91 43 58 50 27 29 4863 66 04 68 89 53 67 30 73 16 69 87 40 3104 62 98 27 23 09 70 98 73 93 38 53 60 04 23Here 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 wantOther possible improvements you think could be done.Don't try to switch it to another algorithm (the reverse working one)
Project Euler#18: Maximum Paths I: Brute Forced Depth First Search
java;programming challenge;depth first search
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 itint max = 1;// maximum is greater than 1int depth = 0;// depth to which we have reachedint sum = a[0];// present sumstackOfindices.push(0);// pushing the index 0treaded[0] = true;// travelled index 0boolean shouldadd = true;// used whether to return or whether add to sum                         // the present numberIn 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.