Dodgsons doublets in Groovy. The rules of the Puzzle are simple enough. Two words are proposed, of the same length; and the Puzzle consists in linking these together by interposing other words, each of which shall differ from the next word in one letter only. That is to say, one letter may be changed in one of the given words, then one letter in…

doublets.groovy

import com.thoughtworks.xstream.core.util.PrioritizedList
import groovy.transform.Field

import java.text.DecimalFormat

/**
 * Dodgsons Duoblets
 *
 * User: gfrison
 * http://programmingpraxis.com/2009/03/20/dodgsons-doublets/
 *
 * usage: ./doublets head tail
 */
String initWord = args[0]
String stopWord = args[1]

//download english word set
def ant = new AntBuilder()
ant.get(src: 'http://www.mieliestronk.com/corncob_lowercase.txt', dest: './corncob_lowercase.txt', skipexisting: true)


@Field List<String> words = []
new File('./corncob_lowercase.txt').eachLine { words.add it }

println "finding $initWord -> $stopWord"

//filter words of input length
words = words.findAll { it.length() == initWord.length() }

if (initWord.length() != stopWord.length()) {
    println "words should have the same length"
    System.exit(0)
}

println "filtered $words.size words with ${initWord.length()}"
@Field List globals = []

public List doublets(def chain, String initWord, String stopWord) {
    chain << initWord
    globals << initWord
    if (initWord == stopWord) {
        return chain
    }
    char[] initWordChars = initWord.toCharArray()
    def founds = []
    for (word in words) {
        if (chain.contains(word) || globals.contains(word)) {
            continue
        } else {
            if (charDifference(word, initWord) == 1) {
                founds << word
            }
        }
    }
    PrioritizedList similars = new PrioritizedList()
    founds.each { similar ->
        similars.add(similar, stopWord.length() - charDifference(stopWord, similar))
    }
    for (String word : similars) {
        List<String> rets = doublets(chain.clone(), word, stopWord)
        if (rets != null) {
            return rets
        }
    }
    return null
}

int charDifference(String a, String b) {
    int diff = a.length()
    for (int i = 0; i < a.length(); i++) {
        if (a.charAt(i) == b.charAt(i)) {
            diff--
        }
    }
    return diff
}

long ts = System.currentTimeMillis()
def path = doublets([], initWord, stopWord)
def secFormat = new DecimalFormat("##,###.##")
println "elaboration time: ${secFormat.format((System.currentTimeMillis() - ts) / 1000)} secs"
if (path != null)
    println "doublets: $path "
else
    println "do not exists any relation between $initWord and $stopWord"