Problem G
Boxed Letters
The New York Times publishes a puzzle called “Boxed Letters” for puzzle enthusiasts. In this puzzle, $12$ letters are shown along the $4$ sides of a box. The task is to find words that are spelled when these letters are connected, subject to the following rules:
-
You may start the first word with any of the letters
-
Consecutive letters in one word cannot be from the same side
-
Words must be at least 3 letters long
-
Letters can be reused
-
The last letter of a word becomes the first letter of the next word, e.g. THY > YES > SINCE
-
All letters must be used
-
Use as few words as possible
After trying the puzzle for a while, you remember that there are dictionaries that should make this task simple.
Can you write a program that solves a Boxed Letters puzzle given a dictionary of words?
Input
The input consists of a single test case, which starts with an integer $n$ ($1 \le n \le 72\, 000$), the size of the dictionary. This line is followed by $n$ lines, each containing a dictionary word of $l$ uppercase English letters ($3 \le l \le 22$). All dictionary words are distinct. The next $5$ lines contains the letters around the box in compressed form. The first line contains the top row, the last line the bottom row. The first character on each of the $3$ lines in between corresponds to the box’s left side, the second character corresponds to the box’s right side. All $12$ characters are distinct uppercase English letters.
Output
Output a word list that solves this puzzle, in the order in which the words would be entered into the puzzle. Place each word on a separate line. If there are multiple word lists that satisfy the conditions, you may output any of them. You are guaranteed that a solution exists.
| Sample Input 1 | Sample Output 1 |
|---|---|
22 DATUM TRUMAN STAINS INSTANTS TACITUS LINUS TANTRUMS MCADAM ILLICIT ALUM CARINA DRUMSTICKS BACILLI SUBURBAN TIC SALSA TALIBAN ATTAIN LUNATIC ASIATICS MANDARIN RUMINANTS R I N M D C S A B U T K |
DRUMSTICKS SUBURBAN |
