Skip to content

Instantly share code, notes, and snippets.

@sudipto80
Last active January 4, 2016 09:24
Show Gist options
  • Save sudipto80/09bb118ff06661d5bd07 to your computer and use it in GitHub Desktop.
Save sudipto80/09bb118ff06661d5bd07 to your computer and use it in GitHub Desktop.
Doublet Cheater
void Main()
{
HashSet<string> allWords = new HashSet<string>(File.ReadAllText(@"C:\T9.txt")
.Split(new char[]{' ','\n'},StringSplitOptions.RemoveEmptyEntries));
Transform2("myth","fact",allWords).Dump("Transform2");
Transform2("damp","like",allWords).Dump("Transform2");
Transform2("door","room",allWords).Dump("Transform2");
Transform2("dawn","boat",allWords).Dump("Transform2");
Transform2("dear","read",allWords).Dump("Transform2");
Transform2("ornament","oriental",allWords).Dump("Transform2");
}
List<string> Transform2(string start, string stop,
HashSet<string> allWords)
{
List<string> ladder = new List<string>();
HashSet<string> visited = new HashSet<string>();
ladder.Add(start);
string lastWord = string.Empty;
while (start != stop)
{
var probableLadder = OneEditAway(start,stop,allWords)
.OrderBy (item => item.Value);
if(probableLadder.Count () == 1
&& probableLadder.First ().Key == ladder[ladder.Count - 2])
//We saw a value before so we are caught up in an infinite loop. So break
return new List<string>();
if(probableLadder.Count ()!=0)
{
foreach (var pair in probableLadder)
{
if(!visited.Contains(pair.Key))
{
visited.Add(pair.Key);
ladder.Add(pair.Key);
start = pair.Key;
break;
}
}
}
else //Nowhere to go from this current word. We are hitting a wall. return.
return new List<string>();
}
return ladder;
}
int Hamming(string a,string b)
{
if(a.Length!=b.Length)
return int.MaxValue;
else
{
int dist = 0;
for(int i = 0;i<a.Length;i++)
{
if(a[i] != b[i])
dist++;
}
return dist;
}
}
List<KeyValuePair<string,int>> OneEditAway(string word,string end, HashSet<string> dictionary)
{
List<KeyValuePair<string,int>> all = new List<KeyValuePair<string,int>>();
foreach (var w in dictionary)
{
if(Hamming(w,word)==1)
all.Add(new KeyValuePair<string,int>(w,Hamming(w,end)));
}
return all;
}
// Define other methods and classes here
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment