Générer paresseux « spirale » dans Scala

Question

Tâche: Pour une position donnée dans le tableau 2D générer la liste des positions situées autour de 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 ne revient pas un sequance de points, mais un sequance de Tuple4 de sequances des points. Comment puis-je « concaténer » 4 générateurs énumérés dans le code? Ou est-il plus une solution concise pour ma tâche? (Je suis assez nouveau pour scala).

P.S. Il est en fait pour mon bot starcraft.

Answer 1

Vous devez aplatir la liste (deux fois), donc cela ferait:

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 », bien.

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. A chaque fois, vous allez pouvoir créer Pair, il est appelé. Dans une solution paresseuse, tu 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 l'utilisation flatMap et ++ pour rejoindre les listes ensemble comme ils sont faits, et vous voudrez peut-être 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 le résultat 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:. Fixe un dx dy par rapport typo

Answer 4

Voici quelques solutions à ce problème. Tout d'abord, si vous ne vous souciez pas de l'ordre, les positions seulement, 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)

Cela donnera la sortie exactement le même 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 retourne 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 des trucs comme ça et obtenir une collection entièrement générée.

Maintenant, supposons que vous voulez une spirale à partir du centre et le déplacement 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 cours d'eau qui se promène sur les bords.

En supposant entrée (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)}

vous pouvez utiliser ce qui suit:

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