Create a lazy spiral in Scala

Question

Task: For a given position in a 2D array, create a list of surrounding positions located in a radius.

For instance:

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

I wrote something like

 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 this code, getPositions does not return a sequence of points, but a sequence of Tuple4 sequence of points. How can I "concatenate" the 4 generators listed in the code? Or is there a more succinct solution for my problem? (I am new to scala).

PS This is actually for my bot star.

Answer 1

You need to flatten the list (twice) for this to happen:

 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 

However, this is not a "lazy spiral."

Edit

This lazy:

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

Ive used the def P method to show real laziness. Each time you create a Pair , it is called. In a lazy solution, you only want this on demand.

Answer 2

Try the following:

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

Conclusion:

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

Answer 3

You can form your ranges directly and use flatMap and ++ to combine the lists together as they are done, and you can also go in a circular direction:

 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, yi)) ++ dx.map(i => (xi, y-radius)) ++ dy.map(i => (x-radius, y+i)) }) } 

If you really want the result to be lazy, you will have to do the same with lazy components:

 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, yi)) ++ dx.map(i => (xi, y-radius)) ++ dy.map(i => (x-radius, y+i)) }) } 

Edit: fixed dx vs. dy typo.

Answer 4

Here are some solutions to this problem. Firstly, if you do not care about the order, just the position, this will do:

 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) 

This will give the same result that you specified. However, you need a Python-style generator, so that would be more appropriate:

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

This will return an Iterator with which you can iterate with next . Check the end using hasNext .

You can replace Iterator with List or Stream or the like, and get a fully generated collection.

Now suppose you want the spiral to start in the center and move one position at a time. We could do it something like this:

 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

Here is the stream that goes around the edges.

Assuming input (3.3), 2 gives

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

then you can use the following:

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

Using:

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