Создание ленивой «спирали» в Scala
Вопрос
Задача:Для заданной позиции в 2D-массиве сгенерируйте список окружающих позиций, расположенных по радиусу.
Например:
input: (1, 1)
radius: 1
output: ( (0, 0), (1, 0), (2, 0),
(0, 1), (2, 1),
(0, 2), (1, 2), (2, 2) ).
Я написал что-то вроде
def getPositions(x:Int, y:Int, r:Int) = {
for(radius <- 1 to r) yield {
List(
for (dx <- -radius to radius) yield Pair(x + dx, y - radius),
for (dx <- -radius to radius) yield Pair(x + dx, y + radius),
for (dy <- -radius to radius) yield Pair(x + radius, y + dy),
for (dy <- -radius to radius) yield Pair(x - radius, y + dy)
)
}
}
В этом коде getPositions возвращает не последовательность точек, а последовательность Tuple4 последовательностей точек.Как я могу «объединить» 4 генератора, перечисленных в коде?Или есть более краткое решение моей задачи?(Я новичок в Scala).
P.S.На самом деле это для моего бота StarCraft.
Решение
Вам нужно сгладить список (дважды), так что это будет делать:
def getPositions(x:Int, y:Int, r:Int) = {
for(radius <- 1 to r) yield {
List(
for (dx <- -radius to radius) yield Pair(x + dx, y - radius),
for (dx <- -radius to radius) yield Pair(x + dx, y + radius),
for (dy <- -radius to radius) yield Pair(x + radius, y + dy),
for (dy <- -radius to radius) yield Pair(x - radius, y + dy)
).flatten
}
}.flatten
Это не «ленивая» спираль, хотя.
Редактировать
Что человек ленивый:
def P(i:Int, j:Int) = { print("eval"); Pair(i,j) }
def lazyPositions(x:Int, y:Int, r:Int) = {
(1 to r).toStream.flatMap{ radius =>
(-radius to radius).toStream.map(dx => P(x + dx, y - radius)) #:::
(-radius to radius).toStream.map(dx => P(x + dx, y + radius)) #:::
(-radius to radius).toStream.map(dy => P(x + radius, y + dy)) #:::
(-radius to radius).toStream.map(dy => P(x - radius, y + dy))
}
}
print(lazyPositions(1,1,1).take(3).toList) # prints exactly three times ‘eval’.
Я использовал def P
способ показать реальную лень. Каждый раз, когда вы создадим Pair
, это вызывается. В ленивом решении вы хотели бы только по требованию.
Другие советы
Попробуй это:
object Spiral
{
def
getPositions(x: Int, y: Int, r: Int): Seq[(Int, Int)] = {
for { radius <- 1 to r
dx <- -radius to radius
dy <- -radius to radius
if dx != 0 || dy != 0
} yield
(x + dx, y + dy)
}
def
main(args: Array[String]): Unit = {
printf("getPositions(1, 1, 1): %s%n", getPositions(0, 0, 1).mkString("{ ", ", ", " }"))
}
}
Выход:
getPositions(1, 1, 1): { (-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1) }
Вы можете формировать свои диапазоны напрямую и использовать flatMap
и ++
чтобы объединить списки по мере их создания, и вы также можете пойти по кругу:
def getPositions(x: Int, y: Int, r: Int) = {
(1 to r) flatMap (radius => {
val dx = -radius to radius
val dy = -(radius-1) to (radius-1)
dx.map(i => (x+i, y+radius)) ++ dy.map(i => (x+radius, y-i)) ++
dx.map(i => (x-i, y-radius)) ++ dy.map(i => (x-radius, y+i))
})
}
Если вы действительно хотите, чтобы результат был ленивым, вам придется сделать то же самое с ленивыми компонентами:
def getPositions(x: Int, y: Int, r: Int) = {
Stream.range(1,r+1) flatMap (radius => {
val dx = Stream.range(-radius,radius+1)
val dy = Stream.range(-(radius+1),radius)
dx.map(i => (x+i, y+radius)) ++ dy.map(i => (x+radius, y-i)) ++
dx.map(i => (x-i, y-radius)) ++ dy.map(i => (x-radius, y+i))
})
}
Редактировать:исправлена ошибка dx vs.да опечатка.
Вот несколько решений этой проблемы. Во-первых, если вам не волнует заказ, просто позиции, это сделает:
def getPositions(x:Int, y:Int, r:Int) = for {
yr <- y - r to y + r
xr <- x - r to x + r
if xr != x || yr != y
} yield (xr, yr)
Это даст точно такой же вывод, который вы указали. Тем не менее, вы хотите генератор стиля Python, так что это будет более подходящим:
def getPositions(x:Int, y:Int, r:Int) = Iterator.range(y - r, y + r + 1) flatMap {
yr => Iterator.range(x - r, x + r + 1) map {
xr => (xr, yr)
}
} filter (_ != (x, y))
Это вернет Iterator
, который вы можете пережить через использование next
. Отказ Проверьте на конец, используя hasNext
.
Вы можете заменить Iterator
с участием List
или Stream
Или такие вещи и получите полностью сгенерированную коллекцию.
Теперь, давайте предположим, что вы хотите, чтобы спираль, начиная с центра и перемещая одну позицию за раз. Мы могли бы сделать это с чем-то вроде этого:
def getPositions(x:Int, y:Int, r:Int) = new Iterator[(Int, Int)] {
private var currentX = x
private var currentY = y
private var currentR = 1
private var incX = 0
private var incY = 1
def next = {
currentX += incX
currentY += incY
val UpperLeft = (x - currentR, y + currentR)
val UpperRight = (x + currentR, y + currentR)
val LowerLeft = (x - currentR, y - currentR)
val LowerRight = (x + currentR, y - currentR)
val PrevSpiral = (x, y + currentR)
val NextSpiral = (x - 1, y + currentR)
(currentX, currentY) match {
case NextSpiral => incX = 1; incY = 1; currentR += 1
case PrevSpiral => incX = 1; incY = 0
case UpperLeft => incX = 1; incY = 0
case UpperRight => incX = 0; incY = -1
case LowerRight => incX = -1; incY = 0
case LowerLeft => incX = 0; incY = 1
case _ =>
}
if (currentR > r)
throw new NoSuchElementException("next on empty iterator")
(currentX, currentY)
}
def hasNext = currentR <= r
}
Вот поток, который ходит по краям.
Предполагая ввод (3,3), 2 дает
{(1,1), (2,1), (3,1), (4,1), (5,1),
(1,2), (5,2),
(1,3), (5,3),
(1,4), (5,4),
(1,5), (2,5), (3,5), (4,5), (5,5)}
Тогда вы можете использовать следующее:
def border(p: (Int,Int), r: Int) = {
val X1 = p._1 - r
val X2 = p._1 + r
val Y1 = p._2 - r
val Y2 = p._2 + r
def stream(currentPoint: (Int,Int)): Stream[(Int,Int)] = {
val nextPoint = currentPoint match {
case (X1, Y1) => (X1+1, Y1)
case (X2, Y2) => (X2-1, Y2)
case (X1, Y2) => (X1, Y2-1)
case (X2, Y1) => (X2, Y1+1)
case (x, Y1) => (x+1, Y1)
case (x, Y2) => (x-1, Y2)
case (X1, y) => (X1, y-1)
case (X2, y) => (X2, y+1)
}
Stream.cons(nextPoint, if (nextPoint == (X1,Y1)) Stream.empty else stream(nextPoint))
}
stream((X1,Y1))
}
Применение:
scala> val b = border((3,3),2)
b: Stream[(Int, Int)] = Stream((2,1), ?)
scala> b.toList
res24: List[(Int, Int)] = List((2,1), (3,1), (4,1), (5,1), (5,2), (5,3), (5,4), (5,5), (4,5), (3,5), (2,5), (1,5), (1,4), (1,3), (1,2), (1,1))