This is a Computer Science Algorithms question. You are given a set of ABC block

Question

This is a Computer Science Algorithms question.

You are given a set of ABC blocks for kids (like the one shown below) and a word. On each face of each block a letter is written (any one from English alphabet). You need to find out, is it possible to form a given word from the blocks? For example, suppose that you have 5 blocks: B1: MXTUAS B_2: O Q A T G E B3: RE WMN A B4: M B D F A C B5:I J K G D E (Here for each block the list of letters written on its faces is given) You can write the word "MAMA" using this set of blocks: M A M A B3 B_2 B4 B1 At the same time, you cannot form the word "SUN". You have all 3 letters "S", "U" and "N" on the blocks, but the letters "S" and "U" are on the same block B1, and you cannot use it twice (or more) for one word. What is this algorithmic problem? Is it possible to solve it in a polynomial time? it is a graph problem.

Explanation / Answer

Algorithm :

Step 1 : Input the data in a form of 2 dimensional matrix.

Step 2 : Store the word to be found in list x[].variable = 0;

Step 3 : Create a function, that returns true or false, upon checking if marker (i,j) is x[ variable ]

Step 4 : Create a function , that returns the no of matches and positions in a list, upon checking if the value of (i,j) | (i+1,j) | (i-1,j) | (i,j+1) | (i,j-1) | (i+1,j+1) | (i+1,j-1) | (i-1,j-1) | (i-1,j+1) is equal to x[ variable ].

Step 5 : Now for every position in the list from step 4, check with the same function if the neighboring values are equal to x [ variable + 1 ]

Step 6 : Similary, repeat step 4 for ” variable ” no of times to get to the correct word.

Step 7 : The variable in the list would give the position of the last word alone but the path of the positions has to be saved using some temporary variable.

To minimize memory usage, the application creates a single instance of the Word Application interface (wordApp) to call the CheckSpelling(string theWord) method for each individual permutation. When complete or when an exception occurs, the wordApp object is destroyed by calling the Quit() method. WhenwordApp is processing permutations, you will note an instance of WINWORD.EXE running in Task Manager’s Processes tab.

The Descrambler Process

The recursive algorithm’s methods are very fast, while passing the results to the Word object for spell checking can be time consuming. A progress bar at the bottom of the UI is updated as each permutation is spell-checked by Word. It is important not to change windows while the application is running.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.