Блог

Вам предоставляется словарь из 3 буквенных слов, и вам нужно найти матрицу размером 3×3, чтобы каждая строка, столбец и диагональ образовывали слово в словаре. Слова в словаре отсортированы, и вы можете предположить O (1) время для извлечения слова из словаря.

Это было задано в качестве вопроса для интервью в Facebook.

Мой подход заключался бы в том, чтобы сначала отфильтровать словарь, чтобы создать два новых словаря: первый содержит все однобуквенные префиксы слов (которых, вероятно, 26), а второй содержит все двухбуквенные префиксы слов (которых меньше 26 ^ 2, поскольку ни одно слово не начинается с BB,например).

1. Выберите слово из словаря, назовите его X . Это будет первая строка матрицы.

2. Проверьте X1 X2 , X3 все ли допустимые однобуквенные префиксы, используя этот удобный список, который вы составили. Если это так, перейдите к шагу 3; в противном случае вернитесь к шагу 1.

3. Выберите слово из словаря, назовите его Y . Это будет вторая строка матрицы.

4. Проверьте X1 Y1 , X2 Y2 , X3 Y3 все допустимые двухбуквенные префиксы, используя этот удобный список, который вы составили. Если это так, перейдите к шагу 5; в противном случае вернитесь к шагу 3. Если это было последнее слово в словаре, то вернитесь к шагу 1.

5. Выберите слово из словаря, назовите его Z . Это будет третья строка матрицы.

6. Убедитесь, что 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-полной, это может быть вашим лучшим вариантом.

(*) Исходная задача с кроссвордом не имеет диагонального условия, которое имеет эта задача, и, конечно, является более общей: матрица nxm, а не только 3×3. Хотя проблемы схожи, сокращение не приходит мне в голову, и я буду рад его увидеть, если оно существует.

• Вы находите каждый уникальный набор из 3 слов.
• Вы получаете все 6 возможных матриц для этих 3 слов.
• Вы выполняете проверку словаря на наличие 5 слов, которые могут быть созданы из этих матриц (3 столбца и 2 диагонали).

Немного 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 символа строки столбца, мы найдем подходящие слова, которые можно поместить во вторую и третью строки.

Для эффективного поиска слов, начинающихся с определенного символа, мы будем использовать сортировку по основанию, чтобы все слова, начинающиеся с определенного символа, хранились в одном списке. Это когда мы выбрали вторую и третью строки матрицы, у нас есть полная матрица.

Мы проверим, является ли матрица допустимой, проверив 2-й и 3-й столбцы, а диагонали образуют слова, которые попадают в словарь.

Как и когда мы обнаружим, что матрица действительна, мы можем остановиться. Это помогает сократить некоторые из возможных комбинаций. Однако я чувствую, что это можно дополнительно оптимизировать, рассмотрев другую строку или столбец, но тогда это было бы немного сложнее. Я публикую рабочий код ниже.

Пожалуйста, не обращайте внимания на названия функций, поскольку я программист-любитель, я обычно даю не очень подходящие имена, а некоторая часть кода жестко запрограммирована для 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 resu<

                            // 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' amp;amp; 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;
}
  

Я протестировал код на небольшом наборе строк, и он работал нормально.