В школе, так получилось, что я валял дурака и математику со статистикой изучаю только сейчас. Таким как я, лодырям с развитой логикой, посвящается. ;) Условие, на инглише:

Two words are friends if they have a Levenshtein distance of 1. That is, you can add, remove, or substitute exactly one letter in word X to create word Y. A word’s social network consists of all of its friends, plus all of their friends, and all of their friends’ friends, and so on. Write a program to tell us how big the social network for the word “causes” is, using this word list. Have fun!

В кратце смысл таков, что нужно найти сеть друзей слова causes, связанных путём изменения одной буквы в слове. Например causes -> cause-> case -> cases и так далее. Я попробовал сперва "в лоб" решить задачку, не заметив маленького но веского "and so on" в условии. Нашёл "друзей", "друзей-друзей" и их "друзей" тоже.

$words = file('word.list');
$words = array_map('trim', $words);
$net  = array( 'causes' );
$i = 0;

while (++$i)
{
  $net +=  find_friends($net, $words);
  $net = array_unique($net);
  echo "Cycle $i -> " . count($net) . " friends, " . count($words) . " words\n";// : " . implode(' ', $net) . "\n";
}

function find_friends($tofind, &$words, $distance = 1)
{
  $friends = array();
  foreach ($tofind as $find)
  {
    foreach ($words as $i=>$word)
    {
      if ( levenshtein($find , $word ) == $distance)
      {
        $friends[] = $word;
        unset ($words[$i]);
      }
    }
  }
  return $friends;
}

Мне показалось что это слишком простая была бы головоломка. И я вчитался. Аха, нужно найти всех, кто повязан через дистанцию Левенштейна равную 1, а не только "друзей" до третьего колена. Переделал цикл на поиск бесконечного удаления "друзей". Комп заскрипел и впал в ступор, как многочисленными проходами по результатам, так и с применением рекурсии.

class Processor {

  public function __construct()
  {
    $words = file('word.list');
    $words = array_map('trim', $words);
    $this->words = array_combine($words, $words);
    $this->net  = array( );
  }

  public function findFriends($find)
  {
    $this->addFriend($find);
    foreach ($this->words as $word)
    {
      if ( levenshtein($find , $word ) == 1)
      {
        $this->findFriends($word);
        reset($this->words);
        echo "(" . count($this->net) ." found/" . count($this->words) ." remain)\n";
      }
    }
  }

  public function addFriend($word)
  {
    $this->net[] = $word;
    echo "$word ";
    unset( $this->words[$word] );
  }

}

$processor = new Processor();
$processor->findFriends('causes');

Слов не мало - около 300 тысячь, колен получается больше 100, PHP-процессор вылетает громко матерясь. Убрал рекурсию и попробовал соорудить что-то вроде очереди - в конец очереди помещал найденных "друзей", убирая их из словаря. Получился более-менее шустрый вариант, дело пошло веселее.

class Processor {

  public function __construct()
  {
    $words = file('word.list');
    $words = array_map('trim', $words);
    $this->words = array_combine($words, $words);
    $this->net  = array( );
  }

  public function findFriends($find)
  {
    foreach ($this->words as $word)
    {
      if ( levenshtein($find , $word ) == 1) $this->addFriend($word);
    }
  }

  public function addFriend($word)
  {
    $this->net[] = $word;
    unset( $this->words[$word] );
  }

}

$processor = new Processor();
$processor->addFriend('causes');

for ($i = 0 ; $i < count( $processor->net ); $i++)
{
  $processor->findFriends( $processor->net[$i] );
  if ($i % 100 == 0) echo "Processing $i of ".
                          count($processor->net) ." friends, " .
                          count($processor->words) ." words remain\n";
}
echo "Final result: " . count($processor->net) ." friends\n";

Наблюдая за циферками, как растёт "сеть друзей" и уменьшается словарик, я подумал о другом решении задачи. Не силён в терминологии, но это кажется называется статистическим анализом. Имея начало некоторой кривой, отображающую рост сети, можно вычислять примерное количество друзей на основе этой статистики.

За 20 часов подсчётов на AMD Athlon 1700, программа выявила сеть из 78482 друзей слова causes вместе с ним самим, а также дала мне кривую с которой буду работать в следующей части этой статьи.

Продолжение следует.