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();
        }
    }
}