I have not written code in C# in a long time lately I have been consumed with Java, SpingBoot and Scala, when I found this a fun quiz I decided to code it in C#. The Quiz states the following given a list of line as follows
H1 Header 1
H2 Header 2
H3 Header 3
H4 header 4
H3 Header 3
H3 Header 3
H4 Header 4
H5 header 5
H2 Header 2
H2 Header 2
H1 Header 1
H2 Header 2
H2 Header 2
H3 header 3
We want to emit HTML that would represent the above as bolts as follows:
-
H1 Header 1
-
H2 Header 2
-
H3 Header 3
- H4 header 4
- H3 Header 3
-
H3 Header 3
-
H4 Header 4
- H5 header 5
-
-
- H2 Header 2
- H2 Header 2
-
-
H1 Header 1
- H2 Header 2
-
H2 Header 2
- H3 header 3
The list can contain more nested levels than 5.
Solution Algorithm
Provided we took care of the converting the strings into a list of classes Heading . containing the weight (1 -,2,3 ..) and text. The problem becomes going through the list one by one and creating a list of subtrees. The imaginary item with H0 is the root of the tree. All H1 nodes are subtrees of the main tree.
The alogrithm goes like this
-
For each item in the Headings list if the next item in the list has a weight higher than the current item
- Add the next item, and its children as children of the current node.
The code in C# below shows the solution heart for this Quiz.
private
static Node toOutline(List<Heading> headings)
{
// if No headings
if (headings.Count <= 0) return
null;
Node currentNode = null;
Node root = new Node(new Heading(0, “”));
currentNode = root;
int currentWeight = 0;
for (int i = 0; i < headings.Count;)
{
var heading = headings[i++];
Debug.WriteLine(heading.ToString());
currentNode = new Node(heading);
root.Children.Add(currentNode);
if (i >= headings.Count) break;
/// check if the next heading
if (currentWeight < headings[i].Weight)
{
Debug.WriteLine(heading.ToString()+” got children”);
currentNode.Children.AddRange(createChildren(currentNode, headings, ref i));
}
}
return root;
}
private
static IEnumerable<Node> createChildren(Node currentNode, List<Heading> headings, ref
int i)
{
List<Node> result = new List<Node>();
if (headings.Count <= 0) return result;
while (i+1 < headings.Count && headings[i].Weight > currentNode.Heading.Weight )
{
Heading currentHeading = headings[i++];
Node node = new Node(currentHeading);
result.Add(node);
if (headings[i].Weight > node.Heading.Weight)
{
node.Children.AddRange(createChildren(node, headings, ref i));
}
}
return result;
}
Complete Code
Below is the complete code, the test class checks two cases on header and one with multiple cases :
[TestClass]
public
class
UnitTest1
{
[TestMethod]
public
void TestOutlineSingle()
{
string[] lines = {“H1 header 1”};
Debug.WriteLine( nodes.Solution.Driver(lines));
}
[TestMethod]
public
void TestOutlineMultiple()
{
string[] lines = {“H1 header 1”,
“H2 header 2”,
“H2 header 2”,
“H3 header 3”,
“H3 header 3”,
“H4 header 4”,
“H5 header 5”,
“H4 header 4”,
“H3 header 1”,
“H2 header 2”,
“H3 header 3”,
“H3 header 3”,
“H1 header 1”,
“H2 header 2”,
“H3 header 3”,
“H3 header 3”,
“H4 header 4”,
“H5 header 5”,
“H3 header 3”,
“H2 header 2”
};
Debug.WriteLine(nodes.Solution.Driver(lines));
}
}
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
namespace nodes
{
class
Heading
{
int weight;
String text;
public
int Weight
{
get { return weight; }
}
public String Text
{
get { return text; }
}
public Heading(int weight, String text)
{
this.weight = weight;
this.text = text;
}
public
override
string ToString()
{
return
string.Format(“Heading {0} {1}”, weight, text);
;
}
}
class
Node
{
Heading heading;
List<Node> children;
public Heading Heading
{
get { return heading; }
}
public List<Node> Children
{
get { return children; }
}
public Node(Heading heading)
{
this.heading = heading;
this.children = new List<Node>();
}
}
public
class
Solution
{
public
static
string Driver(string[] lines)
{
var headings = new List<Heading>();
foreach (var line in lines)
{
headings.Add(parse(line));
}
var outline = toOutline(headings);
var html = toHtml(outline);
return html;
}
private
static Node toOutline(List<Heading> headings)
{
// if No headings
if (headings.Count <= 0) return
null;
Node currentNode = null;
Node root = new Node(new Heading(0, “”));
currentNode = root;
int currentWeight = 0;
for (int i = 0; i < headings.Count;)
{
var heading = headings[i++];
Debug.WriteLine(heading.ToString());
currentNode = new Node(heading);
root.Children.Add(currentNode);
if (i >= headings.Count) break; ;
if (currentWeight < headings[i].Weight)
{
Debug.WriteLine(heading.ToString()+” got children”);
currentNode.Children.AddRange(createChildren(currentNode, headings, ref i));
}
}
return root;
}
private
static IEnumerable<Node> createChildren(Node currentNode, List<Heading> headings, ref
int i)
{
List<Node> result = new List<Node>();
if (headings.Count <= 0) return result;
while (i+1 < headings.Count && headings[i].Weight > currentNode.Heading.Weight )
{
Heading currentHeading = headings[i++];
Node node = new Node(currentHeading);
result.Add(node);
if (headings[i].Weight > node.Heading.Weight)
{
node.Children.AddRange(createChildren(node, headings, ref i));
}
}
return result;
}
/** Parses a line of input.
This implementation is correct for all predefined test cases. */
private
static Heading parse(String record)
{
String[] parts = record.Split(” “.ToCharArray(), 2);
int weight = Int32.Parse(parts[0].Substring(1));
Heading heading = new Heading(weight, parts[1].Trim());
return heading;
}
/** Converts a node to HTML.
This implementation is correct for all predefined test cases. */
private
static String toHtml(Node node)
{
StringBuilder buf = new StringBuilder();
if (node.Heading.Text != “”)
{
buf.Append(node.Heading.Text);
buf.Append(“\n”);
}
if (node.Children.Count > 0)
{
buf.Append(“<ol>”);
var childStrings = node.Children.Select(child =>
“<li>” + toHtml(child) + “</li>”
);
buf.Append(String.Join(“\n”, childStrings));
buf.Append(“</ol>”);
}
return buf.ToString();
}
}
}
Moustafa Refaat Insghts 