Very nice. Though I must admit I would be tempted to rephrase things slightly:
nsqr=: [ * maxbitlen@ceilpos"0 1~ maxsqr=: >./@(nsqr ~.) That said, the speed difference seems to be inconsequential. Also perhaps worth noting that using deal instead of roll to generate the sample set is probably the worst case for this approach (and yours is still noticeably faster than mine). Thanks, -- Raul On Wed, Jun 21, 2017 at 6:10 AM, Danil Osipchuk <[email protected]> wrote: > I believe this problem requires checking every possible height of the > rectangle. I've come up with something like below, that seems to be an > improvement: > > 6!:2 'a =: maxsq arr' > 0.860414 > 6!:2 'b =: >./,(+**@[)/\.|:(*<:/~) arr' > 4.47701 > a -: b > 1 > > NB. maxsq: find the maximum square over the set of each unique height > NB. nsq: max square of height x: mark positions where the height exceeds > the value, determine the maximum length of uninterrupted sequence by > subtracting adjacent positions, get square by multiplying to the height > chosen > > > ceilpos =: ceilpos =: 0: , (I.@:>) , (#@:]) > maxbitlen =: 13 : '<: >./ 2-~/\y' > nsq =: ([* maxbitlen@:ceilpos)"0 1 > maxsq =: ([:>./ ~.nsq])f. > > arr =: 10000?.1000000 > > > 2017-06-20 23:43 GMT+03:00 Raul Miller <[email protected]>: > >> 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 <[email protected]> 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 <[email protected]> >> > 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 <[email protected]> >> 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 >> > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
