Euler Problem 18 and 67

Originally posted on May 30, 2010

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 the 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 a few bounced emails, I finally got the correct answer as confirmed by the successful delivery of my mail (no bounce back).

Reading through the comments for the posting, I found out about Euler Project which is hosting a 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 the Internet you will find a lot of explanations and solutions to the puzzle.

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

One way to solve such a problem is brute force. But that would not scale beyond a certain depth of the tree. For example, noting the following comment from Euler Problem 67 (a tree with a 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 backward. 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 backward, 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 the top, adding the top value to the max of two values, of the 2nd row, we get our answer.

The following is a complete solution. You can click here to download the source code.

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 = "files//triangle_euler67.txt";
   int depth = 100;
   int[][] triangle = getTriangle(fileName, depth);
   findMax(triangle, depth);
  }
 }