Sort 6 Discussions, By:
Please Login in order to post a comment
The condition "A single node will never have more than children." is not true for test case no. 15
I have solved this problem but I have cheated :-) 'cause I have used a mutable data structure (in Scala).
To solve this problem in a real "functional way" I should have used immutable data structures. This means that every time I had to change something (change value, add, delete) I should have copied/created an entire new tree with only "that" change.
Well, I thought about this for a while but I found this way to approach the problem quite overwhelming. Could anybody show me how to solve this problem with immutable data structures? How do you handle the add/delete/change operations?
I suggest have a look here: https://en.wikipedia.org/wiki/Zipper_(data_structure)
I've finished 5 minutes ago. It took some patience
Thanks. Didn't know about zippers.
A possible approach (which I took) is to treat the entire tree as one big data structure, with a collection of nodes, and various representations of the links between them (i.e. think Graph represented as an adjancy list). You can then expose a trait called Tree, which is in fact just a front for the tree and a specific node in it (i.e. the tree and a node id). Each operation on the node is performed "behind the scenes" as an operation on the entire tree, and then return a new Tree and node. Then again I supposed that's just another way of describing the zipper principle, just implemented in an object-oriented way.
task can be solved without zipper and everything is immutable
just put the tree and navigation into two different structures
final case class Node(value: Int, children: Vector[Node] = Vector.empty)
final case class PathNode(link: Node, pos: Int, parent: Option[Node])
Learning something new is why I like this place. I did not know about
But this was a very difficult task in the wrong I my mind. Solving
the problem was the easy part. Geting it to pass within the allowed
time frame was an entire different story.
If you try to solve this task with erlang and you have issues with
timeout, try search for
"Erlang: Read from an input stream in a efficient way"
Using module string will not work, use binaries. I also had to write
my own split line method for the operations.
Thanks for all the pointers to the Zipper. That helped a lot. Took me a while to debug and get all the details right but that was fun!