In this post, we will solve The Tree Of Life HackerRank Solution. This problem (The Tree Of Life) is a part of HackerRank Functional Programming series.
Task
This challenge asks you to write a program which computes cellular automata state in a nonstandard world. Instead of each cell living on a grid it lives on a binary tree.
Overview
A Cellular Automaton (CA) is a set of cells which evolve together in stages. At each stage, a given cell changes according to a given rule which depends upon values of cells in its neighborhood.
Commonly, CAs consist of a grid of cells so that each cell has a neighborhood of 8 cells.
123
  
4X5
  
678
The dynamics of a CA on a grid is thus determined by a way of mapping all 9 of the values near X
to a new value which X
takes in the next iteration.
rule(v(1), ..., v(8), v(X)) = ...
An example grid CA is Conway’s Game of Life which stores boolean values at each cell and has the following update rule:
Consider the sum N = v(1) + ... + v(8).
If v(X) then
If N < 2 : return False
If N > 3 : return False
otherwise : return True
else
If N == 3 : return True
A Game is played by picking an initial state of the grid and updating each cell according to the given rule repeatedly. Conway’s rule produces startlingly interesting behavior for many initial states—in fact, given an infinite grid there exist starting states which compute an encoding of any computable function. In other words, the Game of Life is Turing complete.
Rule encoding
CA update rules can be complex, but oftentimes they are serialized to a simple format.
Most of the time there are only finitely many possible CA rules. Rules over binaryvalued cells are usually assigned numbers by extending an ordering on the neighborhood of cells. For example, if we consider a linear automaton then the neighborhood of a cell looks like
1X2
a rule takes the form
(v(1), v(X), v(2)) > {0, 1}
and so if we assign an order to the input space we can write any such rule as a binary number
111 110 101 100 011 010 001 000

0 0 0 1 1 1 1 0 "Rule 30"
0 1 1 0 1 1 1 0 "Rule 110"
Clearly there are 256 such rules and so we can read any 8bit number as a rule specification for a linear CA over binary values.
Problem statement
Instead of computing a CA on a grid, we’ll compute a CA on a binary tree. The formulation of CAs above does not depend upon arranging the cells in a grid—we can pick any topology so long as there’s a notion of the neighborhood of a cell.
So the task is to build a CA evaluator on binary trees. A conformant program should take a serialized binary tree and a rule (encoded as an integer) as input. Then, given a sequence of counts of iteration steps and associated “paths” into the tree the evaluator must interactively print out the binary value stored in the tree at the given path after the specified number of steps.
Importantly, while paths are guaranteed to always be valid, step counts are not guaranteed to always be positive. We may ask you travel back in time—though never beyond the beginning of time.
1. Parsing trees
The initial state of the binary tree automaton is a nonempty binary tree. A conformant program should parse its initial state from a format like as follows
X > A leaf containing a single "on" cell
. > A leaf containing a single "off" cell
(X . .) > A branch holding an "off" with
An "on" leaf as the left subtree
An "off" leaf as the right subtree
(X . (X . .)) > A branch with an "off" cell with
An "on" leaf as the left subtree
The prior example as the right subtree
2. Parsing rules
The behavior of the automaton is governed by a choice of update rule operating on the 4cell (unbiased) neighborhood of each cell. There are thus 2^(2^4) = 2^16 = 65536 possible rules and a conformant program must determine the rule in force by evaluating a given 16 bit code given as an unsigned integer.
In pictures, the (maximal) neighborhood of a cell in a binary tree looks like and is numbered like
(1)

(3)
/ \
(2) (4)
and we’ll encode each rule as a bigendian 16bit word beginning with the big encoding the “all on neighborhood”
1111 1110 1101 1100 1011 1010 1001 1000 ...
_ _ _ _ _ _ _ _
Here are a few examples:
Rule 7710: (An analogue of Rule 30)
(X X X X) > .
(X X X .) > .
(X X . X) > .
(X X . .) > X
(X . X X) > X
(X . X .) > X
(X . . X) > X
(X . . .) > .
(. X X X) > .
(. X X .) > .
(. X . X) > .
(. X . .) > X
(. . X X) > X
(. . X .) > X
(. . . X) > X
(. . . .) > .
Rule 42354:
(X X X X) > X
(X X X .) > .
(X X . X) > X
(X X . .) > .
(X . X X) > .
(X . X .) > X
(X . . X) > .
(X . . .) > X
(. X X X) > .
(. X X .) > X
(. X . X) > X
(. X . .) > X
(. . X X) > .
(. . X .) > .
(. . . X) > X
(. . . .) > .
3. Parsing Paths
Paths are pointers into a tree. The simplest path is the empty path which points to the root value of the tree. From there, they are merely sequences of directions, left (denoted by the single character <
) and right (denoted by >
). Some example paths are
[<><<<><>>]
[>>><<><]
[]
[><<<<<<<<>]
where the third example was the empty path.
Full input specification
A conformant program works as follows. First, it reads two lines setting up the initial state: a rule integer and a serialized binary tree. The next line contains a natural number, n (1 <= n <= 1100), indicating the number of queries that will be asked.
Then, it begins to execute the n queries. It reads a single line indicating the first query and must immediately print out the value stored at the path in the tree after the indicated number of rule iterations followed by a newline. For cells which are “on”, emit a X
and for those which are “off” emit a .
. This repeats n1 more times.
An example transcript follows where lines sent from the server are preceeded by >
and lines returned from the client are preceeded by <
.
> 42354
> ((. X (. . .)) . (X . (. X X)))
> 6
> 0 []
< .
> 2 [><]
< X
> 0 [><]
< X
> 0 [<>]
< .
> 1 [><]
< X
> 0 [<>]
< X
For rule r
, number of cases n
, and step increments s
we have 0 <= r <= 65535
, 1 <= n <= 1100
, and 1000 <= s <= 1000
.
To see a bit of what’s going on behind the scenes, here are snapshots of the first 5 tree states at times [0, 4]
0  ((. X (. . .)) . (X . (. X X)))
1  ((X . (. X .)) X (. X (X . X)))
2  ((. X (X . X)) . (X X (. X .)))
3  ((X . (. X .)) X (X . (X X X)))
4  ((. X (X . X)) . (. X (X . X)))
Sample Input
42354
((. X (. . .)) . (X . (. X X)))
6
0 []
2 [><]
0 [><]
0 [<>]
1 [><]
0 [<>]
Sample Output
.
X
X
.
X
X
Solution – The Tree Of Life – HackerRank Solution
Scala
import java.util.Scanner import scala.annotation.tailrec trait Tree { def value: Boolean def applyRule(rule: Int, parentValue: Boolean = false): Tree @tailrec final def changeState(rule: Int, stepCount: Int): Tree = if (stepCount == 0) this else applyRule(rule).changeState(rule, stepCount  1) def atPath(path: List[Char]): Boolean protected def nextValue(rule: Int, parentValue: Boolean, leftValue: Boolean, rightValue: Boolean): Boolean = { def toBit(value: Boolean, index: Int) = (if (value) 1 else 0) << index val bit = toBit(parentValue, 3)  toBit(leftValue, 2)  toBit(value, 1)  toBit(rightValue, 0) (rule & (1 << bit)) != 0 } } object Tree { def parse(s: List[Char]): Tree = { def inner(s: List[Char]): (Tree, List[Char]) = s match { case Nil => (Empty, Nil) case c :: cs => c match { case '.' => (Leaf(false), cs) case 'X' => (Leaf(true), cs) case '(' => val (left, afterLeft) = inner(cs) val (root, afterRoot) = inner(afterLeft) val (right, afterRight) = inner(afterRoot) (Node(root.value, left, right), afterRight) case _ => inner(cs) } } inner(s)._1 } } case class Node(value: Boolean, left: Tree, right: Tree) extends Tree { override def applyRule(rule: Int, parentValue: Boolean): Tree = Node( nextValue(rule, parentValue, left.value, right.value), left.applyRule(rule, value), right.applyRule(rule, value) ) override def atPath(path: List[Char]): Boolean = path match { case ']' :: _ => value case c :: cs => (if (c == '<') left else right).atPath(cs) case Nil => throw new Exception("Wrong path") } } case class Leaf(value: Boolean) extends Tree { override def applyRule(rule: Int, parentValue: Boolean): Tree = Leaf( nextValue(rule, parentValue, leftValue = false, rightValue = false) ) override def atPath(path: List[Char]): Boolean = path match { case ']' :: _ => value case _ => throw new Exception("Wrong path") } } object Empty extends Tree { override def value: Boolean = throw new Exception("Value of empty tree") override def applyRule(rule: Int, parentValue: Boolean): Tree = this override def atPath(path: List[Char]): Boolean = throw new Exception("atPath of empty tree") } case class Rule(n: Int) object Solution { def main(args: Array[String]): Unit = { val sc = new Scanner(System.in) val rule = sc.nextInt sc.nextLine val s = sc.nextLine val root = Tree.parse(s.toList) val n = sc.nextInt case class Query(initialIndex: Int, time: Int, path: List[Char]) @scala.annotation.tailrec def readQueries(rest: Int, time: Int, acc: List[Query]): List[Query] = if (rest == 0) acc else { val stepCount = sc.nextInt val path = sc.nextLine.toList.drop(2) val nextTime = time + stepCount readQueries(rest  1, nextTime, Query(n  rest, nextTime, path) :: acc) } val queries = readQueries(n, 0, Nil).sortBy(_.time) sc.close() case class Answer(initialIndex: Int, value: Boolean) case class Accumulator(tree: Tree, time: Int, answers: List[Answer]) val accumulator = queries.foldLeft(Accumulator(root, 0, Nil))((acc, query) => { val tree = acc.tree.changeState(rule, query.time  acc.time) Accumulator(tree, query.time, Answer(query.initialIndex, tree.atPath(query.path)) :: acc.answers) }) println(accumulator.answers.sortBy(_.initialIndex).map(v => if (v.value) 'X' else '.').mkString("\n")) } }
Note: This problem (The Tree Of Life) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.