I am struggling in finding the name of this game (in order to find research papers related to it in the literature).

Given an initial word $X$ and a target word $Y$, what is the minimum number of (letter) flips needed for $X$ to reach $Y$ assuming $X$ and $Y$ having the same number of letters, we flip only one letter each time and such sequence(s) of flips exist.

That is, there is a sequence $A_1\rightarrow A_2\rightarrow \dots\rightarrow A_n$ where $X=A_1$ and $Y=A_n$ and every thing in between is a correct word (i.e. has a meaning in a given dictionary).

For instance, $X=Pork\rightarrow Park\rightarrow Dark=Y$

Yes; I do not have the minimum knowledge in games.


I think you are referring to Hamming Distance. See http://en.wikipedia.org/wiki/Hamming_distance.

As for a game, having the extra condition that intermediate modifications must be real words is the Word Ladder. See http://en.wikipedia.org/wiki/Word_ladder.

  • $\begingroup$ Yes. If there is such a sequence of flips then I need at least $HD(X,Y)$ flips to reach $Y$ from $X$. In other words, a sequence with $HD(X,Y)$ is an optimal sequence. $\endgroup$ – seteropere Sep 28 '14 at 7:10
  • $\begingroup$ That's right. So it seems that you now have what you wanted. $\endgroup$ – d'alar'cop Sep 28 '14 at 7:12
  • $\begingroup$ @seteropere I recalled that I used to actually play this game. $\endgroup$ – d'alar'cop Sep 28 '14 at 7:23
  • $\begingroup$ @seteropere If this resolves your problem, please tick the answer. $\endgroup$ – d'alar'cop Oct 1 '14 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.