I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Word Chains

07.04.2012
| 3141 views |
  • submit to reddit

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()

 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.