| 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 |
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 17:35 | 2 |
| 1627.2 | TRACE::GILBERT | Ownership Obligates | Fri Jun 12 1992 21:32 | 3 | |
| 1627.3 | 10 here | WECARE::GRIFFIN | Sat Jun 13 1992 05: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 11: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 13: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 09:17 | 5 | |
> Are there word linkages that require more steps? See note 1565. Andrew. | |||||