0

Daily Challenge #1

Czas na kolejne zadanie z cyklu Daily Coding Problem, autorem dzisiejszego jest Google. W porównaniu do dnia wczorajszego (Daily Challenge #0), nad tym musiałem się dłużej pochylić, ponieważ dzisiejsze zadanie jest trudniejsze – o ile chcielibyśmy je rozwiązywać w języku niskiego poziomu, ponieważ w C# to rozwiązanie zajęłoby może z 30 sekund 😉.

Tak jak zawsze kod jest dostępny na GitHubie.

Wpis ten należy do cyklu Daily Challenge. W cyklu tym rozwiązuję każdego dnia nowe zadanie. Zadanie te traktuję w taki sposób, jakbym dostał je na rozmowie kwalifikacyjnej i miał coś wymyślić. Implementuję pierwszą myśl jaka przyjdzie mi do głowy. Nie musi być ona (zazwyczaj nie będzie) najlepszym rozwiązaniem. Chodzi po prostu o zabawę i sprawdzenie jakbym sobie poradził z podobnym wyzwaniem. Zaimplementowane rozwiązanie nie jest z reguły tłumaczone, jeżeli masz pytania możesz je zadawać w komentarzach. Wszystkie zadania udostępniane są subskrybentom Daily Coding Problem.

Zadanie

Treść dzisiejszego zadania brzmi następująco:

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’

Jak widać jest ono dosyć banalne do zaimplementowania w C#, gdyż wystarczy użyć DataContractSerializer i wszystko się „samo” zrobi. Jednak takie rozwiazanie na byłoby żadnym wyzwaniem, a czasami trzeba się pomęczyć.

No to zaczynamy!

Testy

Na początku powstały testy sprawdzające algorytm:

[TestMethod]
public void DailyChallenge1()
{
    Node node = new Node
    {
        Value = "Root",
        Left = new Node
        {
            Value = "Left",
            Left = new Node
            {
                Value = "Left.Left"
            },
            Right = new Node
            {
                Value = "Left.Right"
            }
        },
        Right = new Node { Value = "Right" }
    };
    DailyChallenge1 serializer = new DailyChallenge1();
    string data = serializer.Serialize(node);
    Node result = serializer.Deserialize(data);
    Assert.AreEqual("Left.Left", result.Left.Left.Value);
}

Implementacja

Na początku postanowiłem wszystko sobie rozrysować na tablicy. Łatwiej coś wymyślić mając to przed oczami, w dodatku tablica umożliwa łatwe wprowadzenie/korygowanie treści. Mój szkic wyglądał następująco:

Po rozrysowaniu wyłoniły się podstawowe wzory oraz format zapisu danych. Zdecydowałem się zapisywać/odczytywać drzewo „w głąb”, a każdy liść zapisywać w takim formacie:

{Level}.{Index}.{Value}

Rozwiązanie to wadę tj. nie zadziała, jeżeli Value będzie połamane na kilka linii. Postanowiłem nie przejmować się tym mankamentem i zaimplementować to co rozrysowałem.

Klasa Node wygląda nastepujęco:

public class Node
{
    public string Value { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }
}

Serializowana jest za pomocą tej funkcji:

public string Serialize(Node node)
{
    StringBuilder sb = new StringBuilder();
    SerializeIntern(node, sb, 0, 0);
    return sb.ToString();
}
 
private void SerializeIntern(Node node, StringBuilder sb, int level, int index)
{
    sb.AppendLine($"{level}.{index}.{node.Value}");
    if (node.Left != null)
    {
        SerializeIntern(node.Left, sb, level + 1, index * 2);
    }
    if (node.Right != null)
    {
        SerializeIntern(node.Right, sb, level + 1, index * 2 + 1);
    }
}

Z kolei deserializacja odbywa się za pomocą tego kawałka kodu:

public Node Deserialize(string data)
{
    var queue = new Queue<string>();
    using (StringReader sr = new StringReader(data))
    {
        string line = sr.ReadLine();
        do
        {
            queue.Enqueue(line);
            line = sr.ReadLine();
        }
        while (string.IsNullOrWhiteSpace(line) == false);
    }
    return DeserializeIntern(queue, 0, 0);
}
 
private Node DeserializeIntern(Queue<string> rows, int level, int index)
{
    if (rows.Any() == false)
    {
        return null;
    }
    Node node = null;
    string strLine = rows.Peek();
    ParseLine(strLine, out int readLevel, out int readIndex, out string value);
    if (level == readLevel && index == readIndex)
    {
        rows.Dequeue();
        node = new Node() { Value = value };
        node.Left = DeserializeIntern(rows, level + 1, index * 2);
        node.Right = DeserializeIntern(rows, level + 1, index * 2 + 1);
    }
    return node;
}
 
private void ParseLine(string strLine, out int level, out int index, out string value)
{
    int indexFirstDot = strLine.IndexOf('.');
    int indexSecondDot = strLine.IndexOf('.', indexFirstDot + 1);
    level = int.Parse(strLine.Substring(0, indexFirstDot));
    index = int.Parse(strLine.Substring(indexFirstDot + 1, indexSecondDot - indexFirstDot - 1));
    value = strLine.Substring(indexSecondDot + 1);
}

Test przechodzi na zielono, co oznacza, że problem rozwiązany 😉.

Mission Complete

Tak jak wspomniałem na wstępnie, zadanie było trudniejsze od wczorajszego, oceniłem je na 3 gwiazdki (chociaż może 2.5 byłoby lepsze). Samo wymyślenie algorytmy na tablicy zajęło mi ok 1-2 min, implementacja kolejne 5.

Pamiętaj proszę, że tak jak we wszystkich wpisach z tej serii, kod ten nie nadaje się do rzeczywistych problemów produkcyjnych. Jest on ubogi, a sam algorytm też jest kiepski. Implementuję po prostu pierwsze co przyjdzie mi do głowy – analiza problemu przez kilka/kilkanaście minut na pewno zaowocowałaby lepszym algorytmem. W powyższym np. lepsze byłoby użycie Regexów, jednak nie zastosowałem ich z prostego powodu – nie lubię wyrażeń regularnych. 😉
Pozdro!

Patryk Bogdański

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

This site uses Akismet to reduce spam. Learn how your comment data is processed.