#!/usr/bin/awk -f

# equiv.awk -- print equivalence class of a word under Lewis Carroll's
# word ladder game.  (What words in a particular lexicon are reachable
# from a given starting word?)

# usage: equiv.awk word [lexicon [lexicon2...]]

# If lexicon is not specified, it will be read from standard input.

function add(word){
        if (state[word] > seen) return;
        print word;
        state[word]++;
        for (i=1; i<=length(word); i++) {
                for (letter in alphabet) {
                        a = alphabet[letter];
                        new = substr(word, 1, i-1) a substr(word, i+1);
                        if (state[new] == seen) add(new);
                }
        }
        state[word]++;
}

BEGIN { letters = "abcdefghijklmnopqrstuvwxyz";
        split(letters, alphabet, "");
        startword = tolower(ARGV[1]);
        equivlen = length(startword);
        ARGV[1] = "";
	seen = 1; reached = 2; done = 3;
}

(length($1) == equivlen) { state[tolower($1)] = seen };

END { state[startword] = seen; add(startword); }