The "Levenshtein" game 1

[tgreer]

The "Levenshtein Difference" measures the difference in two strings, that is to say, how many characters must be changed to make two strings equal. I'm using "strings" in the technical sense.

I thought it an appropriate name of a game wherein you change one letter of a word at a time to transform it into another word. Whoever can make the transformation in the least steps, wins. It's easiest with 4-letter words. In homage to another thread, I give you WORD to MEAN in 5 steps:

CTRL-A to see answer.
[COLOR=white]
WORD
WORE
MORE
MORN
MOAN
MEAN
[/color]

Can you do better?

Thomas D. Greer

Providing PostScript & PDF
Training, Development & Consulting

 

[tgreer]

Hint: it can be done in 4 steps. Can it be done in 3?

Thomas D. Greer

Providing PostScript & PDF
Training, Development & Consulting

 

[gmmastros]

how's this?

[white]word
worn
morn
moan
mean[/white]

-George

Strong and bitter words indicate a weak cause. - Fortune cookie wisdom

 

[johnwm]

Since you have 4 letters to change, and can only change one at a time, it seems unlikely that it's possible in 3 moves!

________________________________________________________________
If you want to get the best response to a question, please check out FAQ222-2244 first.
'If we're supposed to work in Hex, why have we only got A fingers?'
Drive a Steam Roller

 

[tgreer]

Exactly

Thomas D. Greer

Providing PostScript & PDF
Training, Development & Consulting

 

[tgreer]

So let's try another pair, how about:

WARM to PIES

Ok, I'm hungry, and there are warm pies waiting for me.

Thomas D. Greer

Providing PostScript & PDF
Training, Development & Consulting

 

[tgreer]

7 steps:

WARM to PIES
[COLOR=white]
0. WARM
1. BARM (term used in brewing beer)
2. BERM
3. TERM
4. TEEM
5. TEES
6. TIES
7. PIES
[/color]

Thomas D. Greer

Providing PostScript & PDF
Training, Development & Consulting

 

[craigsboyd]

[COLOR=white]0. WARM
1. WARS
2. PARS
3. PATS
4. PITS
5. PIES[/color]

SweetPotato Software Website
My Blog

 

[SantaMufasa]

How about four transformations for four letters:

[COLOR=white]WARM
WARS
PARS
PIRS (a religious instructor, esp. in mystical sects)
PIES[/color]

Mufasa
(aka Dave of Sandy, Utah, USA)
[

http://www.dasages.com:

Providing low-cost remote Database Admin services]
Click here to join Utah Oracle Users Group on Tek-Tips if you use Oracle in Utah USA.

 

[tgreer]

I don't see "pirs" defined in my dictionaries. Can you provide a reference?

Thomas D. Greer

Providing PostScript & PDF
Training, Development & Consulting

 

[PaulTEG]

a religious instructor, esp. in mystical sects<-- is this a typo ??

cigless ...

 

[SantaMufasa]

Sure: pir. To be without this link, one might be "pirless" <grin>.

Mufasa
(aka Dave of Sandy, Utah, USA)
[

http://www.dasages.com:

Providing low-cost remote Database Admin services]
Click here to join Utah Oracle Users Group on Tek-Tips if you use Oracle in Utah USA.

 

[tgreer]

Thank you! I can add it to my lexicon.

Thomas D. Greer

Providing PostScript & PDF
Training, Development & Consulting

 

[craigsboyd]

That is so unfair! I was going to use Pirs, but rejected it because it is Farsi and not English. SantaMufasa you've clearly cheated.

SweetPotato Software Website
My Blog

 

[tgreer]

next pair is "NEXT to PAIR"


Thomas D. Greer

Providing PostScript & PDF
Training, Development & Consulting

 

[SantaMufasa]

I always cheat...like when I use clearly foreign words such as:

chimpanzee, impala, marimba, zombie (Bantu)

gumbo, juke, okra, voodoo, yam (West Africa)

kaftan, coffee, divan, horde, mammoth, tartar, turquoise, yogurt (Turkey)

boomerang, kangaroo, koala, kookaburra, wallaby, wombat (Australian Aborigine)

junk, batik (Javanese)

bamboo, caddy, camphor, cockatoo, gecko, gingham, gong, compound, rattan, sarong (Malay)

hula, kiwi, lanai, lei, muumuu, taboo, tattoo, ukelele (Polynesian)

chaparral, jai alai (Basque)

patio, lasso, rodeo, aficionado, armada, bronco, burro, cafeteria, caldera, cargo, chili, corral, mosquito, nacho, peyote, plaza, rumba, silo, tomato, tuna, vanilla, and vigilante (Spanish)

catamarran, curry, mango, pariah (Tamil)

aardvark, apartheid, commando, trek (Afrikaans)

howitzer, pistol, robot, ahoy (Czech)

bluff, boor, boss, brandy, bully, bumpkin, clamp, clipper, coleslaw, cookie, dapper, derrick, dope, drill, drum, easel, frolic, golf, grime, hunk, kink, loiter, rant, runt, scow, skipper, sled, slim, smack, smuggle, snap, snoop, splint, spook, stoop, yacht (Dutch)

aperitif, cafe, chef, croissant, cuisine, debut, debacle, dessert, elite, envoy, fiance, garage, gourmet, hotel, liaison, limousine, lingerie, morale, parole, petite, prestige, regime, silhouette, souvenir, vignette, voyeur (French)

blitz, dachshund, dote, frankfurter, hamburger, kindergarten, pretzel, quartz, tackle, waltz (German)

bungalow, dinghy, loot, shampoo, (Hindi)

geyser, saga (Icelandic)

lemming, krill, ski, slalom (Norwegian)

bazaar, caravan, check, checkmate, dervish, jackal, khaki, kiosk, lilac, magic, mogul, pajamas, paradise, peach, pilaf, shawl, spinach, talc, tiara, tulip, turban (Farsi [Persian/Irani])

Could go on, but you're already bored (German), so I'll quit (French). So, yes, I always cheat [especially at Scrabble (with a little help from my foreign friends)<grin>.


Mufasa
(aka Dave of Sandy, Utah, USA)
[

http://www.dasages.com:

Providing low-cost remote Database Admin services]
Click here to join Utah Oracle Users Group on Tek-Tips if you use Oracle in Utah USA.

 

[tgreer]

NEXT to PAIR, 8 steps. Surely someone can beat this.
[COLOR=white]
0 NEXT
1 NEAT
2 HEAT
3 HEAL
4 HELL
5 HALL
6 HAIL  or  PALL
7 PAIL  
8 PAIR
[/color]

Thomas D. Greer

Providing PostScript & PDF
Training, Development & Consulting

 

[SantaMufasa]

I can name that tune in 6 steps:

[COLOR=white]0 NEXT
1 NEST
2 PEST
3 PERT
4 PART
5 PARR
6 PAIR[/color]

Mufasa
(aka Dave of Sandy, Utah, USA)
[

http://www.dasages.com:

Providing low-cost remote Database Admin services]
Click here to join Utah Oracle Users Group on Tek-Tips if you use Oracle in Utah USA.

 

[craigsboyd]

Given that we are dealing with the Levenshtein Distance, I can name that tune in 5 steps:

[COLOR=white]0. NEXT
1. NET
2. PET
3. PAT
4. PAR
5. PAIR[/color]

I think my post may illustrate the need for some formalized rules. After having read up on this, it appears that we are adhering to the operations for the Hamming Distance with a twist. The rules here appear to be that each derivation must be of equal length to the original and also be words that can be found in some English lexicon of note. But these rules are, for the most part, implicit at the moment.

There are other operations that are generally accepted for computing the Levenshtein Distance. Such as dropping or adding characters, and even switching the position of characters. Thomas, would you care to take a stab at formalizing the rules so SantaMufasa and I can accurately accuse one another of cheating? <g>

SantaMufasa,

I knew better than to call you a cheater! <bg>

SweetPotato Software Website
My Blog

 

[tgreer]

Craig,

I accept your rules and clarification on the Levenshtein distance.

Namely, all words must have the same number of letters. Only one letter may change at a time. Each word in the sequence must be, in this case, English. An "English word" is one that is found in a dictionary of the English language.

Let's also stipulate that proper nouns may not be used. So with "next/pair", SantaMufasa is the leader. "Parr", which is a salmon in a particular stage of growth, is brilliant.

I had:

NEXT
NEST
PEST
PAST...

and then got stuck, seeing how PAIT nor PASR are words.


Thomas D. Greer

Providing PostScript & PDF
Training, Development & Consulting