Petit quizz en passant


Bonjour à tous, je suis tombé sur un article proposant un problème sympathique, je me permets de vous le partager.

Petit contest, comment obtenir l’affichage suivant:

a
├─b
│ ├─c
│ │ └─d
│ └─e
│   └─f
└─g
  ├─h
  │ └─i
  └─j

(astuce: vous pouvez copier/coller les caractères semi-graphiques depuis cet article même…)

Avec l’entrée suivante :

var root = new Node("a",
    new Node("b",
        new Node("c",
            new Node("d")),
        new Node("e",
            new Node("f"))),
    new Node("g",    
        new Node("h",
            new Node("i")),
        new Node("j")));

Le modèle étant assez basique :

class Node
{
    public Node(string text, params Node[] children)
    {
        this.Text = text;
        this.Children = children ?? new Node[] {};
    }
    public string Text { get; private set; }
    public IList<Node> Children { get; private set; }
}

Je vous laisse implémenter la classe Dumper !

sealed class Dumper
{
    static public string Dump(Node root) { /* … */ }
    /* … */
}

Je suis preneur de tout type d’implémentation (CSharp, VB, Java, PHP, FSharp…)

Mitsu

Comments (15)

  1. Matthieu MEZIL says:

    Je pense que F# est bien plus adapté que C# pour ça.

    En C#, ça peut se faire comme ça :

    #if Recursive

    public static string Dump(Node root)

    {

       return Dump(root, "");

    }

    private static string Dump(Node root, string space)

    {

       StringBuilder sb = new StringBuilder();

       sb.Append(root.Text);

       IEnumerator<Node> nodeEnumerator = root.Children.GetEnumerator();

       if (nodeEnumerator.MoveNext())

           for (; ; )

           {

               sb.Append(Environment.NewLine);

               sb.Append(space);

               var subNode = nodeEnumerator.Current;

               if (nodeEnumerator.MoveNext())

               {

                   sb.Append("├─");

                   sb.Append(Dump(subNode, space + "│ "));

               }

               else

               {

                   sb.Append("└─");

                   sb.Append(Dump(subNode, space + "  "));

                   break;

               }

           }

       return sb.ToString();

    }

    #else

    public static string Dump(Node root)

    {

       StringBuilder sb = new StringBuilder();

       List<Tuple<Node, string, string>> nodes = new List<Tuple<Node, string, string>>();

       nodes.Add(new Tuple<Node, string, string>(root, "", ""));

       while (nodes.Count != 0)

       {

           var nodeAndSpace = nodes[0];

           nodes.RemoveAt(0);

           Node node = nodeAndSpace.Item1;

           string space = nodeAndSpace.Item2;

           string graphLine = nodeAndSpace.Item3;

           if (!string.IsNullOrEmpty(space))

           {

               sb.Append(Environment.NewLine);

               sb.Append(space.Substring(0, space.Length – 2));

               sb.Append(graphLine);

           }

           sb.Append(node.Text);

           var nodeEnumerator = node.Children.GetEnumerator();

           if (nodeEnumerator.MoveNext())

           {

               int index = 0;

               for (; ; )

               {

                   var subNode = nodeEnumerator.Current;

                   if (nodeEnumerator.MoveNext())

                       nodes.Insert(index++, new Tuple<Node, string, string>(subNode, space + "│ ", "├─"));

                   else

                   {

                       nodes.Insert(index++, new Tuple<Node, string, string>(subNode, space + "  ", "└─"));

                       break;

                   }

               }

           }

       }

       return sb.ToString();

    }

    #endif

  2. Michel Perfetti says:

        sealed class Dumper

       {

           const string MiddleBranch = "├-";

           const string EndBranch = "└-";

           const string VerticalBranch = "│ ";

           static public string Dump(Node root)

           {

               StringBuilder sb;

               sb = new StringBuilder();

               DumpCore(root, new List<bool>(), sb);

               return sb.ToString();

           }

           static void DumpUpperBranches(List<bool> branchList, StringBuilder sb)

           {

               if (branchList == null || branchList.Count == 0)

                   return;

               var n = branchList.Count;

               for (int i = 0; i < n -1; i++)

               {

                   var b = branchList[i];            

                   if (b)

                   {

                       sb.Append(VerticalBranch);

                   }

                   else

                   {

                       sb.Append("  ");

                   }

               }

               bool isLastNode = !branchList[n – 1];

               if (isLastNode)

               {

                   sb.Append(EndBranch);

               }

               else

               {

                   sb.Append(MiddleBranch);

               }            

           }

           static private void DumpCore(Node node, List<bool> branchList, StringBuilder sb)

           {

               DumpUpperBranches(branchList, sb);

               sb.AppendLine(node.Text);

               if (branchList == null)

               {

                   branchList = new List<bool>();

               }

               var n = node.Children.Count;

               branchList.Add(true);

               int branchListLastIndex = branchList.Count – 1;

               for (int i = 0; i < n; i++)

               {

                   bool isLastChildNode = i == (n – 1);

                   branchList[branchListLastIndex] = !isLastChildNode;

                   var childNode = node.Children[i];

                   DumpCore(childNode, branchList, sb);                

               }

               branchList.RemoveAt(branchListLastIndex);

           }

       }

  3. Thierry Bouquain says:

    A première vu je ferais un truc du genre en c#

    static public string Dump(Node root)

           {

               StringBuilder sb = new StringBuilder();

               StringWriter writer = new StringWriter(sb);

               List<bool> levelStatuses = new List<bool>();

               DumpNode(writer, root, levelStatuses);

               return sb.ToString();

           }

           static public void DumpNode(StringWriter writer, Node node, List<bool> levelStatuses, bool? isLastSibling = null)

           {

               WriteLevel(writer, levelStatuses);

               if (isLastSibling.HasValue)

                   writer.Write(isLastSibling.Value ? "└─" : "├─");

               writer.WriteLine(node.Text);

               DumpCollection(writer, levelStatuses, node.Children);

           }

           static public void DumpCollection(StringWriter writer, List<bool> levelStatuses, IList<Node> collection)

           {

               for (int i = 0; i < collection.Count; i++)

               {

                   levelStatuses.Add(i == collection.Count – 1);

                   DumpNode(writer, collection[i], levelStatuses, i == collection.Count – 1);

                   levelStatuses.RemoveAt(levelStatuses.Count – 1);

               }

           }

           private static void WriteLevel(StringWriter writer, List<bool> levelStatuses)

           {

               int cnt = 0;

               foreach (var lastNodeReachedForLevel in levelStatuses)

               {

                   if (cnt == levelStatuses.Count – 1)

                       break;

                   if (!lastNodeReachedForLevel)

                       writer.Write("| ");

                   else

                       writer.Write("  ");

                   cnt++;

               }

           }

  4. NeuroCypher says:

    Salut Mitsu !

    C'est sympa, ca detend pour les pauses au boulot !

     public sealed class Dumper

       {

           private static string MiddleBranch = "├─";

           private static string LastBranch = "└─";

           private static string Pipe = "│ ";

           private static string EmptyPlace = "  ";

           public static string Dump(Node node)

           {

               var sBuilder = new StringBuilder();

               DumpNode(node, sBuilder, "");

               return sBuilder.ToString();

           }

           private static void DumpNode(Node node, StringBuilder sBuilder, string depth)

           {

               if (node == null)

                   return;

               sBuilder.Append(depth);

               sBuilder.AppendLine(node.Text);

               if (depth.Length > 1)

               {

                   var frontDepht = depth.Substring(0, depth.Length – 2);

                   var lastDepth = depth.Substring(depth.Length – 2, 2);

                   depth = (lastDepth.Equals(LastBranch) ? frontDepht + EmptyPlace :

                            lastDepth.Equals(MiddleBranch) ? frontDepht + Pipe : depth);

               }

               for (int count = 0; count < node.Children.Count; count++)

               {

                   var subDepth = depth + (count == node.Children.Count – 1 ? LastBranch : MiddleBranch);

                   DumpNode(node.Children[count], sBuilder, subDepth);

               }

           }

       }

  5. Miiitch says:

    Un peu d'F# pour changer:

    namespace FDumper

    module public Dumper =

       let private MiddleBranch = "├-"

       let private  EndBranch = "└-"

       let private  VerticalBranch = "│ "

       let rec private WriteLine bl  nodeText  (sb: System.Text.StringBuilder) =

           match bl with

           | true :: [] -> sb.AppendLine(MiddleBranch+nodeText) |> ignore

           | false:: [] -> sb.AppendLine(EndBranch+nodeText) |> ignore

           | true :: tail ->  WriteLine  tail nodeText (sb.Append(VerticalBranch))

           | false :: tail ->  WriteLine tail nodeText (sb.Append("  "))

           | [] ->  sb.AppendLine(nodeText) |> ignore

       let rec private DumpCore (node: NodeLib.Node) sb bl =

            let rec DumpChilds bl childList sb =

               match childList with

               | node :: [] -> DumpCore node sb (List.append bl [false])

               | node :: tail -> DumpCore node sb (List.append bl [true] ); DumpChilds bl tail sb

               | [] -> ()  in

                   WriteLine bl node.Text sb;DumpChilds bl (List.ofSeq node.Children) sb

       let public Dump (node: NodeLib.Node) =

           let sb = new System.Text.StringBuilder() in

               DumpCore node sb [];

               sb.ToString()

    Beaucoup plus sympa hein!!!

  6. Jmix90 says:

    @miitch : les cours d'Ocaml de l'école te manquent ? 🙂

  7. Jmix90 says:

    @miitch : les cours d'Ocaml de l'école te manquent ? 🙂

  8. jrouaix says:

    sealed class Dumper

    {

       class MaxDepth { public int Value; }

       static IEnumerable<IEnumerable<string>> Recurse(Node node, int depth, MaxDepth maxDepth)

       {

           maxDepth.Value++; depth++;

           yield return new[] { node.Text, Environment.NewLine };

           int nbChildren = node.Children.Count;

           foreach (var child in node.Children)

           {

               nbChildren–;

               foreach (var childBranch in Recurse(child, depth, maxDepth))

               {

                   int distance = maxDepth.Value – depth;

                   string myBranch = (distance == 1) ? (nbChildren == 0 ? "└-" : "├-") : (nbChildren == 0 ? "  " : "│ ");

                   yield return new[] { myBranch }.Concat(childBranch);

               }

           }

           maxDepth.Value–;

       }

       static public string Dump(Node root)

       {

           var sb = new StringBuilder();

           foreach (var branch in Recurse(root, 0, new MaxDepth()))

               foreach (string s in branch) sb.Append(s);

           return sb.ToString();

       }

    }

  9. mitsu says:

    Des choses intéressantes !

    Bravo à ceux qui ont déjà posté leurs réponses.

    Bon, voici une première solution de ma part.

       sealed class DumperClassic
       {
           private static StringBuilder sb;
           static public string Dump(Node root)
           {
               sb = new StringBuilder();
               DumpLine(root, "");
               return sb.ToString();
           }

           static void DumpLine(Node node, string indent)
           {
               sb.AppendLine(node.Text);
               for (int i = 0; i < node.Children.Count; i++)
               {
                   var isLast = i == node.Children.Count – 1;
                   sb.Append(indent + (isLast ? "└─" : "├─"));
                   DumpLine(node.Children[i], indent + (isLast ? "  " : "│ "));
               }
           }
       }

    J'ajoute une contrainte : la méthode récursive ne doit avoir qu'un seul paramètre !!! (virez moi les indent, space et autres depth !) :p

  10. Thomas Levesque says:

    Pour ceux que ça intéresserait, ce problème vient du blog d'Eric Lippert, dont je conseille vivement la lecture

    blogs.msdn.com/…/old-school-tree-display.aspx

    Voilà ma solution :

    sealed class Dumper

    {

       static public string Dump(Node root)

       {

           var sb = new StringBuilder();

           Dump(sb, root, new bool[] { });

           return sb.ToString();

       }

       static private void Dump(StringBuilder builder, Node node, bool[] isLast)

       {

           int level = isLast.Length;

           for (int i = 0; i < level; i++)

           {

               if (i == level – 1)

                   builder.Append(isLast[i] ? "u2514u2500" : "u251cu2500");

               else

                   builder.Append(isLast[i] ? "  " : "u2502 ");

           }

           builder.AppendLine(node.Text);

           for (int i = 0; i < node.Children.Count; i++)

           {

               Dump(

                   builder,

                   node.Children[i],

                   isLast.Concat(new[] { i == node.Children.Count – 1 }).ToArray());

           }

       }

    }

  11. JB Lagorce says:

    J'imagine que tu vas nous sortir une belle solution avec "yield" 🙂

    Sinon, je tenterais bien un truc de ce genre :

    sealed class Dumper

    {

    static public string Dump(Node root)

    {

    return String.Join("n", GetLines(root).ToArray());

    }

    static IList<string> GetLines(Node root)

    {

    var result = new List<string> {root.Text};

    foreach (var child in root.Children)

    {

    var childLines = GetLines(child);

    var isLast = child == root.Children.Last();

    result.Add((isLast ? "+-" : "+-")+childLines[0]);

    result.AddRange(childLines.Skip(1).Select(s => (isLast ? " " : "|") + s));

    }

    return result;

    }

    }

  12. JB Lagorce says:

    Oups illisible…

    Sorry pour l'indent et les u2514 et u251c

  13. Jb Evain says:

    Bon, je crois pouvoir prétendre à la plus convolutée et à la moins performante des solutions, mais au moins elle tient en une seule expression avec un Y combinator: http://gist.github.com/647076

    static class TreePrettyPrinter {

    struct NodeTuple {

    public readonly Node Node;

    public readonly bool IsTail;

    public readonly string Indent;

    NodeTuple (Node node, bool is_tail, string indent)

    {

    this.Node = node;

    this.IsTail = is_tail;

    this.Indent = indent;

    }

    public static NodeTuple Create (Node node, bool is_tail, string indent)

    {

    return new NodeTuple (node, is_tail, indent);

    }

    }

    static Func<A, R> Y<A, R> (Func<Func<A, R>, Func<A, R>> f)

    {

    Func<A, R> g = null;

    g = f (a => g (a));

    return g;

    }

    static string Print (Node node)

    {

    return Y<NodeTuple, string> (f => t =>

    t.Indent

    + (t.IsTail ? "└" : "├")

    + '─'

    + t.Node.Text

    + Environment.NewLine

    + t.Node.Children

    .Select (c =>

    f (NodeTuple.Create (

    c,

    c == t.Node.Children [t.Node.Children.Count – 1],

    t.Indent + (t.IsTail ? "  " : "│ "))))

    .Aggregate ("", (a, b) => a + b)

    ) (NodeTuple.Create (node, true, ""));

    }

    public static void Print (TextWriter writer, Node node)

    {

    writer.WriteLine (Print (node));

    }

    }

  14. Yann Schwartz says:

    +1 pour le Y Combinator. Si tu pouvais ajouter un générateur monadique, ce serait parfait.

  15. mitsu says:

    Cool de voir enfin autant de réponses !! et a priori, vous n'êtes pas trop allé voir les réponses sur le blog d'Eric Lippert qui était en effet la source dont je parlais.

    Voici une solution utilisant les itérateurs:

    sealed class Dumper

    {

       static public string Dump(Node root)

       {

           return root.Text + "n" + string.Join("n", DumpLine(root));

       }

       static IEnumerable<string> DumpLine(Node node)

       {

           for (int i = 0; i < node.Children.Count; i++)

           {

               var isLast = i == node.Children.Count – 1;

               yield return (isLast ? "└─" : "├─") + node.Children[i].Text;

               foreach (var child in DumpLine(node.Children[i]))

                   yield return (isLast ? "  " : "│ ") + child;

           }

       }

    }

    Ce n'est pas la plus performante mais j'aime la simplicité d'écriture et le fait de se passer de calcul de la profondeur de la récursivité. En effet, ici, tout est résolu en jouant sur le positionnement avant et au retour de la récursivité.

    La même en F#:

    let Dump(node : Node) =

       let rec DumpLine(node : Node) =

           seq { for i in 0 .. node.Children.Count – 1 do

                   let isLast = (i = node.Children.Count – 1)

                   yield (if isLast then "└─" else "├─") + node.Children.[i].Text

                   for child in DumpLine node.Children.[i] do

                       yield (if isLast then "  " else "│ ") + child

               }

       node.Text + "n" + String.Join("n", DumpLine node)