#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'
@Absinthe How about, one crazy function that works both ways!
https://git.sr.ht/~namark/mercury_stuff/tree/master/toys/serialize_btree.m
Though, it goes haywire if input is invalid or if value contains anything in the form of "|number|", where number is less than depth of the tree. Probably has something to do with compiler complaining that code I wrote is impure and non-deterministic, and me just silencing it.
Also it only handles string values, cause I don't know how to write generic code yet.
Here’s a live, runnable Elm solution to the serialized tree problem. You can change the <textarea> labelled “Input serialized node JSON here”, and it will parse and serialize after each keystroke.
https://ellie-app.com/6PrNYFqhwhja1
#toyprogrammingchallenge #elmlang
import Json.Encode as JE exposing (Value)
import Json.Decode as JD exposing (Decoder)
{-| A simple two-way branching tree node with an optional string value.
-}
type Node =
Node
{ value : Maybe String
, left : Maybe Node
, right : Maybe Node
}
{-| Serialization
-}
nodeToString : Int -> Node -> String
nodeToString indent node =
JE.encode indent <| encodeNode node
{-| Deserialization
-}
stringToNode : String -> Result JD.Error Node
stringToNode string =
JD.decodeString nodeDecoder string
--- Implementation
encodeMaybe : (a -> Value) -> Maybe a -> Value
encodeMaybe encoder maybeA =
case maybeA of
Nothing ->
JE.null
Just a ->
encoder a
encodeNode : Node -> Value
encodeNode (Node { value, left, right }) =
JE.object
[ ("value", encodeMaybe JE.string value)
, ("left", encodeMaybe encodeNode left)
, ("right", encodeMaybe encodeNode right)
]
nodeDecoder : Decoder Node
nodeDecoder =
JD.map3 (\value left right -> Node { value = value, left = left, right = right })
(JD.field "value" <| JD.nullable JD.string)
(JD.field "left" <| JD.nullable (JD.lazy (\() -> nodeDecoder)))
(JD.field "right" <| JD.nullable (JD.lazy (\() -> nodeDecoder)))
Okay, I figured it out. I am open to critique on this version:
@billstclair @namark aiming for simple or elegant. Would be happy with "pythonical" :)
@Absinthe
Loosey-goosey perhaps? :D
I tried to break it with some weird input, but it just gobbles everything up, without second thoughts, even if it isn't technically a proper serialization string.
Maybe a bit hard to read, but with stuff that I'm putting out, I don't think I have the right to say that.
@namark "Loosey-Goosey" How so? I can certainly try to tighten it up some.
@Absinthe I tried giving it a value, in a place where it would expect a node, and it seems like it just assumes that to be a None node.
So something like
serialize(deserialize("a")), gives out None
"a,b" -> "a,None,None"
"a,b,c" -> "a,b,None,None,None"
Just being weirdly ok with things I thought should break it. Though arbitrary input wasn't a part of the problem, so that probably doesn't count.
Also aside from the commas in values, "None" as a value also seems to break things.
@namark yeah, I fixed the comma thing, made it into RS 0x1E. I guess I could change the 'None' to either actual None or another control character. But FWIW I think I may have to just leave it be, as close enough for government work :) I found some other people solve similar problems with # for the None value. I think I am ready to move on to the next problem. Got a new one today, seems like a real PITA.
@namark @khird ultimately in a real serialization using a format like JSON or XML or something with a DOM and library to handle it. Then it can be used from something else as well. But these problems however, are meant to be quick enough to accomplish in a job interview. I thought of a different way to try also. I think I can create a geenrator and just use next() then maybe I can avoid the idx. But this seemed like a fun enough way to solve the problem.
What did you think of this weekend's problem? The "One to Nine" one?
The freebie today is pretty annoying too. Debating if I want to try to solve it or not yet.
My take on it is, "Man-hours cost more than CPU-hours." Say I figure out a more sophisticated algorithm that can save CPU time, but implementing it and debugging the extra complexity costs an hour of my time. It probably doesn't make sense to go that route unless it will save more than about fifty hours of compute time in the long run.
E.g. if on a typical dataset I can save a second per run by getting fancy, we would recoup my invested time after 180,000 executions of the program. If it's a report that gets run daily, that break-even point is about five hundred years in the future.
@khird @Absinthe
I would also pick readable code over optimal code most of the time, however if you are not the sole user, you'll have to divide that by the number of users, and then it can become a completely different story.
The ever illusive nature of software - to be copyable with practically no effort.
@billstclair @namark Oh, yeah, I know my values can't contain ',' characters. I may redo it with some other control or npc