The sixth problem included a fairly
simple graph/tree problem. In the first part you were supposed to find the
total depth of all nodes in the tree and in the second part you had to find the
common ancestor of two nodes and calculate the distance between them (through
that common ancestor).
This problem showed a shortcoming of Sophia, we are missing some functions on
string, to handle the raw input data we would have needed String.split
which is not yet there. So
we did some preprocessing of the input data (you could do this and write it to
the state, so not to much cheating I think).
The naive implementation of part 1 became pretty expensive 3.5G gas and more
than 15 seconds runtime, but after adding some memoization (using the state!)
the solution actually fits in a block at 5.7M gas. Part 2 was a lot easier and
only require 1.6M gas.