// Map Reduce by Rob Hutchinson 2020/Hiroix

​

using System;

using System.Collections.Generic;

using System.Drawing;

​

public class Program

{

    private const string pattern1 = @"

XXXX_XXX__

_____XXXX_

XXXXXXXXXX

XXXXXXXXXX

_XXX_X__XX

_XXX_XX_XX

___XX_____

XX_XX_XXX_

_XX__XXXXX

__XX__XXXX

";

​

    private const string pattern2 = @"

XXXXXXXXXX

XXXXXXXXXX

XXXXXXXXXX

XXXXXXXXXX

XXXXXXXXXX

XXXXXXXXXX

XXXXXXXXXX

XXXXXXXXXX

XXXXXXXXXX

XXXXXXXXXX

";

​

    private const string pattern3 = @"

X_XXXXXXXX

X_XXXXXXXX

X_XXXXXXXX

X_XXXXXXXX

XXXXXXXXXX

XXXXXXXXXX

XXXXXXX_XX

XXXXXXX_XX

XXXXXXX_XX

XXXXXXX_XX

";

​

    private const string pattern4 = @"

X_XXXXXXXX

X_XX__XXXX

X_XXXXXXXX

X_XXXX__XX

XXXXX_XXXX

XXX__XXXXX

XXXX_XX_XX

XXX_XXX_XX

XXXXX_X_XX

XXX_XXX_XX

";

​

    private const string pattern5 = @"

XXXXXXXXXX

__XXXXXXXX

____XXXXXX

_____XXXXX

______XXXX

______XXXX

_____XXXXX

____XXXXXX

__XXXXXXXX

XXXXXXXXXX

";

​

    public static void Main()

    {

        bool[,] map = PatternTo2DArray(pattern1);

        //bool[,] map = PatternTo2DArray(pattern2);

        //bool[,] map = PatternTo2DArray(pattern3);

        //bool[,] map = PatternTo2DArray(pattern4);

        //bool[,] map = PatternTo2DArray(pattern5);

​

        var rects = ReduceMap(map);

        int index = 0;

        foreach (var rect in rects)

        {

            Console.WriteLine("{0}: {{ {1}, {2}, {3}, {4} }}", ((index + 1).ToString().PadLeft(1, '0')), rect.X, rect.Y, rect.Width, rect.Height);

            index++;

        }

​

        var total = DumpMap(map);

        Console.WriteLine("\r\nOptimised Map From: {0} to {1}", total, index);

    }

​

    public static IEnumerable<Rectangle> ReduceMap(bool[,] map)

    {

        int width = map.GetLength(0), height = map.GetLength(1);

        MapElement[,] bin = new MapElement[width, height];

​

        // Reduce

        // Step 1: Convert to map elements:

        for (int y = 0; y < height; y++)

            for (int x = 0; x < width; x++)

            {

                if (map[x, y])

                    bin[x, y] = new MapElement() { X = x, Y = y, Width = 1, Height = 1, Set = true };

            }

​

        // Step 2: Process the bin map and generate a collection of Rectangles horizontally     

        for (int y = 0; y < height; y++)

        {

            for (int x = 0; x < width; x++)

            {

                // Only care about this if we are set.

                if (bin[x, y].Set)

                {

                    // Scan forward and link this tile with its following tiles

                    int xx = 0;

                    for (int xForward = x + 1; xForward < width; xForward++)

                    {

                        if (!bin[xForward, y].Set)

                            break;

​

                        // We can link this...

                        bin[xForward, y].Set = false;

                        bin[x, y].Width++;

                        xx++; // Skip over these tiles.

                    }

​

                    x += xx;

                }

            }

        }

​

        // Step 3: Process the bin map veritically and join any blocks that have equivalent blocks below them.

        for (int y = 0; y < height; y++)

        {

            for (int x = 0; x < width; x++)

            {

                // Only care about this if we are set.

                if (bin[x, y].Set)

                {

                    // Scan down and link this tile with its following tiles

                    for (int yDown = y + 1; yDown < height; yDown++)

                    {

                        if (!bin[x, yDown].Set || bin[x, yDown].Width != bin[x, y].Width)  // We might be able to link this if it's the same size

                            break;

​

                        bin[x, yDown].Set = false;

                        bin[x, y].Height++;

                    }

                }

            }

        }

​

        // Step 4: Convert map to rectangles

        for (int y = 0; y < height; y++)

        {

            for (int x = 0; x < width; x++)

            {

                // Only care about this if we are set.

                if (bin[x, y].Set)

                {

                    var b = bin[x, y];

                    yield return new Rectangle(b.X, b.Y, b.Width, b.Height);

                }

            }

        }

    }

​

    public static int DumpMap(bool[,] map)

    {

        Console.WriteLine("");

        var @out = 0;

        int width = map.GetLength(0), height = map.GetLength(1);

        for (int y = 0; y < height; y++)

        {

            for (int x = 0; x < width; x++)

            {

                Console.Write(map[x, y] ? "X" : "_");

                @out++;

            }

​

            Console.WriteLine();

        }

​

        return @out;

    }

​

    public static int CountDataPoints(bool[,] map)

    {

        var @out = 0;

        int width = map.GetLength(0), height = map.GetLength(1);

        for (int y = 0; y < height; y++)

            for (int x = 0; x < width; x++)

                if (map[x, y])

                    @out++;

​

        return @out;

    }

​

    public static bool[,] PatternTo2DArray(string pattern)

    {

        var lines = new List<string>(pattern.Split('\n'));

        for (int i = lines.Count - 1; i > -1; i--)

        {

            string line = lines[i].TrimEnd('\r');

            if (line.Length == 0)

                lines.RemoveAt(i);

            else

                lines[i] = line;

        }

​

        var @out = new bool[lines[0].Length, lines.Count];

        for (int y = 0; y < lines.Count; y++)

        {

            string line = lines[y];

            for (int x = 0; x < line.Length; x++)

            {

                @out[x, y] = !(line[x] == '_');

            }

        }

​

        return @out;

    }

​

    internal struct MapElement

    {

        public int X;

        public int Y;

        public int Width;

        public int Height;

        public bool Set;

    }

}

​