Recently, I found this article on Java Lobby - Best Interview Question I've seen. This article was referring to a question posted by one recruiting agency.

While we can argue that it really is best question, but you have to give credit to the ingenuity in-terms of creating very simple but automated means of finding out if you got the correct answer for the puzzle. The recruiting agency created one email account with id equal to the correct answer. So, if you got the correct answer, you will not have your email bounced back.

Anyway, the problem sounded interesting to me so thought of giving it a shot. After few bounced mails, I finally got the correct answer as confirmed by my successful delivery of my mail (no bounce back).

Reading through the comments for the posting, I found out about interesting project - http://projecteuler.net/, which is hosting lot of similar puzzles. The puzzle number 18 and 67 happen to be similar to the one posted by the recruiting agency. If you dig Internet you will find lot of explanation and solution to the puzzle.

The problem defined here is also called Critical Path Method (CPM), used in project management for project duration estimation for execution of number of dependent tasks.



One way to solve such problem is brute force. But that would not scale beyond a certain depth of tree. For example, noting the following comment from Euler Problem 67 (a tree with depth of 100 rows):

If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all.

Such problems are best solved if you work backwards. The logic I followed was starting from second last row, find the max of two adjacent values (of next row that) can be reached. Once we find the max, for each item of the row, add the max value to the row value. This will eliminate the last row. Now, we can work our way backwards, i.e to the top. Note that as we move upwards the triangles, the number of rows reduces, till we reach the top. Once we reach 2nd row from top, adding the top value to the max of two values, of the 2nd row, we get our answer.

Following is complete solution. You can click here to download the source code.




tbody {color:blue;height:50px} package euler;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Scanner;

public class EulerProblem18_67 {

/*
* the logic is that starting from second last row, find the max
* of two adjacent values (of next row that) can be reached. Once we find the max,
* for each item of the row, add the max value to the row value. This will
* eliminate the last row.
* Now, we can work our way backwards, i.e to the top. Note that as we move
* upwards the triangles, the number of rows reduces, till we reach the top.
* Once we reach 2nd row from top, adding the top value to the max of two values,
* of the 2nd row, we get our answer.
*/
private static void findMax(int[][] triangle, int depth) {
int[] previous = null;
for(int i = 1; i < depth; i++) {
int[] last = triangle[depth - i];
previous = calculateRowMaximal(triangle[(depth - i) - 1], last);
printValues(previous);
}
System.out.println("result = " + previous[0]);
}

private static int[] calculateRowMaximal(int[] previous, int[] last) {
for (int i = 0; i < previous.length; i++) {
previous[i] = previous[i] + (Math.max(last[i], last[i + 1]));
}
return previous;
}

private static void printValues(int[] values) {
System.out.println();
for (int i : values) {
System.out.print("\t" + i);
}
}

private static int[][] getTriangle(String fileName, int depth) throws Exception {
int[][] triangle = new int[depth][];
FileReader fr = new FileReader(fileName);
BufferedReader br = new BufferedReader(fr);

String s;
int i = 0;
while ((s = br.readLine()) != null) {
triangle[i] = new int[i + 1];
int j = 0;
Scanner tokens = new Scanner(s);
while (tokens.hasNext()) {
int value = tokens.nextInt();
triangle[i][j++] = value;
}
i++;
}

return triangle;
}

public static void main(String args[]) throws Throwable {
String fileName = "src//euler//triangle_euler67.txt";
int depth = 100;
int[][] triangle = getTriangle(fileName, depth);
findMax(triangle, depth);
}
}




Also, I ended up creating one applet to visually show the solution (works on Firefox and IE, not Chrome). You can click run to let the solution run to the end. Or, you can click pause/resume and step to step through each step and see what is going on for easier understanding.

Note that this applet uses tree of 15 rows and data is taken from Problem 18 of Euler Project, but I changed few entries so that you don't just take the answer and cheat with Euler project. Therefore, by design, the answer obtained is NOT the correct answer for Euler problem 18.Of course you can download the code and run to get the correct answer, but that would require some effort and if you are willing to do that, why not just solve the puzzle on your own!
























Read More about [Euler Problem 18 and 67...