The Maximal Rectangle Problem

If you guys can solve the Polybus Square, this should not be a stretch:

http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529

I think it can be used to solve this question:
http://macscripter.net/viewtopic.php?id=40034

Well here’s an AppleScript version of the “Brute Force” solution in the “Dr Dobbs” article. It returns the upper-left and lower-right coordinates of the largest “all ones” rectangle in the grid. If there are more than one with the largest area, the coordinates are for the first one found (nearest the upper left). The script also returns a crude text representation of the grid so you can check the results. The source of the grid is the lower-left corner.

The run-handler code at the bottom of the script generates the grid and you can set your own dimensions there.

(* Given a two-dimensional array (AppleScript 'list') representing a rectangular grid of 0s and 1s, return the upper-left and lower-right cell coordinates of the largest non-oblique rectangular area within it containing only 1s (or the first such found if there's a tie). {1, 1} is the cell at the grid's upper-left corner. The array's subarrays represent rows, so cell {x, y} of the grid is item x of item y of the array.

"Brute Force" method: Calculate the area of every possible subrectangle in the grid and examine the contents of any found to have more cells than the largest all-1s rectangle so far identified.
Based on pseudocode by David Vandervoorde <http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529>. *)

on main(b)
	set M to (count b)
	set N to (count beginning of b)
	
	set best_ulx to 0
	set best_uly to 0
	set best_lrx to -1
	set best_lry to -1
	set best_area to 0
	
	-- Repeat with the "bounds" coordinates of every possible subrectangle in the grid.
	repeat with ulx from 1 to N
		repeat with uly from 1 to M
			repeat with lrx from ulx to N
				repeat with lry from uly to M
					-- If this rectangle's area's larger than that of the largest "all 1s" rectangle so far found, and it contains only 1s itself, keep its coordinates.
					set this_area to area(ulx, uly, lrx, lry)
					if ((this_area > best_area) and (all_ones(b, ulx, uly, lrx, lry))) then
						set best_ulx to ulx
						set best_uly to uly
						set best_lrx to lrx
						set best_lry to lry
						set best_area to this_area
					end if
				end repeat
			end repeat
		end repeat
	end repeat
	
	-- Return the upper-left and lower-right coordinates of the successful rectangle.
	return {upper_left:{best_ulx, best_uly}, lower_right:{best_lrx, best_lry}}
end main

-- Calculate the area of a rectangle from its "bounds" coordinates.
on area(ulx, uly, lrx, lry)
	if ((ulx > lrx) or (uly > lry)) then
		return 0
	else
		return (lrx - ulx + 1) * (lry - uly + 1)
	end if
end area

-- Given the array and a set of "bounds", test to see if the bounded rectangle contains "all 1s" (ie. no 0s).
on all_ones(b, ulx, uly, lrx, lry)
	script o
		property b : {}
	end script
	set o's b to b
	
	repeat with x from ulx to lrx
		repeat with y from uly to lry
			if (item x of item y of o's b is 0) then return false
		end repeat
	end repeat
	
	return true
end all_ones

-- Test stuff:

on makeRectangle(rowCount, columnCount)
	script o
		property b : {}
		property r : {}
	end script
	
	repeat with M from 1 to rowCount
		set o's r to {}
		repeat with N from 1 to columnCount
			set end of o's r to some item of {0, 1} --random number 1
		end repeat
		set end of o's b to o's r
	end repeat
	
	return o's b
end makeRectangle

on makeChart(b)
	copy b to b
	
	set astid to AppleScript's text item delimiters
	set AppleScript's text item delimiters to ""
	repeat with r from 1 to (count b)
		set item r of b to (item r of b) as text
	end repeat
	set AppleScript's text item delimiters to linefeed
	set chart to linefeed & (b as text)
	set AppleScript's text item delimiters to astid
	
	return chart
end makeChart

local M, N, b

set M to 16 -- Number of rows.
set N to 12 -- Number of columns.
set b to makeRectangle(M, N)

{main(b), makeChart(b)}

Edit: Grid origin changed from lower-left to upper-left corner and other, cosmetic edits to match the later scripts below.

Hi Nigel. As always, awesome script … thank you. I am trying to find the best way to determine the largest empty rectangle to place a new window in, given the bounds and positions of the currently open windows. I found this script to determine the screen size:

set {W, H} to {word 3 of (do shell script "defaults read /Library/Preferences/com.apple.windowserver | grep -w Width") as number, word 3 of (do shell script "defaults read /Library/Preferences/com.apple.windowserver | grep -w Height") as number}

Adding a zero to M, N in the brute force method slows it down considerably. I am starting to doubt that it will be able to handle numbers such as 1920 x 1200. Do you have any ideas for a faster algorithm that would be able to exclude chunks of coordinates supplied to it via window properties?

tell application "Finder" to set {winBounds, winPos} to {bounds, position} of window 1

Hi John.

The script in post #2 is just an AppleScript transcription of the article’s Pseudocode for how not to do it! :wink: I hope at more leisure to work through the rest of the article and work out what the Pseudocode in the later examples actually means. Presumably those algorithms will prove faster.

I’m not specifically thinking in terms of your other query. For that, you’d need first to map the existing “occupied” and “free” pixels to a two-dimensional array representing the screen, which could take a while. You’d also need to modify the “largest rectangle” goal used here to “largest usably-shaped rectangle.”

Look here further

Hey chaps.

Could we discuss windows in adayzone’s other thread “Position window at largest unused space”, specifically started for that purpose? Whatever his ulterior motive for starting this one, it is specifically titled and phrased as a “Maximal Rectangle” challenge.

Thanks, fellas. You’ve done great job of “moving house”. It seems a little echoey in this thread now… :wink:

Sorry I’ve been a while getting back. My attention’s been required elsewhere for the past few days.

I’ve now done AppleScript versions of the three “better algorithm” pseudocode examples in the David Vandervoorde article to which adayzdone linked in post #1. In case anyone wants to compare the scripts with the pseudocode, I’ve named them after the relevant section headings in the article and kept the variable names as similar as possible to the originals. However, this isn’t ideal if you’re trying to understand the scripts in their own right. To add to the confusion, a couple of the pseudocode examples appear to have bugs and there’s an HTML intrusion in one of them!

The origin in Vandervoorde’s grid is the cell in the lower left corner and he uses zero-based numbering. My grid begins in the upper left corner and, since we’re numbering cells, not offsets, the coordinates are one-based. Thus, in a grid with N columns and M rows (like Vandervoorde’s), the cell in the top left corner is {1, 1} and that in the bottom right corner is {N, M}. In the two-dimensional array representing the grid, the subarrays are equivalent to rows, so item x of item y of the array represents cell x of row y of the grid, whose coordinates are {x, y}.

All the scripts below contain the same “set-up and test” code, which is why they’re so long.

The aim is to find the largest rectangle of 1s in a grid containing only 1s and 0s.

Brute Force: The deliberately simplistic and inefficient method reproduced in post #2 above. It individually calculates the area of every possible rectangle in the grid! Any which has more cells than the largest all-1s rectangle so far identified is examined to see if it too contains only 1s. If it does, it becomes the front runner. The script returns the coordinates of the winning rectangle or, in the event of a tie, of the first joint-winner found.

Adding Direction: A more directed search than the Brute Force method and visibly faster, even with the small grid used here. At every cell in the grid, the grow_ones() handler is called to “grow” the largest possible all-1s rectangle(s) to the right and downwards, depending on the availability of 1s in those directions. Its inner loop tests for consecutive 1s along the rows, the search being restricted by the variable x_max to columns whose vertical growth is so far uninterrupted. The limit is further tightened if a zero turns up in it, effectively ending the growth of a wider rectangle but continuing the downward growth of a narrower one. Since the wider rectangle or a later narrower one could turn out to be the largest, the current area is calculated at the end of every row sweep and the lower-right coordinates of the largest so far are kept as a “best”. Downward growth stops when there’s a zero in the growth area’s leftmost column ” which of course means there’s no growth at all if there’s a zero in the start cell. The best area from each call of the handler is compared with the best from all the other calls.

(* "Adding Direction" method: Starting from each position in the grid, "grow" the largest possible all-1s rectangle to the right and downwards. 
Based on pseudocode by David Vandervoorde <http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529>. *)

on main(b)
	set M to (count b)
	set N to (count beginning of b)
	
	set best_ulx to 0
	set best_uly to 0
	set best_lrx to -1
	set best_lry to -1
	set best_area to 0
	
	-- Repeat with every cell in the grid, traversing columns from top to bottom, left to right.
	repeat with ulx from 1 to N
		repeat with uly from 1 to M
			-- Grow the largest possible "all 1s" rectangle using this cell as the upper-left corner. If its area's larger than that of the largest "all 1s" rectangle so far obtained, keep its coordinates.
			set {lrx, lry} to grow_ones(b, ulx, uly) -- Lower-right coordinates returned.
			set this_area to area(ulx, uly, lrx, lry)
			if (this_area > best_area) then
				set best_ulx to ulx
				set best_uly to uly
				set best_lrx to lrx
				set best_lry to lry
				set best_area to this_area
			end if
		end repeat
	end repeat
	
	-- Return the upper-left and lower-right coordinates of the successful rectangle.
	return {upper_left:{best_ulx, best_uly}, lower_right:{best_lrx, best_lry}}
end main

-- Calculate the area of a rectangle from its "bounds" coordinates.
on area(ulx, uly, lrx, lry)
	if ((ulx > lrx) or (uly > lry)) then
		return 0
	else
		return (lrx - ulx + 1) * (lry - uly + 1)
	end if
end area

-- "Grow" the largest possible "all 1s" rectangle whose upper-left corner is {ulx, uly} in the grid.
on grow_ones(b, ulx, uly)
	script o
		property b : {}
	end script
	set o's b to b
	
	-- Initialise the lower-right coordinates to give an effective area of 0.
	set lrx to ulx - 1
	set lry to uly - 1
	-- Initialise a right limit for the rectangle to the right edge of the grid.
	set x_max to (count beginning of b)
	
	-- Try successive rows, aiming for the bottom of the grid.
	repeat with y from uly to (count b)
		-- End if the prospective rectangle's left column has a 0 in this row.
		if (item ulx of item y of o's b is 0) then exit repeat
		-- Otherwise try the succeeding cells in this row, aiming for the current right limit. If there's a 0 before the limit, we've hit a new limit. Update the limit variable and finish with this row.
		repeat with x from ulx + 1 to x_max
			if (item x of item y of o's b is 0) then
				set x_max to x - 1
				exit repeat
			end if
		end repeat
		
		-- If the rectangle now defined has a greater area than the previous largest grown from the given upper-left corner, keep the lower-right coordinates.
		if (area(ulx, uly, x_max, y) > area(ulx, uly, lrx, lry)) then
			set lrx to x_max
			set lry to y
		end if
	end repeat
	
	-- Return the finally decided lower-right coordinates.
	return {lrx, lry}
end grow_ones

-- Test stuff:

on makeRectangle(rowCount, columnCount)
	script o
		property b : {}
		property r : {}
	end script
	
	repeat with M from 1 to rowCount
		set o's r to {}
		repeat with N from 1 to columnCount
			set end of o's r to some item of {0, 1}
		end repeat
		set end of o's b to o's r
	end repeat
	
	return o's b
end makeRectangle

on makeChart(b)
	copy b to b
	
	set astid to AppleScript's text item delimiters
	set AppleScript's text item delimiters to ""
	repeat with r from 1 to (count b)
		set item r of b to (item r of b) as text
	end repeat
	set AppleScript's text item delimiters to linefeed
	set chart to linefeed & (b as text)
	set AppleScript's text item delimiters to astid
	
	return chart
end makeChart

local M, N, b

set M to 16 -- Number of rows.
set N to 12 -- Number of columns.
set b to makeRectangle(M, N)

{main(b), makeChart(b)}

Remember!: The same basic idea as in “Adding Direction”, but with more efficient horizontal growth. In “Adding Direction”, since the main handler’s outer repeat advances the start point through the columns from left to right, and grow_ones()'s inner repeat too iterates over 1s from left to right to find out where they end, many of the same 1s are iterated over several times. “Remember!” gets round this by advancing the start point from the right instead and remembering how many 1s it passes in each run of them on the way. The remembering is done with a “cache” of values, one for each row, which are updated at the beginning of each iteration of the outer column repeat. grow_ones() then simply reads the relevant values from the cache instead of repeatedly pacing them out with an inner repeat.

For the sake of elitism and showing off, the cache in this script comes in a script object with its own handlers for intialisation, updating, and retrieval of values.

A side-effect of having the outer column repeat advancing from the right is that where there are more than one rectangle with the largest area, the first one found ” and thus returned by the script ” isn’t usually the one it would have been otherwise. Vandervoorde could have kept the outer loop as it was and grown the rectangles to the left instead; but he didn’t and I haven’t either in this script.

(* "Remember!" method: Like "Adding Direction", but using a cache of counters to "remember" how many contiguous 1s extend to the right in every row from the current column.
Based on pseudocode by David Vandervoorde <http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529>. *)

on main(b)
	script o
		property b : {}
	end script
	
	script cache
		property c : {}
		
		on initialise(M)
			repeat M times
				set end of my c to 0
			end repeat
		end initialise
		
		on update(x)
			-- Where cells in column x of the grid contain 1, increment the cache's counters for those rows. Otherwise set the counters to 0.
			repeat with y from 1 to (count o's b)
				if (item x of item y of o's b is 1) then
					set item y of my c to (item y of my c) + 1
				else
					set item y of my c to 0
				end if
			end repeat
		end update
		
		on retrieve(y)
			return item y of my c
		end retrieve
	end script
	
	set M to (count b)
	set N to (count beginning of b)
	
	set best_ulx to 0
	set best_uly to 0
	set best_lrx to -1
	set best_lry to -1
	set best_area to 0
	
	set o's b to b
	tell cache to initialise(M)
	
	-- Repeat with every column in the grid, from right to left.
	repeat with ulx from N to 1 by -1
		-- Increment or zero the cache values according to the 1s and 0s in this column.
		tell cache to update(ulx)
		-- Repeat with every cell in this column, from top to bottom.
		repeat with uly from 1 to M
			-- Grow the largest possible "all 1s" rectangle using this cell as the upper-left corner. If its area's larger than that of the largest "all 1s" rectangle so far obtained, keep its coordinates.
			set {lrx, lry} to grow_ones(o, ulx, uly, cache) -- Lower-right coordinates returned.
			set this_area to area(ulx, uly, lrx, lry)
			if (this_area > best_area) then
				set best_ulx to ulx
				set best_uly to uly
				set best_lrx to lrx
				set best_lry to lry
				set best_area to this_area
			end if
		end repeat
	end repeat
	
	-- Return the upper-left and lower-right coordinates of the successful rectangle.
	return {upper_left:{best_ulx, best_uly}, lower_right:{best_lrx, best_lry}}
end main

-- Calculate the area of a rectangle from its "bounds" coordinates.
on area(ulx, uly, lrx, lry)
	if ((ulx > lrx) or (uly > lry)) then
		return 0
	else
		return (lrx - ulx + 1) * (lry - uly + 1)
	end if
end area

-- "Grow" the largest possible "all 1s" rectangle whose upper-left corner is {ulx, uly} in the grid.
-- This version grows rectangles to the right by adding run lengths from the "memory" cache instead of testing for 1s itself.
on grow_ones(o, ulx, uly, cache)
	-- Initialise the lower-right coordinates to give an effective area of 0.
	set lrx to ulx - 1
	set lry to uly - 1
	-- Set a limit for the rectangle's right edge, initiauly the right edge of the grid.
	set x_max to (count beginning of o's b)
	
	-- Try successive rows, aiming for the bottom of the grid.
	repeat with y from uly to (count o's b)
		-- End if the prospective rectangle's left column has a 0 in this row.
		if (item ulx of item y of o's b is 0) then exit repeat
		-- Otherwise calculate the rectangle's rightmost limit as from this row. It's the smaller out of (left column + number of available 1s - 1) and (current limit).
		set x_max to min(ulx + (cache's retrieve(y)) - 1, x_max)
		
		-- If the rectangle now defined has a greater area than the previous largest grown from the given upper-left corner, keep the lower-right coordinates.
		if (area(ulx, uly, x_max, y) > area(ulx, uly, lrx, lry)) then
			set lrx to x_max
			set lry to y
		end if
	end repeat
	
	-- Return the finally decided lower-right coordinates.
	return {lrx, lry}
end grow_ones

-- Get the lower of two values.
on min(a, b)
	if (b < a) then
		return b
	else
		return a
	end if
end min

-- Test stuff:

on makeRectangle(rowCount, columnCount)
	script o
		property b : {}
		property r : {}
	end script
	
	repeat with M from 1 to rowCount
		set o's r to {}
		repeat with N from 1 to columnCount
			set end of o's r to some item of {0, 1}
		end repeat
		set end of o's b to o's r
	end repeat
	
	return o's b
end makeRectangle

on makeChart(b)
	copy b to b
	
	set astid to AppleScript's text item delimiters
	set AppleScript's text item delimiters to ""
	repeat with r from 1 to (count b)
		set item r of b to (item r of b) as text
	end repeat
	set AppleScript's text item delimiters to linefeed
	set chart to linefeed & (b as text)
	set AppleScript's text item delimiters to astid
	
	return chart
end makeChart

local M, N, b

set M to 16 -- Number of rows.
set N to 12 -- Number of columns.
set b to makeRectangle(M, N)

{main(b), makeChart(b)}

Exploiting Structure: Because it’s called at every cell in every column, the modified grow_ones() handler in “Remember!” still has the “overlapping search” inefficiency in the downward direction. And it will often superfluously grow and compare rectangles which can’t possibly be the largest in the grid because they’re wholly contained by rectangles already grown from further up the column.

“Exploiting Structure” dispenses with the grow_ones() capsule altogether and instead uses the cache from “Remember!” as a profile of the available rectangle widths all the way down the column. It traverses this profile and only does anything where consecutive widths differ.

A greater width obviously indicates the beginning of a wider rectangle. The row number in which this occurs and the previous width are pushed onto a “stack” for later reference.

A lesser width occurs in the row after one or more wider rectangles end. In this case, the most recent {row number, width} pairs are popped in succession from the stack and used in conjuction with the current column position to calculate the area(s) of the just closed rectangle(s). These areas are compared directly with that of the current front-running rectangle in the grid. The pop/compare process continues all the time the popped widths are greater than the current one. If the final popped width turns out to be less than the current one, it’s pushed back onto the stack for when that narrower rectangle ends later.

Because the popping process is activated on the row beneath a wider rectangle, the cache here has an extra value of zero at the end to represent a notional empty row beneath any rectangles sitting on the bottom of the grid.

As with the cache, I’ve implemented the stack as a script object with its own handers. Only three small adjustments were needed to convert this script to left->right operation, so I’ve implemented that here. The cached values are therefore the numbers of 1s to the left of the current column.

(* "Exploiting Structure" method: Traverse a cache similar to "Remember!"'s using a stack to record each row in which the width of remembered 1s is more than in the preceding row and, along with it, the width in the preceding row. Only compare areas when the corresponding width decreases are encountered.
Based on pseudocode by David Vandervoorde <http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529>. *)

on main(b)
	script o
		property b : {}
	end script
	
	script cache
		property c : {}
		
		on initialise(M)
			repeat M times
				set end of my c to 0
			end repeat
		end initialise
		
		on update(x)
			-- Where cells in column x of the grid contain 1, increment the cache's counters for those rows. Otherwise set the counters to 0.
			repeat with y from 1 to (count o's b)
				if (item x of item y of o's b is 1) then
					set item y of my c to (item y of my c) + 1
				else
					set item y of my c to 0
				end if
			end repeat
		end update
		
		on retrieve(y)
			return item y of my c
		end retrieve
	end script
	
	script stack
		property s : {}
		
		on push(val)
			set beginning of my s to val
		end push
		
		on pop()
			set val to beginning of my s
			set s to rest of my s
			return val
		end pop
	end script
	
	set M to (count b)
	set N to (count beginning of b)
	
	set best_ulx to 0
	set best_uly to 0
	set best_lrx to -1
	set best_lry to -1
	set best_area to 0
	
	set o's b to b
	-- We need to overrun the last row in each column to notice the bottom edges of any rectangles there and trigger the area comparisons, so we need an additional, unchanging 0 in the cache.
	tell cache to initialise(M + 1)
	
	-- Repeat with every column in the grid, from left to right.
	repeat with x from 1 to N -- N to 1 by -1
		-- Increment or zero the cache values according to the 1s and 0s in this column.
		tell cache to update(x)
		-- Initialise a "current rectangle width" variable.
		set width to 0
		-- Repeat with every value in the cache (the rectangle widths for every row in this column from top to bottom plus the additional "no 1s" end marker).
		repeat with y from 1 to M + 1
			-- Retrieve the cached width value for this row.
			tell cache to set cy to retrieve(y)
			if (cy > width) then -- Wider rectangle entered.
				-- Push the row number and previous width onto the stack. Note the new current width.
				tell stack to push({y, width})
				set width to cy
			else if (cy < width) then -- One or more overlapping wider rectangles egressed.
				-- Pop the start-row number and previous width for each one from the stack, calculate its area, and keep its coordinates if it's larger than the largest so far. Stop after the popped width stops being larger than the current one.
				repeat while (cy < width)
					tell stack to set {y0, w0} to pop()
					if (width * (y - y0) > best_area) then
						set best_ulx to x - width + 1 -- x
						set best_uly to y0
						set best_lrx to x -- x + width - 1
						set best_lry to y - 1
						set best_area to area(best_ulx, best_uly, best_lrx, best_lry)
					end if
					set width to w0
				end repeat
				-- If the popped width is LESS than the current one, push the popped data back onto the stack.
				if (width < cy) then
					tell stack to push({y0, width})
					set width to cy
				end if
			end if
		end repeat
	end repeat
	
	-- Return the upper-left and lower-right coordinates of the successful rectangle.
	return {upper_left:{best_ulx, best_uly}, lower_right:{best_lrx, best_lry}}
end main

-- Calculate the area of a rectangle from its "bounds" coordinates.
on area(ulx, uly, lrx, lry)
	if ((ulx > lrx) or (uly > lry)) then
		return 0
	else
		return (lrx - ulx + 1) * (lry - uly + 1)
	end if
end area

-- Test stuff:

on makeRectangle(rowCount, columnCount)
	script o
		property b : {}
		property r : {}
	end script
	
	repeat with M from 1 to rowCount
		set o's r to {}
		repeat with N from 1 to columnCount
			set end of o's r to some item of {0, 1}
		end repeat
		set end of o's b to o's r
	end repeat
	
	return o's b
end makeRectangle

on makeChart(b)
	copy b to b
	
	set astid to AppleScript's text item delimiters
	set AppleScript's text item delimiters to ""
	repeat with r from 1 to (count b)
		set item r of b to (item r of b) as text
	end repeat
	set AppleScript's text item delimiters to linefeed
	set chart to linefeed & (b as text)
	set AppleScript's text item delimiters to astid
	
	return chart
end makeChart

local M, N, b

set M to 16 -- Number of rows.
set N to 12 -- Number of columns.
set b to makeRectangle(M, N)

{main(b), makeChart(b)}

Now to catch up on that other thread… :slight_smile:

Nigel, awesome post! I forgot to mention lower-left should be replaced with top-left but of course you picked up on it.

Do you think the Exploiting Structure" method can produce a third solution ?
http://macscripter.net/viewtopic.php?pid=159285#p159285