توليد "حلزوني" كسول في سكالا

Question

المهمة: بالنسبة لموقع معين في صفيف ثنائي الأبعاد ، قم بإنشاء قائمة بالمواقف المحيطة الموجودة في نصف القطر.

علي سبيل المثال:

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

كتبت شيئًا مثل

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

في هذا الكود ، لا يعيد GetPositions سلسلة من النقاط ، ولكن تسلسل TUPLE4 من تسلسل النقاط. كيف يمكنني "Concatenate" 4 مولدات مدرجة في الكود؟ أم أن هناك حلًا أكثر إيجازًا لمهمتي؟ (أنا جديد جدًا على سكالا).

ملاحظة: إنه في الواقع لبروت Starcraft الخاص بي.

Answer 1

تحتاج إلى تسطيح القائمة (مرتين) ، لذلك فإن هذا سيفعل:

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

إنها ليست دوامة "كسول".

تعديل

هذا كسول:

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

لقد استخدمت def P طريقة لإظهار الكسل الحقيقي. في كل مرة ، يمكنك إنشاء ملف Pair, ، يتم استدعاؤه. في حل كسول ، تريد فقط ذلك عند الطلب.

Answer 2

جرب هذا:

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

انتاج:

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

Answer 3

يمكنك تشكيل نطاقاتك مباشرة ، والاستخدام flatMap و ++ للانضمام إلى القوائم معًا عند صنعها ، وقد ترغب في الذهاب في اتجاه دائري أيضًا:

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

إذا كنت تريد حقًا أن تكون النتيجة كسولًا ، فسيتعين عليك فعل الشيء نفسه مع المكونات البطيئة:

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

تحرير: تم إصلاح DX مقابل DY Typo.

Answer 4

فيما يلي بعض الحلول لهذه المشكلة. أولاً ، إذا كنت لا تهتم بالطلب ، فقط المواقف ، فسيكون ذلك:

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)

هذا سيعطي نفس الإخراج الذي حددته بالضبط. ومع ذلك ، فأنت تريد مولدًا على غرار بيثون ، لذلك سيكون هذا أكثر ملاءمة:

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

التي ستعود Iterator, ، والتي يمكنك التكرار من خلال استخدامها next. تحقق من استخدام النهاية hasNext.

يمكنك استبدال Iterator مع List أو Stream أو أشياء من هذا القبيل والحصول على مجموعة تم إنشاؤها بالكامل.

الآن ، لنفترض أنك تريد بدءًا دوامة في المركز وتحريك موقفًا واحدًا في كل مرة. يمكننا أن نفعل ذلك بشيء من هذا القبيل:

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

إليك تيار يتجول حول الحواف.

على افتراض المدخلات (3،3) ، 2 يعطي

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

ثم يمكنك استخدام ما يلي:

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

الاستخدام:

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