Создайте ленивую «спираль» в Scala

Question

Задача: Для данной позиции в 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 возвращает а не sequance точек, но sequance из Tuple4 из sequances точек. Как я могу «конкатенировать» 4 генератора, перечисленных в коде? Или есть более сжатое решение для моей задачи? (Я довольно новичок в scala).

P.S. Это на самом деле мой бот.

Answer 1

Вы должны выравнивать список (дважды), так что это будет делать:

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, он будет вызван. В ленивом решении вам нужно только это по требованию.

Answer 2

Попробуйте это:

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) } 

Answer 3

Вы можете сформировать свои диапазоны непосредственно, а также использовать 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)) 
    }) 
} 

Edit: пофиксить дй д против опечатку.

Answer 4

Вот несколько решений этой проблемы. Во-первых, если вы не заботиться о порядке, просто позиции, это будет делать:

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 
} 

Answer 5

Вот поток, который идет по краям.

Предполагая, что вход (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))