using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
namespace FourLetters
{
class Program
{
static void Main(string[] args)
{
var words = File.ReadAllLines(@"C:\temp\input.txt");
var g = new LadderGraph(@"C:\temp\longest.txt");
foreach (var word in words)
{
g.Add(word);
}
Console.WriteLine("Done: " + g.GetLongestLadder().Count());
}
}
public class LadderGraph
{
public IList<WordNode> Nodes;
private int wordLength;
private int letterDifferences;
static int longest = 0;
static object longLock = new object();
private string outputFilename;
public LadderGraph(string outputFilename, int wordLength = 4, int letterDifferences = 1)
{
this.outputFilename = outputFilename;
this.Nodes = new List<WordNode>();
this.wordLength = wordLength;
this.letterDifferences = letterDifferences;
}
public void Add(string word)
{
var node = new WordNode(word);
Connect(node);
this.Nodes.Add(node);
}
public IList<string> GetLongestLadder()
{
var paths = new List<IList<string>>();
Parallel.ForEach(this.Nodes, n =>
{
var longest = GetLongestPathFromNode(n);
Console.WriteLine(string.Format("done path starting at {0}", n.Word));
lock(paths)
{
paths.Add(longest);
}
});
return paths.OrderByDescending(x => x.Count()).FirstOrDefault();
}
public IList<string> GetLongestPathFromNode(WordNode source)
{
var currentPath = new List<WordNode>();
var longestPath = new List<WordNode>();
var visited = new HashSet<WordNode>();
foreach(var n in source.Neighbors)
{
currentPath.Clear();
visited.Clear();
Go(currentPath, n, longestPath, visited);
}
return longestPath.Select(x => x.Word).ToList();
}
private void Go(IList<WordNode> currentPath, WordNode next, IList<WordNode> longestPath, ISet<WordNode> visited)
{
currentPath.Add(next);
visited.Add(next);
if(currentPath.Count() > longestPath.Count())
{
longestPath.Clear();
foreach(var c in currentPath)
{
longestPath.Add(c);
}
lock(longLock)
{
if(longestPath.Count() > LadderGraph.longest)
{
LadderGraph.longest = longestPath.Count();
Console.WriteLine(LadderGraph.longest);
File.WriteAllLines(this.outputFilename, longestPath.Select(x => x.Word).ToArray());
}
}
}
foreach(var neighbor in next.Neighbors.Where(n => !visited.Contains(n)).ToArray())
{
Go(currentPath, neighbor, longestPath, visited);
}
currentPath.Remove(next);
visited.Remove(next);
}
private void Connect(WordNode sourceNode)
{
foreach(var potentialNeighbor in this.Nodes)
{
if(NodesAreNeighbors(sourceNode, potentialNeighbor))
{
ConnectNodes(sourceNode, potentialNeighbor);
}
}
}
private bool NodesAreNeighbors(WordNode node1, WordNode node2)
{
var a = node1.Word.ToCharArray();
var b = node2.Word.ToCharArray();
var differences = 0;
for (int i = 0; i < a.Length; i++)
{
if(a[i] != b[i])
{
differences++;
}
}
return differences == this.letterDifferences;
}
private void ConnectNodes(WordNode a, WordNode b)
{
a.Neighbors.Add(b);
b.Neighbors.Add(a);
}
}
public class WordNode : IEquatable<WordNode>
{
public string Word;
public IList<WordNode> Neighbors;
public WordNode(string word)
{
this.Word = word;
this.Neighbors = new List<WordNode>();
}
public bool Equals(WordNode w)
{
return this.Word == w.Word;
}
public override bool Equals(object o)
{
return this.Word == ((WordNode)o).Word;
}
public override int GetHashCode()
{
return this.Word.GetHashCode();
}
}
}