In this abstraction from a molecular engineering problem associated with developing a synthetic fuel, we are given four, equal-length, molecular chains that are to form a super molecule. In the simplified two-dimensional model used here, the super molecule is formed as an interlocking rectangular arrangement of the four given molecular chain strands. The interlocking feature is the sharing of a common molecule between pairs of chains.
To illustrate, suppose we have the four, length-twelve, molecular chains:
O I M D I H E I A F N L C H J D B J M H P J K D L C B J O J G I E K B O K A I N L H L O L B E J
These can be placed in the interlocking arrangements:
O L I C M B C H J D B J M H P J K D I O H J E G I I A E F K K A I N L H L O L B E J L O
O C I H M J D D L C B J O J G I E K B O H J E M K A I N L H L O L B E J A P F J N K L D
In this problem, we have some constraints on the arrangements being sought:
The area is measured as the count of vacant character positions within the enclosed rectangle of the super molecule. The area counts of the two super molecules illustrated above are thirty (30) and four (4).
The input consists of a series of data sets. Each data set consists of four molecular chains of 12 fixed elements each. These 12 elements are given as contiguous capital letters. The molecule designators within the chains will be restricted to the sixteen letters, A...P. The first letter of a chain will appear as the first character on an input line.
The first molecule designator within the first chain of a data set will be the letter "Q" to indicate the end of data.
A line with a single integer is to be emitted for each input data set encountered. This integer is the maximum area enclosed by any legitimate arrangement of the four chains.
Use the output value zero (0) to indicate that no legitimate super molecule could be formed for a givendata set.
The first digit of an output value should be the first character on a line.
CDBADCBBEFEF DACCBADAFEAB EFBDCAADBDCD ABCDABCDABCD DACCBADAFEAB EFBDCAADBDCD ABCDABCDABCD CDBADCBBEFEF ABABABABABAB CDCDCDCDCDCD EEEEEEEEEEEE FFFFFFFFFFFF ABAAAAAAAABA CBCCCCCCCCBC DBDDDDDDDDBD EBEEEEEEEEBE ABBBBBBBBBBA ACCCCCCCCCCA ADDDDDDDDDDA AEEEEEEEEEEA BBBABBBABBBB CCACCCACCCCC DDDDADDADDDD EEAEEAEEEEEE Q
48 48 0 64 0 6