Problem of the Day -- Word Ladder

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

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

Word Ladder

Comments:

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