Talk:Cut a rectangle: Difference between revisions
Content added Content deleted
(J: update comments for new version) |
|||
Line 44: | Line 44: | ||
<lang j> poss init 3 4 |
<lang j> poss init 3 4 |
||
7 10</lang> |
7 10</lang> |
||
And then I discard asymmetric neighbors. In other words: I remove from the list of neighbor locations for a bit matrix which correspond to the maximum location value minus a location value which is already set in that bit matrix. |
|||
Finally, I need to represent the rectangles with these bits set. |
Finally, I need to represent the rectangles with these bits set. |
||
Line 91: | Line 93: | ||
<lang j> $ step step step step step init 3 4 |
<lang j> $ step step step step step init 3 4 |
||
9 3 4</lang> |
|||
But 60 is the number of ways of dividing the rectangle in half -- with one corner guaranteed to always be classified the same way, and also with a guarantee that all cells classified that way are [transitively] contiguous with each other -- but 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 |
<lang j> N init 2 3 |
||
2 |
2 |
||
step step init 2 3 |
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 1 1 |
||
0 0 1 |
0 0 1 |
||
Line 119: | Line 107: | ||
1 1 1</lang> |
1 1 1</lang> |
||
(Note: the bulk of the following discussion relates to an earlier version of this code. I've left them here for completeness, but they are only indirectly relevant to the current implementation.) |
|||
Here, the third bit matrix did not have the symmetry I wanted, so I eliminated this one: |
|||
<lang j>0 1 0 |
|||
0 1 1</lang> |
|||
: Two thoughts: |
: Two thoughts: |
||
:* Instead of using a two-state matrix (marked/unmarked), how about using a tri-state one (unmarked/side one/side two)? Every time you mark a cell "side one", also mark its diagonal opposite "side two"; while looking for new neighbors, only pick unmarked cells. This way, when you finish N/2 steps, you are garanteed a symmetric solution, no need to throw out asymmetric combinations. |
:* Instead of using a two-state matrix (marked/unmarked), how about using a tri-state one (unmarked/side one/side two)? Every time you mark a cell "side one", also mark its diagonal opposite "side two"; while looking for new neighbors, only pick unmarked cells. This way, when you finish N/2 steps, you are garanteed a symmetric solution, no need to throw out asymmetric combinations. |
||
Line 131: | Line 117: | ||
::Anyways thank you for the suggestions -- if we are dealing with large rectangles, I believe the win for testing for symmetry at every step would outweigh its additional computational cost. And I do not have to use a tri-state representation for that -- I just need to test that the new bit's reflected position does not overlap an existing bit. --[[User:Rdm|Rdm]] 11:27, 13 October 2011 (UTC) |
::Anyways thank you for the suggestions -- if we are dealing with large rectangles, I believe the win for testing for symmetry at every step would outweigh its additional computational cost. And I do not have to use a tri-state representation for that -- I just need to test that the new bit's reflected position does not overlap an existing bit. --[[User:Rdm|Rdm]] 11:27, 13 October 2011 (UTC) |
||
::: Tracking the path can still be done with your bit matrix, albeit its size should be (m+1) x (n+1) now. The advantage is it will never produce duplicate solutions, and due to symmetry, you'll only need to search in half or a quarter (if m = n) of the solution space. --[[User:Ledrug|Ledrug]] 14:41, 13 October 2011 (UTC) |
::: Tracking the path can still be done with your bit matrix, albeit its size should be (m+1) x (n+1) now. The advantage is it will never produce duplicate solutions, and due to symmetry, you'll only need to search in half or a quarter (if m = n) of the solution space. --[[User:Ledrug|Ledrug]] 14:41, 13 October 2011 (UTC) |
||
:::: I've implemented your suggestion of asymmetric neighbor pruning at each step. I am not quite sure how I would implement the division path approach -- the data structures for that all seem more complex than the bit matrix (and neighbor location) approach I currently use. --[[User:Rdm|Rdm]] 03:22, 14 October 2011 (UTC) |