Generieren Sie faul „Spirale“ in Scala
Frage
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.
Lösung
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.
Andere Tipps
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) }
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
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
}
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))