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

Comments:

• Kevin - 10 years, 9 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, 9 months ago

  Good question, it will take something to solve this.

  reply permalink

• Anonymous - 10 years, 9 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, 8 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, 9 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, 8 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, 8 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