Euler Problem 18 and 67

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.

/\*\*
 \* Copyright (c) 2010-2020 Malkit S. Bhasin. All rights reserved.
 \* 
 \* All source code and material on this Blog site is the copyright of Malkit S.
 \* Bhasin, 2010 and is protected under copyright laws of the United States. This
 \* source code may not be hosted on any other site without my express, prior,
 \* written permission. Application to host any of the material elsewhere can be
 \* made by contacting me at mbhasin at gmail dot com
 \* 
 \* I have made every effort and taken great care in making sure that the source
 \* code and other content included on my web site is technically accurate, but I
 \* disclaim any and all responsibility for any loss, damage or destruction of
 \* data or any other property which may arise from relying on it. I will in no
 \* case be liable for any monetary damages arising from such loss, damage or
 \* destruction.
 \* 
 \* I further grant you ("Licensee") a non-exclusive, royalty free, license to
 \* use, modify and redistribute this software in source and binary code form,
 \* provided that i) this copyright notice and license appear on all copies of
 \* the software;
 \* 
 \* As with any code, ensure to test this code in a development environment
 \* before attempting to run it in production.
 \* 
 \* @author Malkit S. Bhasin
 \* 
 \*/

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//dzone//javalobby//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, not IE or 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!

Comments:

nicely done

Posted by guest on April 23, 2011 at 08:14 PM PDT #

it is a great way to solve it. I rewrite it with python and it works perfectly!

Posted by guest on May 05, 2012 at 12:52 AM PDT #

Post a Comment:
  • HTML Syntax: NOT allowed
About

Malkit works in software development at Oracle, Inc. working in Oracle Business Process Manager, part of Oracle Fusion Middleware. Malkit came to Oracle through Sun Microsystems acquisition, living and working in Los Angeles, California.

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today