为什么迭代列表时会出现IndexOutOfBoundsException？

Question

我正在尝试将python代码转换为scala。我是Scala的新手，它是一种与python截然不同的语言。你知道吗

我尝试过将所有python函数转换为Scala，如下所示：

def legalMoves(board: List[Int]): List[List[Int]] = {
    val moves = List[List[Int]]()
    for ((piece, pos) <- board.zipWithIndex) {
      val jumpmove = pos + (piece * 2)
      val move = pos + (piece)
      if (piece != 0) {
        if (!((jumpmove < 0) || (jumpmove >= board.size))) {
          if (board(jumpmove) == 0) {
            val t = List(board)
            t.updated(pos, 0)
            t.updated(jumpmove, piece)
            moves :+ t
          }
        }
        if (!((move < 0) || (move >= board.size))) {
          if (board(move) == 0) {
            val t = List(board)
            t.updated(pos, 0)
            t.updated(move, piece)
            moves :+ t
          }
        }
      }
    }
    return moves
  }

  def evalAll(current: List[List[Int]], target: List[Int]): List[List[Int]] = {
    val next = List[List[Int]]()
    for (a <- current) {
      val n = legalMoves(a)
      for (q <- n) {
        val t = List(a)
        t :+ q
        if (q == target) {
          return t
        }
        next :+ t
      }
    }
    return next
  }

  def solve(start: List[Int]): List[List[Int]] = {
    var temp = List(start)
    val end = start.reverse
    while (temp.last != end) {
      temp = evalAll(temp, end)
    }
    return temp
  }

  def main(args: Array[String]) {
    println(solve(List(1, 1, 1, 0, -1, -1, -1)))
  }

这是我在尝试运行它时得到的错误：

[error]        at scala.collection.TraversableLike$WithFilter.foreach(TraversableLike.scala:791)
[error]        at org.mq.frogsandtoads.Main$.legalMoves(Main.scala:6)
[error]        at org.mq.frogsandtoads.Main$.$anonfun$evalAll$1(Main.scala:34)
[error]        at org.mq.frogsandtoads.Main$.$anonfun$evalAll$1$adapted(Main.scala:33)
[error]        at scala.collection.immutable.List.foreach(List.scala:392)
[error]        at org.mq.frogsandtoads.Main$.evalAll(Main.scala:33)
[error]        at org.mq.frogsandtoads.Main$.solve(Main.scala:51)
[error]        at org.mq.frogsandtoads.Main$.main(Main.scala:57)
[error] Nonzero exit code returned from runner: 1
[error] (Compile / run) Nonzero exit code returned from runner: 1
[error] Total time: 3 s, completed Aug 23, 2019, 8:18:35 PM

我不明白怎么了。我很想被放在正确的方向上。你知道吗

Answer 1

我通过这样编辑代码找到了解决方案（列表中的更改太多）：

package org.mq.frogsandtoads

object Main {
  def legalMoves(board: List[Int]): List[List[Int]] = {
    var moves = List[List[Int]]()
    for ((piece, pos) <- board.zipWithIndex) {
      val jumpmove = pos + (piece * 2)
      val move = pos + (piece)
      if (piece != 0) {
        if (!((jumpmove < 0) || (jumpmove >= board.size))) {
          if (board(jumpmove) == 0) {
            var t = board
            t = t.patch(pos, List(0), 1)
            t = t.patch(jumpmove, List(piece), 1)
            moves = moves :+ t
          }
        }
        if (!((move < 0) || (move >= board.size))) {
          if (board(move) == 0) {
            var t = board
            t = t.patch(pos, List(0), 1)
            t = t.patch(move, List(piece), 1)
            moves = moves :+ t
          }
        }
      }
    }
    return moves
  }

  def evalAll(
      current: List[List[List[Int]]],
      target: List[Int]
  ): List[List[List[Int]]] = {
    var next = List[List[List[Int]]]()
    for (a <- current) {
      val n = legalMoves(a.last)
      for (q <- n) {
        var t = a
        t = t :+ q
        if (q == target) {
          return List(t)
        }
        next = next :+ t
      }
    }
    return next
  }

  def solve(start: List[Int]): List[List[List[Int]]] = {
    var temp = List(List(start))
    val end = start.reverse
    while (temp.last.last != end) {
      temp = evalAll(temp, end)
    }
    return temp
  }

  def main(args: Array[String]) {
    println(solve(List(1, 1, 1, 0, -1, -1, -1)))
  }
}

Answer 2

欢迎来到斯卡拉的奇妙世界！你知道吗

事情有时肯定会有点混乱，但只要有一点毅力，一切皆有可能。：-）

异常的原因是无效的列表索引值。（如果不明显，如果您有一个包含n元素的列表，那么如果您试图访问任何索引超出范围[0, n - 1]的成员，就会出现该异常。）

不幸的是，您的“解决方案”只是添加了另一层列表，修复了症状，但我认为它没有解决问题。不过，对于给定的问题，您的代码正确地列出了一系列具有一个解决方案的电路板。你知道吗

然而，对于任何给定的电路板，这个问题有两种解决方案，它们是彼此的镜像。还有一些其他的规则是解决方案的特征，比如对于一个有F青蛙和T蟾蜍的游戏：

• 每个解中的跳转总数是F x T。你知道吗
• 每个溶液中的载玻片总数为F + T。你知道吗
• 因此，每个解中的移动总数是(F x T) + F + T。你知道吗

我试着理解你的代码，但我放弃了；我无法理解它！：-）相反，我编写了一个更详细一点的解决方案，但它会产生更易于理解的输出（希望您也能理解它）。你知道吗

顺便说一句，ScalaList并不是真的要以您尝试的方式使用的。每个List基本上由两个元素组成：一个head（它是列表中的第一个元素）和一个tail（它是包含其余元素的List）。值Nil表示空列表。这建立了一个递归关系，允许我们遍历List，根据需要对连续的head元素执行操作。因此，当您需要根据元素在列表中的位置来查找它时，它的性能就不太好了（这种查找的效率是O(n)）。一个Array在这方面要好得多（顺序效率O(1)）。你知道吗

另外，Scala中不鼓励使用while循环和var，因为有更好的方法可用。为了说明这一点，我重新编写了您的程序，以利用Scala的函数式编程功能： 你知道吗

package org.mq.frogsandtoads

import scala.annotation.tailrec

object Main {

  // Moves are to the right or to the left, so let's capture directions as
  // a hierarchy of directions.
  //
  // (This is nicer than using integer values.)
  //
  // A trait is like an abstract class that takes no class arguments. A case
  // object is an object that can be used in pattern matching, which we'll see
  // shortly. We can't create a Direction, but we can create Right & Left.
  trait Direction {

    // An index multiplier. 1 = to the right, -1 to the left.
    //
    // This is an abstract value, overridden in base classes.
    val multiplier: Int
  }

  case object Left extends Direction {
    override val multiplier = -1
  }

  case object Right extends Direction {
    override val multiplier = 1
  }

  // Let's capture frogs, toads and the hole as a hierarchy of board elements.
  trait Element

  // Frogs and toads are movable elements, holes are not.
  trait MovableElement extends Element {

    // Direction this element can move in.
    val direction: Direction
  }

  // Frogs can only move to the right.
  case object Frog extends MovableElement {
    override val direction = Right
  }

  // Toads can only move to the left.
  case object Toad extends MovableElement {
    override val direction = Left
  }

  // The hole cannot be moved (directly).
  case object Hole extends Element

  // A "board" is now a vector of elements. So let's define a type for that.
  //
  // Arrays are preferable to Lists because they support efficient element
  // retrieval given an index. Alas, they're also mutuable collections, which
  // we typically prefer to avoid. So instead we'll use a Vector, which is
  // immutable, if a little slower than an Array. I'm using it to demonstrate
  // how  immutable collections are used.
  type Board = Vector[Element]

  // Let's capture the turns as either Slides (1 position) or Jumps (2
  // positions).
  trait Turn {
    val positions: Int
  }

  case object Slide extends Turn {
    override val positions = 1
  }

  case object Jump extends Turn  {
    override val positions = 2
  }

  // A move, which applies only movable elements, consists of a turn a
  // direction, and the resulting board. We'll use a case class for this.
  final case class Move(turn: Turn, direction: Direction, board: Board)

  // A solution is now a list of moves. This type can also be used for
  // potential solutions.
  type Solution = List[Move]

  // A game has the specified number of frogs and toads.
  final class Game(frogs: Int, toads: Int) {

    // Sanity checks.
    require(frogs > 0, s"Number of frogs must be positive: $frogs")
    require(toads > 0, s"Number of toads must be positive: $toads")

    // Size of the boards in this game: the frogs + the toads + 1 for the hole.
    val boardSize = frogs + toads + 1

    // Create an initial board, in which we have all the frogs, a hole then all
    // the toads. Tabulate takes, as its first argument, the size of the board.
    // The second argument determines what element goes into each slot.
    private val initialBoard: Board = Vector.tabulate(boardSize) {i =>

      // If i (a 0-based index) is less than frogs, then this is a Frog.
      if(i < frogs) Frog

      // If it's equal to frogs, then it is the Hole.
      else if(i == frogs) Hole

      // Otherwise, it's a Toad.
      else Toad
    }

    // Create a final board. This happens when we have all the toads, the hole,
    // then all the frogs. We can obtain it by reversing the initial board.
    private val finalBoard: Board = initialBoard.reverse

    // Validate a board. This checks whether we have the right number of frogs,
    // toads and a hole. It returns true if the board is valid, false
    // otherwise.
    private def validate(board: Board): Boolean = {

      // An initial count, as a 3 value tuple: the number of frogs, holes and
      // toads respectively. Each count in the tuple is accessed by the member
      // references _1, _2 and _3.
      val initialCounts = (0, 0, 0)

      // Perform a fold left, where we iterate through the board counting the
      // types of element it contains. The first argument is the initial count
      // and the second argument is a function that takes two arguments, a
      // count tuple and an element. The fold operation calls this function for
      // each element of the board in turn, providing the new count for each
      // one.
      val finalCounts = board.foldLeft(initialCounts) {(counts, element) =>
        element match {
          case Frog => (counts._1 + 1, counts._2, counts._3)
          case Hole => (counts._1, counts._2 + 1, counts._3)
          case Toad => (counts._1, counts._2, counts._3 + 1)
        }
      }

      // Check that the final counts match our expected counts, returning the
      // result.
      finalCounts == (frogs, 1, toads)
    }

    // Use the validation function to ensure that our initial and final boards
    // are valid.
    assert(validate(initialBoard), s"Initial board is invalid: $initialBoard")
    assert(validate(finalBoard), s"Final board is invalid: $finalBoard")

    // Determine if the board is done, that is, if we have all the toads, then
    // the hole, then all the frogs.
    private def isFinished(board: Board): Boolean = board == finalBoard

    // Determine if a position is valid. Return true if it is, false if not.
    private def isValidPosition(i: Int): Boolean = i >= 0 && i < boardSize

    // Determine if a move is possible on a given board, returning the
    // successful move wrapped in Some, or None if it cannot be made. The
    // result is of type Option.
    //
    // board is the current board before making the move, i is the position of
    // the piece and turn is the action being attempted.
    private def makeMove(board: Board, i: Int, turn: Turn): Option[Move] = {

      // Sanity checks.
      assert(validate(board), s"Intermediate board is invalid: $board")
      assert(isValidPosition(i), s"Invalid move position: $i")

      // Examine the element at the specified board position.
      board(i) match {

        // If the element is a movable element, then we need to examine its
        // turn type.
        case me: MovableElement => {

          // Get the direction of this move, based upon the element at the
          // specified postion.
          val dir = me.direction

          // Get the target position for the move. It if's invalid, we cannot
          // make this move.
          val target = i + dir.multiplier * turn.positions
          if(!isValidPosition(target)) None

          // Otherwise, if the element at the target position is not a Hole,
          // then we cannot make this move.
          else if(board(target) != Hole) None

          // If this turn is a jump, and the element we're attempting to jump
          // over is the same type as this element, then we cannot make this
          // move.
          else if(turn == Jump && board(i + dir.multiplier) == board(i)) None

          // OK. We can make this move. Create a new board by replacing the
          // hole at the target position with this element, and replace this
          // element with a Hole.
          else {
            val newBoard = board.updated(target, me).updated(i, Hole)

            // Sanity check to ensure that the new board is valid.
            assert(validate(newBoard), s"New board following $turn, $dir is invalid: $newBoard")

            // Create the move we're considering making.
            val move = Move(turn, dir, newBoard)

            // Return the move wrapped in Some.
            Some(move)
          }
        }

        // Otherwise, it's a hole, so it can't be moved.
        case _ => None
      }
    }

    // Evaluate the current state of play.
    @tailrec
    private def validMoves(solutions: List[Solution],
    partialSolutions: List[(Solution, Board)]): List[Solution] =  {

      // If there are no more partial solutions, then we're done. Return all
      // the solutions found.
      if(partialSolutions.isEmpty) solutions

      // Otherwise, try to perform another set of moves for each partial
      // solution.
      else {

        // For each partial solution, try all possible moves, filtering out
        // those that could not be made.
        val updated = partialSolutions.flatMap {

          // Split the current partial solution into a list of moves and a board.
          case (ms, b) => {
            for {

              // Check each position on the board.
              i <- 0 until boardSize

              // Check each turn at each position.
              t <- List(Slide, Jump)

              // Determine the result of attempting to make this move on the
              // partial solution's last board.
              r = makeMove(b, i, t)

              // Filter out those moves that failed, retaining only those that
              // are defined (i.e. not None).
              //
              // Note: if there are NO valid moves for this board, then this
              // will filter out the initial partial solution.
              if r.isDefined

              // Retrieve the move.
              m = r.get

              // For the result, create a Solution by adding the move to the
              // current list of moves (note that we have to build it in
              // reverse) and updating the resulting board.
            } yield (m :: ms, m.board)
          }
        }

        // Now partition the partial solutions by looking at the resulting
        // board: any that match the final board are complete solutions.
        val (completed, newPartialSolutions) = updated.partition {
          case (_, b) => isFinished(b)
        }

        // Determine the new list of completed solutions by processing the
        // completed list. "map" operates on each member of completed, changing
        // the result.
        val newSolutions = completed.map {

          // Reverse the set of moves so that it is the right way around.
          // Discard the completed board.
          case (moves, _) => moves.reverse
        }

        // Perform another iteration.
        validMoves(newSolutions, newPartialSolutions)
      }
    }

    // Solve the game, finding all possible sequence of moves that result in
    // the final board. Because there are more than one solution, we'll return
    // a list of all the solutions found.
    //
    // Initially, we have no solutions. Our only partial solution consists of
    // no moves and the initial board.
    def solve: List[Solution] = validMoves(Nil, List((Nil, initialBoard)))
  }

  // Main function.
  def main(args: Array[String]): Unit = {

    // Create a game with 3 frogs and 3 toads and find the solutions.
    val solutions = new Game(3, 3).solve

    // Now report the number of solutions and detail them.
    println(s"Number of solutions found: ${solutions.size}")
    solutions.foreach {sol =>

      // For each solution, output a summary of the solution.
      println()
      println("Solution begins:")
      println()
      val moves = sol.size
      val (slides, jumps) = sol.map(_.turn).foldLeft((0, 0)) {(c, t) =>
        t match {
          case Slide => (c._1 + 1, c._2) // Increment number of slides.
          case _ => (c._1, c._2 + 1)     // Increment number of jumps.
        }
      }
      assert(slides + jumps == moves,
        s"slides ($slides) + jumps ($jumps) != moves ($moves)")

      println(s"Total moves: $moves (slides: $slides, jumps: $jumps)")
      println()
      println("Moves:")
      sol.foreach(println)
    }
  }
}

这将产生以下输出： 你知道吗

Number of solutions found: 2

Solution begins:

Total moves: 15 (slides: 6, jumps: 9)

Moves:
Move(Slide,Right,Vector(Frog, Frog, Hole, Frog, Toad, Toad, Toad))
Move(Jump,Left,Vector(Frog, Frog, Toad, Frog, Hole, Toad, Toad))
Move(Slide,Left,Vector(Frog, Frog, Toad, Frog, Toad, Hole, Toad))
Move(Jump,Right,Vector(Frog, Frog, Toad, Hole, Toad, Frog, Toad))
Move(Jump,Right,Vector(Frog, Hole, Toad, Frog, Toad, Frog, Toad))
Move(Slide,Right,Vector(Hole, Frog, Toad, Frog, Toad, Frog, Toad))
Move(Jump,Left,Vector(Toad, Frog, Hole, Frog, Toad, Frog, Toad))
Move(Jump,Left,Vector(Toad, Frog, Toad, Frog, Hole, Frog, Toad))
Move(Jump,Left,Vector(Toad, Frog, Toad, Frog, Toad, Frog, Hole))
Move(Slide,Right,Vector(Toad, Frog, Toad, Frog, Toad, Hole, Frog))
Move(Jump,Right,Vector(Toad, Frog, Toad, Hole, Toad, Frog, Frog))
Move(Jump,Right,Vector(Toad, Hole, Toad, Frog, Toad, Frog, Frog))
Move(Slide,Left,Vector(Toad, Toad, Hole, Frog, Toad, Frog, Frog))
Move(Jump,Left,Vector(Toad, Toad, Toad, Frog, Hole, Frog, Frog))
Move(Slide,Right,Vector(Toad, Toad, Toad, Hole, Frog, Frog, Frog))

Solution begins:

Total moves: 15 (slides: 6, jumps: 9)

Moves:
Move(Slide,Left,Vector(Frog, Frog, Frog, Toad, Hole, Toad, Toad))
Move(Jump,Right,Vector(Frog, Frog, Hole, Toad, Frog, Toad, Toad))
Move(Slide,Right,Vector(Frog, Hole, Frog, Toad, Frog, Toad, Toad))
Move(Jump,Left,Vector(Frog, Toad, Frog, Hole, Frog, Toad, Toad))
Move(Jump,Left,Vector(Frog, Toad, Frog, Toad, Frog, Hole, Toad))
Move(Slide,Left,Vector(Frog, Toad, Frog, Toad, Frog, Toad, Hole))
Move(Jump,Right,Vector(Frog, Toad, Frog, Toad, Hole, Toad, Frog))
Move(Jump,Right,Vector(Frog, Toad, Hole, Toad, Frog, Toad, Frog))
Move(Jump,Right,Vector(Hole, Toad, Frog, Toad, Frog, Toad, Frog))
Move(Slide,Left,Vector(Toad, Hole, Frog, Toad, Frog, Toad, Frog))
Move(Jump,Left,Vector(Toad, Toad, Frog, Hole, Frog, Toad, Frog))
Move(Jump,Left,Vector(Toad, Toad, Frog, Toad, Frog, Hole, Frog))
Move(Slide,Right,Vector(Toad, Toad, Frog, Toad, Hole, Frog, Frog))
Move(Jump,Right,Vector(Toad, Toad, Hole, Toad, Frog, Frog, Frog))
Move(Slide,Left,Vector(Toad, Toad, Toad, Hole, Frog, Frog, Frog))

会有很多你可能不明白的，马上。我鼓励您访问Scala API documentation，查找一些您不确定的细节。你知道吗