(eratta) I should have written:
... but time and space are proportional to the square of the list of bar lengths ... Sorry about the bad sentence structure. -- Raul On Tue, Jun 20, 2017 at 4:43 PM, Raul Miller <rauldmil...@gmail.com> wrote: > Hmm... maybe I should have just gone out and shown how I approached > the problem... > > (but feel free to hold off on reading this post, or replies to it, if > you are wanting to solve it on your own and you think you understand > the problem description). > > And, perhaps, I should add that that drdobbs writeup is a more general > problem than the one I'm proposed. There you start with a boolean > array, instead of a list of bar lengths. > > So, anyways, we need some kind of representation of which bars are > lower than which other bars. Something like this: > > <:/~2 6 7 4 1 7 > 1 1 1 1 0 1 > 0 1 1 0 0 1 > 0 0 1 0 0 1 > 0 1 1 1 0 1 > 1 1 1 1 1 1 > 0 0 1 0 0 1 > > Next, to calculate area, we'll need to know how high each of those bar > representations are. We can get that by multiplying each length by the > corresponding "relevant height" bits: > > (* <:/~)2 6 7 4 1 7 > 2 2 2 2 0 2 > 0 6 6 0 0 6 > 0 0 7 0 0 7 > 0 4 4 4 0 4 > 1 1 1 1 1 1 > 0 0 7 0 0 7 > > Now we just need to add them up, stopping when we hit a zero. We could > use a rank 1 scan, but since our operation is going to be a bit > complex maybe it makes more sense to work on the transpose of that > array: > > |: (* <:/~)2 6 7 4 1 7 > 2 0 0 0 1 0 > 2 6 0 4 1 0 > 2 6 7 4 1 7 > 2 0 0 4 1 0 > 0 0 0 0 1 0 > 2 6 7 4 1 7 > > Now... when building up a scan, it's worth starting with a > representative pair of arguments and figuring out what operation we > want on them. In other words something to go in the parenthesis, here: > > 0 0 0 0 1 0 () 2 6 7 4 1 7 > > Given our description of adding them up and stopping at zeros, I went > with (+ * *@[) > > 0 0 0 0 1 0 (+ * *@[) 2 6 7 4 1 7 > 0 0 0 0 2 0 > > In other words: > > (+ * *@[)/\. |: (* <:/~)2 6 7 4 1 7 > 8 0 0 0 6 0 > 6 12 0 12 5 0 > 4 6 7 8 4 7 > 2 0 0 4 3 0 > 0 0 0 0 2 0 > 2 6 7 4 1 7 > > We can see all the various rectangle areas here, and we just need to > find the largest: > > >./ , (+ * *@[)/\. |: (* <:/~)2 6 7 4 1 7 > 12 > > Now... that works reasonably well up to a point, but time and space > are proportional to the square length of the list of bar lengths. > > In other words, this is reasonably fast: > > >./ , (+ * *@[)/\. |: (* <:/~) 1000?.1000000 > 7030779 > > ... but this is not so fast: > > >./ , (+ * *@[)/\. |: (* <:/~) 10000?.1000000 > 9694475 > > Anyways, I believe that it should be possible to solve this quite a > bit more quickly, but I have not worked out how yet. > > Thanks, > > -- > Raul > > > On Tue, Jun 20, 2017 at 1:03 PM, Joe Bogner <joebog...@gmail.com> wrote: >> possible spoiler - >> http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529 >> >> At a minimum, it help explains the problem >> >> >> >> On Tue, Jun 20, 2017 at 1:02 PM, Xiao-Yong Jin <jinxiaoy...@gmail.com> >> wrote: >> >>> Brute force: >>> >>> (\:*/"1);<@:((#,<./)\.)\2 6 7 4 1 7 >>> 2 6 >>> 3 4 >>> 4 2 >>> 2 4 >>> 1 7 >>> 1 7 >>> 1 6 >>> 3 2 >>> 6 1 >>> 5 1 >>> 5 1 >>> 2 2 >>> 1 4 >>> 4 1 >>> 4 1 >>> 3 1 >>> 3 1 >>> 1 2 >>> 2 1 >>> 2 1 >>> 1 1 >>> >>> Though the complexity looks like n^3 to me. There must be a more >>> efficient algorithm. >>> >>> > On Jun 20, 2017, at 10:29 AM, Raul Miller <rauldmil...@gmail.com> wrote: >>> > >>> > Something I stumbled over today. >>> > >>> > 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 example: >>> > >>> > '*'#"0~2 6 7 4 1 7 >>> > ** >>> > ****** >>> > ******* >>> > **** >>> > * >>> > ******* >>> > >>> > I'll post a solution later, and I'll be interested in seeing if it's >>> > basically the only obvious approach or if there's a variety of good >>> > approaches. (I have reason to believe, though, that there's a better >>> > way than what I came up with.) >>> > >>> > Thanks, >>> > >>> > -- >>> > Raul >>> > ---------------------------------------------------------------------- >>> > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
