14
2
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.
The character 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 -
and |
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 O
:
- 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 O
.
Examples
If N = 0, then x and y must both be 1. The output is simply
O
If N = 1, x = 1, and y = 2, the output would be
-+
O|
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|-+||
|+-||-+|
+--++--+
Details
- 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.)
1An impressive first run at Python golfing! Some quick charsaves. You can cut the space before
if p!=i
; the list inside.join()
doesn't need[]
;(1-i%2)
can be done as~i%2
; you can use iterable unpacking to writet,l,a=[],...
as*t,l,a=...
;if n==0
can be checked asif n<1
becausen
can't be negative; the final"\n".join
can probably be done by printing each element, since general rules allow printing in place of returning;if p!=i
can beif p-i
because nonzero values are Truthy. – xnor – 2015-04-21T10:04:26.007@xnor Thanks for the tips! The unpacking to get an implicit empty list is very neat. I use return instead of print as
f
is a recursive function. I actually have to revert the output formatting withsplit()
after every self-call. – randomra – 2015-04-21T11:00:38.047A few more: The last line can be written as
A,B,C,D=t;return'\n'.join(map("".join,zip(A+C,B+D)))
,t+=[...]
on the second-last line can be written ast+=...,
(adding a tuple instead of a list) and I'm not sure if this one works butA if B else C
can be written asB and A or C
(also on the second-last line), but only if A is never falsy (which I don't think it is?) – Sp3000 – 2015-04-21T11:03:52.270