0
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – rolfl Jun 9 '15 at 16:54
  • \$\begingroup\$ @rolfl speed is no problem and I have already implemented the reverse working algorithm in problem 67. \$\endgroup\$ – RE60K Jun 9 '15 at 17:09
  • 3
    \$\begingroup\$ 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!) \$\endgroup\$ – rolfl Jun 9 '15 at 17:11
  • 1
    \$\begingroup\$ See rags-to-riches version. \$\endgroup\$ – rolfl Jun 9 '15 at 17:40
4
\$\begingroup\$
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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.