Horizontal and Vertical Puzzle
InterviewTime limit1sMemory limit128 MB
Given 6 three-letter words, choose 3 as rows and 3 as columns so the grid's columns also match the remaining words, outputting the lexicographically smallest valid arrangement.
- Level
Medium4 of 10
- Topics
- Brute force, String, Combinatorics
- Solved
- No attempts yet
Problem
We want to make a 3x3 horizontal-and-vertical word puzzle like the one below.
Across clues
- A device used to cool a PC
- Solid water
- To obtain
Down clues
- A small, soft, sweet fruit
- A strong playing card
- A fisherman's tool
You are given 6 words. Use 3 of them as the rows and the other 3 as the columns to form a 3x3 puzzle. Each column, read from top to bottom, must also be one of the given words. Every word may be used only as many times as it appears in the input.
Input
The input contains 6 lines. Each line contains one 3-letter word consisting of uppercase English letters. The words are sorted in lexicographic order, and the same word may appear more than once.
Output
If it is impossible to use all 6 words to form a 3x3 puzzle, print 0. Otherwise, print the 3 row words of the puzzle from top to bottom, one per line.
If there is more than one possible puzzle, print the one whose 9-letter string formed by concatenating the three output rows is lexicographically smallest.