<p>欢迎来到斯卡拉的奇妙世界!你知道吗</p>
<p>事情有时肯定会有点混乱,但只要有一点毅力,一切皆有可能。:-)</p>
<p>异常的原因是无效的列表索引值。(如果不明显,如果您有一个包含<code>n</code>元素的列表,那么如果您试图访问任何索引超出范围<code>[0, n - 1]</code>的成员,就会出现该异常。)</p>
<p>不幸的是,您的“解决方案”只是添加了另一层列表,修复了症状,但我认为它没有解决问题。不过,对于给定的问题,您的代码正确地列出了一系列具有一个解决方案的电路板。你知道吗</p>
<p>然而,对于任何给定的电路板,这个问题有两种解决方案,它们是彼此的镜像。还有一些其他的规则是解决方案的特征,比如对于一个有<code>F</code>青蛙和<code>T</code>蟾蜍的游戏:</p>
<ul>
<li>每个解中的跳转总数是<code>F x T</code>。你知道吗</li>
<li>每个溶液中的载玻片总数为<code>F + T</code>。你知道吗</li>
<li>因此,每个解中的移动总数是<code>(F x T) + F + T</code>。你知道吗</li>
</ul>
<p>我试着理解你的代码,但我放弃了;我无法理解它!:-)相反,我编写了一个更详细一点的解决方案,但它会产生更易于理解的输出(希望您也能理解它)。你知道吗</p>
<p>顺便说一句,<em>Scala</em><code>List</code>并不是真的要以您尝试的方式使用的。每个<code>List</code>基本上由两个元素组成:一个<code>head</code>(它是列表中的第一个元素)和一个<code>tail</code>(它是包含其余元素的<code>List</code>)。值<code>Nil</code>表示空列表。这建立了一个递归关系,允许我们遍历<code>List</code>,根据需要对连续的head元素执行操作。因此,当您需要根据元素在列表中的位置来查找它时,它的性能就不太好了(这种查找的效率是<code>O(n)</code>)。一个<code>Array</code>在这方面要好得多(顺序效率<code>O(1)</code>)。你知道吗</p>
<p>另外,Scala中不鼓励使用while循环和<code>var</code>,因为有更好的方法可用。为了说明这一点,我重新编写了您的程序,以利用Scala的函数式编程功能:
你知道吗</p>
<pre><code>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)
}
}
}
</code></pre>
<p>这将产生以下输出:
你知道吗</p>
<pre><code>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))
</code></pre>
<p>会有很多你可能不明白的,马上。我鼓励您访问<a href="https://www.scala-lang.org/api/2.12.9/" rel="nofollow noreferrer"><em>Scala</em> API documentation</a>,查找一些您不确定的细节。你知道吗</p>