Вам предоставляется словарь из 3 буквенных слов и должен найти матрицу 3x3, так что каждая строка, столбец и диагональ образуют слово в словаре. Слова в словаре сортируются, и вы можете предположить время O (1) для извлечения слова из словаря.
Это задан как вопрос интервью с Facebook.
Мой подход заключается в том, чтобы сначала отфильтровать словарь, чтобы создать два новых словаря: первый содержит все однобуквенные префиксы слов (из которых, вероятно, 26), а второй содержит все двузначные префиксы слов (из которых меньше, чем 26 ^ 2, поскольку, например, слово не начинается с BB).
Выберите слово из словаря, назовите его X. Это будет первая строка матрицы.
Убедитесь, что X1, X2, X3 - все допустимые однобуквенные префиксы, используя тот удобный список, который вы сделали. Если да, переходите к шагу 3; в противном случае вернитесь к шагу 1.
Выберите слово из словаря, назовите его Y. Это будет вторая строка матрицы.
Убедитесь, что X1 Y1, X2 Y2, X3 Y3 - все допустимые двухбуквенные префиксы, используя тот удобный список, который вы сделали. Если да, переходите к шагу 5; в противном случае вернемся к шагу 3. Если это последнее слово в словаре, перейдите к шагу 1.
Выберите слово из словаря, назовите его Z. Это будет третья строка матрицы.
Убедитесь, что X1 Y1 Z1, X2 Y2 Z2, X3 Y3 Z3 - все слова в словаре. Если они, поздравляю, ты это сделал! В противном случае вернитесь к шагу 5. Если это последнее слово в словаре, перейдите к шагу 3.
Я закодировал это в Maple, и он работает достаточно хорошо. Я оставил его работать, чтобы найти все такие матрицы, и оказалось, что их достаточно, чтобы свернуть Maple из-за переполнения памяти.
Ваш комментарий предполагает, что вы также ищете решение обратного отслеживания, которое будет неэффективным, но решает это. Псевдо-код:
solve(dictionary,matrix):
if matrix is full:
if validate(dictionary,matrix) == true:
return true
else:
return false
for each word in dictionary:
dictionary -= word
matrix.add(word)
if solve(dictionary,matrix) == true:
return true
else:
dictionary += word
matrix.removeLast()
return false //no solution for this matrix.
В приведенном выше псевдокоде matrix.add() добавляет данное слово в первую незанятую строку. matrix.remove() удаляет последнюю занятую строку, а validate() проверяет, является ли решение законным.
Активация: solve(dictionary,empty_matrix), если алгоритм дает true, есть решение, и входная матрица будет содержать его, иначе он будет давать false.
Вышеупомянутый псевдокод работает в экспоненциальном времени! это очень неэффективно. Однако, поскольку эта проблема напоминает (*) проблему кроссворда, которая NP-Complete, это может быть ваш лучший снимок.
(*) Исходная проблема кроссвордов не имеет диагонального условия, что эта проблема имеет и, конечно, более общая: nxm-матрица, а не только 3x3. Несмотря на то, что проблемы схожи, сокращение не появляется мне в голову, и я буду рад увидеть его, если он существует.
Некоторые иллюстрации JavaScript.
//setup a test dictionary
var dict = [
"MAD",
"FAD",
"CAT",
"ADD",
"DOG",
"MOD",
"FAM",
"ADA",
"DDD",
"FDD"
];
for(var i=0; i<dict.length; i++)
dict[dict[i]]=true;
// functions
function find(dict) {
for(var x=0; x<dict.length; x++) {
for(var y=x+1; y<dict.length; y++) {
for(var z=y+1; z<dict.length; z++) {
var a=dict[x];
var b=dict[y];
var c=dict[z];
if(valid(dict,a,b,c)) return [a,b,c];
if(valid(dict,a,c,b)) return [a,c,b];
if(valid(dict,b,a,c)) return [b,a,c];
if(valid(dict,b,c,a)) return [b,c,a];
if(valid(dict,c,a,b)) return [c,a,b];
if(valid(dict,c,b,a)) return [c,b,a];
}
}
}
return null;
}
function valid(dict, row1, row2, row3) {
var words = [];
words.push(row1.charAt(0)+row2.charAt(0)+row3.charAt(0));
words.push(row1.charAt(1)+row2.charAt(1)+row3.charAt(1));
words.push(row1.charAt(2)+row2.charAt(2)+row3.charAt(2));
words.push(row1.charAt(0)+row2.charAt(1)+row3.charAt(2));
words.push(row3.charAt(0)+row2.charAt(1)+row1.charAt(2));
for(var x=0; x<words.length; x++)
if(dict[words[x]] == null) return false;
return true;
}
//test
find(dict);
Я не обязательно искал решение обратной связи. Мне просто поразило, что можно использовать обратное отслеживание, но решение с этим немного сложно. Однако мы можем использовать ветвь, связать и обрезать, чтобы прервать технику грубой силы.
Вместо поиска всех возможных комбинаций в матрице сначала мы выберем одну строку в качестве самой верхней строки. Используя первый символ, мы найдем подходящего соперника для 1-го столбца. Теперь, используя 2 и 3 символа строки столбца, мы найдем подходящие слова, которые могут быть установлены во второй и третьей строках.
Чтобы эффективно находить слова, начинающиеся с определенного символа, мы будем использовать сортировку radix, чтобы все слова, начинающиеся с определенного символа, были сохранены в том же списке. Это, когда мы выбрали вторую и третью строки матрицы, имеем полную матрицу. \
Мы проверим, действительна ли матрица, проверяя 2-й и 3-й столбцы, а диагонали образуют слова, которые попадают в словарь.
Как и когда мы находим, что матрица верна, мы можем остановиться. Это помогает сократить некоторые из возможных комбинаций. Однако я считаю, что это можно оптимизировать, рассмотрев еще одну строку или столбец, но тогда это будет немного сложнее. Я размещаю рабочий код ниже.
Пожалуйста, не обращайте внимание на назначение функций, так как я любительский кодер, я вообще не даю очень подходящих имен, а часть кода жестко закодирована для трех буквенных слов.
#include<iostream>
#include<string>
#include<algorithm>
#include<fstream>
#include<vector>
#include<list>
#include<set>
using namespace std;
// This will contain the list of the words read from the
// input file
list<string> words[26];
// This will contain the output matrix
string out[3];
// This function finds whether the string exits
// in the given dictionary, it searches based on the
// first character of the string
bool findString(string in)
{
list<string> strings = words[(int)(in[0]-'a')];
list<string>:: iterator p;
p = find(strings.begin(),strings.end(),in);
if(p!=strings.end())
return true;
}
// Since we have already chosen valid strings for all the rows
// and first column we just need to check the diagnol and the
// 2 and 3rd column
bool checkMatrix()
{
// Diagnol 1
string d1;
d1.push_back(out[0][0]);
d1.push_back(out[1][1]);
d1.push_back(out[2][2]);
if(!(findString(d1)))
return false;
// Diagnol 2
string d2;
d2.push_back(out[0][0]);
d2.push_back(out[1][1]);
d2.push_back(out[2][2]);
if(!(findString(d2)))
return false;
// Column 2
string c2;
c2.push_back(out[0][1]);
c2.push_back(out[1][1]);
c2.push_back(out[2][1]);
if(!(findString(c2)))
return false;
// Column 3
string c3;
c3.push_back(out[0][2]);
c3.push_back(out[1][2]);
c3.push_back(out[2][2]);
if(!(findString(c3)))
return false;
else
return true;
// If all match then return true
}
// It finds all the strings begining with a particular character
list<string> findAll(int i)
{
// It will contain the possible strings
list<string> possible;
list<string>:: iterator it;
it = words[i].begin();
while(it!=words[i].end())
{
possible.push_back(*it);
it++;
}
return possible;
}
// It is the function which is called on each string in the dictionary
bool findMatrix(string in)
{
// contains the current set of strings
set<string> current;
// set the first row as the input string
out[0]=in;
current.insert(in);
// find out the character for the column
char first = out[0][0];
// find possible strings for the column
list<string> col1 = findAll((int)(first-'a'));
list<string>::iterator it;
for(it = col1.begin();it!=col1.end();it++)
{
// If this string is not in the current set
if(current.find(*it) == current.end())
{
// Insert the string in the set of current strings
current.insert(*it);
// The characters for second and third rows
char second = (*it)[1];
char third = (*it)[2];
// find the possible row contenders using the column string
list<string> secondRow = findAll((int)(second-'a'));
list<string> thirdRow = findAll((int)(third-'a'));
// Iterators
list<string>::iterator it1;
list<string>::iterator it2;
for(it1= secondRow.begin();it1!=secondRow.end();it1++)
{
// If this string is not in the current set
if(current.find(*it1) == current.end())
{
// Use it as the string for row 2 and insert in the current set
current.insert(*it1);
for(it2 = thirdRow.begin();it2!=thirdRow.end();it2++)
{
// If this string is not in the current set
if(current.find(*it2) == current.end())
{
// Insert it in the current set and use it as Row 3
current.insert(*it2);
out[1]=*it1;
out[2]=*it2;
// Check ifthe matrix is a valid matrix
bool result = checkMatrix();
// if yes the return true
if(result == true)
return result;
// If not then remove the row 3 string from current set
current.erase(*it2);
}
}
// Remove the row 2 string from current set
current.erase(*it1);
}
}
// Remove the row 1 string from current set
current.erase(*it);
}
}
// If we come out of these 3 loops then it means there was no
// possible match for this string
return false;
}
int main()
{
const char* file = "input.txt";
ifstream inFile(file);
string word;
// Read the words and store them in array of lists
// Basically radix sort them based on their first character
// so all the words with 'a' appear in the same list
// i.e. words[0]
if(inFile.is_open())
{
while(inFile.good())
{
inFile >> word;
if(word[0] >= 'a' && word[0] <= 'z')
{
int index1 = word[0]-'a';
words[index1].push_back(word);
}
}
}
else
cout<<"The file could not be opened"<<endl;
// Call the findMatrix function for each string in the list and
// stop when a true value is returned
int i;
for(i=0;i < 26;i++)
{
it = words[i].begin();
while(it!=words[i].end())
{
if(findMatrix(*it))
{
// Output the matrix
for(int j=0;j<3;j++)
cout<<out[j]<<endl;
// break out of both the loops
i=27;
break;
}
it++;
}
}
// If i ==26 then the loop ran the whole time and no break was
// called which means no match was found
if(i==26)
cout<<"Matrix does not exist"<<endl;
system("pause");
return 0;
}
Я проверил код на небольшом наборе строк, и он отлично работал.