Minimizing Letters

Question

The example below shows the amount of letters in the word being minimized by 1 each time, but the letters still form a legitimate word:

What is the longest set like this with the initial word longer or equal to 6 letters long?

Answer 1

I think it will be very difficult to find a confirmed count of all possible words for this. It seems very open-ended. Perhaps it should be switched to a contest to find the longest?

---

_{Everything below this is copied from @Kevin from a very similar question}

I'm using the circa 2013 Words With Friends dictionary.

If you can only add to the right end of the word, 8-letter words are possible:

a
ba
bar
barb
barbe
barbel
barbell
barbells

a
ma
max
maxi
maxim
maxima
maximal
maximals

a
pa
pas
past
paste
paster
pastern
pasterns

If you can add to either end, 9-letter words are possible:

I
id
aid
aide
aider
aiders
raiders
braiders
abraiders

a
la
lap
laps
lapse
elapse
relapse
relapser
relapsers

I
in
pin
ping
aping
raping
craping
scraping
scrapings

a
at
eat
eath
heath
sheath
sheathe
sheather
sheathers

I
is
ais
rais
raise
raiser
raisers
praisers
upraisers

If you can add at any point, 11-letter words are possible:

I   
pi
pig
ping
oping
coping
comping
compting
competing
completing
complecting

Answer 2

Using Mathematica's dictionary, my longest chain is:

10 Letters:

SPLITTINGS, SPLITTING, SLITTING, SITTING, SITING, STING, SING, SIN, IN, I

My code is below, it takes less than a second to run.

words = ToUpperCase @ DictionaryLookup[___];

g = Graph[Join @@ Table[StringDrop[w, {#}] -> w & /@ Range[StringLength[w]], {w, words}]];

reachable = VertexOutComponent[g, {""}];

MaximalBy[reachable, StringLength]

FindShortestPath[g, "", First @ %]

The strategy is to create a tree-like structure were each word is linked to all the "words" that can be created by dropping one letter. Some of those words are not in the dictionary (psuedo-words), but they can be ignored since there is no path to them from the root node (the empty word).

Once this structure is created, finding the solution is simple: find the longest word that can be reached from the root node.

How many?

To answer your original question (how many chains are there), we can try counting the number of reachable words of each length:

Grid[List @@@ Normal@GroupBy[reachable, StringLength, Length]]

0   1
1   2
2   29
3   254
4   942
5   1561
6   1390
7   878
8   325
9   51
10  1

A total of 2645 words at least six letters long can be put into a chain. This doesn't exactly answer your question however, since some words can be reached in multiple ways:

AcyclicGraphQ[UndirectedGraph@g] (* False *)

In order to find the total number of ways to make each word, I make use of a recursive enumeration:

The number of ways to make a word is equal to the sum of the number of ways to make each of its predecessors.

From here we can make use of the adjacency matrix of our graph. The adjacency matrix $A$ has entries $a_{ij}$ equal to the number of edges from vertex $i$ to vertex $j$. If the number of ways to make the word (vertex) $i$ is $c_i$, then we can write:

$$ c_i = \sum_j c_j a_{ji} $$

Notice this is exactly equal to the matrix multiplication $c=A^{\intercal} c$, making finding $c$ equivalent to finding the eigenvector of $A^{\intercal}$. (There is one complication: we have to set $a_{11}=1$, otherwise the number of ways to reach the empty word "" is zero.)

clean = Subgraph[g, reachable]; (* remove unreachable words *)
m = AdjacencyMatrix[clean];
m[[1, 1]] = 1;
e = First@Eigenvectors[N@Transpose@m, 1];
Total[Pick[Round[e/First[e]], VertexList[clean], x_ /; StringLength[x] >= 6]]

giving an answer of 26,322 (for Mathematica's word list). This solution is very fast, even on much larger word lists (~100,000 words).

Answer 3

I'm confused as to whether the question is "How many six-letter words can you find that fit this pattern?" or "What is the longest word you can create that fits this pattern?" I will answer the latter.

Longest word: 9 letters

CLEANSERS
CLEANSES
CLEANSE
CLEANS
CLEAN
LEAN
LEA
LA
A

Answer 4

Without resorting to (read as: figuring out) a program to determine all the possible and best answers, here is what I've come up with for words longer than six letters:

amasses masses masse mass ass as a (though the E should have an accent in masse...)

mangled mangle mange mane man an a
sharped shared shard hard had ad a

EIGHT!

prattled rattled ratted rated rate rat at a
startled started stated state stat tat at a

Forget EIGHT, move on to NINE!

spiriting spirting spiting siting sting sing sin in i
(spirting is antiquated, so 8 and 9 could be splitting and spitting)

Answer 5

I have one that's six (or seven if you count proper nouns)

I
IN
SIN
SINE
SPINES
SPLINES
SPLINERS - questionable, it's a company name

edit: improvement

I
IN
PIN
PINE
PINED
SPINED
SPLINED

edit: and one starting with O

O
ON
TON
TONE
TONER
STONER
STONIER

Answer 6

SKATERS
SKATER
SKATE
SATE
ATE
AT
A

and...

STRAINS
TRAINS
TRAIN
RAIN
RAN
AN
A

Another!

BRAINED
BRINED
BRINE
BINE
BIN
IN
I

I'll keep thinking on this one...

Answer 7

escape

scape

cape

ape

pe

e

with six letters