2
\$\begingroup\$

I had to write code for a competition which calculates sum of the perimeter of two non-overlapping rectangles in a 2D space. My code is working fine and resulting in expected outputs. But it is taking a good amount of time to clear all test cases at that website, and I don't have the test cases because they are inbuilt in the websites. I need to improve the following code such that time complexity is reduced.

  static void Main(string[] args)
            {

                int[][] arrL = new int[3][];
                arrL[0] = new int[2] { 1, 1 };
                arrL[1] = new int[2] { 1, 2 };
                arrL[2] = new int[2] { 1, 3 };


                int i = test(1, 3, 3, 1,  arrL); // 22
                Console.WriteLine(i);
                Console.WriteLine((i == 8) ? "Pass" : "Fail");
                Console.ReadLine();

            }

            public static int test(int input1, int input2, int input3, int input4,  int[][] input5)
            {
                int output = 0;
                _matrix = new int[input1, input2];
                length = input2;
                width = input1;
                minHubs = input4;
                int totalHubsinSection = input3;

                if (totalHubsinSection != input5.Length)
                {
                    return output;
                }
                //adding cordinates
                foreach (int[] cordinate in input5)
                {
                    int y = cordinate[0] - 1;
                    int x = cordinate[1] - 1;

                    if (_matrix[y, x] > 0)
                    {
                        _matrix[y, x] = _matrix[x, y] + 1;
                    }
                    else
                    {
                        _matrix[y, x] = 1;
                    }
                }

                _Revmatrix = new int[input2, input1];
                TransposeMatrix(_matrix, length, width);
                TraverseMatrix();
                GetPointsRectangle();
                output = CheckRectangle();
                return output;
            }
            public static void TraverseMatrix()
            {
                for (int k = 0; k < length; k++)
                {
                    for (int l = 0; l < width; l++)
                    {
                        for (int i = 0; i < length; i++)
                        {
                            for (int j = 0; j < width; j++)
                            {
                                Rectang objRectang = new Rectang
                                {
                                    y1 = l,
                                    y2 = j,
                                    x1 = k,
                                    x2 = i
                                };

                                _listRectan.Add(objRectang);
                            }
                        }
                    }
                }
            }

            public static void TransposeMatrix(int[,] matrix, int m, int n)
            {
                for (int i = m - 1, k = 0; i >= 0; i--, k++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        _Revmatrix[k, j] = matrix[j, i];
                    }
                }
            }

            private static List<Rectang> _actualRectangle;
            public static void GetPointsRectangle()
            {
                _actualRectangle = new List<Rectang>();

                foreach (var obj in _listRectan)
                {
                    int x1 = obj.x1;
                    int x2 = obj.x2;
                    int y1 = obj.y1;
                    int y2 = obj.y2;
                    int s = 0;

                    for (int i = x1; i <= x2; i++)
                    {
                        for (int j = y1; j <= y2; j++)
                        {
                            if (_Revmatrix[i, j] > 0)
                            {

                                s += _Revmatrix[i, j];
                            }
                        }
                    }

                    if (s == minHubs)
                    {
                        _actualRectangle.Add(obj);
                    }
                }
            }
            public static int CheckRectangle()
            {
                List<int> perimeterList = new List<int>();
                //rohit new code start

                for (int i = 0; i < _actualRectangle.Count; i++)
                {
                    for (int j = i; j < _actualRectangle.Count; j++)
                    {
                        if ((Convert.ToString(_actualRectangle[i].x1) + Convert.ToString(_actualRectangle[i].y1)
                             == Convert.ToString(_actualRectangle[j].x1) + Convert.ToString(_actualRectangle[j].y1)) ||
                            (Convert.ToString(_actualRectangle[i].x2) + Convert.ToString(_actualRectangle[i].y2)
                             == Convert.ToString(_actualRectangle[j].x2) + Convert.ToString(_actualRectangle[j].y2)) ||
                              //added extra

                              (Convert.ToString(_actualRectangle[i].x2) + Convert.ToString(_actualRectangle[i].y1)
                             == Convert.ToString(_actualRectangle[j].x2) + Convert.ToString(_actualRectangle[j].y2)) ||
                              (Convert.ToString(_actualRectangle[i].x2) + Convert.ToString(_actualRectangle[i].y1)
                             == Convert.ToString(_actualRectangle[j].x1) + Convert.ToString(_actualRectangle[j].y1)) ||
                              (Convert.ToString(_actualRectangle[i].x1) + Convert.ToString(_actualRectangle[i].y2)
                             == Convert.ToString(_actualRectangle[j].x1) + Convert.ToString(_actualRectangle[j].y1)) ||
                              (Convert.ToString(_actualRectangle[i].x1) + Convert.ToString(_actualRectangle[i].y2)
                             == Convert.ToString(_actualRectangle[j].x2) + Convert.ToString(_actualRectangle[j].y2))
                             )
                        {
                            continue;
                        }
                        int deltaLength = Math.Abs(_actualRectangle[i].x2 - _actualRectangle[i].x1);
                        int deltaBreadth = Math.Abs(_actualRectangle[i].y2 - _actualRectangle[i].y1);
                        int leastperim = 18 * ((deltaLength + 1) + (deltaBreadth + 1));

                        int deltaLength1 = Math.Abs(_actualRectangle[j].x2 - _actualRectangle[j].x1);
                        int deltaBreadth1 = Math.Abs(_actualRectangle[j].y2 - _actualRectangle[j].y1);
                        int leastperim1 = 18 * ((deltaLength1 + 1) + (deltaBreadth1 + 1));
                        perimeterList.Add(leastperim + leastperim1);
                    }
                }
                var result = perimeterList.Distinct().ToList().OrderBy(x => x).FirstOrDefault();
                return result;
            }
            public class Rectang
            {
                public int x1;
                public int y1;
                public int x2;
                public int y2;
            }

I'm particularly looking for help to speed up this code; I think the critical method is checkRectangle().

\$\endgroup\$
  • \$\begingroup\$ "I don't have test cases" - but surely you must be able to invent some? \$\endgroup\$ – Toby Speight May 24 '17 at 16:28
  • \$\begingroup\$ Can you add an actual problem statement? \$\endgroup\$ – vnp May 24 '17 at 16:38
  • 1
    \$\begingroup\$ I think the critical method is checkRectangle() You think? You want to optimize something without knowing if it even requries optimizing? \$\endgroup\$ – t3chb0t May 24 '17 at 17:21
  • 2
    \$\begingroup\$ Perhaps you want to use fewer Convert.ToString() calls. \$\endgroup\$ – Rick Davin May 24 '17 at 18:22
2
\$\begingroup\$

I know I should review your code but I find there is no point in doing this. It is so complex for such a simple task that I won't do it as everything is simply wrong. There's no need for any loops or conversions to string. It's just a simple math. What does it mean? You already created a Rectangle class so let's start from that and improve it by encapsulating the coordinates in a Point struct and let the rectangle calculate it's Width and Height and the Perimtere. To tell whether to rectangles overlap you just need to calculate their bounding box and check whether it's smaller then the one when the rectangles are not overlapping.

struct Point
{
    public int X { get; set; }
    public int Y { get; set; }
}

struct Rectangle 
{
    public Point TopLeft { get; set; }
    public Point BottomRight { get; set; }

    public int Width => Math.Max(TopLeft.X, BottomRight.X) - Math.Min(TopLeft.X, BottomRight.X);
    public int Height => Math.Max(TopLeft.Y, BottomRight.Y) - Math.Min(TopLeft.Y, BottomRight.Y);

    public int Perimeter => 2 * Width + 2 * Height;

    public bool Contains(Rectangle other)
    {
        var bbox = new Rectangle
        {
            TopLeft = new Point
            {
                X = Math.Min(TopLeft.X, other.TopLeft.X),
                Y = Math.Min(TopLeft.Y, other.TopLeft.Y)
            },
            BottomRight = new Point
            {
                X = Math.Max(BottomRight.X, other.BottomRight.X),
                Y = Math.Max(BottomRight.Y, other.BottomRight.Y)
            }
        };
        return 
            bbox.Width <= Width + other.Width || 
            bbox.Height <= Height + other.Height;
    }
}

Why TopLeft and BottomRight? Because I assumed the windows coordinate system.

Alternatively you can use the Rectangle from the System.Drawing namespace.

And an example:

var r1 = new Rectangle
{
    TopLeft = new Point { X = 1, Y = 1 },
    BottomRight = new Point { X = 3, Y = 3 },
};

var r2 = new Rectangle
{
    TopLeft = new Point { X = 2, Y = 2 },
    BottomRight = new Point { X = 4, Y = 4 },
};  

r1.Contains(r2).Dump(); // true, overlap

var r3 = new Rectangle
{
    TopLeft = new Point { X = 4, Y = 4 },
    BottomRight = new Point { X = 5, Y = 5 },
};

r1.Contains(r3).Dump(); // false, don't overlap

Calculating the sum of their perimeter is now as easy as r1.Perimeter + r3.Perimter, isn't it?

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice approach. I'm not a fan of names P1 and P2 as they lack context. Perhaps TopLeftCorner and BottomRightCorner. Or should that be BottomLeftCorner and TopRightCorner? \$\endgroup\$ – Rick Davin May 26 '17 at 15:44
  • 2
    \$\begingroup\$ @RickDavin you're right, the names are really stupid, I'll correct them later, I was going to change them but forgot. I would never use such names ;-D so actually you didn't see them :-P \$\endgroup\$ – t3chb0t May 26 '17 at 15:47
0
\$\begingroup\$

It appears to me that you may be a student or beginner with C#, so I will try to help to some degree. It was really hard for me to read through checkRectangle(), so let's focus on cleaning that up while also improving performance.

First and foremost, Convert.ToString() or ToString() in general is very sluggish, particular when comparing equality of objects. The smarter and cleaner way is just to compare the objects directly, especially integers.

Before I get to that, I am going to mention some other things about your code for you to consider in the future.

  • Don't stick everything the Program class. Your methods don't all have to be static. Create separate classes (plural) to keep your code cleaner.
  • Try to employ the DRY Principle (Don't Repeat Yourself).
  • Code should be readable by others as to your intent, and should not give them headaches trying to figure out what you are doing.
  • In checkRectangle(), you have a magic number of 18. This should be given a name in a constant, and then use the constant in expressions. I'm stuck at a suggestion for a name because I have no idea what your intent is behind the 18.
  • There is no need for the .ToList() inside of Distinct().ToList().OrderBy(x => x).

Consider how ugly and jumbled your big if statement is inside of checkRectangle() (no offense). Its very hard to follow. This logic can be simplified by moving the logic to your Rectang class. FORGIVE ME if I translated some of your logic incorrectly. Again it was difficult (as just a volunteer enthusiast to review your code) to follow your original. The important thing is for you to concentrate on the why's and how it's being changed.

public class Rectang
{
    public int x1;
    public int y1;
    public int x2;
    public int y2;

    public bool HasOverlap(Rectang other)
    {
        return ((x1 == other.x1) && (y1 == other.y1)) ||
               ((x2 == other.x2) && (y2 == other.y2)) ||
               ((x2 == other.x2) && (y1 == other.y2)) ||
               ((x2 == other.x1) && (y1 == other.y1)) ||
               ((x1 == other.x1) && (y2 == other.y1)) ||
               ((x1 == other.x2) && (y2 == other.y2));
    }
}

This could even be simplified further by adding another method to Rectang:

    private static bool HasOverlap(int xi, int yi, int xj, int yj)
    {
        // Could be a one liner with C# 6 or better.
        return (xi == xj) && (yi == yj);
    }

    public bool HasOverlap(Rectang other)
    {
        return HasOverlap(x1, y1, other.x1, other.y1) ||
               HasOverlap(x2, y2, other.x2, other.y2) ||
               HasOverlap(x2, y1, other.x2, other.y2) ||
               HasOverlap(x2, y1, other.x1, other.y1) ||
               HasOverlap(x2, y1, other.x2, other.y2) ||
               HasOverlap(x1, y2, other.x2, other.y2);
    }

This employs DRY, avoids ToString(), and is more understandable. But the big payoff is in checkRectangle():

    public static int CheckRectangle()
    {
        List<int> perimeterList = new List<int>();
        //rohit new code start

        for (int i = 0; i < _actualRectangle.Count; i++)
        {
            for (int j = i; j < _actualRectangle.Count; j++)
            {
                // Look at how much cleaner
                if (_actualRectangle[i].HasOverlap(_actualRectangle[j]))
                {
                    continue;
                }

                const int magicNumber = 18; // Give this a MEANINGFUL name

                int deltaLength = Math.Abs(_actualRectangle[i].x2 - _actualRectangle[i].x1);
                int deltaBreadth = Math.Abs(_actualRectangle[i].y2 - _actualRectangle[i].y1);
                int leastperim = magicNumber * ((deltaLength + 1) + (deltaBreadth + 1));

                int deltaLength1 = Math.Abs(_actualRectangle[j].x2 - _actualRectangle[j].x1);
                int deltaBreadth1 = Math.Abs(_actualRectangle[j].y2 - _actualRectangle[j].y1);
                int leastperim1 = magicNumber * ((deltaLength1 + 1) + (deltaBreadth1 + 1));
                perimeterList.Add(leastperim + leastperim1);
            }
        }
        // .ToList() was removed.
        return perimeterList.Distinct().OrderBy(x => x).FirstOrDefault();
    }

And it should be faster since it uses far fewer ToString(), though I leave the testing to you. If it's faster but you are still exceeding your time limit, you now have cleaner code that others could understand better to help with additional performance tweaks.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.