Based on an idea from Mike Day (off-forum) I have come up with the following
approach that could be extended to produce a correct solution, but it will only
work as long as there are no over- or underhanging or regions.
Anyone have an approach that will handle those cases too?
tst1=: _99&".;._2 (0 : 0)
0 0 0 1 1 1
0 0 0 0 0 0
1 1 1 0 0 0
0 0 0 1 1 1
0 0 0 1 1 1
1 1 1 0 0 0
1 1 1 0 0 0
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 0 0 1 1 1
0 0 0 1 1 1
)
firstones=: > 0: , }:
lastones=: > 0: ,~ }.
tl=: (firstones *. firstones"1) NB. topleft
br=: (lastones *. lastones"1) NB. bottomright
indices=: (1 , {:@$) *"1 [: (<. ,. 1&|) {:@$ %~ [: I. ,
NB. gets row,.col indices of 1s in a table
indices tl tst1 NB. list row,.col indices of top left of blocks
0 3
2 0
3 3
5 0
indices br tst1 NB. list row,.col indices of bottom right of blocks
0 5
2 2
4 5
11 5
The first three blocks are OK, however the last block (has over- and
underhanging regions) isn't correct.
lbls=: ('firstones';'lastones';'firstones"1';'lastones"1')
lbls,:(firstones;lastones;firstones"1;lastones"1) tst1
+-----------+-----------+-----------+-----------+
|firstones |lastones |firstones"1|lastones"1 |
+-----------+-----------+-----------+-----------+
|0 0 0 1 1 1|0 0 0 1 1 1|0 0 0 1 0 0|0 0 0 0 0 1|
|0 0 0 0 0 0|0 0 0 0 0 0|0 0 0 0 0 0|0 0 0 0 0 0|
|1 1 1 0 0 0|1 1 1 0 0 0|1 0 0 0 0 0|0 0 1 0 0 0|
|0 0 0 1 1 1|0 0 0 0 0 0|0 0 0 1 0 0|0 0 0 0 0 1|
|0 0 0 0 0 0|0 0 0 1 1 1|0 0 0 1 0 0|0 0 0 0 0 1|
|1 1 1 0 0 0|0 0 0 0 0 0|1 0 0 0 0 0|0 0 1 0 0 0|
|0 0 0 0 0 0|0 0 0 0 0 0|1 0 0 0 0 0|0 0 1 0 0 0|
|0 0 0 1 1 1|0 0 0 0 0 0|1 0 0 0 0 0|0 0 0 0 0 1|
|0 0 0 0 0 0|0 0 0 0 0 0|1 0 0 0 0 0|0 0 0 0 0 1|
|0 0 0 0 0 0|1 1 1 0 0 0|1 0 0 0 0 0|0 0 0 0 0 1|
|0 0 0 0 0 0|0 0 0 0 0 0|0 0 0 1 0 0|0 0 0 0 0 1|
|0 0 0 0 0 0|0 0 0 1 1 1|0 0 0 1 0 0|0 0 0 0 0 1|
+-----------+-----------+-----------+-----------+
---Sherlock, Ric wrote:
> tsta is a boxed table(matrix) of mixed numeric and literal type
>
> ischar=: 3!:0 e. 2 131072"_
> tst1=: ischar &> tsta NB. Mask of boxed literals in tsta
>
> NB. Below is an example tst1 for copying into a session.
> tst1=: _99&".;._2 (0 : 0)
> 0 0 0 1 1 1
> 0 0 0 0 0 0
> 1 1 1 0 0 0
> 0 0 0 1 1 1
> 0 0 0 1 1 1
> 1 1 1 0 0 0
> 1 1 1 0 0 0
> 1 1 1 1 1 1
> 1 1 1 1 1 1
> 1 1 1 1 1 1
> 0 0 0 1 1 1
> 0 0 0 1 1 1
> )
>
> The problem is to specify the blocks of ones in the table.
> A block is specified by the position of its top left member
> and its shape.
...
> Obviously there are other ways to organise the blocks of ones
> in tst1. A solution is correct as long as all ones in tst1
> are included in one and only one block. Solutions that
> produce fewer blocks are better provided they don't take much
> longer to find the minimum number of blocks.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
