Binary Map Reduce

CSharp · Console

/Program.cs

// 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;
    }
}