When students are first taught about the proof technique of mathematical induction, a common example is the problem of tiling a 2N×2N grid with L-shaped trominoes, leaving one predetermined grid space empty. (N is some nonnegative integer.)
I will leave it to you to go over the proof if you do not already know it. There are many resources that discuss it.
Your task here is to write a program that takes in a value for N, as well as the coordinates of the grid space to leave empty, and prints an ASCII representation of the resulting tromino tiled grid.
O will fill the empty space, and the 4 rotations of our tromino will look like this:
| +- | -+ -+ | +- |
(Yes, it can be ambiguous which
+ goes with which
| for certain arrangements, but that's ok.)
Your program must work for N = 0 (for a 1×1 grid) up to at least N = 8 (for a 256×256 grid). It will be given x and y values that are the coordinates for the
- x is the horizontal axis. x = 1 is the left grid edge, x = 2N is the right grid edge.
- y is the vertical axis. y = 1 is the top grid edge, y = 2N is the bottom grid edge.
Both x and y are always in the range [1, 2N].
So for a given N, x, and y, your program must print a 2N×2N grid, tiled completely with L-shaped trominoes, except for the x, y grid coordinate which will be an
If N = 0, then x and y must both be 1. The output is simply
If N = 1, x = 1, and y = 2, the output would be
N = 2, x = 3, y = 2:
+--+ ||O| |+-| +--+
N = 2, x = 4, y = 1:
+-|O ||+- |+-| +--+
N = 3, x = 3, y = 6 (e.g. the image on this page):
+--++--+ |+-||-+| ||+--+|| +-|-+|-+ +--+||-+ ||O|-+|| |+-||-+| +--++--+
- You may write a function that takes the 3 integers instead of writing an entire program. It should print or return the grid string.
- Take input from stdin, command line, (or function args if you write function).
- The output may optionally contain a single training newline.
- You are not required to use the tiling method that the proof normally suggests. It only matters that the grid is filled with L-shaped trominoes besides the
O. (Trominoes may not be cut or go out of the grid bounds.)
The shortest code in bytes wins. Tiebreaker is earlier post. (Handy byte counter.)