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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

TRUMP RUMP RUM RIM RID RIDE BIDE BIDEN

Answer 5

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