Homework 03: Glyph Tiling

The rectangular printing sheet is divided into a grid of pixels. The grid consists of R rows and C columns.
A glyph is an image of a particular character when that character is printed. In this problem we are considering only the glyph of character "A". We think of the glyph as being drawn by four lines of equal and constant thickness. Two lines are vertical and they share the same length. The remaining two lines are horizontal, representing the top and the central bar of the glyph. See the schemes below. A glyph is described by a tuple of four integers (H, W, T, B).
     H is the height of the glyph in pixels.
     W is the width of the glyph in pixels.
     T is the thickness of the line by which the glyph is drawn.
     B is the height of the bottom part of the glyph. It is equal to the number of rows occupied by both legs of the glyph below the central horizontal bar of the glyph.
     Two pixels, the pixel in the upper left corner and the pixel in the upper right corner of the glyph, are not part of the glyph. This improves visual appearance of the whole glyph.
For example, a glyph described by tuple (13, 10, 3, 5) is schematically drawn in the left part in the scheme below. 

                             W=10
                    +-----------------+                                         1
                    |                 |                     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8
                                                          +---------------------------------------+-
     +-----           X X X X X X X X    --+            0 | . . . . . . . . . . . . . . . . . . . |
     |              X X X X X X X X X X    | T=3        1 | . . X X . . . X X . . . X X . . . . . |
     |              X X X X X X X X X X  --+            2 | . X . . X . X . . X . X . . X . . . . |
     |              X X X         X X X                 3 | . X X X X . X X X X . X X X X . . . . |
     |              X X X         X X X                 4 | . X . . X . X . . X . X . . X . . . . |
H=13 |              X X X X X X X X X X  --+            5 | . X . . X . X . . X . X . . X . . . . |
     |              X X X X X X X X X X    | T=3        6 | . . . . . . . . . . . . . . . . . . . |
     |              X X X X X X X X X X  --+            7 | .   X X   .   X X   .   X X   . . . . |
     |         +--  X X X         X X X                 8 | . X . . X . X . . X . X . . X . . . . |
     |         |    X X X         X X X                 9 | . X X X X . X X X X . X X X X . . . . |
     |     B=5 |    X X X         X X X                10 | . X . . X . X . . X . X . . X . . . . |
     |         |    X X X         X X x                11 | . X . . X . X . . X . X . . X . . . . |
     +-----    +--  X X X         X X X                12 | . . . . . . . . . . . . . . . . . . . |
                                                       13 | . . . . . . . . . . . . . . . . . . . |
                    |   |         |   |                14 | . . . . . . . . . . . . . . . . . . . |
                    +---+         +---+                   +---------------------------------------+
                     T=3           T=3
The printing area is to be tiled with identical glyphs. The glyphs are organized into rows and columns.
Two adjacent glyphs in one row are separated by a vertical gap which width is single pixel. Two adjacent rows of glyphs are separated by a horizontal gap which width is single pixel.
The glyphs are printed starting from the second row and from the second column of the sheet.
If any part of a printed glyph would appear in the last row or in the last column of the printing sheet, that glyph is not printed.
An example scheme of a sheet with 15 rows and 19 columns of pixels is shown in the right part in the scheme above. The sheet is tiled with glyphs described by tuple (5, 4, 1, 2). Note the empty rows and columns in the right part and in the bottom part of the sheet. (Horizontal spaces between adjacent pixels are added for better scheme readability.)

There are occasional impurities in the printing sheet. The impurities affect some pixels. If any part of the printed glyph would cover the impurity, that glyph is not printed. The Examples 1 and 3 below illustrate this rule.

Example 1

(H, W, T, B) = (8, 7, 2, 2)

Input sheet
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000002200000000
00000000000000000000000200000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000002200000000000000000000
00000000002200000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000
Output sheet
00000000000000000000000000000000
00111110001111100000000000000000
01111111011111110000002200000000
01100011011000110000000200000000
01100011011000110000000000000000
01111111011111110000000000000000
01111111011111110000000000000000
01100011011000110000000000000000
01100011011000110000000000000000
00000000000000000000000000000000
00111110000000000011111000000000
01111111000000000111111100000000
01100011002200000110001100000000
01100011002200000110001100000000
01111111000000000111111100000000
01111111000000000111111100000000
01100011000000000110001100000000
01100011000000000110001100000000
00000000000000000000000000000000
00000000000000000000000000000000
00000000000000000000000000000000

Example 2

(H, W, T, B) = (4, 3, 1, 1)

Input sheet
000000000000000000000000000000
020202022202020222020202220202
002000202020002020200020202002
200000002000000020000000200002
202000202020002020200020202002
000000000000000000000000000000
000000000022222000000000000000
000000000022222000000000000000
000000000022222000000000000000
000000000000000000000000000000
Output sheet
000000000000000000000000000000
021202122212021222120212221202
012101212121012121210121212102
211101112111011121110111211102
212101212121012121210121212102
000000000000000000000000000000
000000000022222000000000000000
000000000022222000000000000000
000000000022222000000000000000
000000000000000000000000000000

Example 3

(H, W, T, B) = (9, 7, 3, 2)

Input sheet
20000000000000002
00000000000000000
00000000000000000
00000000000000000
00000000000000000
00000000000000000
00000000000000000
00000000000000000
00000000000000000
00000000000000000
00000000200000000
00000000000000000
00000000000000000
00000000000000000
00000000000000000
00000000000000000
00000000000000000
00000000000000000
00000000000000000
02000000000000000
20000000000000002
Output sheet
20000000000000002
00111110001111100
01111111011111110
01111111011111110
01110111011101110
01111111011111110
01111111011111110
01111111011111110
01110111011101110
01110111011101110
00000000200000000
00000000001111100
00000000011111110
00000000011111110
00000000011101110
00000000011111110
00000000011111110
00000000011111110
00000000011101110
02000000011101110
20000000000000002

The task

Create file main.py containing function print_glyphs with 5 parameters: h, w, t, b, matrix (in this particular order). Parameters h, w, t, b describes the glyph and matrix represents the printing sheet which may contain impurities. Tile the sheet with glyphs described by the given tuple, and output the sheet.

Input

Matrix describing printing sheet is standard Python 2D matrix (list of lists). An empty pixel in printing sheet is described by value 0, a pixel with impurity is described by value 2. To guarantee that there is always the central "hole" above the horizontal bar in the glyph, and that the lowermost part of the horizontal bar is higher than the lowermost part of both vertical legs of the glyph following rules apply:
   1 ≤ T < min((H−1)/2, W/2);    1 ≤ B ≤ H−(2×T+1).

Output

Each pixel of the glyph is represented by value 1. An empty pixel is represented by value 0, a pixel with impurity is represented by value 2.

Evaluation

Your code will be evaluated on 8×2 test cases. Each of the 8 test cases (listed bellow) will grant you 0.75 points if both randomly generated tests pass.

Test case min_size (R/C) max_size (R/C) contains impurities timeout
1 8 10 ❌ 4 s
2 16 20 ✅ 8 s
3 32 40 ❌ 12 s
4 64 80 ✅ 16 s
5 128 160 ❌ 20 s
6 256 320 ✅ 24 s
7 512 640 ❌ 28 s
8 987 1000 ✅ 32 s
note: the entire output of the evaluation will not be displayed due to BRUTE's output file size limit.

Starter Code

Below is a basic code structure you can use. Note that example in the function docstring is identical as Example 2 which was described above. Copy-paste the following code and complete the print_glyphs function according to the description above. Then submit your final main.py. 

def print_glyphs(h, w, t, b, m):
	"""
	>>> sheet = [
	... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
	... [0, 2, 0, 2, 0, 2, 0, 2, 2, 2, 0, 2, 0, 2, 0, 2, 2, 2, 0, 2, 0, 2, 0, 2, 2, 2, 0, 2, 0, 2],
	... [0, 0, 2, 0, 0, 0, 2, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 2, 0, 0, 2],
	... [2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 2],
	... [2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 2, 0, 0, 2],
	... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
	... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
	... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
	... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
	... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	... ]
	>>> printed = [
	... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
	... [0, 2, 1, 2, 0, 2, 1, 2, 2, 2, 1, 2, 0, 2, 1, 2, 2, 2, 1, 2, 0, 2, 1, 2, 2, 2, 1, 2, 0, 2],
	... [0, 1, 2, 1, 0, 1, 2, 1, 2, 1, 2, 1, 0, 1, 2, 1, 2, 1, 2, 1, 0, 1, 2, 1, 2, 1, 2, 1, 0, 2],
	... [2, 1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 1, 0, 2],
	... [2, 1, 2, 1, 0, 1, 2, 1, 2, 1, 2, 1, 0, 1, 2, 1, 2, 1, 2, 1, 0, 1, 2, 1, 2, 1, 2, 1, 0, 2],
	... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
	... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
	... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
	... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
	... [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	... ]
	>>> print_glyphs(4, 3, 1, 1, sheet) == printed
	True
	"""
	pass