Last active
January 4, 2016 09:24
-
-
Save sudipto80/09bb118ff06661d5bd07 to your computer and use it in GitHub Desktop.
Doublet Cheater
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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