Transforming one word into another word

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

scratch123
Posts: 236
Joined: Mon Mar 07, 2011 9:18 pm UTC

Transforming one word into another word

Postby scratch123 » Sun May 01, 2011 10:48 pm UTC

Ok I came up with this puzzle where you take one word and transform it into another one (both words have to be real english words) using one of the following transformations:

1. Rearrange the letters in the word (ex tan - ant)
2. Replace one letter in the word with another one (ex ban - can)
3. Insert one letter between 2 other letters (ex bat - boat)

See how many words you can come up with like this.

morsch
Posts: 2
Joined: Mon May 02, 2011 2:08 am UTC

Re: Transforming one word into another word

Postby morsch » Mon May 02, 2011 2:23 am UTC

Okay. :)

one letter substitutions: ban can fan man pan ran van wan ten tin ton tun tab tad tag tam tap tar tat tau tax
one letter insertions: than
permutations: ant

Or, for "treat":
one letter substitutions: great tread
one letter insertions: threat
permutations: tetra tater tetra tater

Code: Select all

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.SortedSet;
import java.util.TreeSet;


public class Wordlist {
   private SortedSet<String> words = new TreeSet<String>();

   public static void main(String[] args) throws IOException {
      Wordlist wordlist = new Wordlist();
      
      wordlist.readFile("2of12.txt");
      wordlist.doWord("tan");
   }

   public void readFile(String filename) throws IOException {
      BufferedReader br = new BufferedReader(new FileReader(filename));
      while (br.ready())
         words.add(br.readLine().toLowerCase());
   }
   
   private void permuteC(String prefix, String permute, String needle) {
      for (int i= 0; i < permute.length(); ++i) {
         char ch = permute.charAt(i);
         String c = prefix + ch;
         if (prefix.length() +1 < needle.length())
            permuteC(c, permute.substring(0, i) + permute.substring(i+1), needle);
         else if (words.contains(c) && !c.equals(needle))
            System.out.println(c);
      }
   }
   
   public void doWord(String string) {
      string = string.trim().toLowerCase();
      System.out.println("word transform for " + string);
      
      System.out.println("\none letter substitutions:");
      for (int i=0; i<string.length(); i++) {
         for (char ch='a'; ch <= 'z'; ch = (char) (((int)ch)+1)) {
            String c = string.substring(0, i) + ch + string.substring(i+1);
            if (words.contains(c) && !c.equals(string))
               System.out.println(c);
         }
      }
      
      System.out.println("\none letter insertions:");
      for (int i=1; i<string.length()-1; i++) {
         for (char ch='a'; ch <= 'z'; ch = (char) (((int)ch)+1)) {
            String c = string.substring(0, i) + ch + string.substring(i);
            if (words.contains(c) && !c.equals(string))
               System.out.println(c);
         }
      }
      
      System.out.println("\npermutations:");
      permuteC("", string, string);
   }
}

Code is released into the public domain. You'll need a wordlist, I used one of these: http://wordlist.sourceforge.net/

Xias
Posts: 363
Joined: Mon Jul 23, 2007 3:08 am UTC
Location: California
Contact:

Re: Transforming one word into another word

Postby Xias » Wed May 04, 2011 9:15 pm UTC

I wonder what the longest chain you can make without using any of the transformations twice in a row is.

Osha
Posts: 727
Joined: Wed Dec 03, 2008 3:24 am UTC
Location: Boise, Idaho, USA

Re: Transforming one word into another word

Postby Osha » Sat May 14, 2011 4:04 am UTC

spoilers 'cause why the heck not? 8O
Spoiler:
On chaining this puzzle:

Once I wrote a simple little program that only used rule 2 (letter replacement) to generate a graph of how all the words from a dictionary were connected. Then I could feed it a start word and a goal word and get the shortest path out. :D

Finding all the immediate neighbors for a specific word using just rule 2 can be accomplished in linear time with respect to the word length (25 constant time dictionary lookups for each position).
Rule 3 would be similar.
Rule 1, at first glance, requires factorial time. Which is actually pretty managable considering the number of letters in most words, but a smarter way to do it for longer words might be to just check all the words in the dictionary with the same length.

One interesting thing to note is that with the rules as given you can increase the length of your word but never decrease it, so it's best to start as short as possible and only grow when you have to.
Another challenge with doing this programmatically is finding a good dictionary, a too small one will fail to generate many connections, a too large one will include too many words that don't really look like they should "count".

I'll have to try and dig up my code, and if I find it, add rules one and three to it.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 6 guests