使用Scala函数式编程生成游戏动作

Question

我正在尝试使用Scala函数式编写策略游戏，但不幸的是，我好像卡在了非常基础的部分。(这不是家庭作业，而是我尝试学习一些新东西，即“纯”函数式编程。)

让我们来看一个简单的“游戏”：(唯一的)玩家在一排无限的方格上有x个相同的棋子。棋子从第0个方格开始，每次可以将一个棋子向前移动一个方格。

作为数据结构，我将使用一个List[Int]，其中每个项都是一个棋子的位置(方格)。

为了生成可能的移动，我想到了以下方法:

def moves(start: List[Int]) = 
    (0 until start.length).map({i => start.updated(i, start(i) + 1)});

val m1 = moves(List(0,0,0))
// m1 then contains Vector(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))

val m2 = moves(List(1,2,3))
// m1 then contains Vector(List(2, 2, 3), List(1, 3, 3), List(1, 2, 4))

我不喜欢使用索引循环(0 until start.length)，这对我来说似乎不太“函数式”。这是正确的做法还是有更好的方法？

---

现在在我的游戏示例中，所有棋子都是相同的，因此在情况m1中，所有三个可能的移动也是相同的，可以/应该被压缩成一个移动。我修改了moves以对每个移动项进行排序，以便我可以获得一个不同项的列表：

def moves(start: List[Int]) = 
    (0 until start.length).map({i => start.updated(i, start(i) + 1).sorted}).distinct;

val m1 = moves(List(0,0,0))
// m1 then contains Vector(List(0, 0, 1))

val m2 = moves(List(1,2,3))
// m1 then contains Vector(List(2, 2, 3), List(1, 3, 3), List(1, 2, 4))

然而，这需要数据结构是可排序的，在我的“真实”应用程序中，它很可能不是一个List[Int]，而是一个元组或案例类。我猜我需要的是一个distinct方法，它接受定义相等性的函数。我该如何实现呢？

- RoToRa

---

列出方法moves的返回类型可以使代码更易读。是的，我可以从m1的注释中获取它，但那已经太晚了... - ziggystar

Answer 1

如果您的棋子是相同的，我认为您选择了错误的数据结构。您需要一个Map[Int,Int]，其中键告诉您方格的索引，而值告诉您有多少个棋子（如果存在默认计数集，则会更容易）。然后

def moves(start: Map[Int,Int]) = start.keySet.map(k => {
  val n = start(k)
  val pickup = (if (n == 1) (start - k) else start + (k -> (n-1)))
  pickup + ((k+1) -> (start.getOrElse(k+1, 0) + 1))
})

这解决了您的玩具示例中的所有问题（但也许不是您真实场景中的问题）。而且它组合起来非常方便：

scala> val firstmoves = moves(Map(0->3))                          
firstmoves: scala.collection.Set[scala.collection.immutable.Map[Int,Int]] =
Set(Map((0,2), (1,1)))

scala> val secondmoves = firstmoves.flatMap(moves)                           
secondmoves: scala.collection.Set[scala.collection.immutable.Map[Int,Int]] =
Set(Map((0,1), (1,2)), Map((0,2), (2,1)))

scala> val thirdmoves = secondmoves.flatMap(moves)
thirdmoves: scala.collection.Set[scala.collection.immutable.Map[Int,Int]] =
Set(Map((1,3)), Map((0,1), (1,1), (2,1)), Map((0,2), (3,1)))

- Rex Kerr

---

这不是我预期的结果，但仍然是“正确”的答案。谢谢。我需要重新调整我的“真正”的程序并看看它的效果如何。 - RoToRa

Answer 2

作为一个小的改进，你可以用start.indices替换(0 until start.length)。递归解决方案完全避免了使用索引：

def moves(start: List[Int]): List[List[Int]] =  start match {
  case Nil => Nil
  case head :: tail => (head + 1 :: tail) :: (moves(tail) map (head :: _))
}

这种方法比使用索引访问性能更高，而且与您的解决方案相比，在内存占用方面具有更好的足迹，因为它具有非常高的列表组件重用率。它还使用了一种常见的功能技术，即将问题分成已知步骤和递归步骤。

让我稍微解释一下。对于任何非空列表，解决方案中的其中一个元素将是第一个元素增加1，并且所有其他元素保持不变的列表。这是上述非空列表的解决方案的第一部分：

head + 1 :: tail

现在，所有其他解决方案都有一个共同点，就是第一个元素相同。因此，想象一下solutions中除了第一个元素的所有其他解决方案，然后以下内容将重新创建解决方案：

solutions map (solution => head :: solution)

或者，简洁表达，

solutions map (head :: _)

现在我们只需要计算solutions。恰好，我们已经有了一种计算的方法：moves本身！我们只需要将列表的tail作为输入即可：

(moves(tail) map (head :: _))

因此，如果我们将这两个结合起来，我们就可以得到上面代码中显示的解决方案。

说了这么多，我不确定列表是否是这个问题的好数据结构。

至于获取不同解决方案的列表，如果创建一个类来存储移动，那么您可以拥有一个equals方法来忽略元素的顺序，在这种情况下，像distinct这样的方法就能很好地工作。

如果那不可行的话，你可以利用SortedSet的一个奇特之处——它们使用隐式的Ordering来确定相等性——来解决问题。例如：

object LO extends Ordering[List[Int]] {
  def compare(x: List[Int], y: List[Int]) = cmp(x.sorted, y.sorted)
  def cmp(x: List[Int], y: List[Int]): Int = (x, y) match {
    case (Nil, Nil) => 0
    case (Nil, _  ) => -1
    case (_  , Nil) => 1
    case (h1 :: t1, h2 :: t2) if h1 < h2 => -1
    case (h1 :: t1, h2 :: t2) if h2 < h1 => 1
    case (h1 :: t1, h2 :: t2) => cmp(t1, t2)
  }
}

val m1 = SortedSet(moves(List(0, 0, 0)): _*)(LO).toList

- Daniel C. Sobral

---

我没有考虑到将x个元素的解决方案建立在x-1个元素的解决方案之上（这是我应该做的）。这正是我寻找的答案，并且帮助了我很多，但我想我将不得不接受Rex的答案，因为它指向了更好的数据结构并回答了两个问题。 - RoToRa

@RoToRa 我无所谓。如果 Rex 还没有那样回答，那么我会建议这样做！:-) 不幸的是，我没有注意到第二个问题。我会在这里补充，因为有一个答案。 - Daniel C. Sobral