Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>First, a couple of helper functions:</p> <pre><code>//count the number of elements matching the head def runLength[T](xs:List[T]) = xs.takeWhile(_ == xs.head).size //pair each element with the number of subsequent occurrences def runLengths[T](row:List[T]) : List[(T,Int)] = row match { case Nil =&gt; Nil case h :: t =&gt; (h, runLength(row)) :: runLengths(t) } //should be optimised for tail-call, but easier to understand this way //sample input: 1,1,2,2,2,3,4,4,4,4,5,5,6 //output: (1,2), (1,1), (2,3), (2,2), (2,1), (3,1), (4,4), (4,3), (4,2), (4,1), (5,2), (5,1), (6,1) </code></pre> <p>This can then be used against each row in the grid:</p> <pre><code>val grid = List( List(0,0,0,0), List(0,1,1,0), List(0,1,1,0), List(0,0,0,0)) val stage1 = grid map runLengths // returns stage1: List[List[(Int, Int)]] = // 0,4 0,3 0,2 0,1 // 0,1 1,2 1,1 0,1 // 0,1 1,2 1,1 0,1 // 0,4 0,3 0,2 0,1 </code></pre> <p>Then having done the horizontal, the rows, we now perform exactly the same operation on the columns. This uses the <code>transpose</code> method available in the Scala standard collection library to exchange rows&lt;->columns, as per the mathematical matrix operation of the same name. We also transpose back once this is done.</p> <pre><code>val stage2 = (stage1.transpose map runLengths).transpose // returns stage2: List[List[((Int, Int), Int)]] = // (0,4),1 (0,3),1 (0,2),1 (0,1),4 // (0,1),2 (1,2),2 (1,1),2 (0,1),3 // (0,1),1 (1,2),1 (1,1),1 (0,1),2 // (0,4),1 (0,3),1 (0,2),1 (0,1),1 </code></pre> <p>What does this mean? Taking one element: <code>(1,2),2</code>, it means that that cell contains the value <code>1</code>, and scanning to the right that there are 2 adjacent cells in the row containing <code>1</code>. Scanning down, there are two adjacent cells with the same property of containing the value <code>1</code> and having the same number of equal values to their right.</p> <p>It's a little clearer after tidying up, converting nested tuples of the form <code>((a,b),c)</code> to <code>(a,(b,c))</code>:</p> <pre><code>val stage3 = stage2 map { _.map {case ((a,b),c) =&gt; a-&gt;(b,c) } } //returns stage3: List[List[(Int, (Int, Int))]] = // 0,(4,1) 0,(3,1) 0,(2,1) 0,(1,4) // 0,(1,2) 1,(2,2) 1,(1,2) 0,(1,3) // 0,(1,1) 1,(2,1) 1,(1,1) 0,(1,2) // 0,(4,1) 0,(3,1) 0,(2,1) 0,(1,1) </code></pre> <p>Where <code>1,(2,2)</code> refers to a cell containing the value <code>1</code>, and being at the top-left corner of a 2x2 rectangle of similarly-valued cells.</p> <p>From here, it's trivial to spot rectangles of the same size. Though a little more work is necessary if you also want to exclude areas that are the subset of a larger rectangle.</p> <p><strong>UPDATE:</strong> As written, the algorithm doesn't work well for cases like the cell at (0,0), which belongs to two distinct rectangles (1x4 and 4x1). If needed, this is also solvable using the same techniques. <em>(do one pass using map/transpose/map/transpose and a second with transpose/map/transpose/map, then zip and flatten the results)</em>.</p> <p>It would also need modifying if the input might contain adjoining rectangles containing cells of the same value, such as:</p> <pre><code>0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 </code></pre> <p>Putting it all together, and cleaning up a little:</p> <pre><code>type Grid[T] = List[List[T]] def runLengths[T](row:List[T]) : List[(T,Int)] = row match { case Nil =&gt; Nil case h :: t =&gt; (h -&gt; row.takeWhile(_ == h).size) :: runLengths(t) } def findRectangles[T](grid: Grid[T]) = { val step1 = (grid map runLengths) val step2 = (step1.transpose map runLengths).transpose step2 map { _ map { case ((a,b),c) =&gt; (a,(b,c)) } } } </code></pre> <h1>UPDATE2</h1> <p><em>Hold onto your hats, this is a big one...</em></p> <p>Before writing a single line of new functionality, we'll first refactor a bit, pulling some of the methods into Ops classes with implicit conversions, so they can be used as though they were methods defined on the underlying collection types:</p> <pre><code>import annotation.tailrec class RowOps[T](row: List[T]) { def withRunLengths[U](func: (T,Int)=&gt;U) : List[U] = { @tailrec def recurse(row:List[T], acc:List[U]): List[U] = row match { case Nil =&gt; acc case head :: tail =&gt; recurse( tail, func(head, row.takeWhile(head==).size) :: acc) } recurse(row, Nil).reverse } def mapRange(start: Int, len: Int)(func: T=&gt;T) = row.splitAt(start) match { case (l,r) =&gt; l ::: r.take(len).map(func) ::: r.drop(len) } } implicit def rowToOps[T](row: List[T]) = new RowOps(row) </code></pre> <p>This adds a <code>withRunLengths</code> method to lists. One notable difference here is that instead of returning a List of <code>(value, length)</code> pairs the method accepts, as a parameter, a function to create an output value for each such pair. This will come in handy later...</p> <pre><code>type Grid[T] = List[List[T]] class GridOps[T](grid: Grid[T]) { def deepZip[U](other: Grid[U]) = (grid zip other) map { case (g,o) =&gt; g zip o} def deepMap[U](f: (T)=&gt;U) = grid map { _ map f} def mapCols[U](f: List[T]=&gt;List[U]) = (grid.transpose map f).transpose def height = grid.size def width = grid.head.size def coords = List.tabulate(height,width){ case (y,x) =&gt; (x,y) } def zipWithCoords = deepZip(coords) def deepMapRange(x: Int, y: Int, w: Int, h: Int)(func: T=&gt;T) = grid mapRange (y,h){ _.mapRange(x,w)(func) } } implicit def gridToOps[T](grid: Grid[T]) = new GridOps(grid) </code></pre> <p>There shouldn't be any surprises here. The <code>deepXXX</code> methods avoid having to write constructs of the form <code>list map { _ map { ... } }</code>. <code>tabulate</code> may also be new to you, but its purpose is hopefully obvious from the use.</p> <p>Using these, it becomes trivial to define functions for finding the horizontal and vertical run lengths over a whole grid:</p> <pre><code>def withRowRunLengths[T,U](grid: Grid[T])(func: (T,Int)=&gt;U) = grid map { _.withRunLengths(func) } def withColRunLengths[T,U](grid: Grid[T])(func: (T,Int)=&gt;U) = grid mapCols { _.withRunLengths(func) } </code></pre> <p>Why 2 parameter blocks and not one? I'll explain shortly.</p> <p>I <em>could</em> have defined these as methods in <code>GridOps</code>, but they don't seem appropriate for general purpose use. Feel free to disagree with me here :)</p> <p>Next, define some input...</p> <pre><code>def parseIntGrid(rows: String*): Grid[Int] = rows.toList map { _ map {_.toString.toInt} toList } val input: Grid[Int] = parseIntGrid("0000","0110","0110","0000") </code></pre> <p>...another useful helper type...</p> <pre><code>case class Rect(w: Int, h: Int) object Rect { def empty = Rect(0,0) } </code></pre> <p><em>as an alternative to a tuple, this really helps with debugging. Deeply nested parenthesis are <strong>not</strong> easy on the eyes. (sorry Lisp fans!)</em></p> <p>...and use the functions defined above:</p> <pre><code>val stage1w = withRowRunLengths(input) { case (cell,width) =&gt; (cell,width) } val stage2w = withColRunLengths(stage1w) { case ((cell,width),height) =&gt; Rect(width,height) } val stage1t = withColRunLengths(input) { case (cell,height) =&gt; (cell,height) } val stage2t = withRowRunLengths(stage1t) { case ((cell,height),width) =&gt; Rect(width,height) } </code></pre> <p>All of the above blocks should be one-liners, but I reformatted for StackOverflow.</p> <p>The outputs at this stage are just grids of Rectangles, I've intentionally dropped any mention of the actual value that the rectangle is comprised of. That's absolutely fine, it's easy enough to find from its co-ordinates in the grid, and we'll be recombining the data in just a brief moment.</p> <p>Remember me explaining that <code>RowOps#withRunLengths</code> takes a function as a parameter? Well, this is where it's being used. <code>case (cell,width) =&gt; (cell,width)</code> is actually a function that takes the cell value and run length (calling them <code>cell</code> and <code>width</code>) then returns the <code>(cell,width)</code> Tuple.</p> <p>This is also why I used two parameter blocks in defining the functions, so the second param can be passed in { braces }, and makes the whole thing all nice and DSL-like.</p> <p>Another <em>very important</em> principle illustrated here is that the type inferencer works on parameter blocks in succession, so for this (remember it?):</p> <pre><code>def withRowRunLengths[T,U](grid: Grid[T])(func: (T,Int)=&gt;U) </code></pre> <p>The type <code>T</code> will be determined by the supplied grid. The compiler then knows the input type for the function supplied as the second argument, - <em><code>Int</code> in this case, as the first param was a <code>Grid[Int]</code></em> - which is why I was able to the write <code>case (cell,width) =&gt; (cell,width)</code> and not have to explicitly state anywhere that <code>cell</code> and <code>width</code> are integers. In the second usage, a <code>Grid[(Int,Int)]</code> is supplied, this fits the closure <code>case ((cell,width),height) =&gt; Rect(width,height)</code> and again, it just works.</p> <p>If that closure had contained anything that wouldn't work for the underlying type of the grid then the compiler would have complained, this is what type safety is all about...</p> <p>Having calculated all the possible rectangles, all that remains is to gather up the data and present it in a format that's more practical for analysing. Because the nesting at this stage could get <em>very</em> messy, I defined another datatype:</p> <pre><code>case class Cell[T]( value: T, coords: (Int,Int) = (0,0), widest: Rect = Rect.empty, tallest: Rect = Rect.empty ) </code></pre> <p>Nothing special here, just a case class with named/default parameters. I'm also glad I had the foresight to define <code>Rect.empty</code> above :)</p> <p>Now mix the 4 datasets (input vals, coords, widest rects, tallest rects), gradually fold into the cells, stir gently, and serve:</p> <pre><code>val cellsWithCoords = input.zipWithCoords deepMap { case (v,(x,y)) =&gt; Cell(value=v, coords=(x,y)) } val cellsWithWidest = cellsWithCoords deepZip stage2w deepMap { case (cell,rect) =&gt; cell.copy(widest=rect) } val cellsWithWidestAndTallest = cellsWithWidest deepZip stage2t deepMap { case (cell,rect) =&gt; cell.copy(tallest=rect) } val results = (cellsWithWidestAndTallest deepMap { case Cell(value, coords, widest, tallest) =&gt; List((widest, value, coords), (tallest, value, coords)) } ).flatten.flatten </code></pre> <p>The last stage is interesting there, it converts each cell to a size-2 list of (rectangle, value, coords) tuples <em>(size 2 because we have both widest and tallest rects for each cell)</em>. Calling flatten twice then takes the resulting <code>List[List[List[_]]]</code> back down to a single <code>List</code>. There's no need to retain the 2D structure any more, as the necessary coordinates are already embedded in the results.</p> <p>Voila!</p> <p>It's now up to you what you now do with this List. The next stage is probably some form of sorting and duplicate removal...</p>
    singulars
    1. This table or related slice is empty.
    1. POHow to find same-value rectangular areas of a given size in a matrix most efficiently?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USKevin Wright
    1. USKevin Wright
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CONope, pure Scala! As per the question...
      singulars
      1. PO
      1. USKevin Wright
    2. COHmmm.... don't know if it's just the Scala plugin for eclipse but it doesn't let me compile it because of this error: "too many arguments for method map2dRowFirst: (grid: HelpersTest.this.Grid[T])(func: (List[T]) => List[T])List[List[T]]" I haven't understood yet what the "2nd" parameter list in map2dRowFirst is good for, I mean in general, not just in your code. Can you shed some light on this?
      singulars
      1. PO
      1. USletmaik
    3. CO@Kevin You wrote that your code would need modifying if the input contains adjoining rectangles. As this is absolutely possible in my case, can you give me a hint on this one?
      singulars
      1. PO
      1. USletmaik
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload