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
-OR-
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:
1)
Any of the four chains can be placed in any of the super molecule's four, general, horizontal or vertical slots, as in the illustrations above.
2)
If a chain is placed in one of the two horizontal slots, it must keep the same left-to-right orientation it had in the original chain listing. That is, it can't be flipped end-for-end.
3)
If a chain is placed in one of the two vertical slots, its left-to-right orientation in the original chain listing must match its top-to-bottom orientation in the slot. It can't be flipped end-for-end from this orientation.
4)
The enclosed rectangular region at the center of the super molecule must have as large an area as possible, and the area cannot be zero. (The large-area constraint arises from a fuel-volatility criterion for the arrangement. The non-zero area constraint arises because neither the vertically nor the horizontally oriented chains can lie immediately next to each other without producing side-effects we're not considering.)
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).
5)
The fore and aft tails of each chain extending beyond the super molecule's central interlocked rectangle must have a minimum length of one chain element. That is, none of the four original chains can have either its first or its last element as part of the interlocking-rectangle boundary.