Saturday, April 9, 2016

Alphabet Slider, Cont'd

The slider mechanism in the Alphabet Slider puzzle determines what's called a "partial ordering" on three-letter words. Specifically, given two words w1 and w2, we write

w1 < w2 

if every letter of w1 occurs earlier in the alphabet than the corresponding letter of w2. For example, we write

ACE < PYX

because A is earlier in the alphabet than P, C is earlier in the alphabet than Y, and E is earlier in the alphabet than X.

There exist words "between" ACE and PYX. For example,

ACE < EON < PYX

as you can check. A solution to the Alphabet Slider is a chain like the one above, and the goal is to find the longest possible chain. With the help of a computer, I found this solution:

ACE < BEG < CHI < DIM < EON < FRO < ITS < JUT < PYX.

(An equally long chain results from using NUT instead of JUT. A reader also notes that OUT could go in this position.)

Here's a picture—note that lines never cross.

The game can be played with words of any length. For example, here's a pretty good chain of four-letter words:

ABBE < DILL < ELMS < FONT < GROW < JURY.

For eight-letter words, I found

HEADACHE > KNEELING > SPONSORS.

2 comments:

mdahlman said...

Can you easily run your program for the variation where "at least one slider must move at each step"? Your original game is interesting. But the move-one-slider variation seems more interesting in some respects. It won't be a partial ordering, so the algorithm is perhaps more complex. And I suspect it will yield more high frequency words (which I suppose could be consider less interesting or more interesting).

Intuitively, "should I move this slider or that slider now?" is an interesting decision.

Jason Zimba said...

Thank you for this comment! I'm at conferences and haven't had time to pursue it, but I'd like to and will report back if I get anywhere on it. As you say, some interesting moments come up in this variation.