Maximum number of rings

There are a number of rings lying on the floor. Any two rings can intersect at two points, may not intersect at all, or touch each other at a single point. Two rings can be lifted simultaneously if and only if they intersect at two points. A bunch of rings mutually satisfying this condition can be lifted at once. You have to find the maximum number of rings that can be lifted in a single attempt. The rings are specified by their x and y coordinates on the floor and their radius, the specifications of a ring being in a single row of a matrix.

 

using System;

using System.Collections.Generic;

using System.Collections;

using System.Linq;

using System.Text;

 

namespace ConsoleApplication2

{

    class Program

    {

        static void Main(string[] args)

        {

            //Given ring matrix

            double[,] ringMatrix = {

                                       {0.0, 0.0, 1.0},

                                       {1.0, 0.0, 1.0},

                                       {2.0, 0.0, 1.0},

                                       {-1.0, 0.0, 1.0}

                                   };

            //Initializing intersection matrix

            int[,] intersectionMatrix = new int[ringMatrix.GetLength(0), ringMatrix.GetLength(0)];

            for (int i = 0; i < intersectionMatrix.GetLength(0); i++)

            {

                for (int j = 0; j < intersectionMatrix.GetLength(0); j++)

                {

                    if (i == j)

                    {

                        intersectionMatrix[i, j] = 1;

                    }

                    else if (Math.Sqrt(Math.Pow((ringMatrix[i, 0] – ringMatrix[j, 0]), 2) + Math.Pow((ringMatrix[i, 1] – ringMatrix[j, 1]), 2)) < (ringMatrix[i, 2] + ringMatrix[j, 2]))

                    {

                        if (ringMatrix[i, 0] == ringMatrix[j, 0] && ringMatrix[i, 1] == ringMatrix[j, 1])

                        {

                            intersectionMatrix[i, j] = 0;

                        }

                        else

                        {

                            intersectionMatrix[i, j] = 1;

                        }

                    }

                    else

                    {

                        intersectionMatrix[i, j] = 0;

                    }

                }

            }

            int maxNumberOfRings = 0;

            ArrayList covered = new ArrayList();

            Queue link = new Queue();

            for (int i = 0; i < intersectionMatrix.GetLength(0) && !covered.Contains(i); i++)

            {

                int tempCount = 0;

                int k = i;

                do

                {

                    if (link.Count != 0)

                    {

                        i = (int)link.Dequeue();

                    }

                    for (int j = 0; j < intersectionMatrix.GetLength(0); j++)

                    {

                        if (intersectionMatrix[i, j] != 0)

                        {

                            //Condition to filter out mutual links

                            if (!covered.Contains(j))

                            {

                                tempCount++;

                                covered.Add(j);

                                //Condition to filter out self link from queueing up

                                if (i != j)

                                    link.Enqueue(j);

                            }

                        }

                    }

                } while (link.Count != 0);

                if (maxNumberOfRings < tempCount)

                {

                    maxNumberOfRings = tempCount;

                }

                i = k;

            }

            Console.WriteLine("Max number of rings that can be lifted in a single attempt: " + maxNumberOfRings);

        }

    }

}

 

Max number of rings that can be lifted in a single attempt: 4
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