Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Dec 4th, 2012  |  syntax: C#  |  size: 3.84 KB  |  views: 89  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6. using System.IO;
  7.  
  8. namespace FourLetters
  9. {
  10.         class Program
  11.         {
  12.                 static void Main(string[] args)
  13.                 {
  14.                         var words = File.ReadAllLines(@"C:\temp\input.txt");
  15.                         var g = new LadderGraph(@"C:\temp\longest.txt");
  16.                         foreach (var word in words)
  17.                         {
  18.                                 g.Add(word);
  19.                         }
  20.                         Console.WriteLine("Done: " + g.GetLongestLadder().Count());
  21.                 }
  22.         }
  23.  
  24.         public class LadderGraph
  25.         {
  26.                 public IList<WordNode> Nodes;
  27.                 private int wordLength;
  28.                 private int letterDifferences;
  29.                 static int longest = 0;
  30.                 static object longLock = new object();
  31.                 private string outputFilename;
  32.  
  33.                 public LadderGraph(string outputFilename, int wordLength = 4, int letterDifferences = 1)
  34.                 {
  35.                         this.outputFilename = outputFilename;
  36.                         this.Nodes = new List<WordNode>();
  37.                         this.wordLength = wordLength;
  38.                         this.letterDifferences = letterDifferences;
  39.                 }
  40.        
  41.                 public void Add(string word)
  42.                 {
  43.                         var node = new WordNode(word);
  44.                         Connect(node);
  45.                         this.Nodes.Add(node);
  46.                 }
  47.        
  48.                 public IList<string> GetLongestLadder()
  49.                 {
  50.                         var paths = new List<IList<string>>();
  51.                         Parallel.ForEach(this.Nodes, n =>
  52.                         {
  53.                                 var longest = GetLongestPathFromNode(n);
  54.                                 Console.WriteLine(string.Format("done path starting at {0}", n.Word));
  55.                                 lock(paths)
  56.                                 {
  57.                                         paths.Add(longest);
  58.                                 }
  59.                         });
  60.                         return paths.OrderByDescending(x => x.Count()).FirstOrDefault();
  61.                 }
  62.        
  63.                 public IList<string> GetLongestPathFromNode(WordNode source)
  64.                 {
  65.                         var currentPath = new List<WordNode>();
  66.                         var longestPath = new List<WordNode>();
  67.                         var visited = new HashSet<WordNode>();
  68.                         foreach(var n in source.Neighbors)
  69.                         {
  70.                                 currentPath.Clear();
  71.                                 visited.Clear();
  72.                                 Go(currentPath, n, longestPath, visited);
  73.                         }
  74.                         return longestPath.Select(x => x.Word).ToList();
  75.                 }
  76.        
  77.                 private void Go(IList<WordNode> currentPath, WordNode next, IList<WordNode> longestPath, ISet<WordNode> visited)
  78.                 {
  79.                         currentPath.Add(next);
  80.                         visited.Add(next);
  81.                         if(currentPath.Count() > longestPath.Count())
  82.                         {
  83.                                 longestPath.Clear();
  84.                                 foreach(var c in currentPath)
  85.                                 {
  86.                                         longestPath.Add(c);
  87.                                 }
  88.                                 lock(longLock)
  89.                                 {
  90.                                         if(longestPath.Count() > LadderGraph.longest)
  91.                                         {
  92.                                                 LadderGraph.longest = longestPath.Count();
  93.                                                 Console.WriteLine(LadderGraph.longest);
  94.                                                 File.WriteAllLines(this.outputFilename, longestPath.Select(x => x.Word).ToArray());
  95.                                         }
  96.                                 }
  97.                         }
  98.                         foreach(var neighbor in next.Neighbors.Where(n => !visited.Contains(n)).ToArray())
  99.                         {
  100.                                 Go(currentPath, neighbor, longestPath, visited);
  101.                         }
  102.                         currentPath.Remove(next);
  103.                         visited.Remove(next);
  104.                 }
  105.        
  106.                 private void Connect(WordNode sourceNode)
  107.                 {
  108.                         foreach(var potentialNeighbor in this.Nodes)
  109.                         {
  110.                                 if(NodesAreNeighbors(sourceNode, potentialNeighbor))
  111.                                 {
  112.                                         ConnectNodes(sourceNode, potentialNeighbor);
  113.                                 }
  114.                         }
  115.                 }
  116.        
  117.                 private bool NodesAreNeighbors(WordNode node1, WordNode node2)
  118.                 {
  119.                         var a = node1.Word.ToCharArray();
  120.                         var b = node2.Word.ToCharArray();
  121.                         var differences = 0;
  122.                         for (int i = 0; i < a.Length; i++)
  123.                         {
  124.                                 if(a[i] != b[i])
  125.                                 {
  126.                                         differences++;
  127.                                 }
  128.                         }
  129.                         return differences == this.letterDifferences;
  130.                 }
  131.        
  132.                 private void ConnectNodes(WordNode a, WordNode b)
  133.                 {
  134.                         a.Neighbors.Add(b);
  135.                         b.Neighbors.Add(a);
  136.                 }
  137.         }
  138.        
  139.         public class WordNode : IEquatable<WordNode>
  140.         {
  141.                 public string Word;
  142.                 public IList<WordNode> Neighbors;
  143.  
  144.                 public WordNode(string word)
  145.                 {
  146.                         this.Word = word;
  147.                         this.Neighbors = new List<WordNode>();
  148.                 }
  149.  
  150.                 public bool Equals(WordNode w)
  151.                 {
  152.                         return this.Word == w.Word;
  153.                 }
  154.  
  155.                 public override bool Equals(object o)
  156.                 {
  157.                         return this.Word == ((WordNode)o).Word;
  158.                 }
  159.  
  160.                 public override int GetHashCode()
  161.                 {
  162.                         return this.Word.GetHashCode();
  163.                 }
  164.         }
  165. }