Saturday, February 7, 2015

Arrange words

"Given a file with 3-letter words, print all 3x3 with each row, column and diagonal
being one of the words from given file"

I stole the idea from Stackflow,  but implemented it using Java. Basically, create two new dictionaries, the first one store all first prefix of all words in the dictionary (singleL), and the second one store all first and second prefixes of all words(doubleL). Since all words in the matrix are words in the dictionary, there must be words that share same prefixes, thus maps are used for these two new dictionaries.


  1. Choose a word X from the dictionary, if any character (X1, X2, X3) is not in the singleL, select another word. 
  2. Choose the second word Y from the dictionary, if any string([X1, Y1], [X2, Y2], [X3, Y3], [X1, Y2], [X3, Y2] (diagonal)) is not in the doubleL, select another word. If all words have been visited, go back to 1. 
  3. Choose the third word Z from the dictionary, if any word([X1, Y1, Z1], [X2, Y2, Z2], [X3, Y3, Z3], [X1, Y2, Z3], [X3, Y2, Z1]) is not in the dictionary, select another word. If all words have been visited, go back to 2.
The following code assumes there is only one such arrangement exists.


import java.util.*;
public class ArrangingWords {
 public static List arrangeWords(Set dicts) {
  if (dicts == null || dicts.size() == 0)
   throw new IllegalArgumentException("Invalid input!");
  Map singleL = new HashMap ();
  Map doubleL = new HashMap ();
  for (String s : dicts) {
   if (!singleL.containsKey(s.substring(0, 1)))
    singleL.put(s.substring(0, 1), 1);
   else
    singleL.put(s.substring(0, 1), singleL.get(s.substring(0, 1)) + 1);
   if (!doubleL.containsKey(s.substring(0, 2))) 
    doubleL.put(s.substring(0, 2), 1);
   else
    doubleL.put(s.substring(0, 2), doubleL.get(s.substring(0, 2)) + 1);
  }
  Map words = new HashMap ();
  List rst = new ArrayList ();
  boolean found = false;
  for (String s1 : dicts) {
   for (int i = 0; i < 3; i++) {
    String tmp = s1.substring(i, i + 1);
    if (!isValid(tmp, words, singleL))
     continue;
   }
   rst.add(s1);
   for (String s2 : dicts) {
    if (s2.equals(s1))
     continue;
    for (int i = 0; i < 3; i++) {
     String tmp = s1.substring(i, i + 1) + s2.substring(i, i + 1);
     if (!isValid(tmp, words, doubleL))
      continue;
    }
    String d1 = s1.substring(0, 1) + s2.substring(1, 2);
    if (!isValid(d1, words, doubleL))
     continue;
    String d2 = s1.substring(2, 3) + s2.substring(1, 2);
    if (!isValid(d2, words, doubleL))
     continue;
    rst.add(s2);
    for (String s3 : dicts) {
     if (s3.equals(s1) || s3.equals(s2))
      continue;
     for (int i = 0; i < 3; i++) {
      String tmp = s1.substring(i, i + 1) + s2.substring(i, i + 1) + s3.substring(i, i + 1);
      if (!dicts.contains(tmp))
       continue;
     }
     String dia1 = s1.substring(0, 1) + s2.substring(1, 2) + s3.substring(2, 3);
     String dia2 = s1.substring(2, 3) + s2.substring(1, 2) + s3.substring(0, 1);
     if (!dicts.contains(dia1) || !dicts.contains(dia2))
      continue;
     found = true;
     rst.add(s3);
     break;
    }
    if (found)
     break;
    rst.remove(s2);
   }
   if (found)
    break;
   rst.remove(s1);
  }
  if (rst.size() < 3)
   return new ArrayList ();
  return rst;
 }
 private static boolean isValid(String word, Map words, Map prefixes) {
  if (!prefixes.containsKey(word))
   return false;
  if (!words.containsKey(word))
   words.put(word, 1);
  else
   words.put(word, words.get(word) + 1);
  if (words.get(word) > prefixes.get(word))
   return false;
  return true;
 }
 

 public static void main(String[] args) {
  Set dicts = new HashSet ();
  dicts.add("abc");
  dicts.add("def");
  dicts.add("ghi");
  dicts.add("adg");
  dicts.add("beh");
  dicts.add("cfi");
  dicts.add("aei");
  dicts.add("ceg");
  dicts.add("acg");
  dicts.add("dgh");
  dicts.add("iok");
  dicts.add("pkm");
  for (String s : arrangeWords(dicts)) {
   System.out.println(s);
  }

 }

}

No comments:

Post a Comment