Ищем метаграммы для русских существительных
Метаграммой (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 [995 просмотров]