Consider a 2-bit bitmap of arbitrary side-lengths overlaid on a coordinate grid and imaged with random data (1's represent an element of the image, 0's represent the "blank" canvas background):
y x—0 2 4 6 8 10 14 18 | 0 0000000000111100000000 0000000011111110000000 2 0000111111111111000000 0000011111111111000000 4 0000000000000000000000 1111111000000000011111 6 1111111111100000000011 1111111111111111000000
Next, consider how the rasterized image may be described using a series of drawn, solid rectangles. Example:
0 2 4 6 8 101214161820 0 0000000000111100000000 0000000011111110000000 2 0000111111111111000000 0000011111111111000000 4 0000000000000000000000 xxxxxxx000000000011111 6 xxxxxxx111100000000011 xxxxxxx111111111000000
The x's describe a region of the bitmap that may be described using a solid rectangle. Finally, consider how that rectangular section of the image can be described under the X-Y coordinate system by two of its vertices in the format:
In this case,
describes the example rectangular section.
Challenge: Design a program which receives a 2D matrix containing bitmap data and outputs a concatenated list of rectangle coordinates.
The output, when processed by remapping (plotting using 1's) the rectangles back onto a blank coordinate canvas (a canvas of all 0's) of the same side-length dimensions, should yield exactly the input matrix.
The output should be a concatenated list of all computed rectangles, no extraneous parsing characters or structures distinguishing one set of coordinates from another. The list will be read top-down, ordering will be inferred given that each rectangle requires only two coordinates to be described.
(Do mind that this example in no way presents the ideal output, however, it is a valid output.)
Input 2D matrix:
0000000000111100000000 0000000011111110000000 0000111111111111000000 0000011111111111000000 0000000000000000000000 1111111000000000011111 1111111111100000000011 1111111111111111000000
Output concatenated list:
Programs will be ranked by their average-case efficiency using this resource (or one which functions identically) to generate pseudorandom, 2-bit, 20x20 matrices. Determine the average-case efficiency by calculating the arithmetic mean of the output lengths of at least 10 iterations (sum of the lengths divided by the number of iterations). The lesser the average length of the output, the greater the efficiency.