# Whats the name of this search game?

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.

## 1 Answer

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.

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