Was talking with a software developer regarding how to determining the max path of a pyramid. We discussed a solution but it is nice to see it come to live.
The following figure illustrates the structure of the pyramid:
The requirements are that the height be in the range 1 <= height <= 25. The tree is complete. There are no missing nodes. That implies that the base contains leaf nodes (no children). The values for the nodes should arbitrarily be in the range 1 <= val <= 100.
The challenge is to determine the max value that one can get starting at the root descending one level down at a time. In the case illustrated the nodes in yellow indicate the path that was used by the solution to achieve the max value of 29.
The following is a screen capture of the console of my Eclipse IDE with the pyramid populated as illustrated in the diagram:
3
2 5
3 2 5
1 2 7 8
8 8 9 5 6
max: 29
I decided to display the values of the nodes (could make them look prettier but that was not the point of the discussion) to be able to trace and verify the solution. In this example the height and width of the pyramid is 5. I decided to use a max value of 9 for the nodes because if I used two digits the numbers would not fit inside the nodes with the font I was using (I made the diagram to be able to describe the goal of the solution).
My code in Java follows:
import java.util.Random;
class Node {
// **** ****
int val;
Node left;
Node right;
/**
* constructor
*/
public Node(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
public class Solution {
// **** ****
static final int MAX_VAL = 9;
static final int HEIGHT = 5;
/**
* Get the max path in the pyramid
*/
static int MaxPath(Node node) {
// **** check if we are done ****
if (node == null) {
return 0;
}
// **** left child ****
int leftVal = MaxPath(node.left);
// **** right child ****
int rightVal = MaxPath(node.right);
// **** ****
return Math.max(leftVal, rightVal) + node.val;
}
/**
* build the pyramid
*/
static Node BuildPyramid(int height) {
Random rand = new Random(System.currentTimeMillis());
Node[][] frame = new Node[height][height];
// **** allocate nodes ****
for (int row = 0; row < height; row++) {
for (int col = 0; col <= row; col++) {
// **** allocate a node ****
Node node = new Node(1 + rand.nextInt(MAX_VAL));
frame[row][col] = node;
// **** display node value ****
System.out.printf(“%3d”, node.val);
}
System.out.println();
}
// **** build the pyramid ****
for (int row = 0; row < (height – 1); row++) {
for (int col = 0; col <= row; col++) {
// **** set left child ****
frame[row][col].left = frame[row + 1][col];
// **** set right child ****
frame[row][col].right = frame[row + 1][col + 1];
}
}
// **** ****
return frame[0][0];
}
/**
* test code
* @param args
*/
public static void main(String[] args) {
// **** build the pyramid ****
int height = HEIGHT;
Node pyramid = BuildPyramid(height);
// **** get the value of the max path ****
System.out.println(“max: ” + MaxPath(pyramid));
}
}
The following run is using larger values [1 : 17] and more levels [11]:
6
3 1
6 9 9
1 11 11 2
4 17 13 13 17
15 9 15 17 17 17
5 16 9 17 5 12 12
10 8 2 7 14 8 10 10
8 15 9 8 1 14 5 1 2
9 3 16 1 6 5 13 6 17 6
4 9 8 2 3 16 1 17 16 5 7
max: 136
If you have comments or questions regarding this or any other entry in this blog please do not hesitate and send me a message. Will reply as soon as possible and will not use your name unless you allow me to do so.
John
john.canessa@gmail
Follow me on Twitter: @john_canessa