Это было написано как часть Первой Периодической Премьер-программы .

Игра

Начальное и конечное слово одинаковой длины. Цель игры состоит в том, чтобы изменить одну букву в начальном слове, чтобы сформировать другое допустимое слово, повторяя этот шаг до достижения конечного слова, используя наименьшее количество шагов. Например, учитывая слова TREE и FLED, результат будет:

TREE
FREE
FLEE
FLED
2

Характеристики

• Статьи из Википедии для OWL или SOWPODS могут быть полезной отправной точкой для составления списков слов.
• Программа должна поддерживать два способа выбора начального и конечного слов:
  1. Определяется пользователем с помощью командной строки, стандартного ввода или любого другого, подходящего для вашего языка (просто укажите, что вы делаете).
  2. Выбор 2 случайных слов из файла.
• Начальные и конечные слова, а также все промежуточные слова должны быть одинаковой длины.
• Каждый шаг должен быть напечатан в своей строке.
• Последняя строка вашего вывода должна содержать количество промежуточных шагов, необходимых для перехода между начальным и конечным словами.
• Если не удается найти совпадение между начальным и конечным словами, выходные данные должны состоять из 3 строк: начальное слово, конечное слово и слово OY.
• Включите в свой ответ обозначение Big O для вашего решения
• Пожалуйста, включите 10 уникальных пар начальных и конечных слов (с их выводом, конечно), чтобы показать шаги, которые производит ваша программа. (Чтобы сэкономить место, в то время как ваша программа должна выводить их в отдельных строках, вы можете объединить их в одну строку для публикации, заменяя новые строки пробелами и запятой между каждым запуском.

Цели / Критерии победы

• Победит самое быстрое / лучшее решение Big O, обеспечивающее кратчайшие промежуточные этапы за одну неделю.
• Если в результате критерия «Большой О» выбрана ничья, победит самый короткий код.
• Если все еще есть ничья, победит первое решение, достигшее самой быстрой и самой короткой ревизии.

Тесты / Образец Вывода

DIVE
DIME
DAME
NAME
2

PEACE
PLACE
PLATE
SLATE
2

HOUSE
HORSE
GORSE
GORGE
2

POLE
POSE
POST
PAST
FAST
3

Проверка

Я работаю над сценарием, который можно использовать для проверки выходных данных.

Это будет:

1. Убедитесь, что каждое слово является действительным.
2. Убедитесь, что каждое слово точно на 1 букву отличается от предыдущего слова.

Он не будет:

1. Убедитесь, что было использовано самое короткое количество шагов.

Как только я получу это, я, конечно, обновлю этот пост. (:

Поскольку длина указана в качестве критерия, вот версия для гольфа с 1681 символом (вероятно, все еще может быть улучшена на 10%):

import java.io.*;import java.util.*;public class W{public static void main(String[]
a)throws Exception{int n=a.length<1?5:a[0].length(),p,q;String f,t,l;S w=new S();Scanner
s=new Scanner(new
File("sowpods"));while(s.hasNext()){f=s.next();if(f.length()==n)w.add(f);}if(a.length<1){String[]x=w.toArray(new
String[0]);Random
r=new Random();q=x.length;p=r.nextInt(q);q=r.nextInt(q-1);f=x[p];t=x[p>q?q:q+1];}else{f=a[0];t=a[1];}H<S>
A=new H(),B=new H(),C=new H();for(String W:w){A.put(W,new
S());for(p=0;p<n;p++){char[]c=W.toCharArray();c[p]='.';l=new
String(c);A.get(W).add(l);S z=B.get(l);if(z==null)B.put(l,z=new
S());z.add(W);}}for(String W:A.keySet()){C.put(W,w=new S());for(String
L:A.get(W))for(String b:B.get(L))if(b!=W)w.add(b);}N m,o,ñ;H<N> N=new H();N.put(f,m=new
N(f,t));N.put(t,o=new N(t,t));m.k=0;N[]H=new
N[3];H[0]=m;p=H[0].h;while(0<1){if(H[0]==null){if(H[1]==H[2])break;H[0]=H[1];H[1]=H[2];H[2]=null;p++;continue;}if(p>=o.k-1)break;m=H[0];H[0]=m.x();if(H[0]==m)H[0]=null;for(String
v:C.get(m.s)){ñ=N.get(v);if(ñ==null)N.put(v,ñ=new N(v,t));if(m.k+1<ñ.k){if(ñ.k<ñ.I){q=ñ.k+ñ.h-p;N
Ñ=ñ.x();if(H[q]==ñ)H[q]=Ñ==ñ?null:Ñ;}ñ.b=m;ñ.k=m.k+1;q=ñ.k+ñ.h-p;if(H[q]==null)H[q]=ñ;else{ñ.n=H[q];ñ.p=ñ.n.p;ñ.n.p=ñ.p.n=ñ;}}}}if(o.b==null)System.out.println(f+"\n"+t+"\nOY");else{String[]P=new
String[o.k+2];P[o.k+1]=o.k-1+"";m=o;for(q=m.k;q>=0;q--){P[q]=m.s;m=m.b;}for(String
W:P)System.out.println(W);}}}class N{String s;int k,h,I=(1<<30)-1;N b,p,n;N(String S,String
d){s=S;for(k=0;k<d.length();k++)if(d.charAt(k)!=S.charAt(k))h++;k=I;p=n=this;}N
x(){N r=n;n.p=p;p.n=n;n=p=this;return r;}}class S extends HashSet<String>{}class H<V>extends
HashMap<String,V>{}

Версия ungolfed, которая использует имена пакетов и методы и не дает предупреждений или расширяет классы только для их псевдонимов, такова:

package com.akshor.pjt33;

import java.io.*;
import java.util.*;

// WordLadder partially golfed and with reduced dependencies
//
// Variables used in complexity analysis:
// n is the word length
// V is the number of words (vertex count of the graph)
// E is the number of edges
// hash is the cost of a hash insert / lookup - I will assume it's constant, but without completely brushing it under the carpet
public class WordLadder2
{
    private Map<String, Set<String>> wordsToWords = new HashMap<String, Set<String>>();

    // Initialisation cost: O(V * n * (n + hash) + E * hash)
    private WordLadder2(Set<String> words)
    {
        Map<String, Set<String>> wordsToLinks = new HashMap<String, Set<String>>();
        Map<String, Set<String>> linksToWords = new HashMap<String, Set<String>>();

        // Cost: O(Vn * (n + hash))
        for (String word : words)
        {
            // Cost: O(n*(n + hash))
            for (int i = 0; i < word.length(); i++)
            {
                // Cost: O(n + hash)
                char[] ch = word.toCharArray();
                ch[i] = '.';
                String link = new String(ch).intern();
                add(wordsToLinks, word, link);
                add(linksToWords, link, word);
            }
        }

        // Cost: O(V * n * hash + E * hash)
        for (Map.Entry<String, Set<String>> from : wordsToLinks.entrySet()) {
            String src = from.getKey();
            wordsToWords.put(src, new HashSet<String>());
            for (String link : from.getValue()) {
                Set<String> to = linksToWords.get(link);
                for (String snk : to) {
                    // Note: equality test is safe here. Cost is O(hash)
                    if (snk != src) add(wordsToWords, src, snk);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException
    {
        // Cost: O(filelength + num_words * hash)
        Map<Integer, Set<String>> wordsByLength = new HashMap<Integer, Set<String>>();
        BufferedReader br = new BufferedReader(new FileReader("sowpods"), 8192);
        String line;
        while ((line = br.readLine()) != null) add(wordsByLength, line.length(), line);

        if (args.length == 2) {
            String from = args[0].toUpperCase();
            String to = args[1].toUpperCase();
            new WordLadder2(wordsByLength.get(from.length())).findPath(from, to);
        }
        else {
            // 5-letter words are the most interesting.
            String[] _5 = wordsByLength.get(5).toArray(new String[0]);
            Random rnd = new Random();
            int f = rnd.nextInt(_5.length), g = rnd.nextInt(_5.length - 1);
            if (g >= f) g++;
            new WordLadder2(wordsByLength.get(5)).findPath(_5[f], _5[g]);
        }
    }

    // O(E * hash)
    private void findPath(String start, String dest) {
        Node startNode = new Node(start, dest);
        startNode.cost = 0; startNode.backpointer = startNode;

        Node endNode = new Node(dest, dest);

        // Node lookup
        Map<String, Node> nodes = new HashMap<String, Node>();
        nodes.put(start, startNode);
        nodes.put(dest, endNode);

        // Heap
        Node[] heap = new Node[3];
        heap[0] = startNode;
        int base = heap[0].heuristic;

        // O(E * hash)
        while (true) {
            if (heap[0] == null) {
                if (heap[1] == heap[2]) break;
                heap[0] = heap[1]; heap[1] = heap[2]; heap[2] = null; base++;
                continue;
            }

            // If the lowest cost isn't at least 1 less than the current cost for the destination,
            // it can't improve the best path to the destination.
            if (base >= endNode.cost - 1) break;

            // Get the cheapest node from the heap.
            Node v0 = heap[0];
            heap[0] = v0.remove();
            if (heap[0] == v0) heap[0] = null;

            // Relax the edges from v0.
            int g_v0 = v0.cost;
            // O(hash * #neighbours)
            for (String v1Str : wordsToWords.get(v0.key))
            {
                Node v1 = nodes.get(v1Str);
                if (v1 == null) {
                    v1 = new Node(v1Str, dest);
                    nodes.put(v1Str, v1);
                }

                // If it's an improvement, use it.
                if (g_v0 + 1 < v1.cost)
                {
                    // Update the heap.
                    if (v1.cost < Node.INFINITY)
                    {
                        int bucket = v1.cost + v1.heuristic - base;
                        Node t = v1.remove();
                        if (heap[bucket] == v1) heap[bucket] = t == v1 ? null : t;
                    }

                    // Next update the backpointer and the costs map.
                    v1.backpointer = v0;
                    v1.cost = g_v0 + 1;

                    int bucket = v1.cost + v1.heuristic - base;
                    if (heap[bucket] == null) {
                        heap[bucket] = v1;
                    }
                    else {
                        v1.next = heap[bucket];
                        v1.prev = v1.next.prev;
                        v1.next.prev = v1.prev.next = v1;
                    }
                }
            }
        }

        if (endNode.backpointer == null) {
            System.out.println(start);
            System.out.println(dest);
            System.out.println("OY");
        }
        else {
            String[] path = new String[endNode.cost + 1];
            Node t = endNode;
            for (int i = t.cost; i >= 0; i--) {
                path[i] = t.key;
                t = t.backpointer;
            }
            for (String str : path) System.out.println(str);
            System.out.println(path.length - 2);
        }
    }

    private static <K, V> void add(Map<K, Set<V>> map, K key, V value) {
        Set<V> vals = map.get(key);
        if (vals == null) map.put(key, vals = new HashSet<V>());
        vals.add(value);
    }

    private static class Node
    {
        public static int INFINITY = Integer.MAX_VALUE >> 1;

        public String key;
        public int cost;
        public int heuristic;
        public Node backpointer;

        public Node prev = this;
        public Node next = this;

        public Node(String key, String dest) {
            this.key = key;
            cost = INFINITY;
            for (int i = 0; i < dest.length(); i++) if (dest.charAt(i) != key.charAt(i)) heuristic++;
        }

        public Node remove() {
            Node rv = next;
            next.prev = prev;
            prev.next = next;
            next = prev = this;
            return rv;
        }
    }
}

Как видите, анализ текущих затрат O(filelength + num_words * hash + V * n * (n + hash) + E * hash). Если вы примете мое предположение, что вставка / поиск в хэш-таблице является постоянным временем, это так O(filelength + V n^2 + E). Конкретная статистика графиков в SOWPODS означает, что это O(V n^2)действительно доминирует O(E)для большинства n.

Пример выходов:

ИДОЛА, ИДОЛЫ, ИДИЛЫ, ОДИЛЫ, ОДАЛЫ, ОВАЛЫ, СУМКИ, ДУХОВКИ, ДАЖЕ, ЭТЕНС, СТЕНЫ, КОЖИ, КОЖИ, СПИНЫ, СПИНЬ, 13

WICCA, PROSY, OY

BRINY, BRINS, TRINS, TAINS, TARNS, YARNS, YAWNS, YAWPS, YAPPS, 7

ГАЛЕЙ, ГАЗЫ, ГАСТЫ, ГАСТЫ, GESTE, GESSE, DESSE, 5

SURES, DURES, DUNES, DINES, DINGS, DINGY, 4

СВЕТ, СВЕТ, СВЕТ, БОЛЬШОЙ, БИГОС, БИРОС, ГИРОС, ДЕВУШКИ, ГУРНЫ, ГУАНЫ, ГУАНА, РУАНА, 10

SARGE, SERGE, SERRE, SERRS, SEERS, DEERS, DYERS, OYERS, OVERS, OVELS, овалы, ODALS, ODYLS, IDYLS, 12

КИРСЫ, SEIRS, SEERS, ПИВО, BRERS, BRERE, BREME, КРЕМ, КРЕП, 7

Это одна из 6 пар с самым длинным кратчайшим путем:

GAINEST, FAINEST, FAIREST, SAIREST, SAIDEST, SADDEST, MADDEST, MIDDEST, MILDEST, WILDEST, WILIEST, WILIEST, WIIEST, CANIEST, CANTEST, КОНКУРС, КОНФЕСС, КОНФЕРСЫ, КОНКЕРЫ, КУХНИ, КУПЕРЫ, КОТЛЫ, КОПЫ, POPPITS, маки, POPSIES, MOPSIES, MOUSIES, муссы, POUSSES, плюсы, PLISSES, PRISSES, прессы, PREASES, уреазы, UNEASES, UNCASES, бескорпусный, UNBASED, UNBATED, Разъединенный, UNMETED, UNMEWED, ENMEWED, ENDEWED, INDEWED, индексированный, УКАЗАТЕЛИ, УКАЗАНИЯ, УКАЗАНИЯ, ОТНОШЕНИЯ, ИНВЕСТЫ, ИНФЕСТЫ, ИНФЕКЦИИ, ВСТАВКИ, 56

И одна из разрешимых 8-буквенных пар в худшем случае:

ENROBING, UNROBING, UNROBING, UNCOPING, UNCINGING, UNCAGING, ENCAGING, ENRACING, ENLACING, UNLACING, UNLAY, UPLING, SPLAY, SPRAY, STRAYING, STROYING, STROBING, STINGINGING, STINGPING, STINGPING, STINGPING, STINGINGING Обжимные, хрустящие, хрустящие, хрустящие, хрустящие, скребки, скребки, скреперы, скреперы, скребки, скребки, молния, молния, мятеж, мятеж, мятежник, мятежник, мятежник, мятежник ЛАНЧЕРЫ, ЛИНЧЕРЫ, ЛИНЧЕТЫ, ЛИНЧЕТЫ, 52

Теперь, когда я думаю, что у меня есть все требования этого вопроса, моя дискуссия.

Для CompSci вопрос, очевидно, сводится к кратчайшему пути в графе G, вершинами которого являются слова, а ребра которого соединяют слова, отличающиеся одной буквой. Эффективное создание графа не тривиально - у меня действительно есть идея, которую я должен пересмотреть, чтобы уменьшить сложность до O (V n hash + E). То, как я это делаю, включает в себя создание графа, который вставляет дополнительные вершины (соответствующие словам с одним символом подстановки) и гомеоморфен рассматриваемому графу. Я подумал об использовании этого графа, а не о сокращении до G - и я полагаю, что с точки зрения игры в гольф я должен был это сделать - исходя из того, что подстановочный узел с более чем 3 ребрами уменьшает число ребер в графе, и Стандартное время выполнения алгоритмов кратчайшего пути составляет O(V heap-op + E).

Тем не менее, первое, что я сделал, - запустил анализ графиков G для разных длин слов, и я обнаружил, что они чрезвычайно редки для слов из 5 или более букв. 5-буквенный граф имеет 12478 вершин и 40759 ребер; добавление узлов ссылок ухудшает график. К тому времени, когда у вас до 8 букв, ребер меньше, чем узлов, и 3/7 слов «в стороне». Поэтому я отклонил эту идею оптимизации как не очень полезную.

Идея, которая оказалась полезной, состояла в том, чтобы изучить кучу. Я могу честно сказать, что я реализовал несколько умеренно экзотических куч в прошлом, но ни одна из них не была такой экзотической, как эта. Я использую A-star (поскольку C не дает никакой пользы, учитывая кучу, которую я использую) с очевидной эвристикой количества букв, отличных от цели, и небольшой анализ показывает, что в любой момент времени не более 3 различных приоритетов в кучу. Когда я открываю узел с приоритетом (стоимость + эвристика) и смотрю на его соседей, я рассматриваю три случая: 1) стоимость соседа равна стоимости + 1; эвристика соседа - эвристика-1 (потому что буква, которую она меняет, становится «правильной»); 2) стоимость + 1 и эвристика + 0 (потому что буква, которую она меняет, переходит от «неправильно» к «все еще неправильно»; 3) стоимость + 1 и эвристика + 1 (потому что буква, которую она меняет, переходит от «правильной» к «неправильной»). Поэтому, если я расслаблю соседа, я собираюсь вставить его с тем же приоритетом, приоритетом + 1 или приоритетом + 2. В результате я могу использовать массив из 3-х элементов связанных списков для кучи.

Я должен добавить примечание о моем предположении, что поиск хеша является постоянным. Хорошо, вы можете сказать, но как насчет хэш-вычислений? Ответ в том, что я их амортизирую: java.lang.Stringкэширует их hashCode(), поэтому общее время, затрачиваемое на вычисление хэшей, составляет O(V n^2)(при создании графика).

Есть еще одно изменение, которое влияет на сложность, но вопрос о том, является ли это оптимизацией или нет, зависит от ваших предположений о статистике. (IMO, ставя «лучшее решение Big O» в качестве критерия, является ошибкой, потому что нет лучшей сложности по простой причине: не существует единственной переменной). Это изменение влияет на шаг генерации графика. В приведенном выше коде это:

        Map<String, Set<String>> wordsToLinks = new HashMap<String, Set<String>>();
        Map<String, Set<String>> linksToWords = new HashMap<String, Set<String>>();

        // Cost: O(Vn * (n + hash))
        for (String word : words)
        {
            // Cost: O(n*(n + hash))
            for (int i = 0; i < word.length(); i++)
            {
                // Cost: O(n + hash)
                char[] ch = word.toCharArray();
                ch[i] = '.';
                String link = new String(ch).intern();
                add(wordsToLinks, word, link);
                add(linksToWords, link, word);
            }
        }

        // Cost: O(V * n * hash + E * hash)
        for (Map.Entry<String, Set<String>> from : wordsToLinks.entrySet()) {
            String src = from.getKey();
            wordsToWords.put(src, new HashSet<String>());
            for (String link : from.getValue()) {
                Set<String> to = linksToWords.get(link);
                for (String snk : to) {
                    // Note: equality test is safe here. Cost is O(hash)
                    if (snk != src) add(wordsToWords, src, snk);
                }
            }
        }

Это O(V * n * (n + hash) + E * hash). Но эта O(V * n^2)часть получается из генерации новой строки из n символов для каждой ссылки и последующего вычисления ее хеш-кода. Этого можно избежать с помощью вспомогательного класса:

    private static class Link
    {
        private String str;
        private int hash;
        private int missingIdx;

        public Link(String str, int hash, int missingIdx) {
            this.str = str;
            this.hash = hash;
            this.missingIdx = missingIdx;
        }

        @Override
        public int hashCode() { return hash; }

        @Override
        public boolean equals(Object obj) {
            Link l = (Link)obj; // Unsafe, but I know the contexts where I'm using this class...
            if (this == l) return true; // Essential
            if (hash != l.hash || missingIdx != l.missingIdx) return false;
            for (int i = 0; i < str.length(); i++) {
                if (i != missingIdx && str.charAt(i) != l.str.charAt(i)) return false;
            }
            return true;
        }
    }

Тогда первая половина генерации графа становится

        Map<String, Set<Link>> wordsToLinks = new HashMap<String, Set<Link>>();
        Map<Link, Set<String>> linksToWords = new HashMap<Link, Set<String>>();

        // Cost: O(V * n * hash)
        for (String word : words)
        {
            // apidoc: The hash code for a String object is computed as
            // s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
            // Cost: O(n * hash)
            int hashCode = word.hashCode();
            int pow = 1;
            for (int j = word.length() - 1; j >= 0; j--) {
                Link link = new Link(word, hashCode - word.charAt(j) * pow, j);
                add(wordsToLinks, word, link);
                add(linksToWords, link, word);
                pow *= 31;
            }
        }

Используя структуру хеш-кода, мы можем генерировать ссылки в O(V * n) . Тем не менее, это имеет эффект удара. Мое предположение о том, что поиск по хешу является постоянным временем, предполагает, что сравнение объектов на равенство обходится дешево. Тем не менее, тест на равенство Link O(n)в худшем случае. Худший случай - когда у нас есть столкновение хешей между двумя равными ссылками, сгенерированными из разных слов - т.е. это происходит O(E)раз во второй половине генерации графа. Кроме этого, за исключением маловероятного случая столкновения хэша между неравными ссылками, мы хороши. Итак, мы обменялись O(V * n^2)на O(E * n * hash). Смотрите мой предыдущий пункт о статистике.

Джава

Сложность : (У меня нет степени CompSci, поэтому я был бы признателен за помощь в этом вопросе.)

Ввод : укажите пару слов (более 1 пары, если хотите) в командной строке. Если командная строка не указана, выбираются 2 разных случайных слова.

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

public class M {

    // for memoization
    private static Map<String, List<String>> memoEdits = new HashMap<String, List<String>>(); 
    private static Set<String> dict;

    private static List<String> edits(String word, Set<String> dict) {
        if(memoEdits.containsKey(word))
            return memoEdits.get(word);

        List<String> editsList = new LinkedList<String>();
        char[] letters = word.toCharArray();
        for(int i = 0; i < letters.length; i++) {
            char hold = letters[i];
            for(char ch = 'A'; ch <= 'Z'; ch++) {
                if(ch != hold) {
                    letters[i] = ch;
                    String nWord = new String(letters);
                    if(dict.contains(nWord)) {
                        editsList.add(nWord);
                    }
                }
            }
            letters[i] = hold;
        }
        memoEdits.put(word, editsList);
        return editsList;
    }

    private static Map<String, String> bfs(String wordFrom, String wordTo,
                                           Set<String> dict) {
        Set<String> visited = new HashSet<String>();
        List<String> queue = new LinkedList<String>();
        Map<String, String> pred = new HashMap<String, String>();
        queue.add(wordFrom);
        while(!queue.isEmpty()) {
            String word = queue.remove(0);
            if(word.equals(wordTo))
                break;

            for(String nWord: edits(word, dict)) {
                if(!visited.contains(nWord)) {
                    queue.add(nWord);
                    visited.add(nWord);
                    pred.put(nWord, word);
                }
            }
        }
        return pred;
    }

    public static void printPath(String wordTo, String wordFrom) {
        int c = 0;
        Map<String, String> pred = bfs(wordFrom, wordTo, dict);
        do {
            System.out.println(wordTo);
            c++;
            wordTo = pred.get(wordTo);
        }
        while(wordTo != null && !wordFrom.equals(wordTo));
        System.out.println(wordFrom);
        if(wordTo != null)
            System.out.println(c - 1);
        else
            System.out.println("OY");
        System.out.println();
    }

    public static void main(String[] args) throws Exception {
        BufferedReader scan = new BufferedReader(new FileReader(new File("c:\\332609\\dict.txt")),
                                                 40 * 1024);
        String line;
        dict = new HashSet<String>(); //the dictionary (1 word per line)
        while((line = scan.readLine()) != null) {
            dict.add(line);
        }
        scan.close();
        if(args.length == 0) { // No Command line Arguments? Pick 2 random
                               // words.
            Random r = new Random(System.currentTimeMillis());
            String[] words = dict.toArray(new String[dict.size()]);
            int x = r.nextInt(words.length), y = r.nextInt(words.length);
            while(x == y) //same word? that's not fun...
                y = r.nextInt(words.length);
            printPath(words[x], words[y]);
        }
        else { // Arguments provided, search for path pairwise
            for(int i = 0; i < args.length; i += 2) {
                if(i + 1 < args.length)
                    printPath(args[i], args[i + 1]);
            }
        }
    }
}

c на Unix

Используя алгоритм Дейкстры.

Большая часть кода представляет собой реализацию костюмного n-арного дерева, которая служит для хранения

• Список слов (таким образом, сводя к минимуму количество раз, когда входной файл читается (дважды без аргументов, один раз для других случаев) при условии медленного ввода-вывода файла
• Частичные деревья, как мы их строим.
• Последний путь.

Любой заинтересованный в том , как это работает , вероятно , следует прочитать findPath, processи processOne(и связанные с ними комментарии). А может быть buildPathи buildPartialPath. Остальное - бухгалтерия и строительные леса. Несколько подпрограмм, используемых во время тестирования и разработки, но не в «производственной» версии, остались на месте.

Я использую /usr/share/dict/wordsна моем Mac OS 10.5 ящик, который имеет так много длинных, эзотерические записи, позволяя ему работать полностью случайным образом генерирует много из OYс.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <getline.h>
#include <time.h>
#include <unistd.h>
#include <ctype.h>

const char*wordfile="/usr/share/dict/words";
/* const char*wordfile="./testwords.txt"; */
const long double RANDOM_MAX = (2LL<<31)-1;

typedef struct node_t {
  char*word;
  struct node_t*kids;
  struct node_t*next;
} node;


/* Return a pointer to a newly allocated node. If word is non-NULL, 
 * call setWordNode;
 */
node*newNode(char*word){
  node*n=malloc(sizeof(node));
  n->word=NULL;
  n->kids=NULL;
  n->next=NULL;
  if (word) n->word = strdup(word);
  return n;
}
/* We can use the "next" links to treat these as a simple linked list,
 * and further can make it a stack or queue by
 *
 * * pop()/deQueu() from the head
 * * push() onto the head
 * * enQueue at the back
 */
void push(node*n, node**list){
  if (list==NULL){
    fprintf(stderr,"Active operation on a NULL list! Exiting\n");
    exit(5);
  }
  n->next = (*list);
  (*list) = n;
}
void enQueue(node*n, node**list){
  if (list==NULL){
    fprintf(stderr,"Active operation on a NULL list! Exiting\n");
    exit(5);
  }
  if ( *list==NULL ) {
    *list=n;
  } else {
    enQueue(n,&((*list)->next));
  }
}
node*pop(node**list){
  node*temp=NULL;
  if (list==NULL){
    fprintf(stderr,"Active operation on a NULL list! Exiting\n");
    exit(5);
  }
  temp = *list;
  if (temp != NULL) {
    (*list) = temp->next;
    temp->next=NULL;
  }
  return temp;
}
node*deQueue(node**list){ /* Alias for pop */
  return pop(list);
}

/* return a pointer to a node in tree matching word or NULL if none */
node* isInTree(char*word, node*tree){
  node*isInNext=NULL;
  node*isInKids=NULL;
  if (tree==NULL || word==NULL) return NULL;
  if (tree->word && (0 == strcasecmp(word,tree->word))) return tree;
  /* prefer to find the target at shallow levels so check the siblings
     before the kids */
  if (tree->next && (isInNext=isInTree(word,tree->next))) return isInNext;
  if (tree->kids && (isInKids=isInTree(word,tree->kids))) return isInKids;
  return NULL;
}

node* freeTree(node*t){
  if (t==NULL) return NULL;
  if (t->word) {free(t->word); t->word=NULL;}
  if (t->next) t->next=freeTree(t->next);
  if (t->kids) t->kids=freeTree(t->kids);
  free(t);
  return NULL;
}

void printTree(node*t, int indent){
  int i;
  if (t==NULL) return;
  for (i=0; i<indent; i++) printf("\t"); printf("%s\n",t->word);
  printTree(t->kids,indent+1);
  printTree(t->next,indent);
}

/* count the letters of difference between two strings */
int countDiff(const char*w1, const char*w2){
  int count=0;
  if (w1==NULL || w2==NULL) return -1;
  while ( (*w1)!='\0' && (*w2)!='\0' ) {
    if ( (*w1)!=(*w2) ) count++;
    w1++;
    w2++;
  }
  return count;
}

node*buildPartialPath(char*stop, node*tree){
  node*list=NULL;
  while ( (tree != NULL) && 
      (tree->word != NULL) && 
      (0 != strcasecmp(tree->word,stop)) ) {
    node*kid=tree->kids;
    node*newN = newNode(tree->word);
    push(newN,&list);
    newN=NULL;
    /* walk over all all kids not leading to stop */
    while ( kid && 
        (strcasecmp(kid->word,stop)!=0) &&
        !isInTree(stop,kid->kids) ) {
      kid=kid->next;
    }
    if (kid==NULL) {
      /* Assuming a preconditions where isInTree(stop,tree), we should
       * not be able to get here...
       */
      fprintf(stderr,"Unpossible!\n");
      exit(7);
    } 
    /* Here we've found a node that either *is* the target or leads to it */
    if (strcasecmp(stop,kid->word) == 0) {
      break;
    }
    tree = kid;
  }
  return list; 
}
/* build a node list path 
 *
 * We can walk down each tree, identfying nodes as we go
 */
node*buildPath(char*pivot,node*frontTree,node*backTree){
  node*front=buildPartialPath(pivot,frontTree);
  node*back=buildPartialPath(pivot,backTree);
  /* weld them together with pivot in between 
  *
  * The front list is in reverse order, the back list in order
  */
  node*thePath=NULL;
  while (front != NULL) {
    node*n=pop(&front);
    push(n,&thePath);
  }
  if (pivot != NULL) {
    node*n=newNode(pivot);
    enQueue(n,&thePath);
  }
  while (back != NULL) {
    node*n=pop(&back);
    enQueue(n,&thePath);
  }
  return thePath;
}

/* Add new child nodes to the single node in ts named by word. Also
 * queue these new word in q
 * 
 * Find node N matching word in ts
 * For tword in wordList
 *    if (tword is one change from word) AND (tword not in ts)
 *        add tword to N.kids
 *        add tword to q
 *        if tword in to
 *           return tword
 * return NULL
 */
char* processOne(char *word, node**q, node**ts, node**to, node*wordList){
  if ( word==NULL || q==NULL || ts==NULL || to==NULL || wordList==NULL ) {
    fprintf(stderr,"ProcessOne called with NULL argument! Exiting.\n");
    exit(9);
  }
  char*result=NULL;
  /* There should be a node in ts matching the leading node of q, find it */
  node*here = isInTree(word,*ts);
  /* Now test each word in the list as a possible child of HERE */
  while (wordList != NULL) {
    char *tword=wordList->word;
    if ((1==countDiff(word,tword)) && !isInTree(tword,*ts)) {
      /* Queue this up as a child AND for further processing */
      node*newN=newNode(tword);
      enQueue(newN,&(here->kids));
      newN=newNode(tword);
      enQueue(newN,q);
      /* This might be our pivot */
      if ( isInTree(tword,*to) ) {
    /* we have found a node that is in both trees */
    result=strdup(tword);
    return result;
      }
    }
    wordList=wordList->next;
  }
  return result;
}

/* Add new child nodes to ts for all the words in q */
char* process(node**q, node**ts, node**to, node*wordList){
  node*tq=NULL;
  char*pivot=NULL;
  if ( q==NULL || ts==NULL || to==NULL || wordList==NULL ) {
    fprintf(stderr,"Process called with NULL argument! Exiting.\n");
    exit(9);
  }
  while (*q && (pivot=processOne((*q)->word,&tq,ts,to,wordList))==NULL) {
    freeTree(deQueue(q));
  }
  freeTree(*q); 
  *q=tq;
  return pivot;
}

/* Find a path between w1 and w2 using wordList by dijkstra's
 * algorithm
 *
 * Use a breadth-first extensions of the trees alternating between
 * trees.
 */
node* findPath(char*w1, char*w2, node*wordList){
  node*thePath=NULL; /* our resulting path */
  char*pivot=NULL; /* The node we find that matches */
  /* trees of existing nodes */
  node*t1=newNode(w1); 
  node*t2=newNode(w2);
  /* queues of nodes to work on */
  node*q1=newNode(w1);
  node*q2=newNode(w2);

  /* work each queue all the way through alternating until a word is
     found in both lists */
  while( (q1!=NULL) && ((pivot = process(&q1,&t1,&t2,wordList)) == NULL) &&
     (q2!=NULL) && ((pivot = process(&q2,&t2,&t1,wordList)) == NULL) )
    /* no loop body */ ;


  /* one way or another we are done with the queues here */
  q1=freeTree(q1);
  q2=freeTree(q2);
  /* now construct the path */
  if (pivot!=NULL) thePath=buildPath(pivot,t1,t2);
  /* clean up after ourselves */
  t1=freeTree(t1);
  t2=freeTree(t2);

  return thePath;
}

/* Convert a non-const string to UPPERCASE in place */
void upcase(char *s){
  while (s && *s) {
    *s = toupper(*s);
    s++;
  }
}

/* Walks the input file stuffing lines of the given length into a list */
node*getListWithLength(const char*fname, int len){
  int l=-1;
  size_t n=0;
  node*list=NULL;
  char *line=NULL;
  /* open the word file */
  FILE*f = fopen(fname,"r");
  if (NULL==f){
    fprintf(stderr,"Could not open word file '%s'. Exiting.\n",fname);
    exit(3);
  }
  /* walk the file, trying each word in turn */
  while ( !feof(f) && ((l = getline(&line,&n,f)) != -1) ) {
    /* strip trailing whitespace */
    char*temp=line;
    strsep(&temp," \t\n");
    if (strlen(line) == len) {
      node*newN = newNode(line);
      upcase(newN->word);
      push(newN,&list);
    }
  }
  fclose(f);
  return list;
}

/* Assumes that filename points to a file containing exactly one
 * word per line with no other whitespace.
 * It will return a randomly selected word from filename.
 *
 * If veto is non-NULL, only non-matching words of the same length
 * wll be considered.
 */
char*getRandomWordFile(const char*fname, const char*veto){
  int l=-1, count=1;
  size_t n=0;
  char *word=NULL;
  char *line=NULL;
  /* open the word file */
  FILE*f = fopen(fname,"r");
  if (NULL==f){
    fprintf(stderr,"Could not open word file '%s'. Exiting.\n",fname);
    exit(3);
  }
  /* walk the file, trying each word in turn */
  while ( !feof(f) && ((l = getline(&line,&n,f)) != -1) ) {
    /* strip trailing whitespace */
    char*temp=line;
    strsep(&temp," \t\n");
    if (strlen(line) < 2) continue; /* Single letters are too easy! */
    if ( (veto==NULL) || /* no veto means chose from all */ 
     ( 
      ( strlen(line) == strlen(veto) )  && /* veto means match length */
      ( 0 != strcasecmp(veto,line) )       /* but don't match word */ 
       ) ) { 
      /* This word is worthy of consideration. Select it with random
         chance (1/count) then increment count */
      if ( (word==NULL) || (random() < RANDOM_MAX/count) ) {
    if (word) free(word);
    word=strdup(line);
      }
      count++;
    }
  }
  fclose(f);
  upcase(word);
  return word;
}

void usage(int argc, char**argv){
  fprintf(stderr,"%s [ <startWord> [ <endWord> ]]:\n\n",argv[0]);
  fprintf(stderr,
      "\tFind the shortest transformation from one word to another\n");
  fprintf(stderr,
      "\tchanging only one letter at a time and always maintaining a\n");
  fprintf(stderr,
      "\tword that exists in the word file.\n\n");
  fprintf(stderr,
      "\tIf startWord is not passed, chose at random from '%s'\n",
      wordfile);
  fprintf(stderr,
      "\tIf endWord is not passed, chose at random from '%s'\n",
      wordfile);
  fprintf(stderr,
      "\tconsistent with the length of startWord\n");
  exit(2);
}

int main(int argc, char**argv){
  char *startWord=NULL;
  char *endWord=NULL;

  /* intialize OS services */
  srandom(time(0)+getpid());
  /* process command line */
  switch (argc) {
  case 3:
    endWord = strdup(argv[2]);
    upcase(endWord);
  case 2:
    startWord = strdup(argv[1]);
    upcase(startWord);
  case 1:
    if (NULL==startWord) startWord = getRandomWordFile(wordfile,NULL);
    if (NULL==endWord)   endWord   = getRandomWordFile(wordfile,startWord);
    break;
  default:
    usage(argc,argv);
    break;
  }
  /* need to check this in case the user screwed up */
  if ( !startWord || ! endWord || strlen(startWord) != strlen(endWord) ) {
    fprintf(stderr,"Words '%s' and '%s' are not the same length! Exiting\n",
        startWord,endWord);
    exit(1);
  }
  /* Get a list of all the words having the right length */
  node*wordList=getListWithLength(wordfile,strlen(startWord));
  /* Launch into the path finder*/
  node *theList=findPath(startWord,endWord,wordList);
  /* Print the resulting path */
  if (theList) {
    int count=-2;
    while (theList) {
      printf("%s\n",theList->word);
      theList=theList->next;
      count++;
    }
    printf("%d\n",count);
  } else {
    /* No path found case */
    printf("%s %s OY\n",startWord,endWord);
  }
  return 0;
}

Некоторый вывод:

$ ./changeword dive name
DIVE
DIME
DAME
NAME
2
$ ./changeword house gorge
HOUSE
HORSE
GORSE
GORGE
2
$ ./changeword stop read
STOP
STEP
SEEP
SEED
REED
READ
4
$ ./changeword peace slate
PEACE
PLACE
PLATE
SLATE
2
$ ./changeword pole fast  
POLE
POSE
POST
PAST
FAST
3
$ ./changeword          
QUINTIPED LINEARITY OY
$ ./changeword sneaky   
SNEAKY WAXILY OY
$ ./changeword TRICKY
TRICKY
PRICKY
PRINKY
PRANKY
TRANKY
TWANKY
SWANKY
SWANNY
SHANNY
SHANTY
SCANTY
SCATTY
SCOTTY
SPOTTY
SPOUTY
STOUTY
STOUTH
STOUSH
SLOUSH
SLOOSH
SWOOSH
19
$ ./changeword router outlet
ROUTER
ROTTER
RUTTER
RUTHER
OUTHER
OUTLER
OUTLET
5
$ ./changeword 
IDIOM
IDISM
IDIST
ODIST
OVIST
OVEST
OVERT
AVERT
APERT
APART
SPART
SPARY
SEARY
DEARY
DECRY
DECAY
DECAN
DEDAN
SEDAN
17

Анализ сложности нетривиален. Поиск является двусторонним, итеративным углублением.

• Для каждого исследуемого узла я прохожу весь список слов (хотя ограничен словами правильной длины). Назовите длину списка W.
• Минимальное количество шагов состоит в том, S_min = (<number of different letter>-1)что если мы на расстоянии только одной буквы, мы оцениваем изменение в 0 промежуточных шагов. Максимум трудно измерить, см. Выше «ТРИКИ - ОГОНЬ». Каждая половина дерева будет S/2-1вS/2
• Я не сделал анализ поведения ветвления дерева, но назову его B.

Таким образом, минимальное количество операций около 2 * (S/2)^B * W, не очень хорошо.