Problem of the Day
A new programming or logic puzzle every Mon-Fri

Word Ladder

Comment previewing has arrived!!! Now on to our regularly scheduled problem.

Today we'll be designing a function that takes in two words and determines if it's possible to transform one word in to the other by changing one letter at a time (letters can not be added or removed, only changed). When a letter is changed the new word must also be a valid word. Each letter index can only be changed one time. Here is an example using "power" and "tuned":

power -> tower -> towed -> toned -> tuned

Most Linux distros come with a built in dictionary or you can find one by searching the internet. Here is one I found for English.

Permalink: http://problemotd.com/problem/word-ladder/

Comments:

  • Kevin - 10 years, 7 months ago

    Lots of room for optimization, but it seems to work.

    import itertools
    
    WORDS = open('wordsEn.txt', 'r').read().split("\r\n")
    
    def wordpaths(start, end):
        if len(start) != len(end):
            raise Exception('words must be the same length')
    
        indexes = [i for i in range(0, len(start))
                   if start[i]!=end[i]] # no duplicate positions
        perms = itertools.permutations(indexes)
        valid_paths = []
        for iset in perms:
            path = [start]
            for i in iset:
                chars = list(path[-1])
                chars[i] = end[i]
                new = ''.join(chars)
                if new in WORDS:
                    path.append(new)
                else:
                    # dead end
                    break
            if path[-1] == end:
                valid_paths.append(path)
        return valid_paths
    
    
    paths = wordpaths('power', 'tuned')
    for path in paths:
        print ' -> '.join(path)
    

    reply permalink

  • Virat - 10 years, 7 months ago

    Good question, it will take something to solve this.

    reply permalink

  • Anonymous - 10 years, 7 months ago

    Recursive python solution, unhappy about the O(n) search of words_found and I had to change the max recursion depth

    from string import ascii_lowercase
    from bisect import bisect_left
    from sys import setrecursionlimit
    
    setrecursionlimit(5000)
    
    def is_word(word, word_list):
        # Binary search as word_list is sorted
        pos = bisect_left(word_list, word)
        return pos != len(word_list) and word_list[pos] == word
    
    def word_ladder_exists(from_word, to_word, word_list):
        def _chain_exists(from_word, to_word, word_list, words_found):
            if from_word == to_word:
                return True
            if len(from_word) != len(to_word):
                return False
            for i in range(len(from_word)):
                for letter in ascii_lowercase:
                    new_word = from_word[:i] + letter + from_word[i+1:]
                    if is_word(new_word, word_list) and new_word not in words_found:
                        words_found.append(new_word) # Prevent loops
                        if _chain_exists(new_word, to_word, word_list, words_found):
                            return True
            return False
    
        word_list = list(filter(lambda x: len(x) == len(from_word), word_list)) # Has to be list for bisect_left
        return _chain_exists(from_word, to_word, word_list, [])
    
    word_list = open('wordsEn.txt', 'r').read().split("\n")
    
    print(word_ladder_exists('power', 'tuned', word_list))
    

    reply permalink

  • Anonymous - 10 years, 7 months ago

    Much happier with it now I've improved it

    # http://www.problemotd.com/problem/word-ladder/
    
    from string import ascii_lowercase
    from sys import setrecursionlimit
    
    setrecursionlimit(5000)
    
    def word_ladder_exists(from_word, to_word, word_list):
        def _words(word, word_to_searched): # Generator for valid words by changing a single letter in word
            for i in range(len(word)):
                for letter in ascii_lowercase:
                    potential_word = word[:i] + letter + word[i+1:]
                    if potential_word in word_to_searched and not word_to_searched[potential_word]:
                        yield potential_word # It's a valid word and it hasn't been searched
    
        def _chain_exists(from_word, to_word, word_to_searched):
            if sum(1 for a, b in zip(from_word, to_word) if a != b) <= 1: # Same or differ by 1 letter
                return True
            word_to_searched[from_word] = True # Mark word as searched to prevent loops
            return any(_chain_exists(word, to_word, word_to_searched) for word in _words(from_word, word_to_searched))
    
        word_list = filter(lambda x: len(x) == len(from_word), word_list) # Only need to consider ones of equal length
        word_to_searched = {word: False for word in word_list} # Dictionary of word (string) to if it's been searched (boolean)
    
        if len(from_word) != len(to_word) or from_word not in word_to_searched or to_word not in word_to_searched:
            return False
        return _chain_exists(from_word, to_word, word_to_searched)
    
    word_list = open('wordsEn.txt', 'r').read().split("\n")
    
    print(word_ladder_exists('power', 'tuned', word_list))
    

    reply permalink

  • gulliver - 10 years, 7 months ago

    def word_ladder(w1,w2,wordfile):
        wordlist = []
        with open(wordfile) as FH:
            for line in FH:
                wordlist.append(line.rstrip()) 
        swap_dict = {}
        if len(w1) != len(w2) or w1 not in wordlist or w2 not in wordlist:
            return False
        for i in range(len(w1)): # generate a dictionary with key = index, value = letter to change
            if w1[i] != w2[i]:
                swap_dict[i] = w2[i]
        swap_letter(w1,w2,wordlist,swap_dict,[],swap_dict,w1)
    
    def swap_letter(w1,w2,wordlist,swap_dict,history,original_swap_dict,original_w1):
        if w1 == w2: # success, print out the history of words
            temp_word = original_w1
            for i in history:
                temp_list = list(temp_word)
                temp_list[i] = original_swap_dict[i]
                temp_word = ''.join(temp_list)
                print temp_word,
            print
            return
        for key in swap_dict:
            temp_list = list(w1)
            temp_list[key] = swap_dict[key] 
            new_word = ''.join(temp_list)
            if new_word in wordlist:
                temp_dict = dict(swap_dict)
                del temp_dict[key] # each letter can only be changed once
                history.append(key)
                swap_letter(new_word,w2,wordlist,temp_dict,history,original_swap_dict,original_w1)
                history.pop()
    

    reply permalink

  • Anonymous - 10 years, 7 months ago

    This is Clojure.

    (def words (set (clojure.string/split-lines (slurp "/usr/share/dict/words"))))
    
    (defn next-steps
      [word goal]
      (remove (partial = word)
        (for [i (range (count word))]
          (apply str (assoc (vec (seq word)) i (nth goal i))))))
    
    (defn ladder-path
      [word goal path]
      (let [steps (next-steps word goal)]
        (if (= (count steps) 1)
          (conj path goal)
          (loop [[s & r :as sts] steps]
            (if (empty? sts)
              []
              (if (contains? words s)
                (ladder-path s goal (conj path s))
                (recur r)))))))
    
    (defn ladder
      [word goal]
      (if (= word goal)
        [word]
        (ladder-path word goal [word])))
    
    (println (ladder "power" "tuned"))  ; => [power tower toner tuner tuned]
    

    reply permalink

  • samebchase - 10 years, 6 months ago

    Common Lisp solution that adds all the words into a graph, adds edges for 1-neighbours. Word ladder is simply a shortest path between the two words.

    (in-package :word-ladder)
    
    (define-constant +alphabet+
        "abcdefghijklmnopqrstuvwxyz"
      :test #'equalp)
    
    (define-constant +dictionary+
        (with-open-file (stream #P "wordsEn.txt") 
          (let ((dictionary (make-instance 'hash-set)))
            (loop for line = (read-line stream nil)
               until (eq line nil)
               do (hs-insert dictionary (string-right-trim '(#\Return) line)))
            dictionary))
      :test #'hs-equal)
    
    (defparameter *dictionary-graph* (populate (make-instance 'graph)))
    
    (defun valid-dictionary-wordp (word)
      (first (hs-memberp +dictionary+ word)))
    
    (defun word-neighbours (word)
      (let ((strings (strings-one-char-change word)))
        (dohashset (string strings)
          (unless (valid-dictionary-wordp string)
            (hs-delete strings string)))
        strings))
    
    (defun strings-one-char-change (word)
      (let ((strings (make-instance 'hash-set))
            (downcased-word (string-downcase word)))
        (loop
           for char across downcased-word
           for char-idx below (length downcased-word)
           do (loop for alphabet-char across +alphabet+
                 when (char-not-equal alphabet-char char)
                 do (let ((insertee-string (copy-seq downcased-word)))
                      (setf (aref insertee-string char-idx) alphabet-char)
                      (hs-insert strings insertee-string))))
        strings))
    
    (defun neighbours-from-set (hash-set)
      (let ((result (make-instance 'hash-set)))
        (dohashset (elt hash-set)
          (dohashset (i (word-neighbours elt))
            (hs-insert result i)))
        result))
    
    (defun load-nodes-into-graph ()
      (dohashset (word +dictionary+)
        (add-node *dictionary-graph* (symbolicate word))))
    
    (defun load-edges-into-graph ()
      (dohashset (word +dictionary+)
        (dohashset (neighbour (word-neighbours word))
          (add-edge *dictionary-graph* (list (symbolicate word) (symbolicate neighbour)) 1))))
    
    (defun load-dictionary ()
      (format t "Loading nodes...~%")
      (load-nodes-into-graph)
      (format t "Finished loading nodes.~%")
      (format t "Loading edges...~%")
      (load-edges-into-graph)
      (format t "Finished loading edges.~%"))
    
    (defun word-ladder (word-a word-b)
      (shortest-path *dictionary-graph* (symbolicate word-a) (symbolicate word-b)))
    
    (defun generate-word-ladder-graph (word-a word-b)
      (let* ((edges (word-ladder word-a word-b))
             (edges-w-values (loop for edge in edges
                                collect (cons edge 2)))
             (nodes (remove-duplicates (flatten edges))))
        (populate (make-instance 'graph)
                  :nodes nodes
                  :edges-w-values edges-w-values)))
    
    (defun generate-html-visualisation (word-a word-b pathspec)
      (with-output-to-file (stream pathspec
                                   :if-exists :supersede
                                   :if-does-not-exist :create)
                   (to-html (generate-word-ladder-graph word-a word-b) :stream stream)))
    
    (when (= 0 (length (graph:nodes *dictionary-graph*)))
        (load-dictionary))
    
    

    Output Image of the word ladder

    reply permalink

Content curated by @MaxBurstein