Monday, 19 August 2013

Word Chain in Core Java

A program that solves the word-chain problem:


Word chain is chain of dictionary words where successive entries in a chain differ from the previous word by just one letter.
For example, you can get from "cat" to "dog" using the following chain.
cat -> cot -> cog -> dog
The challenge is to write a program that accepts start and end words of the chain and using the words from a dictionary build the shortest word chain between them.

The attached dictionary for the universe of the words is to be used.
The code has been written in Core Java.

package com.self.wordchain.normal;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordChain {

  private final static Character[] letters = { 'a', 'b', 'c', 'd', 'e', 'f',
   'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
   't', 'u', 'v', 'w', 'x', 'y', 'z' };

  public static final ArrayList<Character> alLetters = new ArrayList<Character>(
   Arrays.asList(WordChain.letters));

  public static void main(final String sArgs[]) {

   final WordChain wc = new WordChain();
  final String file = "wordsEn.txt";
  final String start = "cat";
  final String end = "dog";

   if (start.length() != end.length()) {
   System.out.println("length of both the words should be same");
  }

   wc.loadDictionary(file, start.length());
  wc.compute(start, end, 0);
 }

  private final ArrayList<String> wordChain = new ArrayList<String>();
 private final Set<String> dictionary = new HashSet<String>();

  /**
  *
  * Start processing for the given starting & ending words
  *
  *
  *
  * @param word
  *
  * @param end
  *
  * @param level
  */

  private void compute(final String word, final String end, int level) {

   System.out.println("[Level-" + (++level) + "]");
  List<String> alnew = this.getNext(word, end);
  while (true) {
   if (this.wordChain.size() > 0) {
    break;
   }

    System.out.println("[Level-" + (++level) + "]");
   final List<String> al = new ArrayList<String>(alnew);
   alnew = new ArrayList<String>();

    for (final String newword : al) {
    // System.out.println("[" + (level) + "]" + newword);
    alnew.addAll(this.getNext(newword, end));
   }

   // Break the chain if reached 26th level
   if (level == 26) {
    break;
   }
  }

   System.out.println("Shortest Word Chain are:");

   for (final String wc : this.wordChain) {
   System.out.println(wc);
  }

  }

  /**
  *
  * Get the last word from the string of word chain
  *
  *
  *
  * @param wholeword
  *
  * @return
  */

  private String getlastword(final String wholeword) {
  final String[] tokens = wholeword.split("_");
  return tokens[tokens.length - 1];

  }

  /**
  *
  * Get the next eligible list of words from the memory for the given word
  *
  *
  *
  * @param wholeword
  *
  * @param end
  *
  * @return
  */

  private List<String> getNext(final String wholeword, final String end) {

   final String word = this.getlastword(wholeword);
  final ArrayList<String> al = new ArrayList<String>();

   for (int i = 0; i < word.length(); i++) {
   for (int j = 0; j < WordChain.alLetters.size(); j++) {
    final char[] newString = word.toCharArray();
    newString[i] = WordChain.alLetters.get(j);
    final String newword = String.valueOf(newString);
    if (newword.equals(end)) {
     this.wordChain.add(wholeword + "_" + newword);
    } else if (!newword.equals(word)
      && !wholeword.startsWith(newword + "_")
      && !wholeword.contains("_" + newword + "_")
      && this.dictionary.contains(newword)) {
     al.add(wholeword + "_" + newword);
    }
   }
  }
  return al;

  }

  /**
  *
  * Load Dictionary words in the memory,the words should be of given length
  *
  *
  *
  * @param file
  *
  * @param i
  */

  private void loadDictionary(final String file, final int length) {

   BufferedReader br = null;
  try {
   br = new BufferedReader(new FileReader(new File(file)));
   String currentline;
   while ((currentline = br.readLine()) != null) {
    if (currentline.length() == length) {
     this.dictionary.add(currentline.toLowerCase());
    }
   }
  } catch (final FileNotFoundException e) {
   e.printStackTrace();
  } catch (final IOException e) {
   e.printStackTrace();
  } finally {
   if (br != null) {
    try {
     br.close();
    } catch (final IOException e) {
     e.printStackTrace();
    }
   }
  }
 }
}




Also refer to:
http://alchemistviews.blogspot.com/2013/08/word-chain-in-map-reduce.html

No comments:

Post a Comment