Daily Programmer 4/18/2014 challenge

gistfile1.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Scratchpad.DailyProgrammer
{
    public class Dp20140418
    {
        public struct Point
        {
            public Point(decimal x, decimal y)
            {
                X = x;
                Y = y;
            }

            public decimal X, Y;

            public override string ToString()
            {
                return string.Format("Point: ({0},{1})", X, Y);
            }
        }

        public struct Rectangle
        {
            public Rectangle(decimal x1, decimal y1, decimal x2, decimal y2)
            {
                X1 = x1;
                Y1 = y1;
                X2 = x2;
                Y2 = y2;
            }

            public Rectangle(Point bottomLeftCorner, Point topRightCorner)
            {
                X1 = bottomLeftCorner.X;
                Y1 = bottomLeftCorner.Y;
                X2 = topRightCorner.X;
                Y2 = topRightCorner.Y;
            }

            public decimal X1, Y1, X2, Y2;

            public decimal Width { get { return Math.Abs(X2 - X1); } }
            public decimal Height { get { return Math.Abs(Y2 - Y1); } }
            public decimal Area { get { return Width * Height; } }
            
            public Point[] Corners
            {
                get
                {
                    return new Point[]
                    {
                        new Point(X1, Y1),
                        new Point(X1, Y2),
                        new Point(X2, Y1),
                        new Point(X2, Y2)
                    };
                }
            }

            public override string ToString()
            {
                return string.Format("Rectangle: ({0}, {1}), ({2}, {3})", X1, Y1, X2, Y2);
            }

            public bool ContainsPoint(Point point)
            {
                return point.X >= X1 &&
                       point.X <= X2 &&
                       point.Y >= Y1 &&
                       point.Y <= Y2;
            }

            public bool ContainsRectangle(Rectangle rectangle)
            {
                return rectangle.Corners.All(ContainsPoint);
            }
        }

        public static decimal ComputeArea(IEnumerable<Rectangle> rectangles)
        {
            var allRectangles = rectangles.ToList();

            // Loop through each rectangle and if it intesects with any other rectangle, replace both of them
            // with split rectangles
            while (true)
            {
                bool intersectingRectanglesFound = false;

                for (int x = 0; x < allRectangles.Count; x++)
                {
                    for (int y = x + 1; y < allRectangles.Count; y++)
                    {
                        var rectangle1 = allRectangles[x];
                        var rectangle2 = allRectangles[y];
                        var splitRectangles = SplitIntersectingRectangles(rectangle1, rectangle2).ToArray();
                        if (splitRectangles.Length > 2)
                        {
                            // Rectangles intersected, remove both and add the split rectangles, and start again
                            allRectangles.RemoveAt(y);
                            allRectangles.RemoveAt(x);

                            allRectangles.AddRange(splitRectangles);
                            intersectingRectanglesFound = true;
                            break;
                        }

                        // If one rectangle is within the other, disregard the inner one
                        if (allRectangles[x].ContainsRectangle(allRectangles[y]))
                        {
                            allRectangles.RemoveAt(y);
                            y--;
                        }
                        else if (allRectangles[y].ContainsRectangle(allRectangles[x]))
                        {
                            allRectangles.RemoveAt(x);
                            x--;
                            break;
                        }
                    }

                    if (intersectingRectanglesFound)
                        break;
                }

                // If we found intersecting rectangles, begin the checks again
                if (intersectingRectanglesFound)
                    continue;

                break;
            }

            return allRectangles.Distinct().Sum(r => r.Area);
        }

        private static IEnumerable<Rectangle> SplitIntersectingRectangles(Rectangle rectangle1, Rectangle rectangle2)
        {
            var intersectingRectangle = GetIntersectingRectangle(rectangle1, rectangle2);
            if (intersectingRectangle.Area == 0)
                return new Rectangle[] {rectangle1, rectangle2}; // Rectangles don't intersect

            // Get a list of all corners of all resulting rectangle
            var initialRectangles = new[] {rectangle1, rectangle2, intersectingRectangle};
            var corners = initialRectangles.SelectMany(x => x.Corners)
                                           .ToList();

            corners = SortCorners(corners);

            // Cycle through all the points to pick out rectangles, starting from the 0,0
            // Pick out the bottom left and top right corners to form rectangles on
            var resultingRectangles = new List<Rectangle>();
            for (int x = 0; x < corners.Count - 3; x++ )
            {
                var bottomLeftCorner = corners[x];

                // FInd the next corner on the same X axis. 
                var topLeftCorner = corners[x + 1];
                if (topLeftCorner.X != bottomLeftCorner.X)
                    continue;

                // Find the next corner to the right
                Point? topRightCorner = null;
                for (int y = x + 2; y < corners.Count; y++)
                {
                    // Ignore if we haven't moved beyond the current X plane
                    if (corners[y].X == bottomLeftCorner.X)
                        continue; 

                    // Next corner we come up against will either be the top right corner,
                    // or an intersection point.  If it's an intersection point we need to create
                    // a new corner from that point on the same Y axis as our last corner
                    if (corners[y].Y == topLeftCorner.Y)
                    {
                        topRightCorner = corners[y];
                    }
                    else
                    {
                        topRightCorner = new Point(corners[y].X, topLeftCorner.Y);
                        
                    }

                    break;
                }

                if (topRightCorner == null)
                    continue;

                // Add a new corner (if it doesn't exist) for the bottom right
                var bottomRightCorner = new Point(topRightCorner.Value.X, bottomLeftCorner.Y);

                // Note down the resulting rectangle
                var splitRectangle = new Rectangle(bottomLeftCorner, topRightCorner.Value);

                // Verify all 4 points are within the original rectangles
                if (splitRectangle.Corners.Any(c => !rectangle1.ContainsPoint(c)) &&
                    splitRectangle.Corners.Any(c => !rectangle2.ContainsPoint(c)))
                {
                    continue;
                }

                // Add the new corners and store the rectangle
                corners.Add(topRightCorner.Value); 
                corners.Add(bottomRightCorner);
                corners = SortCorners(corners);
                
                resultingRectangles.Add(splitRectangle);
            }

            return resultingRectangles;
        }

        private static Rectangle GetIntersectingRectangle(Rectangle rectangle1, Rectangle rectangle2)
        {
            decimal resultX1 = 0, resultY1 = 0, resultX2 = 0, resultY2 = 0;

            // Get the boundaries of the intersection rectangle
            resultX1 = Math.Max(rectangle1.X1, rectangle2.X1);
            resultY1 = Math.Max(rectangle1.Y1, rectangle2.Y1);
            resultX2 = Math.Min(rectangle1.X2, rectangle2.X2);
            resultY2 = Math.Min(rectangle1.Y2, rectangle2.Y2);

            // If an invalid rectangle was created, the two rectangles don't intersect
            if (resultX1 >= resultX2 || resultY1 >= resultY2)
                return new Rectangle(0,0,0,0);

            return new Rectangle(resultX1, resultY1, resultX2, resultY2);
        }

        private static List<Point> SortCorners(IEnumerable<Point> corners)
        {
            return corners.Distinct()
                          .OrderBy(x => x.X)
                          .ThenBy(x => x.Y)
                          .ToList();
        }
    }
}