using System;

namespace SquareFinder
{
    /// <summary>
    /// Summary description for Class1.
    /// </summary>
    /// 
    class Class1
    {
        /// <summary>
        /// The main entry point for the application.
        /// </summary>
        /// 
        const int WIDTH = 8;
        const int HEIGHT = 8;

        [STAThread]
        static void Main(string[] args) 
        { 
            int totalCalls = 0;
            int totalGridsEvaluated = 0;
            int squares = 0;
            int rectangles = 0;

            for (int left = 0; left<WIDTH; ++left) 
                for (int right = 1; right<=WIDTH; ++right) 
                    for (int bottom = 0; bottom<HEIGHT; ++bottom) 
                        for (int top = 1; top<=HEIGHT; ++top) 
                        {
                            Grid grid = new Grid(left, right, bottom, top);
                            
                            //Shape shape = Recognize0(grid);
                            //Looked at 4096 grids.
                            //Detected 204 squares.
                            //Detected 1092 rectangles.
                            //Detected 2800 invalid grids.
                            //Called CountBlocksSet 109072 times.
                            //Average calls per grid 26.62890625
                            
                            //Shape shape = Recognize1(grid);
                            //Looked at 4096 grids.
                            //Detected 204 squares.
                            //Detected 1092 rectangles.
                            //Detected 2800 invalid grids.
                            //Called CountBlocksSet 63520 times.
                            //Average calls per grid 15.5078125

                            //Shape shape = Recognize2(grid); 
                            //Looked at 4096 grids.
                            //Detected 204 squares.
                            //Detected 1092 rectangles.
                            //Detected 2800 invalid grids.
                            //Called CountBlocksSet 41494 times.
                            //Average calls per grid 10.13037109375                            

                            //Shape shape = Recognize3(grid);
                            //Looked at 4096 grids.
                            //Detected 204 squares.
                            //Detected 1092 rectangles.
                            //Detected 2800 invalid grids.
                            //Called CountBlocksSet 11632 times.
                            //Average calls per grid 2.83984375

                            //Shape shape = Recognize4(grid);
                            //Looked at 4096 grids.
                            //Detected 204 squares.
                            //Detected 1092 rectangles.
                            //Detected 2800 invalid grids.
                            //Called CountBlocksSet 11464 times.
                            //Average calls per grid 2.798828125     
                       
                            Shape shape = Recognize5(grid);
                            //Looked at 4096 grids.
                            //Detected 204 squares.
                            //Detected 1078 rectangles.
                            //Detected 2814 invalid grids.
                            //Called CountBlocksSet 4793 times.
                            //Average calls per grid 1.170166015625

                            totalCalls += grid.TotalCalls;
                            ++totalGridsEvaluated;

                            bool gridIsSquare = (right - left == top - bottom);

                            if (shape == Shape.Square) 
                            {
                                squares++;
                                if (!gridIsSquare) 
                                    throw new Exception("Square was incorrectly recognized.");
                            }
                            else if (shape == Shape.Rectangle)
                            {
                                rectangles++;
                                if (gridIsSquare) 
                                    throw new Exception("Rectangle was incorrectly recognized.");
                            }
                            else
                            {
                                // Unknown Shape
                            }
                        }
            Console.WriteLine("Looked at " + totalGridsEvaluated + " grids.");
            Console.WriteLine("Detected " + squares + " squares.");
            Console.WriteLine("Detected " + rectangles + " rectangles.");
            Console.WriteLine("Detected " + (totalGridsEvaluated - squares - rectangles) + " invalid grids.");
            Console.WriteLine("Called CountBlocksSet " + totalCalls + " times.");
            Console.WriteLine("Average calls per grid " + (double)totalCalls / (double)totalGridsEvaluated);
            Console.ReadLine();
        }

        //    static Shape Recognize(IGrid grid)
        //    {
        //        // Implement this.
        //    }
        static Shape Recognize0(IGrid grid) 
        {
            int left = Int32.MaxValue;
            int right = -1;
            int bottom = Int32.MaxValue;
            int top = -1;

            int area = grid.CountBlocksSet(0, WIDTH, 0, HEIGHT);

            if ( area == 0)
                return Shape.Unknown;

            for (int x = 0; x <= WIDTH; ++x)    
            {
                for (int y = 0; y <= HEIGHT; ++y)   
                {
                    if (grid.CountBlocksSet(x, x+1, y, y+1) == 1) 
                    {
                        left = Math.Min(left, x);
                        right = Math.Max(right, x+1);
                        bottom = Math.Min(bottom, y);
                        top = Math.Max(top, y+1);
                    }
                }
            }

            if (right - left == top - bottom) 
            {
                return Shape.Square;
            }

            return Shape.Rectangle;
        }

        static Shape Recognize1(IGrid grid) 
        {
            int left = Int32.MaxValue;
            int right = -1;
            int bottom = Int32.MaxValue;
            int top = -1;

            int area = grid.CountBlocksSet(0, WIDTH, 0, HEIGHT);

            if ( area == 0)
                return Shape.Unknown;

            int thisarea = -1;

            for (int x = 0; x <= WIDTH && thisarea < area; ++x) 
            {
                for (int y = 0; y <= HEIGHT && thisarea < area; ++y)    
                {
                    if (grid.CountBlocksSet(x, x+1, y, y+1) == 1) 
                    {
                        left = Math.Min(left, x);
                        right = Math.Max(right, x+1);
                        bottom = Math.Min(bottom, y);
                        top = Math.Max(top, y+1);
                        thisarea = (right - left) * (top - bottom);
                    }
                }
            }

            if (right - left == top - bottom) 
            {
                return Shape.Square;
            }

            return Shape.Rectangle;
        }


        static Shape Recognize2(IGrid grid) 
        {
            int left = 0;
            int right = WIDTH;
            int bottom = 0;
            int top = HEIGHT;

            int area = grid.CountBlocksSet(left, right, bottom, top);

            if (area == 0)
                return Shape.Unknown;

            // One space is a square
            if (area == 1) 
                return Shape.Square;
            
            // Two spaces is a rect
            if (area == 2) 
                return Shape.Rectangle;
       
            // everything full is a square
            // SQRT section would cover this also
            else if (area == WIDTH*HEIGHT)
                return Shape.Square;

            // areas that have a integer sqrt and are bigger than 
            // a 1xheight column, and don't divide evenly by a dimension
            // have to be a square
            if (area > HEIGHT)
            {
                // If the area divides evenly by the height (e.g. 16) then it 
                // could be a rectangle, but if it doesn't it can only be
                // a square
                if (area % HEIGHT != 0)
                {
                    double Root = System.Math.Sqrt((double)area);
                    if ( System.Math.Floor(Root) == Root)
                        return Shape.Square;
                }
            }

            // Remaining (non integer sqrt) odd areas are rectangles
            if (area % 2 == 1)
                return Shape.Rectangle;

            // 4, 16

            Console.WriteLine("Brute-Forcing value " + area);
            
            return Recognize1(grid);
           
        }

        
        static Shape Recognize3(IGrid grid) 
        {
            int left = 0;
            int right = WIDTH;
            int bottom = 0;
            int top = HEIGHT;

            int area = grid.CountBlocksSet(left, right, bottom, top);

            if (area == 0)
                return Shape.Unknown;

            // One space or all spaces is a square
            if (area == 1 || area == WIDTH*HEIGHT) 
                return Shape.Square;

            // If no integral sqrt then must be a rect
            double Root = System.Math.Sqrt((double)area);
            bool bRoot = (System.Math.Floor(Root) == Root);

            if (area > HEIGHT && bRoot == true && area % HEIGHT != 0)
                return Shape.Square;

            if (bRoot == false)
                return Shape.Rectangle;

            // 4, 6, 8, 16, 24

            Console.WriteLine("Brute-Forcing value " + area);
            
            return Recognize1(grid);
           
        }


        static Shape RecognizeBrute (IGrid grid, int area)  
        {
            int left = Int32.MaxValue;
            int right = -1;
            int bottom = Int32.MaxValue;
            int top = -1;

            if ( area == 0)
                return Shape.Unknown;

            int thisarea = -1;

            for (int x = 0; x <= WIDTH && thisarea < area; ++x) 
            {
                for (int y = 0; y <= HEIGHT && thisarea < area; ++y)    
                {
                    if (grid.CountBlocksSet(x, x+1, y, y+1) == 1) 
                    {
                        left = Math.Min(left, x);
                        right = Math.Max(right, x+1);
                        bottom = Math.Min(bottom, y);
                        top = Math.Max(top, y+1);
                        thisarea = (right - left) * (top - bottom);
                    }
                }
            }

            if (right - left == top - bottom) 
            {
                return Shape.Square;
            }

            return Shape.Rectangle;
        }


        static Shape Recognize4(IGrid grid) 
        {
            int left = 0;
            int right = WIDTH;
            int bottom = 0;
            int top = HEIGHT;

            int area = grid.CountBlocksSet(left, right, bottom, top);

            if (area == 0)
                return Shape.Unknown;

            // One space or all spaces is a square
            if (area == 1 || area == WIDTH*HEIGHT) 
                return Shape.Square;

            // If no integral sqrt then must be a rect
            double Root = System.Math.Sqrt((double)area);
            bool bRoot = (System.Math.Floor(Root) == Root);

            if (area > HEIGHT && bRoot == true && area % HEIGHT != 0)
                return Shape.Square;

            if (bRoot == false)
                return Shape.Rectangle;

            // only 4 (or value less 1 dimension that has an 
            // integral sqrt remains.
            //Console.WriteLine("Brute-Forcing value " + area);
            return RecognizeBrute(grid, area);
           
        }


        static Shape Recognize5(IGrid grid) 
        {
            int left = 0;
            int right = WIDTH;
            int bottom = 0;
            int top = HEIGHT;

            int area = grid.CountBlocksSet(left, right, bottom, top);

            if (area == 0)
                return Shape.Unknown;

            // One space or all spaces is a square
            if (area == 1 || area == WIDTH*HEIGHT) 
                return Shape.Square;

            // If no integral sqrt then must be a rect
            double Root = System.Math.Sqrt((double)area);
            bool bRoot = (System.Math.Floor(Root) == Root);

            if (area > HEIGHT && bRoot == true && area % HEIGHT != 0)
                return Shape.Square;

            if (bRoot == false)
                return Shape.Rectangle;

            // only value less than 1 dimension or evenly divisible by 
            // one dimension and having an integral sqrt remain.
            int thisarea = 0;
            for (int y = 0; y <= HEIGHT && thisarea < area; ++y)    
            {
                thisarea = grid.CountBlocksSet(0, WIDTH, y, y+1);
                
                if (thisarea == area || thisarea == 1)
                    return Shape.Rectangle;

                if (thisarea == System.Math.Sqrt(area))
                    return Shape.Square;

            }

            return Shape.Unknown;
           
        }

    }
}