Thursday Code Puzzler: Word Chains
It's Thursday already, so time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find 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!
Word Chains
Write a program to solve word-chain puzzles. A word chain is where you provide a start word and an end word. You need to work out how to get to the end word by changing only one letter through each step. So let's say we have cat and dog: the chain would be cat,cot,cog,dog. You could use a dictionary from here to help.
Catch up on all our previous puzzlers here
Comments
Vijay Nathani replied on Thu, 2012/07/05 - 3:33am
The folloiwng Groovy code prints 'dog'.
def originalWord = 'cat' def wordChain(lettersOriginal, lettersReplaced) { def ALL_LETTERS = 'a'..'z' as HashSet def LIST_OF_VALID_WORDS = ['dog', 'turtle', 'horse'] as HashSet if (lettersOriginal) { def deleteOneChar = lettersOriginal.tail() ALL_LETTERS.minus(lettersOriginal.head()).findResult() { wordChain(deleteOneChar, lettersReplaced + it) } } else { def answer = lettersReplaced.join('') LIST_OF_VALID_WORDS.contains(answer)?answer:null } } println wordChain(originalWord.chars.toList(),[])We can read the dictionary and store it in LIST_OF_VALID_WORDS, but that part has not been done here.
Vijay Nathani replied on Thu, 2012/07/05 - 3:24am
This version of solution reads the dictionary to get the list of valid words.
class WordChain { private def ALL_LETTERS = 'a'..'z' as HashSet def listOfValidWords = [] as HashSet def WordChain() { def DIRECTORY = 'scowl-7.1\\final\\' def FILES_WITH_WORDS = [ 'english-words.10', 'english-words.20', 'english-words.35', 'english-words.40' ] //so on FILES_WITH_WORDS.each { listOfValidWords.addAll(new File(DIRECTORY+it).readLines()) } } private def recurseLetters(firstChar, remainingChars, lettersReplaced) { def alternateChars = firstChar.isLetter()?ALL_LETTERS.minus(firstChar):[ firstChar ] alternateChars.findResult() { process(remainingChars, lettersReplaced + it) } } private def checkValidity(word) { listOfValidWords.contains(word)?word:null } def process(lettersOriginal, lettersReplaced=[]) { lettersOriginal? recurseLetters(lettersOriginal.head(), lettersOriginal.tail(), lettersReplaced) : checkValidity(lettersReplaced.join('')) } } def originalWord = "cat" println new WordChain().process(originalWord.chars.toList())Vijay Nathani replied on Thu, 2012/07/05 - 7:12am
In my previous solution, I was printing the last word; not the full chain. On re-thinking, the question probably wants me to print the full word chain. The output of this groovy program is [cat, cot, dot, dog]
class WordChain { private def ALL_LETTERS = 'a'..'z' private def listOfValidWords = [] as HashSet private String endWord, currentWord; private Map<String,String>tree = new LinkedHashMap() private LinkedList<String>toBeProcessed = [] as LinkedList; def WordChain(initial, desired) { readListOfValidWords() currentWord = initial endWord = desired tree.put(initial,'') } private void readListOfValidWords() { def DIRECTORY = 'scowl-7.1\\final\\' def FILES_WITH_WORDS = [ 'english-words.10', 'english-words.20', 'english-words.35', 'english-words.40' ] //so on FILES_WITH_WORDS.each { listOfValidWords.addAll(new File(DIRECTORY+it).readLines()) } } def search() { while (currentWord && currentWord != endWord) { currentWord.size().times { combine (currentWord[0..<it],currentWord.substring(it+1)) } currentWord = toBeProcessed.isEmpty()? null : toBeProcessed.removeFirst(); } getSolution() } private def getSolution() { def soln = [currentWord] as LinkedList for (String l=currentWord; l; l = tree.get(l)) soln.addFirst(tree.get(l)) soln.tail() } private def combine(String firstPart, String lastPart) { ALL_LETTERS.each { String s = firstPart + it + lastPart if (tree.get(s) != null || !listOfValidWords.contains(s)) return tree.put(s,currentWord) toBeProcessed.add(s) } } } println new WordChain('cat','dog').search()