Daily Coding Problem #3

Ivan on November 26, 2018

For quite some time I found my time procastinating after getting home from work. Untill a few days ago I stumbled upon the Daily Coding Problem (... [Read Full]
markdown guide
 

In Javascript, JSON serialization/unserialization is already supported, so this felt like cheating:

class Node {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    toString() {
        return JSON.stringify(this);
    }
};

const serialize = node => node.toString();
const deserialize = string => JSON.parse(string);

const node = new Node('root', new Node('left', new Node('left.left')), new Node('right'));

console.log(deserialize(serialize(node)).left.left.val); // prints "left.left"

 

The tricky part is to make it work for arbitrary values, i.e. drop the assumption the symbols for Empty_Marker and '-' are not going to be used in any node's value.

Here's such a solution in Perl, tests included:

#!/usr/bin/perl
use warnings;
use strict;

package Node {
    use Moo;

    has value => (is => 'ro', required => 1);
    has left  => (is => 'ro', isa => sub { shift->isa('Node') or die });
    has right => (is => 'ro', isa => sub { shift->isa('Node') or die });

    my $_escape_value = sub {
        my ($self) = @_;
        my $value = $self->value;
        $value =~ s/$_->[0]/\\$_->[1]/g
            for [qr/\\/ => '\\'],
                [qr/"/  => '\''],
                [qr/\(/ => '['],
                [qr/\)/ => ']'];

        return $value
    };

    my $unescape = sub {
        my ($value) = @_;

        $value =~ s/(?<!\\)\\$_->[0]/$_->[1]/g
            for [qr/\]/ => ')'],
                [qr/\[/ => '('],
                [qr/'/  => '"'];
        $value =~ s/\\\\/\\/g;

        return $value
    };

    my $parse = sub {
        my ($rest) = @_;
        my $pos = '(' eq substr $rest, 0, 1;
        my $rank = $pos;
        until (0 == $rank) {
            ++$rank if '(' eq substr $rest, $pos, 1;
            --$rank if ')' eq substr $rest, $pos, 1;
            ++$pos;
        }

        my $left  = substr $rest, 0, $pos;
        my $right = substr $rest, $pos + ($pos != length $rest);

        length $_ and $_  = __PACKAGE__->deserialize($_)
            for $left, $right;

        return $left, $right
    };

    sub serialize {
        my ($self) = @_;

        my $value = $self->$_escape_value;
        my ($left, $right) = map $_ ? $_->serialize : "",
                                 $self->left,
                                 $self->right;

        return '(' . join(',', qq("$value"), $left, $right) . ')'
    }

    sub deserialize {
        my ($class, $string) = @_;

        return undef unless length $string;

        my ($value, $rest) = $string =~ /^\("([^"]*)",(.*)\)$/sg;

        $value = $unescape->($value);
        my ($left, $right) = $parse->($rest);

        return $class->new(value => $value,
                           (left  => $left)  x !! ref $left,
                           (right => $right) x !! ref $right)
    }

};

use Test::More tests => 7;

my $node1 = 'Node'->new(
    value => 'root',
    left  => 'Node'->new(
        value => 'left',
        left => 'Node'->new(value => my $left_left = 'left.left')),
    right => 'Node'->new(value => 'right'),
);

is 'Node'->deserialize($node1->serialize)->left->left->value, $left_left;

my $node2 = 'Node'->new(
    value => my $empty = "",
    right => 'Node'->new(value => my $special_chars = '("[,\'\\]"))',
                         right => 'Node'->new(
                             value => my $newline = "1\n2")));

is 'Node'->deserialize($node2->serialize)->value,
    $empty;
is 'Node'->deserialize($node2->serialize)->right->value,
    $special_chars;
is 'Node'->deserialize($node2->serialize)->right->right->value,
    $newline;

my $node3 = 'Node'->new(value => $node1->serialize,
                        left  => 'Node'->new(value => $node2->serialize));

is 'Node'->deserialize($node3->serialize)->value,
    $node1->serialize;
is 'Node'->deserialize($node3->serialize)->left->value,
    $node2->serialize;

my $super = $node3->serialize;

$super = 'Node'->new(
    value => 'Node'->deserialize($super)->serialize
)->serialize
    for 1 .. 6;

my $root = $super;
$root = 'Node'->deserialize($root)->value for 1 .. 8;
is $root, 'root';
 

Python solution using recursion.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Stringifier():
    def __init__(self):
        self.current = 0

    def serialize(self, root, strTree = []):
        if root is None:
            return
        strTree.append('{')
        strTree.append('\"' + root.val + '\"')
        self.serialize(root.left, strTree)
        self.serialize(root.right, strTree)
        strTree.append('}')
        return "".join(strTree)

    def _deserialize(self, strTree):
        left = None
        right = None
        if strTree[self.current] == '{' :
            self.current += 1
            val = ""
            if strTree[self.current] == '\"':
                self.current += 1
            while strTree[self.current] != '\"':
                val += strTree[self.current]
                self.current += 1
            self.current += 1
            if strTree[self.current] == '{':
                left = self._deserialize(strTree)
            if strTree[self.current] == '{':
                right = self._deserialize(strTree)
            if strTree[self.current] == '}':
                self.current += 1
                return Node(val, left, right)

    def deserialize(self, strTree):
        self.current = 0
        return self._deserialize(strTree)

if __name__ == "__main__":
    stringifier = Stringifier()
    node = Node('root', Node('left', Node('left.left')), Node('right'))
    assert stringifier.deserialize(stringifier.serialize(node)).left.left.val == 'left.left'
 

Python solution defining __repr__, which is meant for exactly this purpose:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        return ( 'Node(' + repr(self.val) + ', '
                         + repr(self.left) + ', '
                         + repr(self.right) + ')' )

    def __eq__(self, other):
        if isinstance(other, Node):
            return ( self.val == other.val and
                     self.left == other.left and
                     self.right == other.right )
        return False

    def __hash__(self):
        return hash((self.val, self.left, self.right))

serialise = repr
deserialise = eval

node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialise(serialise(node)).left.left.val == 'left.left'
assert deserialise(serialise(node)) == node
assert hash(deserialise(serialise(node))) == hash(node)

Edit: Included test from problem statement in the code, so that it should now be ready for copy and paste into file and python3 -i <file>. While we are at it, implemented __eq__ and __hash__, so that we can assert even stronger tests.

 
 

Go solution. Its a bit verbose as it does not have optional/default params.

package main

import (
    "fmt"
    "strings"
)

type Node struct {
    val   string
    left  *Node
    right *Node
}

func (node *Node) serialize() string {
    if node == nil {
        return "#"
    }

    leftSide := node.left.serialize()
    rightSide := node.right.serialize()

    ret := fmt.Sprintf("%s->%s->%s", node.val, leftSide, rightSide)
    return ret
}

func deserialize(str string) Node {
    node, _ := deserailizeNodes(strings.Split(str, "->"))
    return node
}

func deserailizeNodes(nodes []string) (Node, []string) {

    if len(nodes) == 0 {
        return Node{"", nil, nil}, nil
    }

    nextNode := nodes[0]

    if nextNode == "#" {
        return Node{"", nil, nil}, nodes[1:]
    }

    left, rem := deserailizeNodes(nodes[1:])
    right, _ := deserailizeNodes(rem)

    if left.val == "" && right.val == "" {
        return Node{nextNode, nil, nil}, nil
    }
    if left.val == "" {
        return Node{nextNode, nil, &right}, nil
    }
    if right.val == "" {
        return Node{nextNode, &left, nil}, nil
    }

    node := Node{val: nextNode, left: &left, right: &right}
    return node, nil

}

func main() {
    node := Node{"root", &Node{"left", &Node{"left.left", nil, nil}, nil}, &Node{"right", nil, nil}}
    fmt.Println(node.serialize())
    // root->left->left.left->#->#->#->right->#->#
    n := deserialize(node.serialize())
    fmt.Println(n.left.left.val == "left.left") // true
}

 

Here's my C# solution

using System;

namespace DailyCodingProblem3
{
    class Node
    {
        public string Val { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }

        public Node(string val, Node left = null, Node right = null)
        {
            Val = val;
            Left = left;
            Right = right;
        }
    }

    class Program
    {
        public static string Serialize(Node node)
        {
            if (node == null)
            {
                return "-";
            }

            string ret = $"{node.Val}-";
            ret += Serialize(node.Left);
            ret += Serialize(node.Right);

            return ret;
        }

        public static Node Deserialize(ref string str)
        {
            if (str.Length == 0 || str.StartsWith("-"))
            {
                return null;
            }

            var val = str.Split('-')[0];

            str = str.Substring(str.IndexOf('-') + 1);
            var left = Deserialize(ref str);

            str = str.Substring(str.IndexOf('-') + 1);
            var right = Deserialize(ref str);

            return new Node(val, left, right);
        }

        static void Main()
        {
            var node = new Node("root", new Node("left", null, new Node("left.right", new Node("left.right.left"))), new Node("right"));
            var ret = Serialize(node);

            Console.WriteLine(ret);
            Console.WriteLine(Serialize(Deserialize(ref ret)));
        }
    }
}
 
require 'json'

class Node
  attr_accessor :v, :l, :r
  def initialize(v, l=nil, r=nil)
    self.v, self.l, self.r =
      case v
      when Hash
        left, right =
          %w|left right|.
            map { |node| v[node] }.
            map { |node| Node.new(node) unless node.to_s.empty? }
        [v['value'], left, right]
      when String
        [v, l, r]
      end
  end

  def to_s
    %Q|{"value":"#{v}","left":#{l || '""'},"right":#{r || '""'}}|
  end

  def ==(other)
    v == other.v && l == other.l && r == other.r
  end
end

# test
nn = Node.new('root', Node.new('left', Node.new('left.left')), Node.new('right'))
Node.new(JSON.parse nn.to_s) == nn
#⇒ true

Bonus: this serialization uses JSON format to make it easier to plug into other 3rd party code, if necessary.

 

My first time to see someone using Lua, thanks for the code, cool!

code of conduct - report abuse