Skip to content

Instantly share code, notes, and snippets.

@ff8c00

ff8c00/Hard.cs

Created June 29, 2017 16:12
Download ZIP

Revisions

  1. ff8c00 created this gist Jun 29, 2017.
    176 changes: 176 additions & 0 deletions Hard.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,176 @@
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Net;
    using System.Xml;
    using System.Xml.Linq;
    using System.Xml.XPath;

    namespace Reddit
    {
    internal static class Hard
    {
    internal static void Run()
    {
    Run("Molecule");
    }

    internal static void Run(string input)
    {
    var visited = new HashSet<string>();
    visited.Add("Philosophy");

    string value = input;
    while (value != null)
    {
    Console.WriteLine(value);
    if (visited.Contains(value))
    {
    value = null;
    }
    else
    {
    visited.Add(value);
    value = Next(value);
    }
    }
    }

    internal static string Next(string input)
    {
    string content = Download(input);
    if (content != null)
    {
    var parentheses = new Parentheses();
    parentheses.Load(content);

    var root = XElement.Parse(content, LoadOptions.SetLineInfo);

    var items = root.Descendants("a").ToList();
    if (items.Count > 0)
    {
    foreach (var item in items.Where(e =>
    e.Attribute("title") != null &&
    e.Attribute("href") != null))
    {
    int position = ((IXmlLineInfo)item).LinePosition;
    if (parentheses.Surround(position) == false)
    {
    return item.Attribute("title").Value;
    }
    }
    }
    }
    return null;
    }

    internal static string Download(string input)
    {
    var uri = new Uri("https://en.wikipedia.org/wiki/" + input);
    using (var client = new WebClient())
    {
    string value = client.DownloadString(uri);

    var root = XElement.Parse(value);
    var content = root.XPathSelectElement(
    "/body/div[@id='content']/div[@id='bodyContent']" +
    "/descendant::p[1]");

    if (content != null)
    {
    return content.ToString(SaveOptions.DisableFormatting);
    }
    }
    return null;
    }
    }

    internal class Parentheses
    {
    internal List<Node> Nodes;

    internal void Load(string input)
    {
    const char start = '(', end = ')';

    var root = new Node();
    root.Index = -1;
    root.Length = -1;

    var child = root;

    for (int i = 0; i < input.Length; i++)
    {
    if (input[i] == start)
    {
    var node = new Node();
    node.Index = i;
    node.Length = -1;
    node.Parent = child;

    child.Add(node);
    child = node;
    }
    else
    {
    if (input[i] == end)
    {
    if (child.Index != -1)
    {
    child.Length = (i - child.Index) + 1;
    child = child.Parent;
    }
    }
    }
    }

    Nodes = new List<Node>(root.Flatten());
    }

    internal bool Surround(int position)
    {
    foreach (var node in Nodes)
    {
    if (position >= node.Index &&
    position <= node.Index + node.Length)
    {
    return true;
    }
    }
    return false;
    }

    internal class Node
    {
    internal int Index;
    internal int Length;

    internal Node Parent;

    internal List<Node> Children = new List<Node>();

    internal void Add(Node node)
    {
    Children.Add(node);
    }

    internal IEnumerable<Node> Flatten()
    {
    if (Length != -1)
    {
    yield return this;
    }
    else
    {
    foreach (var child in Children)
    {
    foreach (var node in child.Flatten())
    {
    yield return node;
    }
    }
    }
    }
    }
    }
    }