This morning after waking up I read Why I Write a Data Science Blog by Rebecca Vickery. The subject of the post is to summarize the benefits that writing a blog, in her case regarding Data Science, provides her with benefits that help her improve towards her goals, and helps others starting a Data Science career with topics and situations that they might / will encounter at work.
I agree with her comments but would like to add that the idea of explaining 
some topic on writing is a great technique and applies to any type of subject. You do not know what you cannot explain. It is a simple as that. That is the reason I spend a couple hours every day reading, experimenting and then writing about what I have learned. I have tried to apply several of Richard Feynman techniques to my daily life. Hope they are working :o)
Yesterday selected from the HackerRank site the Java Visitor Pattern problem. Very interesting but I spend a great amount of time, not dealing with the Visitor pattern, but building the binary tree.
Please note that the Visitor pattern applies to any object oriented programming language. In this post the language used is Java, but any other language (e.g., C++, C#, etc) would do.
The problems calls for you to first populate a tree and then work on three different visitor patterns. They all require visiting nodes, computing some value, and retrieving the results when done. The sequence is very well expressed in the test scaffolding as follows:
/*
* Test scaffolding
*/
public static void main(String[] args) {
Tree root = solve();
SumInLeavesVisitor vis1 = new SumInLeavesVisitor();
ProductOfRedNodesVisitor vis2 = new ProductOfRedNodesVisitor();
FancyVisitor vis3 = new FancyVisitor();
root.accept(vis1);
System.out.println();
root.accept(vis2);
System.out.println();
root.accept(vis3);
System.out.println();
int res1 = vis1.getResult();
int res2 = vis2.getResult();
int res3 = vis3.getResult();
System.out.println(res1);
System.out.println(res2);
System.out.println(res3);
}
The SumInLeavesVisitor() as the name very eloquently suggests, requires computing a sum of the values of leaf nodes. The tree has regular nodes and leaf nodes. In this case sum only the values of the leaf ones.
Each node has a color assigned. In our test case we have RED and GREEN nodes. The diagram in the requirements provides a good representation of the test data. In the ProductOfRedNodesVisitor() we need to compute the product which is initialized to 1 and the current node and to avoid overflow we need to apply the modulus operator using the value 1000000007. Our test case is quite simple and small, but who knows what the hidden test cases do.
Finally, we have to implement the FancyVisitor() class. In this case we need to take into consideration that depth of the node and color to aggregate two different values which will be combined when the results are requested.
My solution was implemented using Java and the Eclipse IDE. The definition of the abstract classes follows:
/*
*
*/
abstract class Tree {
private int value;
private Color color;
private int depth;
public Tree(int value, Color color, int depth) {
this.value = value;
this.color = color;
this.depth = depth;
}
public int getValue() {
return value;
}
public Color getColor() {
return color;
}
public int getDepth() {
return depth;
}
public abstract void accept(TreeVis visitor);
}
/*
*
*/
abstract class TreeVis {
public abstract int getResult();
public abstract void visitNode(TreeNode node);
public abstract void visitLeaf(TreeLeaf leaf);
}
We can see that value, color and depth are available.
We need to implement getResults() to compute and retrieve the results, visitNode() to perform the operations on nodes and finally visitLeaf() to perform operations on leaf nodes.
My implementation follows:
/*
*
*/
class TreeNode extends Tree {
private ArrayList<Tree> children = new ArrayList<>();
public TreeNode(int value, Color color, int depth) {
super(value, color, depth);
}
public void accept(TreeVis visitor) {
visitor.visitNode(this);
for (Tree child : children) {
child.accept(visitor);
}
}
public void addChild(Tree child) {
children.add(child);
}
// ???? ????
public String toString() {
return "" + this.getValue() + " " + this.getColor() + " " + this.getDepth();
}
}
/*
*
*/
class TreeLeaf extends Tree {
public TreeLeaf(int value, Color color, int depth) {
super(value, color, depth);
}
public void accept(TreeVis visitor) {
visitor.visitLeaf(this);
}
// ???? ????
public String toString() {
return "" + this.getValue() + " " + this.getColor() + " " + this.getDepth();
}
}
/*
* Implementation
*/
class SumInLeavesVisitor extends TreeVis {
private int sumOfLeaf = 0;
// **** get result ****
public int getResult() {
return sumOfLeaf;
}
// **** visit node ****
public void visitNode(TreeNode node) {
// ???? ????
System.out.println("node: " + node.toString());
}
// ***** visit leaf ****
public void visitLeaf(TreeLeaf leaf) {
// ???? ????
System.out.println("leaf: " + leaf.toString());
sumOfLeaf += leaf.getValue();
}
}
/*
* Implementation
*/
class ProductOfRedNodesVisitor extends TreeVis {
private long product = 1;
private final int mod = 1000000007;
// **** get result ****
public int getResult() {
return (int)product;
}
// **** visit node ****
public void visitNode(TreeNode node) {
if (node.getColor() == Color.RED) {
// ???? ????
System.out.println("node: " + node.toString());
// **** ****
product = (product * node.getValue()) % mod;
}
}
// **** visit leaf ****
public void visitLeaf(TreeLeaf leaf) {
if (leaf.getColor() == Color.RED) {
// ???? ????
System.out.println("leaf: " + leaf.toString());
// **** ****
product = (product * leaf.getValue()) % mod;
}
}
}
/*
* Implementation
*/
class FancyVisitor extends TreeVis {
private int evenDepthNodeSum = 0;
private int greenLeavesSum = 0;
// **** get result ****
public int getResult() {
return Math.abs(evenDepthNodeSum - greenLeavesSum);
}
// **** visit node ****
public void visitNode(TreeNode node) {
if (node.getDepth() % 2 == 0) {
// ???? ????
System.out.println("node: " + node.toString());
// **** ****
evenDepthNodeSum += node.getValue();
}
}
// ***** visit leaf ****
public void visitLeaf(TreeLeaf leaf) {
if (leaf.getColor().equals(Color.GREEN)) {
// ???? ????
System.out.println("leaf: " + leaf.toString());
// **** ****
greenLeavesSum += leaf.getValue();
}
}
}
I tend to use print statements to make sure the code is working as expected. In some cases I remove most of the print cases. I have left some which I believe will be beneficial to you. Remember not to submit code to HackerRank with additional print statements. It will disqualify your submission because the parser does not expect them.
The doe used to build the tree follows:
// **** ****
private static int[] values = null;
private static Color[] colors = null;
private static HashMap<Integer, Set<Integer>> edges = new HashMap<>();
/*
*
*/
private static void connectEdge(Tree parent, Integer connectedNode) {
// **** ****
if (edges.get(connectedNode).size() == 0) {
((TreeNode) parent).addChild(
new TreeLeaf(values[connectedNode - 1], colors[connectedNode - 1], parent.getDepth() + 1));
return;
}
// **** ****
Tree node = new TreeNode(values[connectedNode - 1], colors[connectedNode - 1], parent.getDepth() + 1);
((TreeNode)parent).addChild(node);
// **** ****
for (Integer child : edges.get(connectedNode)) {
// System.out.println("child: " + child);
edges.get(child).remove(connectedNode);
connectEdge(node, child);
}
}
/*
* read the tree from STDIN and return its root as a return value of this function
*/
public static Tree solve() {
// **** ****
Tree root = null;
// **** ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** ****
int n;
try {
// **** read number of notes ****
n = Integer.parseInt(br.readLine());
// System.out.println("n: " + n);
// **** allocate values and colors ****
values = new int[n];
colors = new Color[n];
// **** read in the values (as strings) ****
String[] valueStrings = br.readLine().split(" ");
// System.out.println("valueStrings: " + Arrays.toString(valueStrings));
// **** read in the colors (as strings) ****
String[] colorStrings = br.readLine().split(" ");
// System.out.println("colorStrings: " + Arrays.toString(colorStrings));
// **** assign the values and colors ****
for (int i = 0; i < n; i++) {
values[i] = Integer.parseInt(valueStrings[i]);
colors[i] = colorStrings[i].equals("0") ? Color.RED : Color.GREEN;
}
// System.out.println("values: " + Arrays.toString(values));
// System.out.println("colors: " + Arrays.toString(colors));
// **** check if a single node has been specified ****
if (n == 1)
return new TreeLeaf(values[0], colors[0], 0);
// **** populate the tree edges ****
for (int i = 0; i < (n - 1); i++) {
// **** read the next edge ****
String[] edgeStrings = br.readLine().split(" ");
int u = Integer.parseInt(edgeStrings[0]);
int v = Integer.parseInt(edgeStrings[1]);
// System.out.println("u: " + u + " v: " + v);
// **** ****
if (!edges.containsKey(u))
edges.put(u, new HashSet<Integer>());
// **** ****
if (!edges.containsKey(v))
edges.put(v, new HashSet<Integer>());
// **** ****
edges.get(u).add(v);
edges.get(v).add(u);
}
// System.out.println("edges: " + edges.toString());
// **** close the buffer reader ****
br.close();
} catch (NumberFormatException | IOException e) {
e.printStackTrace();
}
// **** instantiate the tree root ****
root = new TreeNode(values[0], colors[0], 0);
// **** connect the nodes ****
for (Integer connectedNode : edges.get(1)) {
// **** ****
edges.get(connectedNode).remove(1);
// System.out.println("connectedNode: " + connectedNode.toString());
// **** ****
connectEdge(root, connectedNode);
}
// **** ****
return root;
}
The code to build the tree took as much time as the one for the three visitor classes. The complexity was due to the way the data was presented and the edges.
If you want to read more about the Visitor pattern I suggest reading and experimenting with VISITOR in chapter 5 Design Patterns Elements of Reusable Object-Oriented Software by the gang of four and chapter 28 Visitor in Agile Software Development Principles, Patterns and Practices by Robert C. Martin.
There are several advantages of implementing a visitor pattern over modifying the base class. You can read about the pros and cons on both books mentioned in the previous paragraph.
The enhanced console output from this solution follows:
5 4 7 2 5 12 0 1 0 0 1 1 2 1 3 3 4 3 5 node: 4 RED 0 leaf: 7 GREEN 1 node: 2 RED 1 leaf: 5 RED 2 leaf: 12 GREEN 2 node: 4 RED 0 node: 2 RED 1 leaf: 5 RED 2 node: 4 RED 0 leaf: 7 GREEN 1 leaf: 12 GREEN 2 24 40 15
The code displays when node and leaf nodes are visited and the values they hold. It seems that we can follow how the values are computed and stored to later be called by invoking the getResults() for each implementation.
Hope you enjoyed this post. Give the challenge a try. You can always learn something new or at least refresh on known concepts. I always find it interesting when one is asked to implement a pattern or algorithm without having access to their IDE and Google. What you need to need to know is that there are patterns and a general idea on some of them. In my opinion developing code in the vacuum is something no one should ever attempt. The waterfall model clearly indicated that is not the way to develop software.
If you wish to see my complete solution, you can find it in my GitHub repository.
If you have comments and / or questions regarding this or any other post in this blog, or if you are in need of consulting / development help, please feel free to leave me a note below. Requests will not be made public.
Keep on reading and experimenting; it is the only way to learn.
John
Follow me on Twitter: @john_canessa