You are given a set of ABC cubes for kids (like the one shown below) and a word. On each side of each cube a letter is written.
You need to find out, whether it it possible to form a given word by the cubes.
For example, suppose that you have 5 cubes:
B1: M X T U A S
B2: O Q A T G E
B3: R E W M N A
B4: M B D F A C
B5: I J K G D E
(here for each cube the list of letters written on its sides is given) You can write the word “MAMA” using cubes B3, B2, B4, B1:
At the same time, you cannot form the word “SUN”. You have all 3 letters “S”, “U” and “N” on the cubes, but the letters “S” and “U” are on the same cube B1, and you cannot use it twice.
Implement an algorithm to solve this problem on Java or Python. Your submission to iCollege should contain the following:
1) Files with your source code
2) Doc/pdf file with the short verbal explanation of your algorithm.
Your program should read an input from a text file and write an output to another text file.
The input file format:
5
MXTUAS
OQATGE
REWMNA
MBDFAC
IJKGDE
MAMA
The first line contains a number of cubes n. Each of the following n lines contains a string of 6 characters written on the sides of each cube. The last line is the word to be formed.
The output format:
3 2 4 1
The output file contains the list of cubes forming the input word separated by spaces. If the word cannot be formed, the output file should contain a single integer -1.
Hint: what algorithm that we studied can be applied here?
