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
Anonymous
October 21, 2010
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(); } #endifAnonymous
October 21, 2010
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); } }Anonymous
October 21, 2010
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++; } }Anonymous
October 21, 2010
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); } } }Anonymous
October 21, 2010
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!!!Anonymous
October 23, 2010
@miitch : les cours d'Ocaml de l'école te manquent ? :-)Anonymous
October 23, 2010
@miitch : les cours d'Ocaml de l'école te manquent ? :-)Anonymous
October 24, 2010
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(); } }Anonymous
October 24, 2010
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 !) :pAnonymous
October 25, 2010
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()); } } }Anonymous
October 25, 2010
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; } }Anonymous
October 25, 2010
Oups illisible... Sorry pour l'indent et les u2514 et u251cAnonymous
October 26, 2010
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)); } }Anonymous
October 26, 2010
+1 pour le Y Combinator. Si tu pouvais ajouter un générateur monadique, ce serait parfait.Anonymous
October 28, 2010
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)