41
$\begingroup$

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??

$\endgroup$
  • 65
    $\begingroup$ 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. $\endgroup$ – Anthony Ingram-Westover Oct 14 at 14:23
  • 6
    $\begingroup$ "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). $\endgroup$ – trolley813 Oct 14 at 15:16
  • 14
    $\begingroup$ What transition? :P $\endgroup$ – qwr Oct 15 at 2:05
  • 4
    $\begingroup$ Nice puzzle, definitely worthy of the humour tag😊 $\endgroup$ – happystar Oct 15 at 11:27
  • 3
    $\begingroup$ If letters can be added and removed, I can do it in 7 steps. $\endgroup$ – Beefster Oct 15 at 19:29
37
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ That looks better! $\endgroup$ – ThatOneNerdyBoy Oct 14 at 18:35
  • $\begingroup$ @Lukas Rotter I am going to wait a couple of days before I accept your answer. Still hope for a 8 step answer!!! $\endgroup$ – DrD Oct 15 at 11:43
  • 2
    $\begingroup$ @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). $\endgroup$ – IT Alex Oct 15 at 14:39
  • 2
    $\begingroup$ Interesting. Did a small prog (using a dict of ~16000 5-letters words), and the best it can find is exactly your answer :-) $\endgroup$ – e2-e4 Oct 17 at 14:37
  • 1
    $\begingroup$ @e2-e4: Same here. I even added french, german, spanish and italian word lists, but couldn't find anything better than 9 steps. $\endgroup$ – Eric Duminil Oct 18 at 9:14
18
$\begingroup$

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

| improve this answer | |
$\endgroup$
13
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ That's 10 steps still $\endgroup$ – Anthony Ingram-Westover Oct 14 at 15:01
  • 6
    $\begingroup$ @AnthonyIngram-Westover Steps is counted from one to another, so 10 words is only 9 steps. $\endgroup$ – ThatOneNerdyBoy Oct 14 at 15:02
  • $\begingroup$ But is TERES in Merriam Webster on its own? I'm not so sure... $\endgroup$ – Stiv Oct 14 at 15:03
  • $\begingroup$ Are bere and bede in Merriam-Webster? $\endgroup$ – hexomino Oct 14 at 15:04
  • 1
    $\begingroup$ merriam-webster.com/dictionary/beres not there $\endgroup$ – DrD Oct 14 at 15:05
11
$\begingroup$

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

TRUMP RUMP RUM RIM RID RIDE BIDE BIDEN

| improve this answer | |
$\endgroup$
  • 8
    $\begingroup$ But deletions and insertions aren't allowed. $\endgroup$ – bobble Oct 15 at 19:33
  • 10
    $\begingroup$ @bobble I will leave that up to OP and mods. Some word ladders allow it and OP never specified. $\endgroup$ – Beefster Oct 15 at 19:36
  • 9
    $\begingroup$ 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. $\endgroup$ – DrD Oct 15 at 20:18
  • 5
    $\begingroup$ Another 7 using this format TRUMP - RUMP - BUMP - BUM - BUD - BID - BIDE - BIDEN $\endgroup$ – corsiKa Oct 15 at 23:52
2
$\begingroup$

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:

  1. First obtained a word list
    aspell -d en dump master | aspell -l en expand > words.en.txt
    
  2. Keep only words that are 5 letters long
    awk 'length($0)== 5' wordlist1.txt > wordlist2.txt
    
  3. Kepp only words without apostrophes (')
    awk '!/'\''/' wordlist2.txt > wordlist3.txt
    
  4. Remove words with capital letters (proper nouns)
    awk '!/[A-Z]/' wordlist3.txt > wordlist4.txt
    
  5. Add 'biden' and 'teres' as words
    printf "%s\n" biden teres >> wordlist4.tx
    
  6. 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
```
| improve this answer | |
New contributor
user000001 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • 3
    $\begingroup$ This is the same as the 9-step accepted answer, but it is nice that you added your working. $\endgroup$ – Jaap Scherphuis Oct 18 at 7:57
  • $\begingroup$ 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. $\endgroup$ – user000001 Oct 18 at 8:04
  • $\begingroup$ @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. $\endgroup$ – user000001 Oct 18 at 9:03
  • $\begingroup$ 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. $\endgroup$ – Lukas Rotter Oct 18 at 9:14
  • 1
    $\begingroup$ 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: 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. $\endgroup$ – Eric Duminil Oct 18 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.