Talk:Cut a rectangle

Zig zags

Do we just want straight cuts here, or are zig zags allowed?

**     ******
****     ****
******     **

The above example is a rectangle cut with a zig zag path. Note that the resultant shapes are not exactly identical, but are mirrored to each other (when rotated). Markhobley 18:21, 9 October 2011 (UTC)

I'd say this is not allowed because of the phrase "along the square edges". --Mwn3d 18:44, 9 October 2011 (UTC)

Right. The zig zag cuts are along the square edges. Maybe we should state a single "straight cut", or something like that. Markhobley 19:11, 9 October 2011 (UTC)

Oh I see what you're talking about now. Those are allowed. No new terminology is necessary. See the middle cut in the bottom row of the example. It actually matches your example perfectly. I thought you meant cutting a square in half diagonally. --Mwn3d 19:25, 9 October 2011 (UTC)

J implementation

I am writing this because so far J is the only implementation for this task. (And this task description was supplied by a non-J programmer -- there is no reason to feel that this task was tailored for J).

Anyways, I thought that perhaps if I showed some of my intermediate results, and described them, it might give some of you something concrete to model your thoughts on, and make other implementations easier.

So:

I start with a rectangle of bits, with one bit set. If you look at the example solutions, you will see that all of them have one corner that is always in one of the two halves. It does not really matter which corner you pick for this purpose.

Once you have a bit rectangle, I develop a concept of "neighboring bits". Here, I have represented "unset bits which are immediately above set bits". Of course, we need to apply that concept in all four rectangular directions (above, below, left, right). And, we need to enumerate all the possibilities. I decided to use a list of "location numbers" to represent all the possible places where an unset bit neighbors a set bit. In other words, given a list of integers filling a rectangle of the desired size:

I can list the bit locations which correspond to a neighboring bit:

Finally, I need to represent the rectangles with these bits set.

<lang j> step init 3 4 0 0 0 0 0 0 0 1 0 0 0 1

0 0 0 0 0 0 0 0 0 0 1 1</lang>

And this gets back to why I was using a bit matrix in the first place -- a bit matrix is a relatively compact representation of an arbitrary way of dividing up a rectangle.

Anyways, once I have this mechanism, I can apply it multiple times (and of course I have code in there to deal with treating each bit matrix independently, and keeping a list of only unique matrices after each step):

<lang j>step step init 3 4 0 0 0 1 0 0 0 1 0 0 0 1

0 0 0 0 0 0 1 1 0 0 0 1

0 0 0 0 0 0 0 1 0 0 1 1

0 0 0 0 0 0 1 0 0 0 1 1

0 0 0 0 0 0 0 0 0 1 1 1</lang>

So, how many times do I need to apply this mechanism?

Basically, I count how many bits are in my rectangle, divide that by 2, and then subtract 1.

Applying this 'step' mechanism that many times is going to give me a lot of possibilities:

But 60 is the number of ways of dividing the rectangle in half -- with one corner guaranteed to be classified the same way, and with a guarantee that all true cells are [transitively] contiguous with each other -- and I only want the options which are symmetric. To test symmetry, I rotate the bit matrix on each axis and then apply logical not to that result -- if that gives me my starting bit matrix, it's a solution that I want.

<lang j> N init 2 3 2

  step step init 2 3

0 1 1 0 0 1

0 0 1 0 1 1

0 1 0 0 1 1

0 0 0 1 1 1

  all 2 3

0 1 1 0 0 1

0 0 1 0 1 1

0 0 0 1 1 1</lang>

Here, the third bit matrix did not have the symmetry I wanted, so I eliminated this one: