[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

1627.0. "Word Linkages" by TRACE::GILBERT (Ownership Obligates) Fri Jun 12 1992 13:44

    We've all seen 'word linkage' problems.  For example:
    
	Problem:  Change LEAD to GOLD in 3 steps.
	Solution: LEAD LOAD GOAD GOLD.

    (The idea is to form a sequence of words that connect the two given words.
     Adjacent words in the sequence differ only by one changed character.)
    
    Okay, here's a *much* harder problem:  Change EWER to INKS.
    I can do it in 26 steps.  Can this be improved?

    Are there word linkages that require more steps?

    If length isn't a reasonable measure of difficulty, what is?
    (assuming the solver doesn't use a computer).

T.R	Title	User	Personal Name	Date	Lines
1627.1	I can link those words in ...	VMSDEV::HALLYB	Fish have no concept of fire.	`Fri Jun 12 1992 14:35`	2
	13 steps, if you permit �fils� which is in my dictionary as 1/1000 of a dinar.
1627.2		TRACE::GILBERT	Ownership Obligates	`Fri Jun 12 1992 18:32`	3
	�fils� wasn't in my dictionary (which was the on-line Scrabble � dictionary. But I found it in the new Webster's Unabridged -- with it's French definition and no mention of dinars!
1627.3	10 here	WECARE::GRIFFIN		`Sat Jun 13 1992 02:22`	8
	I get the transformation in 10 steps, using non-obscure words. Isn't the general problem here one of language (or word) recognition --- as in, "automata theory"? From the complexity point of view, if we're talking about checking transformations against a finite dictionary, (given various relevant restrictions in place on the English language), I don't think this is a "hard" problem.
1627.4	Suggestions for part 3	UNTADA::TOWERS		`Mon Jun 15 1992 08:38`	13
	Apart from length I'd say that were two other obvious metrics for difficulty - Choice The more choices you have at any stage the more difficult the problem. Hence the example in .0 is easy for its length because there are few choices for where to go from INKS. Obscurity The more words along the way that you have to get right that are obscure, the more difficult the problem. Brian
1627.5	optimality?	MOCA::BELDIN_R	All's well that ends	`Mon Jun 15 1992 10:15`	7
	-.1 suggests that too many choices and too few are both likely to complicate the problem, "too many" because of combinatorial explosion and "too few" because of the "recognition" problem (which depends on the efficiency of the search technique). That combination suggests there may be some way to formulate an optimality criterion. /rab
1627.6	x-ref	DESIR::BUCHANAN		`Mon Jul 06 1992 06:17`	5
	> Are there word linkages that require more steps? See note 1565. Andrew.