生成游戏斯卡拉移动功能

我想了解使用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方法,这需要定义一个平等的功能。 我将如何实施?

--------------解决方案-------------

如果你的作品是相同的,我想你已经得到了错误的数据结构。 你想要一个地图[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)))

作为未成年人挑,可以更换(0 until start.length)start.indices 。 递归解决方案避免了使用指数共:

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

这比使用索引访问更好的性能,而且还具有更好的内存占用比你的解决方案,因为它具有很高的再利用列表中的组件。 它还使用一个共同的功能的技术,它是划分问题成已知和递归步骤。

让我有点解释。 为任何非空列表,该溶液的元素之一将是与第一元件增加一,和所有其他元件相同的列表。 这是对非空列表上方的溶液的第一部分:

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

分类:斯卡拉 时间:2015-03-15 人气:2
本文关键词: 函数式编程,斯卡拉
分享到:

相关文章

Copyright (C) 55228885.com, All Rights Reserved.

55228885 版权所有 京ICP备15002868号

processed in 1.663 (s). 10 q(s)