Generieren Sie faul „Spirale“ in Scala

Question

Aufgabe: Für eine gegebene Position in 2D-Array erzeugt Liste der umliegenden Positionen in Radius.

Zum Beispiel:

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

Ich schrieb etwas wie

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

In diesem Code getPositions kehrt nicht ein sequance Punkt, aber ein sequance von Tuple4 von sequances von Punkten. Wie kann ich „verketten“ 4 Generatoren im Code enthalten sind? Oder gibt es prägnante Lösung für meine Aufgabe? (Ich bin ziemlich neu in scala).

P. S. Es ist eigentlich für meine starcraft bietet.

Answer 1

Sie müssen die Liste (zweimal) glätten, so würde dies tun:

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

Es ist kein ‚faul‘ Spirale, though.

Bearbeiten

Dass man faul:

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

Ich habe die def P Methode verwendet, um die wirkliche Faulheit zu zeigen. Jedes Mal, Sie eine Pair schaffen würde, wird es genannt. In einer faulen Lösung, würden Sie wollen nur diese auf Anfrage.

Answer 2

Versuchen Sie diese:

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

Ausgabe:

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

Answer 3

Sie können Ihre Bereiche direkt und Verwendung flatMap und ++ bilden die Listen miteinander zu verbinden, wie sie gemacht sind, und Sie können in einer kreisförmigen Richtung gehen, mögen auch:

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

Wenn Sie wirklich das Ergebnis wollen, faul sein, werden Sie das gleiche mit faulen Komponenten zu tun haben:

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:. Fest ein dx gegen dy Tippfehler

Answer 4

Hier sind ein paar Lösungen für dieses Problem. Erstens, wenn Sie nicht für den Auftrag ist es egal, nur die Positionen, dies zu tun:

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)

Das gibt genau die gleiche Ausgabe, die Sie angegeben. Sie möchten jedoch einen Python-Stil-Generator, so dass diese besser geeignet wäre:

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

Das wird eine Iterator zurückkehren, die Sie durch den Einsatz von next laufen kann. Überprüfen Sie, ob das Ende mit hasNext.

Sie können Iterator mit List oder Stream oder Sachen wie das ersetzen und eine voll erzeugte Sammlung erhalten.

Nun lassen Sie uns annehmen, dass Sie eine Spirale wollen in der Mitte beginnt und zu einem Zeitpunkt, um eine Position zu bewegen. Wir könnten es tun, mit so etwas wie folgt aus:

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

Hier ist ein Strom, der an den Rändern geht.

Unter der Annahme Eingang (3,3), 2 gibt

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

, dann könnten Sie die folgende verwenden:

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

Verbrauch:

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