{"id":593,"date":"2008-08-18T19:10:35","date_gmt":"2008-08-18T09:10:35","guid":{"rendered":"http:\/\/www.somethinkodd.com\/oddthinking\/?p=593"},"modified":"2008-08-18T19:19:53","modified_gmt":"2008-08-18T09:19:53","slug":"chemical-word-ladders","status":"publish","type":"post","link":"https:\/\/www.somethinkodd.com\/oddthinking\/2008\/08\/18\/chemical-word-ladders\/","title":{"rendered":"Chemical Word Ladders"},"content":{"rendered":"

The Challenge<\/h3>\n

Mark Nandor<\/a> is a school-teacher who has exhaustively listed<\/a> all of the 26,811 English words that can be spelled using only chemical symbols.<\/p>\n

But, he didn’t stop there with his musings. He came up with many little restrictions (one letter chemical symbols or no repeating). He also came up with Chemical Word Squares.<\/p>\n

Finally, in passing he wrote:<\/p>\n

\nChemical Word Ladders<\/p>\n

A word ladder is a list of words that only one character at a time, as this ladder provided by a reader:
\nFeN
\nFeAt
\nCoAt
\nCOAt
\nCHeAt
\nReHeAt
\nReHeAr<\/p>\n

At some point in the future, I’ll be looking to generate lists of these. If you beat me to it, let me know and I’ll link to your work!\n<\/p><\/blockquote>\n

That sounds like a challenge I could take up.<\/p>\n

The Method<\/h3>\n

I read in all of the 28,611 English words, and put them into an array of dictionaries, based on their word length.<\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Word Length<\/th>\nNumber of Words in Mark Nandor’s List<\/th>\n<\/tr>\n
1 <\/td>\n 0 <\/td>\n<\/tr>\n
2 <\/td>\n 47 <\/td>\n<\/tr>\n
3 <\/td>\n 351 <\/td>\n<\/tr>\n
4 <\/td>\n 1310 <\/td>\n<\/tr>\n
5 <\/td>\n 2516 <\/td>\n<\/tr>\n
6 <\/td>\n 3454 <\/td>\n<\/tr>\n
7 <\/td>\n 4278 <\/td>\n<\/tr>\n
8 <\/td>\n 4392 <\/td>\n<\/tr>\n
9 <\/td>\n 3406 <\/td>\n<\/tr>\n
10 <\/td>\n 2417 <\/td>\n<\/tr>\n
11 <\/td>\n 1693 <\/td>\n<\/tr>\n
12 <\/td>\n 1197 <\/td>\n<\/tr>\n
13 <\/td>\n 756 <\/td>\n<\/tr>\n
14 <\/td>\n 449 <\/td>\n<\/tr>\n
15 <\/td>\n 251 <\/td>\n<\/tr>\n
16 <\/td>\n 153 <\/td>\n<\/tr>\n
17 <\/td>\n 80 <\/td>\n<\/tr>\n
18 <\/td>\n 35 <\/td>\n<\/tr>\n
19 <\/td>\n 18 <\/td>\n<\/tr>\n
20 <\/td>\n 5 <\/td>\n<\/tr>\n
21 <\/td>\n 1 <\/td>\n<\/tr>\n
22 <\/td>\n 1 <\/td>\n<\/tr>\n
23 <\/td>\n 1 <\/td>\n<\/tr>\n<\/table>\n
I am not sure why Iodine (Chemical Symbol: I) doesn’t deserve a mention as a 1-letter word. I didn’t bother to correct it, though.<\/div>\n

Now, I arbitrarily decided what the shortest word-length in the ladder should be. In the example above, the anonymous reader started with a three-letter word. I went with that to begin with.<\/p>\n

I created another array of dictionaries, again based on word-length.<\/p>\n

In the first (length 3) dictionary, I put all of the 351 three-letter words from the master list.<\/p>\n

In the second dictionary (length 4), I put all of the four-letter words that could be built from a three-letter word. I did this by iterating through each of the 1310 four-letter words, and for each one, dropping each letter, and checking if the result was in the previous (3-letter) dictionary.<\/p>\n

I now had 680 four-letter words that could be formed from 3-letter words.<\/p>\n

I did it again, for five-letter words, filtering out the words that couldn’t be formed from four-letter words, and so on.<\/p>\n

Eventually, the dictionaries were empty.<\/p>\n

Now, each word may be able to reduce to more than one of the shorter words. So, for each word in the dictionary, I recorded a list of the shorter words it could reduce to.<\/p>\n

All that I needed to do next, was print the result.<\/p>\n

Results<\/h3>\n

How Many Words Can Be Produced From Three-Letters?<\/h4>\n\n\n\n\n\n\n\n\n\n\n\n\n
Word Length<\/th>\nNumber of Words That Can Be “Laddered” from Three-Letter Words<\/th>\n<\/tr>\n
1 <\/td>\n N\/A <\/td>\n<\/tr>\n
2 <\/td>\n N\/A <\/td>\n<\/tr>\n
3 <\/td>\n 351 (All of them) <\/td>\n<\/tr>\n
4 <\/td>\n 680 <\/td>\n<\/tr>\n
5 <\/td>\n 823 <\/td>\n<\/tr>\n
6 <\/td>\n 624 <\/td>\n<\/tr>\n
7 <\/td>\n 346 <\/td>\n<\/tr>\n
8 <\/td>\n 131 <\/td>\n<\/tr>\n
9 <\/td>\n 13 <\/td>\n<\/tr>\n
10 <\/td>\n 0 <\/td>\n<\/tr>\n<\/table>\n

All Nine-Letter To Three-Letter Chemical Ladders<\/h4>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
Nine-Letter Word<\/th>\nLadders That Lead To That Word<\/th>\n<\/tr>\n
pricklier<\/td>\n\n→ prickier → pickier → picker → piker → pier → per
\n→ prickier → pricier → pricer → prier → pier → per
\n→ prickier → pricker → picker → piker → pier → per
\n→ prickier → pricker → pricer → prier → pier → per \n<\/td>\n<\/tr>\n
upraisers<\/td>\n\n→ praisers → praises → prises → pries → pies → pes
\n→ praisers → praises → prises → pries → pies → pis
\n→ praisers → praises → prises → priss → piss → pis
\n→ praisers → praises → prases → pases → pass → ass
\n→ praisers → praises → prases → pases → pass → pas
\n→ uprisers → uprises → prises → pries → pies → pes
\n→ uprisers → uprises → prises → pries → pies → pis
\n→ uprisers → uprises → prises → priss → piss → pis
\n→ upraises → praises → prises → pries → pies → pes
\n→ upraises → praises → prises → pries → pies → pis
\n→ upraises → praises → prises → priss → piss → pis
\n→ upraises → praises → prases → pases → pass → ass
\n→ upraises → praises → prases → pases → pass → pas
\n→ upraises → uprises → prises → pries → pies → pes
\n→ upraises → uprises → prises → pries → pies → pis
\n→ upraises → uprises → prises → priss → piss → pis \n<\/td>\n<\/tr>\n
broachers<\/td>\n\n→ broaches → braches → braces → braes → bras → ras
\n→ broaches → braches → braces → braes → bras → bas \n<\/td>\n<\/tr>\n
saltiness<\/td>\n\n→ saltines → salines → alines → lines → lies → lis
\n→ saltines → salines → alines → lines → lins → ins
\n→ saltines → salines → alines → lines → lins → lis \n<\/td>\n<\/tr>\n
confiners<\/td>\n\n→ confines → conines → conies → cones → ones → oes
\n→ confines → conines → conies → cones → ones → ons
\n→ confines → conines → conies → cones → cons → ons
\n→ confines → conines → conies → cones → cons → cos
\n→ confines → conines → conins → coins → cons → ons
\n→ confines → conines → conins → coins → cons → cos
\n→ confines → conines → conins → conns → cons → ons
\n→ confines → conines → conins → conns → cons → cos
\n→ confines → conines → conins → conns → cons → ons
\n→ confines → conines → conins → conns → cons → cos \n<\/td>\n<\/tr>\n
smaltines<\/td>\n\n→ saltines → salines → alines → lines → lies → lis
\n→ saltines → salines → alines → lines → lins → ins
\n→ saltines → salines → alines → lines → lins → lis \n<\/td>\n<\/tr>\n
caressers<\/td>\n\n→ caresses → cresses → cesses → esses → eses → ess
\n→ caresses → cresses → cesses → esses → eses → ess \n<\/td>\n<\/tr>\n
sheathers<\/td>\n\n→ heathers → heaters → haters → hates → hats → has
\n→ sheathes → sheaths → heaths → heths → hehs → hes
\n→ sheathes → sheaths → heaths → heats → hats → has \n<\/td>\n<\/tr>\n
splashers<\/td>\n\n→ plashers → lashers → lasers → lases → lass → ass
\n→ plashers → lashers → lasers → lases → lass → las
\n→ plashers → lashers → lashes → ashes → shes → hes
\n→ plashers → lashers → lashes → lases → lass → ass
\n→ plashers → lashers → lashes → lases → lass → las
\n→ plashers → plashes → lashes → ashes → shes → hes
\n→ plashers → plashes → lashes → lases → lass → ass
\n→ plashers → plashes → lashes → lases → lass → las
\n→ plashers → plashes → pashes → ashes → shes → hes
\n→ plashers → plashes → pashes → pases → pass → ass
\n→ plashers → plashes → pashes → pases → pass → pas
\n→ slashers → lashers → lasers → lases → lass → ass
\n→ slashers → lashers → lasers → lases → lass → las
\n→ slashers → lashers → lashes → ashes → shes → hes
\n→ slashers → lashers → lashes → lases → lass → ass
\n→ slashers → lashers → lashes → lases → lass → las
\n→ slashers → slashes → lashes → ashes → shes → hes
\n→ slashers → slashes → lashes → lases → lass → ass
\n→ slashers → slashes → lashes → lases → lass → las
\n→ slashers → slashes → sashes → ashes → shes → hes
\n→ splashes → plashes → lashes → ashes → shes → hes
\n→ splashes → plashes → lashes → lases → lass → ass
\n→ splashes → plashes → lashes → lases → lass → las
\n→ splashes → plashes → pashes → ashes → shes → hes
\n→ splashes → plashes → pashes → pases → pass → ass
\n→ splashes → plashes → pashes → pases → pass → pas
\n→ splashes → slashes → lashes → ashes → shes → hes
\n→ splashes → slashes → lashes → lases → lass → ass
\n→ splashes → slashes → lashes → lases → lass → las
\n→ splashes → slashes → sashes → ashes → shes → hes \n<\/td>\n<\/tr>\n
scrappers<\/td>\n\n→ crappers → rappers → rapers → rapes → raps → ras
\n→ crappers → rappers → rapers → rapes → raps → ras
\n→ scrapers → scrapes → crapes → rapes → raps → ras
\n→ scrapers → scrapes → crapes → craps → raps → ras
\n→ scrapers → scrapes → scraps → craps → raps → ras
\n→ scrapers → scrapes → crapes → rapes → raps → ras
\n→ scrapers → scrapes → crapes → craps → raps → ras
\n→ scrapers → scrapes → scraps → craps → raps → ras \n<\/td>\n<\/tr>\n
chorusses<\/td>\n\n→ choruses → chouses → houses → hoses → oses → oes
\n→ choruses → chouses → houses → hoses → hoes → oes
\n→ choruses → chouses → houses → hoses → hoes → hes
\n→ choruses → chouses → choses → hoses → oses → oes
\n→ choruses → chouses → choses → hoses → hoes → oes
\n→ choruses → chouses → choses → hoses → hoes → hes
\n→ choruses → chouses → choses → coses → oses → oes
\n→ choruses → chouses → choses → coses → coss → cos
\n→ choruses → chouses → houses → hoses → oses → oes
\n→ choruses → chouses → houses → hoses → hoes → oes
\n→ choruses → chouses → houses → hoses → hoes → hes
\n→ choruses → chouses → choses → hoses → oses → oes
\n→ choruses → chouses → choses → hoses → hoes → oes
\n→ choruses → chouses → choses → hoses → hoes → hes
\n→ choruses → chouses → choses → coses → oses → oes
\n→ choruses → chouses → choses → coses → coss → cos \n<\/td>\n<\/tr>\n
breachers<\/td>\n\n→ breaches → braches → braces → braes → bras → ras
\n→ breaches → braches → braces → braes → bras → bas \n<\/td>\n<\/tr>\n
launchers<\/td>\n\n→ launches → launces → lances → laces → lacs → las \n<\/td>\n<\/tr>\n<\/table>\n

Pushing Further<\/h3>\n

I made an arbitrary starting point of three-letter words near the beginning. Almost as an afterthought, I decided to do the run again, but based on two-letter words.<\/p>\n

I expected to get poorer results, with shorter maximum words (or at the least, fewer of them). To my surprise, while I did get fewer three- to seven-letter words, by the time it got to eight-letter words, it had stabilized.<\/p>\n

I got exactly the same list of nine-letter words coming out!<\/em><\/p>\n

How Many Words Can Be Produced From Two-Letters?<\/h4>\n\n\n\n\n\n\n\n\n\n\n\n\n
Word Length<\/th>\nNumber of Words That Can Be “Laddered” from Two-Letter Words<\/th>\n<\/tr>\n
1 <\/td>\n N\/A <\/td>\n<\/tr>\n
2 <\/td>\n 47 (All of them)<\/td>\n<\/tr>\n
3 <\/td>\n 183 <\/td>\n<\/tr>\n
4 <\/td>\n 474 <\/td>\n<\/tr>\n
5 <\/td>\n 702 <\/td>\n<\/tr>\n
6 <\/td>\n 579 <\/td>\n<\/tr>\n
7 <\/td>\n 338 <\/td>\n<\/tr>\n
8 <\/td>\n 131 <\/td>\n<\/tr>\n
9 <\/td>\n 13 <\/td>\n<\/tr>\n
10 <\/td>\n 0 <\/td>\n<\/tr>\n<\/table>\n

All Nine-Letter To Two-Letter Chemical Ladders<\/h4>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
pricklier<\/td>\n\n→ prickier → pickier → picker → piker → pier → per → er
\n→ prickier → pricier → pricer → prier → pier → per → er
\n→ prickier → pricker → picker → piker → pier → per → er
\n→ prickier → pricker → pricer → prier → pier → per → er \n<\/td>\n<\/tr>\n
upraisers<\/td>\n\n→ praisers → praises → prises → pries → pies → pes → es
\n→ praisers → praises → prises → pries → pies → pis → is
\n→ praisers → praises → prises → priss → piss → pis → is
\n→ praisers → praises → prases → pases → pass → ass → as
\n→ praisers → praises → prases → pases → pass → pas → as
\n→ uprisers → uprises → prises → pries → pies → pes → es
\n→ uprisers → uprises → prises → pries → pies → pis → is
\n→ uprisers → uprises → prises → priss → piss → pis → is
\n→ upraises → praises → prises → pries → pies → pes → es
\n→ upraises → praises → prises → pries → pies → pis → is
\n→ upraises → praises → prises → priss → piss → pis → is
\n→ upraises → praises → prases → pases → pass → ass → as
\n→ upraises → praises → prases → pases → pass → pas → as
\n→ upraises → uprises → prises → pries → pies → pes → es
\n→ upraises → uprises → prises → pries → pies → pis → is
\n→ upraises → uprises → prises → priss → piss → pis → is \n<\/td>\n<\/tr>\n
broachers<\/td>\n\n→ broaches → braches → braces → braes → bras → ras → as
\n→ broaches → braches → braces → braes → bras → bas → as \n<\/td>\n<\/tr>\n
saltiness<\/td>\n\n→ saltines → salines → alines → lines → lies → lis → is
\n→ saltines → salines → alines → lines → lins → ins → is
\n→ saltines → salines → alines → lines → lins → lis → is \n<\/td>\n<\/tr>\n
confiners<\/td>\n\n→ confines → conines → conies → cones → ones → oes → es
\n→ confines → conines → conies → cones → ones → oes → os
\n→ confines → conines → conies → cones → ones → ons → os
\n→ confines → conines → conies → cones → cons → ons → os
\n→ confines → conines → conies → cones → cons → cos → os
\n→ confines → conines → conins → coins → cons → ons → os
\n→ confines → conines → conins → coins → cons → cos → os
\n→ confines → conines → conins → conns → cons → ons → os
\n→ confines → conines → conins → conns → cons → cos → os
\n→ confines → conines → conins → conns → cons → ons → os
\n→ confines → conines → conins → conns → cons → cos → os \n<\/td>\n<\/tr>\n
smaltines<\/td>\n\n→ saltines → salines → alines → lines → lies → lis → is
\n→ saltines → salines → alines → lines → lins → ins → is
\n→ saltines → salines → alines → lines → lins → lis → is \n<\/td>\n<\/tr>\n
caressers<\/td>\n\n→ caresses → cresses → cesses → esses → eses → ess → es
\n→ caresses → cresses → cesses → esses → eses → ess → es \n<\/td>\n<\/tr>\n
sheathers<\/td>\n\n→ heathers → heaters → haters → hates → hats → has → as
\n→ sheathes → sheaths → heaths → heths → hehs → hes → es
\n→ sheathes → sheaths → heaths → heats → hats → has → as \n<\/td>\n<\/tr>\n
splashers<\/td>\n\n→ plashers → lashers → lasers → lases → lass → ass → as
\n→ plashers → lashers → lasers → lases → lass → las → as
\n→ plashers → lashers → lashes → ashes → shes → hes → es
\n→ plashers → lashers → lashes → lases → lass → ass → as
\n→ plashers → lashers → lashes → lases → lass → las → as
\n→ plashers → plashes → lashes → ashes → shes → hes → es
\n→ plashers → plashes → lashes → lases → lass → ass → as
\n→ plashers → plashes → lashes → lases → lass → las → as
\n→ plashers → plashes → pashes → ashes → shes → hes → es
\n→ plashers → plashes → pashes → pases → pass → ass → as
\n→ plashers → plashes → pashes → pases → pass → pas → as
\n→ slashers → lashers → lasers → lases → lass → ass → as
\n→ slashers → lashers → lasers → lases → lass → las → as
\n→ slashers → lashers → lashes → ashes → shes → hes → es
\n→ slashers → lashers → lashes → lases → lass → ass → as
\n→ slashers → lashers → lashes → lases → lass → las → as
\n→ slashers → slashes → lashes → ashes → shes → hes → es
\n→ slashers → slashes → lashes → lases → lass → ass → as
\n→ slashers → slashes → lashes → lases → lass → las → as
\n→ slashers → slashes → sashes → ashes → shes → hes → es
\n→ splashes → plashes → lashes → ashes → shes → hes → es
\n→ splashes → plashes → lashes → lases → lass → ass → as
\n→ splashes → plashes → lashes → lases → lass → las → as
\n→ splashes → plashes → pashes → ashes → shes → hes → es
\n→ splashes → plashes → pashes → pases → pass → ass → as
\n→ splashes → plashes → pashes → pases → pass → pas → as
\n→ splashes → slashes → lashes → ashes → shes → hes → es
\n→ splashes → slashes → lashes → lases → lass → ass → as
\n→ splashes → slashes → lashes → lases → lass → las → as
\n→ splashes → slashes → sashes → ashes → shes → hes → es \n<\/td>\n<\/tr>\n
scrappers<\/td>\n\n→ crappers → rappers → rapers → rapes → raps → ras → as
\n→ crappers → rappers → rapers → rapes → raps → ras → as
\n→ scrapers → scrapes → crapes → rapes → raps → ras → as
\n→ scrapers → scrapes → crapes → craps → raps → ras → as
\n→ scrapers → scrapes → scraps → craps → raps → ras → as
\n→ scrapers → scrapes → crapes → rapes → raps → ras → as
\n→ scrapers → scrapes → crapes → craps → raps → ras → as
\n→ scrapers → scrapes → scraps → craps → raps → ras → as \n<\/td>\n<\/tr>\n
chorusses<\/td>\n\n→ choruses → chouses → houses → hoses → oses → oes → es
\n→ choruses → chouses → houses → hoses → oses → oes → os
\n→ choruses → chouses → houses → hoses → hoes → oes → es
\n→ choruses → chouses → houses → hoses → hoes → oes → os
\n→ choruses → chouses → houses → hoses → hoes → hes → es
\n→ choruses → chouses → choses → hoses → oses → oes → es
\n→ choruses → chouses → choses → hoses → oses → oes → os
\n→ choruses → chouses → choses → hoses → hoes → oes → es
\n→ choruses → chouses → choses → hoses → hoes → oes → os
\n→ choruses → chouses → choses → hoses → hoes → hes → es
\n→ choruses → chouses → choses → coses → oses → oes → es
\n→ choruses → chouses → choses → coses → oses → oes → os
\n→ choruses → chouses → choses → coses → coss → cos → os
\n→ choruses → chouses → houses → hoses → oses → oes → es
\n→ choruses → chouses → houses → hoses → oses → oes → os
\n→ choruses → chouses → houses → hoses → hoes → oes → es
\n→ choruses → chouses → houses → hoses → hoes → oes → os
\n→ choruses → chouses → houses → hoses → hoes → hes → es
\n→ choruses → chouses → choses → hoses → oses → oes → es
\n→ choruses → chouses → choses → hoses → oses → oes → os
\n→ choruses → chouses → choses → hoses → hoes → oes → es
\n→ choruses → chouses → choses → hoses → hoes → oes → os
\n→ choruses → chouses → choses → hoses → hoes → hes → es
\n→ choruses → chouses → choses → coses → oses → oes → es
\n→ choruses → chouses → choses → coses → oses → oes → os
\n→ choruses → chouses → choses → coses → coss → cos → os \n<\/td>\n<\/tr>\n
breachers<\/td>\n\n→ breaches → braches → braces → braes → bras → ras → as
\n→ breaches → braches → braces → braes → bras → bas → as \n<\/td>\n<\/tr>\n
launchers<\/td>\n\n→ launches → launces → lances → laces → lacs → las → as \n<\/td>\n<\/tr>\n<\/table>\n

Run-Time<\/h3>\n

The run-time to do all of this was trivial; so trivial, I never actually timed it accurately.<\/p>\n

It took about 3 seconds to read in the file, and generate both sets of dictionaries. Recursing through to print out the results took another 15 seconds or so.<\/p>\n

All of this is on an aging machine, running Python, with no attempts to optimise.<\/p>\n","protected":false},"excerpt":{"rendered":"

In which Julian stumbles over the concept of Chemical Word Ladders, and proceeds to generate them.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_s2mail":"","footnotes":""},"categories":[28,33,34],"tags":[],"class_list":["post-593","post","type-post","status-publish","format-standard","hentry","category-doubleplus-geek","category-puzzle-solving","category-software-development"],"_links":{"self":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/593","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/comments?post=593"}],"version-history":[{"count":5,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/593\/revisions"}],"predecessor-version":[{"id":597,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/posts\/593\/revisions\/597"}],"wp:attachment":[{"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/media?parent=593"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/categories?post=593"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.somethinkodd.com\/oddthinking\/wp-json\/wp\/v2\/tags?post=593"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}