Générer paresseux "spirale" dans Scala

Question

Tâche: Pour une position donnée dans la matrice 2D générer la liste des positions environnantes situées dans le rayon.

Par exemple:

input: (1, 1) 
radius: 1 
output: ((0, 0), (1, 0), (2, 0), 
      (0, 1),   (2, 1), 
      (0, 2), (1, 2), (2, 2)). 

j'ai écrit quelque chose comme

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

Dans ce code getPositions renvoie pas un sequance de points, mais un sequance de Tuple4 de sequances des points. Comment puis-je "concaténer" 4 générateurs répertoriés dans le code? Ou y a-t-il une solution plus concise pour ma tâche? (Je suis assez nouveau à Scala).

P.S. C'est en fait pour mon robot Starcraft.

Answer 1

Vous devez aplatir la liste (deux fois), donc ce serait faire:

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 

Ce n'est pas une spirale « paresseux », cependant.

Modifier

Que l'on est paresseux:

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’. 

Je l'ai utilisé la méthode def P pour montrer la paresse réelle. À chaque fois, vous créez un Pair, il est appelé. Dans une solution paresseuse, vous ne voulez que cela sur demande.

Answer 2

Essayez ceci:

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("{ ", ", ", " }")) 
    } 
} 

Sortie:

getPositions(1, 1, 1): { (-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1) } 

Answer 3

Vous pouvez former vos gammes directement, et utiliser flatMap et ++ pour rejoindre les listes ensemble comme ils sont faits, et vous pourriez aimer pour aller dans une direction circulaire aussi:

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

Si vous voulez vraiment résultat e d'être paresseux, vous devrez faire la même chose avec des composants paresseux:

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: Correction d'un rapport dx dy faute de frappe.

Answer 4

Voici quelques solutions à ce problème. Tout d'abord, si vous ne vous souciez pas de l'ordre, juste les positions, cela va faire:

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) 

qui donnera la même sortie exacte que vous avez spécifié. Cependant, vous voulez un générateur de style Python, donc ce serait plus approprié:

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

qui renverra un Iterator, que vous pouvez itérer en utilisant next. Vérifiez la fin en utilisant hasNext.

Vous pouvez remplacer Iterator avec List ou Stream ou d'autres choses semblables et ainsi obtenir une collection entièrement générée. Supposons maintenant que vous voulez une spirale partant du centre et se déplaçant d'une position à la fois. Nous pourrions le faire avec quelque chose comme ceci:

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

Voici un flux qui contourne les bords.

entrée supposant (3,3), 2 donne

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

alors vous pouvez utiliser les éléments suivants:

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

Utilisation:

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