TRUMP to BIDEN : This transition won't be easy

Question

Can you change the word TRUMP to the name BIDEN in 10 steps or less by changing one letter at a time?

Each change must result in a valid word from MW dictionary.

No proper nouns, abbreviations or acronyms. No rearrangement or anagrams either.

Have fun.

I did it in 10 but there must be a faster solution??

I can change it in one step... VOTE :) My initial run was 12 steps, but I'm sure I can tweak it down a bit lower. — Anthony Ingram-Westover, Oct 14 '20 at 14:23
"No proper nouns". Well, Biden is a proper noun (Trump is not; e.g. we can have trumps when playing card games like whist and bridge). — trolley813, Oct 14 '20 at 15:16
If letters can be added and removed, I can do it in 7 steps. — Beefster, Oct 15 '20 at 19:29
@AnthonyIngram-Westover you can not, but we can! Together, we will! — emory, Oct 17 '20 at 13:51
@trolley813 - in the North of England, a 'trump' is a fart. In standard English, it is a blast on a trumpet (there is predicted to be a 'last trump', at the end of the world, in the Bible). — Michael Harvey, Oct 17 '20 at 21:01
"TRUMP->TRAMP->GRAMP->GRAME->GRACE->GLACE->PLACE->PEACE->PENCE" would also be an alternative, after "COVID->COMID->COMPD->COMPS->COOPS->CROPS->CRAPS->CRAMS->CRAMP->CRUMP->TRUMP->GRUMP->GRAMP->GRAME->GRAVE". — Eric Duminil, Oct 17 '20 at 21:50
Do you know how to obtain a wordlist from the MW dictionary? I wasn't able to find one had to use aspell, but MW is probably more complete, so there may be smaller paths in that DB. — user000001, Oct 18 '20 at 07:54
@user000001: I used https://github.com/dwyl/english-words and couldn't find anything better than the accepted solution. — Eric Duminil, Oct 18 '20 at 09:13
I found a solution with 7 steps, using terms defined in https://www.urbandictionary.com/. There are some proper nouns (first names), though. — Eric Duminil, Oct 18 '20 at 09:46

score 41 · Accepted Answer · answered Oct 14 '20 at 16:57

41

Based on ThatOneNerdyBoy's answer, here's a 9-step solution in which all words are contained within MW

TRUMP
TRAMP
TRAMS
TEAMS
TERMS
TERES
TIRES
TIDES
BIDES
BIDEN

answered Oct 14 '20 at 16:57

Lukas Rotter

10,321
1
49
89

That looks better! – ThatOneNerdyBoy Oct 14 '20 at 18:35
@Lukas Rotter I am going to wait a couple of days before I accept your answer. Still hope for a 8 step answer!!! – DrD Oct 15 '20 at 11:43
2

@DrD 5 letters to full change, it takes too long to move into common words 8-step might actually be impossible especially because you have to move to the wrong vowel before getting to the right one (7 steps now) and 2 steps to reach vowel movement (9). – IT Alex Oct 15 '20 at 14:39
Point well taken @IT Alex. – DrD Oct 15 '20 at 14:48
4

Interesting. Did a small prog (using a dict of ~16000 5-letters words), and the best it can find is exactly your answer :-) – Déjà vu Oct 17 '20 at 14:37
It's interesting how the ladder itself seems to contain some subtle political commentary – Chris Sunami Oct 17 '20 at 16:32
1

@e2-e4: Same here. I even added french, german, spanish and italian word lists, but couldn't find anything better than 9 steps. – Eric Duminil Oct 18 '20 at 09:14
@EricDuminil try to add the word BIDEN ... ;-) – Déjà vu Oct 18 '20 at 09:20
@e2-e4: I had to, because it isn't present in any word list I had. – Eric Duminil Oct 18 '20 at 09:44
@e2-e4 oh, so you allowed letters to be removed and added? – Eric Duminil Oct 18 '20 at 10:13
@e2-e4 sorry, I still don't get it. What would the complete chain look like? It doesn't seem to make sense to repeat any word. – Eric Duminil Oct 18 '20 at 11:02
@EricDuminil (removed previous comments to avoid the 'chat' punishment) there would be incorrect words in between in 5 steps if BIDEN is auth., and we can only change 1 letter at once, so indeed adding it wouldn't hurt (then dep on algo, the tree search (in mine) is a bit faster by stopping at 4 common chars) – Déjà vu Oct 18 '20 at 11:13
@e2-e4: Once again, I don't get it. Getting into chat wouldn't bother me. 'BIDEN' must be in the graph, doesn't it? Do you have an example of the incorrect words? What would the chain look like, exactly? – Eric Duminil Oct 18 '20 at 12:20

score 18 · Answer 2 · answered Oct 14 '20 at 14:52

18

Here it is in 10 steps, at least

TRUMP
TRAMP
TRAMS
TEAMS
BEAMS
BEATS
BENTS (noun - stalks of stiff coarse grass)
BINTS
BINES
BIDES
BIDEN

answered Oct 14 '20 at 14:52

hexomino

135,910
10
384
563

ThatOneNerdyBoy · Answer 3 · 2020-10-14T15:01:51.910

14

Here is a possible 9 step:

TRUMP
TRAMP
TRAMS
TEAMS
TERMS
TERES - a shoulder blade muscle
BERES - bere: a type of cereal grass
BEDES - bede: a devout deity petition
BIDES
BIDEN

edited Oct 14 '20 at 15:01

answered Oct 14 '20 at 15:00

ThatOneNerdyBoy

1,151
1
7
19

That's 10 steps still – Anthony Ingram-Westover Oct 14 '20 at 15:01
7

@AnthonyIngram-Westover Steps is counted from one to another, so 10 words is only 9 steps. – ThatOneNerdyBoy Oct 14 '20 at 15:02
But is TERES in Merriam Webster on its own? I'm not so sure... – Stiv Oct 14 '20 at 15:03
Are bere and bede in Merriam-Webster? – hexomino Oct 14 '20 at 15:04
1

https://www.merriam-webster.com/dictionary/beres not there – DrD Oct 14 '20 at 15:05
@DrD Oh sorry, I went off Scrabble words... – ThatOneNerdyBoy Oct 14 '20 at 15:05

score 11 · Answer 4 · answered Oct 15 '20 at 19:32

11

If deletions and insertions are allowed, it is possible in 7 steps:

TRUMP RUMP RUM RIM RID RIDE BIDE BIDEN

answered Oct 15 '20 at 19:32

Beefster

303
1
3

11

But deletions and insertions aren't allowed. – bobble Oct 15 '20 at 19:33
12

@bobble I will leave that up to OP and mods. Some word ladders allow it and OP never specified. – Beefster Oct 15 '20 at 19:36
11

Hello @Beefster. Thanks for your answer. Honestly when I made up the puzzle I did not even think of removing/adding letters. To me "change one letter at a time" meant replacing it with another. If that did not come across here I apologize. This is something new I learned today. For my next word ladder puzzle I will keep it in mind. Thanks again. – DrD Oct 15 '20 at 20:18
5

Another 7 using this format TRUMP - RUMP - BUMP - BUM - BUD - BID - BIDE - BIDEN – corsiKa Oct 15 '20 at 23:52

score 4 · Answer 5 · answered Oct 18 '20 at 07:49

I found a solution in only 8 intermediate steps:

0. trump
1. tramp
2. trams
3. teams
4. terms
5. teres
6. tires
7. tides
8. bides
Done: biden

It is possible that shorter paths still exists, because I couldn't obtain the complete MW dataset.

Methodology:

First obtained a word list

aspell -d en dump master | aspell -l en expand > words.en.txt

Keep only words that are 5 letters long

awk 'length($0)== 5' wordlist1.txt > wordlist2.txt

Kepp only words without apostrophes (')

awk '!/'\''/' wordlist2.txt > wordlist3.txt

Remove words with capital letters (proper nouns)
```
awk '!/[A-Z]/' wordlist3.txt > wordlist4.txt
```

Add 'biden' and 'teres' as words

printf "%s\n" biden teres >> wordlist4.tx

Sort the file
```
sort wordlist4.txt > words.sorted
```

After that a simple Breadth first search in ruby was enough to obtain the result, and finally the answer was confirmed to contain only words that exist in MW.


#!/usr/bin/env ruby
# frozen_string_literal: true
words = File.readlines('words.sorted', chomp: true)
def distance_is_1?(letters, otherword)
  diff = 0
  val_letters = otherword.split('')
0.upto(4) do |i|
    diff += 1 if letters[i] != val_letters[i]
    return false if diff > 1
  end
  diff == 1
end
def distance(letters, otherword)
  diff = 0
  val_letters = otherword.split('')
0.upto(4) do |i|
    diff += 1 if letters[i] != val_letters[i]
  end
  diff
end
def neighbors(word_list, word)
  letters = word.split ''
word_list.select do |w|
    dist = distance_is_1?(letters, w)
    dist
  end.map(&:downcase).uniq
end
solutions = { ['trump'] => distance(%w[b i d e n], 'trump') }
iter = 0
counted_nodes = {}
loop do
  res = {}
  new_counted = {}
  solutions.each do |s, _v|
    neighbors(words, s.last).uniq.each do |n|
      if s.include?(n) || counted_nodes.include?(n) || distance(%w[b i d e n], n) > 12 - iter
        next
      end
  new_counted[n] = s + [n]
  res[s + [n]] = 1
end

end
  solutions = res
  counted_nodes = counted_nodes.merge new_counted
  iter += 1
  break if iter > 12
p 'solutions', solutions, solutions.count
  if solutions.any? { |k, _v| k.last == 'biden' }
    p('FINAL ANSWER', solutions.select { |k, _v| k.last == 'biden' })
    exit
  end
end
```

This is the same as the 9-step accepted answer, but it is nice that you added your working. — Jaap Scherphuis, Oct 18 '20 at 07:57
Thanks, it's almost the same because I didn't have the word beres in my list, I'm running it again with that word to see It there is anything shorter than that. — user000001, Oct 18 '20 at 08:04
@JaapScherphuis: Actually now that I see it again, it isn't the same because that answer contains lists not in the dictionary specified by OP. — user000001, Oct 18 '20 at 09:03
I think you're confusing this answer with this answer. The second one is the exact same as yours. And this is 9 steps, not 8. — Lukas Rotter, Oct 18 '20 at 09:14
I didn't try your code and don't know how long it takes, but it looks like at least O(n²). If you're interested, you could try an algorithm like this one in order to find the neighbours: https://pastebin.com/8q7fm6A7
You iterate once over every word, and you save them into a hash of arrays, each time replacing one letter by '-'.

You can then iterate over the values of the hash, and select the ones with more than one element: every word inside this array has a distance of exactly 1 with all the other ones. — Eric Duminil, Oct 18 '20 at 10:35
For example: {"-RUMP"=>["CRUMP", "ERUMP", "FRUMP", "GRUMP", "TRUMP"], "T-UMP"=>["THUMP", "TRUMP"], "TR-MP"=>["TRAMP", "TROMP", "TRUMP"], "TRU-P"=>["TRUMP"], "TRUM-"=>["TRUMP"]} — Eric Duminil, Oct 18 '20 at 10:35

TRUMP to BIDEN : This transition won't be easy

5 Answers5

Methodology: