Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I was not necessarily looking for a backtracking solution. It just struck to me that back tracking can be used, but the solution with that is a bit complicated. However we can use <strong>branch and bound and pruning to cut short the brute force technique.</strong> </p> <p>Instead of searching for all possible combinations in the matrix, first we will select one string as the topmost row. Using the first character we find a <strong>suitable contender</strong> for the 1st column. Now using the 2 and 3 characters of the column string, we will find suitable words that can be fitted in the second and third row.</p> <p>To efficiently find words beginning with a particular character we will use <strong>radix sort</strong> so that all words beginning with a particular character are stored in the same list. This when we have chosen the the second and third row of the matrix, we have a complete matrix.\</p> <p>We will check whether the matrix is valid, by checking the 2nd and 3rd column and the diagonals form words that fall in the dictionary.</p> <p>As and when we find that the matrix is valid we can stop. This helps in cutting down some of the possible combinations. However I feel this can be further optimized by considering another row or column, but then it would be a bit complicated. I am posting a working code below.</p> <p>Please don't mind the naming of the functions, since I am an amateur coder, I generally do not give very appropriate names and some part of the code is hard coded for 3 letter words.</p> <pre><code>#include&lt;iostream&gt; #include&lt;string&gt; #include&lt;algorithm&gt; #include&lt;fstream&gt; #include&lt;vector&gt; #include&lt;list&gt; #include&lt;set&gt; using namespace std; // This will contain the list of the words read from the // input file list&lt;string&gt; 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&lt;string&gt; strings = words[(int)(in[0]-'a')]; list&lt;string&gt;:: 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&lt;string&gt; findAll(int i) { // It will contain the possible strings list&lt;string&gt; possible; list&lt;string&gt;:: 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&lt;string&gt; 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&lt;string&gt; col1 = findAll((int)(first-'a')); list&lt;string&gt;::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&lt;string&gt; secondRow = findAll((int)(second-'a')); list&lt;string&gt; thirdRow = findAll((int)(third-'a')); // Iterators list&lt;string&gt;::iterator it1; list&lt;string&gt;::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 &gt;&gt; word; if(word[0] &gt;= 'a' &amp;&amp; word[0] &lt;= 'z') { int index1 = word[0]-'a'; words[index1].push_back(word); } } } else cout&lt;&lt;"The file could not be opened"&lt;&lt;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 &lt; 26;i++) { it = words[i].begin(); while(it!=words[i].end()) { if(findMatrix(*it)) { // Output the matrix for(int j=0;j&lt;3;j++) cout&lt;&lt;out[j]&lt;&lt;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&lt;&lt;"Matrix does not exist"&lt;&lt;endl; system("pause"); return 0; } </code></pre> <p>I have tested the code on a small set of strings and it worked fine.</p>
    singulars
    1. This table or related slice is empty.
    1. POArranging 3 letter words in a 2D matrix such that each row, column and diagonal forms a word
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USSachin
    1. USSachin
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload