2
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2014 at 7:10
  • $\begingroup$ That's right. So it seems that you now have what you wanted. $\endgroup$
    – d'alar'cop
    Sep 28, 2014 at 7:12
  • $\begingroup$ @seteropere I recalled that I used to actually play this game. $\endgroup$
    – d'alar'cop
    Sep 28, 2014 at 7:23
  • $\begingroup$ @seteropere If this resolves your problem, please tick the answer. $\endgroup$
    – d'alar'cop
    Oct 1, 2014 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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