Сначала пара вспомогательных функций:
//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 => Nil
case h :: t => (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)
Это может быть использовано против каждой строки в сетке:
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
Затем, выполнив горизонтальные строки, теперь мы выполняем точно такую же операцию со столбцами. При этом используется метод transpose, доступный в стандартной библиотеке коллекций Scala, для обмена строками <-> столбцов согласно операции с математической матрицей с тем же именем. Мы также переносим обратно, как только это будет сделано.
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
Что это значит? Взяв один элемент: (1,2),2, это означает, что эта ячейка содержит значение 1, и сканирование вправо, что в строке есть 2 соседние ячейки, содержащие 1. При сканировании вниз есть две соседние ячейки с одинаковым свойством, содержащие значение 1 и имеющие одинаковое количество равных значений справа.
После уборки становится немного понятнее, конвертируя вложенные кортежи вида ((a,b),c) в (a,(b,c)):
val stage3 = stage2 map { _.map {case ((a,b),c) => a->(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)
Где 1,(2,2) относится к ячейке, содержащей значение 1 и находящейся в верхнем левом углу прямоугольника 2x2 с аналогичными по значению ячейками.
Отсюда тривиально определять прямоугольники одинакового размера. Хотя требуется немного больше работы, если вы также хотите исключить области, которые являются подмножеством большего прямоугольника.
ОБНОВЛЕНИЕ: Как написано, алгоритм не работает хорошо для случаев, таких как ячейка в (0,0), которая принадлежит двум разным прямоугольникам (1x4 и 4x1). При необходимости это также можно решить, используя те же методы. (выполните один проход с помощью map / transpose / map / transpose, а второй - с transpose / map / transpose / map, а затем сожмите и сгладьте результаты) .
Также потребуется изменить, если входные данные могут содержать смежные прямоугольники, содержащие ячейки с одинаковым значением, например:
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
Собираем все вместе и убираем немного:
type Grid[T] = List[List[T]]
def runLengths[T](row:List[T]) : List[(T,Int)] = row match {
case Nil => Nil
case h :: t => (h -> 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) => (a,(b,c)) } }
}
UPDATE2
Держись за свои шляпы, это большая ...
Прежде чем написать одну строку новой функциональности, мы сначала немного проведем рефакторинг, перенеся некоторые методы в классы Ops с неявными преобразованиями, чтобы их можно было использовать так, как если бы они были методами, определенными для базовых типов коллекций:
import annotation.tailrec
class RowOps[T](row: List[T]) {
def withRunLengths[U](func: (T,Int)=>U) : List[U] = {
@tailrec def recurse(row:List[T], acc:List[U]): List[U] = row match {
case Nil => acc
case head :: tail =>
recurse(
tail,
func(head, row.takeWhile(head==).size) :: acc)
}
recurse(row, Nil).reverse
}
def mapRange(start: Int, len: Int)(func: T=>T) =
row.splitAt(start) match {
case (l,r) => l ::: r.take(len).map(func) ::: r.drop(len)
}
}
implicit def rowToOps[T](row: List[T]) = new RowOps(row)
Это добавляет withRunLengths метод к спискам. Одно заметное отличие состоит в том, что вместо возврата списка из (value, length) пар метод принимает в качестве параметра функцию для создания выходного значения для каждой такой пары. Это пригодится позже ...
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) => g zip o}
def deepMap[U](f: (T)=>U) = grid map { _ map f}
def mapCols[U](f: List[T]=>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) => (x,y) }
def zipWithCoords = deepZip(coords)
def deepMapRange(x: Int, y: Int, w: Int, h: Int)(func: T=>T) =
grid mapRange (y,h){ _.mapRange(x,w)(func) }
}
implicit def gridToOps[T](grid: Grid[T]) = new GridOps(grid)
Здесь не должно быть никаких сюрпризов. Методы deepXXX позволяют избежать написания конструкций вида list map { _ map { ... } }. tabulate также может быть новым для вас, но, как мы надеемся, его назначение очевидно из использования.
Используя их, становится тривиально определить функции для нахождения длин по горизонтали и вертикали по всей сетке:
def withRowRunLengths[T,U](grid: Grid[T])(func: (T,Int)=>U) =
grid map { _.withRunLengths(func) }
def withColRunLengths[T,U](grid: Grid[T])(func: (T,Int)=>U) =
grid mapCols { _.withRunLengths(func) }
Почему 2 блока параметров, а не один? Я скоро объясню.
Я мог бы определить их как методы в GridOps, но они не подходят для общего использования. Не стесняйтесь не соглашаться со мной здесь:)
Затем определите некоторый вход ...
def parseIntGrid(rows: String*): Grid[Int] =
rows.toList map { _ map {_.toString.toInt} toList }
val input: Grid[Int] = parseIntGrid("0000","0110","0110","0000")
... еще один полезный тип помощника ...
case class Rect(w: Int, h: Int)
object Rect { def empty = Rect(0,0) }
как альтернатива кортежу, это действительно помогает при отладке. Глубоко вложенные скобки не легко для глаз. (извините фанатов Lisp!)
... и используйте функции, определенные выше:
val stage1w = withRowRunLengths(input) {
case (cell,width) => (cell,width)
}
val stage2w = withColRunLengths(stage1w) {
case ((cell,width),height) => Rect(width,height)
}
val stage1t = withColRunLengths(input) {
case (cell,height) => (cell,height)
}
val stage2t = withRowRunLengths(stage1t) {
case ((cell,height),width) => Rect(width,height)
}
Все вышеперечисленные блоки должны быть однострочными, но я переформатировал для StackOverflow.
Выходные данные на этом этапе - просто сетки прямоугольников, я намеренно отбросил любое упоминание о фактическом значении, из которого состоит прямоугольник. Это совершенно нормально, это достаточно просто найти по его координатам в сетке, и мы ненадолго свяжем данные.
Помните, я объяснял, что RowOps#withRunLengths принимает функцию в качестве параметра?Ну, это где он используется.case (cell,width) => (cell,width) на самом деле является функцией, которая принимает значение ячейки и длину выполнения (вызывая их cell и width), а затем возвращает (cell,width) кортеж.
Именно поэтому я использовал два блока параметров вопределяя функции, поэтому второй параметр может быть передан в {фигурные скобки} и делает все это очень красивым и похожим на DSL.
Другой очень важный принцип, проиллюстрированный здесь, заключается в том, чтоInferencer последовательно работает с блоками параметров, поэтому для этого (помните?):
def withRowRunLengths[T,U](grid: Grid[T])(func: (T,Int)=>U)
Тип T будет определяться поставляемой сеткой.Затем компилятор знает тип ввода для функции, предоставленной в качестве второго аргумента, - Int в этом случае, поскольку первый параметр был Grid[Int] - поэтому я смог написать case (cell,width) => (cell,width) и не нужно явно указывать где-либо, что cell и width являются целыми числами.При втором использовании предоставляется Grid[(Int,Int)], это соответствует замыканию case ((cell,width),height) => Rect(width,height) и снова оно просто работает.
Если это замыкание содержало что-то, что не работало бы для базового типа сеткитогда компилятор жаловался бы, вот что такое безопасность типов ...
Подсчитав все возможные прямоугольники, остается только собрать данные и представить их в более удобном для формата формате.анализирующая.Поскольку вложенность на этом этапе может привести к очень беспорядку, я определил другой тип данных:
case class Cell[T](
value: T,
coords: (Int,Int) = (0,0),
widest: Rect = Rect.empty,
tallest: Rect = Rect.empty
)
Ничего особенного здесь, только класс case с именованными / параметрами по умолчанию.Я также рад, что у меня была дальновидность, чтобы определить Rect.empty выше:)
Теперь смешайте 4 набора данных (входные значения, координаты, самые широкие линии, самые высокие линии), постепенно складывайте в ячейки, осторожно перемешивайте,и обслуживаем:
val cellsWithCoords = input.zipWithCoords deepMap {
case (v,(x,y)) => Cell(value=v, coords=(x,y))
}
val cellsWithWidest = cellsWithCoords deepZip stage2w deepMap {
case (cell,rect) => cell.copy(widest=rect)
}
val cellsWithWidestAndTallest = cellsWithWidest deepZip stage2t deepMap {
case (cell,rect) => cell.copy(tallest=rect)
}
val results = (cellsWithWidestAndTallest deepMap {
case Cell(value, coords, widest, tallest) =>
List((widest, value, coords), (tallest, value, coords))
}
).flatten.flatten
Последний этап интересен: он конвертирует каждую ячейку в список кортежей размера 2 (прямоугольник, значение, координаты) (размер 2, поскольку у нас есть как самые широкие, так исамые высокие ректы для каждой ячейки) .При повторном вызове flatten полученный List[List[List[_]]] возвращается к одному List.Больше нет необходимости сохранять 2D-структуру, поскольку необходимые координаты уже включены в результаты.
Вуаля!
Теперь вам решать, что вы теперь будете делать с этим списком.Следующим этапом, вероятно, является некоторая форма сортировки и удаления дубликатов ...