The Tree of Life: Top Level Code

We have built the tools that we will use to solve this problem in previous three posts, now it’s time to put them together into an application.

Let’s start by reading the input:

def main(args: Array[String]) {
    val rule = Rule(StdIn.readInt())
    val tree = readTree(StdIn.readLine().toList)
    val queryCount = StdIn.readInt()
}

This of course assumes valid input. I said this a few times already. It’s important because in a real life application we must validate all input. Also I would definitely do TDD in a real life situation. I have no smart excuses for you, I got lazy and go pretty much full cowboy during these challenges. I did however some quick and dirty testing during development.

Moving on… We have read the rule, the tree and the number of queries to be sent. Now we need to go into a REPL-like loop to read each query and print out the output. It is similar to a REPL also because there is state, each query is executed with the version of tree evolved in the last query is used as a starting point. In other words if we do 3 evolutions in the first query and 2 evolutions in the second query we would have a 5th generation (counting from zero) tree to start with when third query is read.

One way to add this state is:

def main(args: Array[String]) {
    val rule = Rule(StdIn.readInt())
    val originalTree = readTree(StdIn.readLine().toList)
    val queryCount = StdIn.readInt()
    var tree = originalTree
}

Notice that tree is a var above. Even though TreeNode implementations are immutable, we can achieve statefulness by reassigning tree variable.

This would have worked if steps weren’t defined with these constraints; -1000 <= s <= 1000. I have read a comment about timeouts[1], and figured it would be prudent to cache (some) generations. So I have created a mutable object:

class TreeEvolutions(private val rule: Rule, private val initialTree: TreeNode) {
    def move(steps: Int): TreeNode = ???
}

I will provide implementation of TreeEvolutions later. But let’s continue building the code top-down

def main(args: Array[String]) {
    val rule = Rule(StdIn.readInt())
    val tree = readTree(StdIn.readLine().toList)
    val queryCount = StdIn.readInt()
    val treeEvolutions = new TreeEvolutions(rule, tree)
    Range(0, queryCount).foreach { _ => query(treeEvolutions) }
}

Once we do our initial setup, we call query function queryCount times. As you can guess, query reads the input, mutates treeEvolutions accordingly, prints out desired output and doesn’t return anything useful. I am not sure if this is the best design but since this code is instable, I think it’s acceptable. Here is the implementation of query:

def query(treeEvolutions: TreeEvolutions) {
    val inputRe = """(-?\d+) \[([<>]*)\]""".r
    val input = StdIn.readLine()
    val (steps, path) = input match {
        case inputRe(s, p) => (s.toInt, p.toList)
    }
    println(walk(treeEvolutions.move(steps), path))
}

First thing I would refactor would be to move inputRe outside, to make sure a new regular expression object is not created every time this function is called. But this is the version I have submitted. Again we assume valid inputs.

The highlighted line actually does all the work:

1. It evolves the tree steps times.
2. TreeEvolutions is mutable, it will remember its state later.
3. move returns the result of the last evolution.
4. walk is called with our (new) tree data and path.
5. Result is printed.

The only missing piece now is the TreeEvolutions’ implementation:

import scala.collection.mutable.{ HashMap => MutableHashMap }


class TreeEvolutions(private val rule: Rule, private val initialTree: TreeNode) {
    var currentGeneration = 0
    val cache: MutableHashMap[Int, TreeNode] = MutableHashMap(0 -> initialTree)

    def move(steps: Int): TreeNode = this.synchronized {
        currentGeneration += steps
        generation(currentGeneration)
    }

    private def generation(n: Int): TreeNode = {
        val nearestGeneration = cache.keys.filter(_ <= n).toSeq.sorted.last
        var currentGeneration = nearestGeneration
        var tree = cache(nearestGeneration)
        while (currentGeneration < n) {
            tree = evolve(rule, tree)
            currentGeneration += 1
            if ((currentGeneration % 64) == 0) {
                cache += currentGeneration -> tree
            }
        }
        tree
    }
}

Eclipse colors variables (mutable references) red, which gives a much better idea about what is going on in our code. This is not a piece of code I am particularly proud of. Name of the class is not well chosen. Function move violates TellDontAsk. An array would be a better choice instead of the hash map. Et cetera. There are however some interesting things to note here:

• currentGeneration is a var while cache is a val. Former is a mutable reference to an immutable object. Latter is an immutable reference to a mutable object. Declaring cache as var would be a mistake in this case.
• I initially synchronized both move and generation but then removed it from generation since it is only called from within move.
• As I mentioned, an Array would be a better choice of data type for cache. But then we would have to calculate the array index as currentGeneration / 64 and size the array properly (1100 / 64 + 1) and store the greatest index of the array that is populated.
• nearestGeneration was initially calculated as cache.keys.filter(_ <= n).last and one of the tests were timing out. It took me an hour to find this subtle bug. cache.keys is an Iterable[Int], but it is not ordered. So filter’ing them guarantees a correct result but taking the last one essentially causes the calculation to start from a random point and recalculate and re-cache needlessly. I have managed to pass that test, but sorting keys every query is still bothering me. Unfortunately there is no mutable SortedMap.

This concludes The Tree of Life series. I hope you find it useful.