Below is my solution, which seems to work on your data, and up to 10000
random rows of maximum length 20 on my phone.
if your data is large, there is probably a lot to be gained by eliminating
zeros due to padding in the matrix returned by m.
sol returns the solution(s) as: width, height, starting row of the rectangle
I'm curious to see other solutions.
NB. maximum surface rectangle
'*'#"0~ l=:2 6 7 4 1 7
NB. matrices of surface and widths
NB. rows= number of rows combined
NB. columns= starting row of rectangle
m=:(>:@i.@# ([(],:*)<./\) ])
NB. get sparse with values indicating
NB. row length, first dim how many rows
second dim starting row where the surface is maximal
s=:([: $. {. * (=>./@,)@{:)
NB. format: combine widths with heights and
NB. starting row:
fmt=: (5&$. ,. 1 0(+"1) 4&$.)
NB. all together
sol=: fmt@s@m
sol l
NB. Best regards,
NB. Jan-Pieter
On 20 Jun 2017 17:42, "Raul Miller" <[email protected]> wrote:
> Actually, the area of the rectangle I am looking for in that data set
> is 12, where the area of the rectangle you proposed is 42. Despite how
> famous 42 is as an answer, that rectangle includes empty spaces, so
> it's an answer which I have rejected.
>
> I hope this helps.
>
> Thanks,
>
> --
> Raul
>
> On Tue, Jun 20, 2017 at 11:39 AM, robert therriault
> <[email protected]> wrote:
> > I think that you are asking for a rectangle that would enclose all of
> the *'s minimally. So that there would be spaces within the rectangle but
> none more than necessary.
> >
> > I would use something like this:
> >
> > '*'#"0~2 6 7 4 1 7
> > **
> > ******
> > *******
> > ****
> > *
> > *******
> > ('o' $~ # , >./) 2 6 7 4 1 7
> > ooooooo
> > ooooooo
> > ooooooo
> > ooooooo
> > ooooooo
> > ooooooo
> >
> > Cheers, bob
> >
> >> On Jun 20, 2017, at 8:29 AM, Raul Miller <[email protected]> wrote:
> >>
> >> If we have a series of bars of varying height, what's the largest
> >> rectangle that can be drawn over the bars without covering any empty
> >> space.
> >
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
