Molecules Problem

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.

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace MaxArea
{
    class Program
    {
        public class myReverserClass : IComparer
        {
            int IComparer.Compare(Object x, Object y)
            {
                return ((new CaseInsensitiveComparer()).Compare(y, x));
            }
        }
        static void Main(string[] args)
        {
            string[] str = new string[4];
            str[0] = "DACCBADAFEAB";//Vertical Right
            str[1] = "EFBDCAADBDCD";//Vertical Left
            str[2] = "ABCDABCDABCD";//Horizontal Up
            str[3] = "CDBADCBBEFEF";//Horizontal Down
            int maxArea = 0;
            int[] pointer = new int[4];
            //Pointer array initialization
            for (int i = 0; i < pointer.Length; i++)
            {
                pointer[i] = i;
            }
            //Pointer increment loop
            pointer[pointer.Length – 1]–;
            do
            {
                int i = pointer.Length – 1;
            label1:
                pointer[i]++;
                if (pointer[i] == pointer.Length && i != 0)
                {
                    pointer[i] = 0;
                    i–;
                    goto label1;
                }
                else if (pointer[0] == pointer.Length)
                {
                    break;
                }
                else
                {
                    bool valid = true;
                    //Check for valid pointer values
                    int[] check = new int[pointer.Length];
                    for (int j = 0; j < pointer.Length; j++)
                    {
                        check[pointer[j]]++;
                        if (check[pointer[j]] > 1)
                        {
                            valid = false;
                            break;
                        }
                    }
                    if (valid)
                    {
                        int tempArea = MaxArea(str[pointer[0]], str[pointer[1]], str[pointer[2]], str[pointer[3]]);
                        if(tempArea > maxArea)
                        {
                            maxArea = tempArea;
                        }
                    }
                }
            } while (pointer[0] != pointer.Length);
            Console.WriteLine("Max Area = " + maxArea);
        }
        public static int MaxCommonLength(char ch1, char ch2, string str1, char chr1, char chr2, string str2)
        {
            ArrayList allLength1 = new ArrayList();
            ArrayList allLength2 = new ArrayList();
            for (int i = 1; i < str1.Length – 2; i++)
            {
                for (int j = i + 1; j < str1.Length – 1; j++)
                {
                    if (str1.Substring(i, 1) == ch1.ToString() && str1.Substring(j, 1) == ch2.ToString())
                    {
                        allLength1.Add((j – i));
                    }
                }
            }
            for (int i = 1; i < str2.Length – 2; i++)
            {
                for (int j = i + 1; j < str2.Length – 1; j++)
                {
                    if (str2.Substring(i, 1) == chr1.ToString() && str2.Substring(j, 1) == chr2.ToString())
                    {
                        allLength2.Add((j – i));
                    }
                }
            }
            if (allLength1.Count == 0 || allLength2.Count == 0)
            {
                return (0);
            }
            else
            {
                IComparer myComparer = new myReverserClass();
                allLength1.Sort(myComparer);
                allLength2.Sort(myComparer);
                for (int i = 0; i < allLength1.Count; i++)
                {
                    for (int j = 0; j < allLength2.Count; j++)
                    {
                        if (allLength1[i].ToString() == allLength2[j].ToString())
                        {
                            return (int.Parse(allLength1[i].ToString()));
                        }
                    }
                }
                return (0);
            }
        }
        public static int MaxArea(string str1, string str2, string str3, string str4)
        {
            int maxArea = 0;
            for (int k = 0; k < str1.Length – 4; k++)
            {
                for (int i = 1; i < str1.Length – 3 – k; i++)
                {
                    for (int j = (i + 2); j < str1.Length – 1 – k; j++)
                    {
                        if (k != 0)
                        {
                            //Console.WriteLine(str2.Substring(i + k, 1) + " " + str1.Substring(i, 1) + " , " + str2.Substring(j + k, 1) + " " + str1.Substring(j, 1));
                            int temp = MaxCommonLength(char.Parse(str2.Substring(i + k, 1)), char.Parse(str1.Substring(i, 1)), str3, char.Parse(str2.Substring(j + k, 1)), char.Parse(str1.Substring(j, 1)), str4);
                            if (temp – 1 > 0)
                            {
                                int tempArea = (temp – 1) * (j – i – 1);
                                if (tempArea > maxArea)
                                {
                                    maxArea = tempArea;
                                }
                            }
                            //Console.WriteLine(str2.Substring(i, 1) + " " + str1.Substring(i + k, 1) + " , " + str2.Substring(j, 1) + " " + str1.Substring(j + k, 1));
                            temp = MaxCommonLength(char.Parse(str2.Substring(i, 1)), char.Parse(str1.Substring(i + k, 1)), str3, char.Parse(str2.Substring(j, 1)), char.Parse(str1.Substring(j + k, 1)), str4);
                            if (temp – 1 > 0)
                            {
                                int tempArea = (temp – 1) * (j – i – 1);
                                if (tempArea > maxArea)
                                {
                                    maxArea = tempArea;
                                }
                            }
                        }
                        else
                        {
                            //Console.WriteLine(str2.Substring(i + k, 1) + " " + str1.Substring(i, 1) + " , " + str2.Substring(j + k, 1) + " " + str1.Substring(j, 1));
                            int temp = MaxCommonLength(char.Parse(str2.Substring(i + k, 1)), char.Parse(str1.Substring(i, 1)), str3, char.Parse(str2.Substring(j + k, 1)), char.Parse(str1.Substring(j, 1)), str4);
                            if (temp – 1 > 0)
                            {
                                int tempArea = (temp – 1) * (j – i – 1);
                                if (tempArea > maxArea)
                                {
                                    maxArea = tempArea;
                                }
                            }
                        }
                    }
                }
            }
            return (maxArea);
        }
    }
}

Max Area = 48
Press any key to continue . . .

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s