Thursday Code Puzzler: Anagram Solver
By now you should be familiar with our Thursday Code Puzzler slot. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you think is suitable.
Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer. It's all about the participation!
Anagram Solver
For this week's challenge, let's take a look at an anagram solver. For a given string, simply find the words that could solve the anagram. And let's take the approach of whole word anagrams only. If you can hook into some online service to prove the word actually exists, even better. Again, all the focus here is on efficiency.
Thanks to everyone who is participating in these puzzlers - last week's seemed to be quite active, with a good discussion around proposed solutions.
Comments
Vijay Nathani replied on Thu, 2012/06/21 - 9:27am
Here is solution in Groovy that prints "have a good day"
String inputLineWithWordsAnagramed = 'vahe a gdoo yad' def LIST_OF_VALID_WORDS = [ 'good', 'have' , 'day', 'a' ] as Set println inputLineWithWordsAnagramed.tokenize().collect { it.getChars().toList().permutations().find { LIST_OF_VALID_WORDS.contains(it.join('')) } ?.join('') }.join(' ')Earnest Dyke replied on Thu, 2012/06/21 - 9:22am
This builds the word list. I leave it to others to validate the words.
Earnie!
package com.ferguson.codepuzzler; import java.util.ArrayList; import java.util.List; import org.junit.Test; public class Anagram { private static final String word = "island"; @Test public void anagram() { List<String> l = rearrange(word.toLowerCase()); System.out.println(l.size() + " possible words"); for (String s : l) { System.out.println(s); } } private List<String> rearrange(String word) { List<String> l = new ArrayList<String>(); if (word.length() == 1) { // short circuit l.add(word); return l; } StringBuilder sb = new StringBuilder(word); if (word.length() == 2) { // ends recursion l.add(word); l.add(sb.reverse().toString()); return l; } for (int i = 0; i < sb.length(); i++) { // shift characters one at a time List<String> l2 = rearrange(sb.substring(1)); for (String s : l2) { l.add(sb.substring(0, 1) + s); } sb = sb.append(sb.charAt(0)).deleteCharAt(0); } return l; } }Biju Kunjummen replied on Thu, 2012/06/21 - 9:58am
Here is one in Java:
import java.util.ArrayList; import java.util.Collections; import java.util.Set; import java.util.HashSet; public class WordUtils { public static Set<String> allAnagrams(String word){ return allAnagrams("", word); } private static Set<String> allAnagrams(String prefix, String word){ if (word.length()==0) { return Collections.singleton(prefix) ; } Set<String> aSet = new HashSet<String>(); for (int i=0;i<word.length();i++){ aSet.addAll(allAnagrams(prefix + word.charAt(i), word.substring(0,i)+word.substring(i+1, word.length()))); } return aSet; } }import static org.hamcrest.MatcherAssert.assertThat; import static org.hamcrest.Matchers.hasItems; import java.util.HashSet; import java.util.List; import java.util.Set; import org.junit.Test; public class WordUtilsTest { @Test public void testSmallAnagrams() { String word = "tes"; Set<String> anagrams = WordUtils.allAnagrams(word); System.out.println(anagrams); assertThat(anagrams, hasItems("tes", "tse", "est", "ets", "set", "ste")); } @Test public void testAnagramsWith5Uniques() { String word = "abcde"; Set<String> anagrams = WordUtils.allAnagrams(word); assertThat(anagrams, hasItems("abcde", "decba", "ecbda", "abced", "cadbe")); } }