TopCoder problem "WordGrid" used in TCO05 Semi 1 (Division I Level One)



Problem Statement

    

You have an old "word search" puzzle which consists of a rectangular grid of letters in which several words are hidden. Each word may begin anywhere in the puzzle, and may be oriented in any straight line horizontally, vertically, or diagonally (forwards or backwards oriented). The puzzle is so old that some of the letters have been washed out and you can not recognize them anymore. Your task is to recover the washed out letters so that the puzzle is solvable - i.e., all given words can be found in the letter grid.

You will be given grid, representing the letter grid, with each washed out letter replaced by a period ('.'). Further, you will be given words, the list of words that can be found in the grid. You are to return the letter grid with the washed out letters replaced by the original letters in those positions. There will be one unique way to replace the washed out letters such that all the words can be found in the grid.

 

Definition

    
Class:WordGrid
Method:fillSpaces
Parameters:String[], String[]
Returns:String[]
Method signature:String[] fillSpaces(String[] grid, String[] words)
(be sure your method is public)
    
 

Notes

-Although the solution to this problem will be unique, the solution of the resulting "word search" puzzle need not be unique - i.e., a word can be located in more than one position in the final grid (see example 1).
 

Constraints

-grid will contain between 1 and 50 elements, inclusive.
-Each element of grid will contain between 1 and 50 characters, inclusive.
-All elements of grid will have the same number of characters.
-All characters of all elements of grid will be uppercase letters ('A'-'Z') or periods ('.').
-grid will contain no more than 3 periods.
-words will have between 1 and 50 elements, inclusive.
-Each element of words will contain between 1 and 50 characters, inclusive.
-Each element of words will be unique.
-All characters of all elements of words will be uppercase letters ('A'-'Z').
-There will be one unique way to replace the washed out letters such that all the words can be found in the grid.
 

Examples

0)
    
{"ABCD",
 "E..H",
 "I.KL",
 "MNOP"}
{"AFK", "DGJM"}
Returns: {"ABCD", "EFGH", "IJKL", "MNOP" }
1)
    
{"AAAAA",
 "ABBBA",
 "AB.BA",
 "ABBBA",
 "AAAAA"}
{"ABC"}
Returns: {"AAAAA", "ABBBA", "ABCBA", "ABBBA", "AAAAA" }
We must fill the center square with a 'C' in order to be able to find "ABC" in the grid. Note that in that case "ABC" can be located at 8 different positions in the grid.
2)
    
{"AAAAAAAAAAAAAAAAAAAAAAAA",
 "AAAAAAAAAFAAAGAAAAAAAAAA",
 "AAAAAAAAAA...AAAAAAAAAAA",
 "AAAAAAAAAAAAAAAAAAAAAAAA",
 "AAAAAAAAAAAAAAAAAAAAAAAA",
 "AAAAAAAAAAAAAAAAAAAAAAAA"}
{"B", "C", "D", "AB", "AC", "AD", "BA", "CA", "DA",
 "AAB", "AAC", "AAD", "BAA", "CAA", "DAA", "AAAB",
 "AAAC", "AAAD", "BAAA", "CAAA", "DAAA", "AAAAB",
 "BAAAA", "AAAAAB", "BAAAAA", "AAAAAAB", "BAAAAAA",
 "AAAAAAAB", "BAAAAAAA", "AAAAAAAAB", "BAAAAAAAA",
 "AAAAAAAAAB", "BAAAAAAAAA", "AAAAAAAAAAB", "BAAAAAAAAAA",
 "AAAAD", "DAAAA", "AAAAAD", "DAAAAA", "AAAAAAD",
 "DAAAAAA", "AAAAAAAD", "DAAAAAAA", "AAAAAAAAD",
 "DAAAAAAAA", "AAAAAAAAAD", "DAAAAAAAAA", "AAAAAAAAAAD",
 "DAAAAAAAAAA", "AAAAAAAAAAAD"}
Returns: 
{"AAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAFAAAGAAAAAAAAAA",
"AAAAAAAAAABCDAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAA",
"AAAAAAAAAAAAAAAAAAAAAAAA" }
Beware of timeout!
3)
    
{"ABCD",
 "EFGH"}
{"AF", "HD"}
Returns: {"ABCD", "EFGH" }
Nothing to do here (all letters of the grid are known in advance, so the same grid is returned).

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4833

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8098&pm=4833

Writer:

gepa

Testers:

PabloGilberto , lbackstrom , Yarin , Olexiy

Problem categories:

Brute Force