Ищем метаграммы для русских существительных

Метаграммой (word ladder) называется цепочка слов, полученная последовательной заменой одной буквы в исходном слове, например, сом - ком - кот - кит (вики). Придумал эту игру Льюис Кэррол. Обычно по условиям все слова должны быть осмысленными и представлять собой существительные только в единственном или же в единственном и множественном числе.

Соответственно, кроме программы поиска метаграмм нам нужен словарь слов, я брал свой файл из этого архива .zip, поменяв ему кодировку с UTF-8 (Юникода) на однобайтовую Windows-1251 (файл прикреплён ниже). В файле приведены существительные русского языка в единственном и множественном числе, буквы "ё" нет ("осел", а не "осёл").

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

Ниже показан листинг консольного приложения Windows и прикреплён словарь. Программа проверялась в актуальной сборке Visual Studio 2019.

#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <Windows.h> /* SetConsoleCP, SetConsoleOutputCP - только Visual Studio */

using namespace std;
using word_map = map<size_t, vector<string>>;

bool one_away(const string& s1, const string& s2) {
 // Да, если s1 и s2 отличаются одной буквой
 if (s1.size() != s2.size()) return false;
 bool result = false;
 for (size_t i = 0, n = s1.size(); i != n; ++i) {
  if (s1[i] != s2[i]) {
   if (result) return false;
   result = true;
  }
 }
 return result;
}

template <typename iterator_type, typename separator_type>
 string join(iterator_type begin, iterator_type end, separator_type separator) {
 // Объединяет последовательности строк в одну строку, используя заданный разделитель 
 string result;
 if (begin != end) {
  result += *begin++;
  for (; begin != end; ++begin) {
   result += separator;
   result += *begin;
  }
 }
 return result;
}

template <typename vector_type, typename element_type>
bool contains(const vector_type& word, const element_type& item) {
 //Да, если word содержит item
 return find(word.begin(), word.end(), item) != word.end();
}

bool word_ladder(const word_map& words, const string& from, const string& to) {
 //Если возможно, выврдит метаграмму для слов from и to по словарю words
 auto w = words.find(from.size());
 if (w != words.end()) {
  auto poss = w->second;
  vector<vector<string>> queue{ {from} };
  while (!queue.empty()) {
   auto curr = queue.front();
   queue.erase(queue.begin());
   vector<string> next;
   for (const string& str : poss) {
    if (one_away(str, curr.back()))
     next.push_back(str);
   }
   if (contains(next, to)) {
    curr.push_back(to);
    cout << join(curr.begin(), curr.end(), " -> ") << endl;
    return true;
   }
   poss.erase(remove_if(poss.begin(), poss.end(), [&next](const string& str) {
     return contains(next, str);
    }),
    poss.end());
   for (const auto& str : next) {
    vector<string> temp(curr);
    temp.push_back(str);
    queue.push_back(move(temp));
   }
  }
 }
 cout << "Не могу преобразовать \"" << from << "\" в \"" << to << "\"" << endl;
 return false;
}

int main() {
 SetConsoleCP(1251); SetConsoleOutputCP(1251);
 word_map words;
 const char * filename = "words.txt"; //Имя файла в текущей папке проекта
 ifstream in(filename);
 if (!in) {
  cerr << "Не могу открыть " << filename << endl;
  return EXIT_FAILURE;
 }
 string word;
 while (getline(in, word)) words[word.size()].push_back(word);
 
 word_ladder(words, "волк", "коза"); //+
 word_ladder(words, "речь", "тост"); //+
 word_ladder(words, "кот", "ток"); //+
 word_ladder(words, "абырвалг", "главрыба"); //-
 
 return EXIT_SUCCESS;
}

 Скачать файл words.txt в архиве .zip (347 Кб)

Файл words.txt в папке проекта

18.08.2021, 09:15 [994 просмотра]