Generating game moves functionally with Scala

I'm trying to understand writing strategy games using Scala functionally, but unfortunately I seem t开发者_如何学编程o be stuck at the very basics. (This is not home work, but my attempts to learn something new, namely "pure" functional programming.)

Let's take following simple "game": the (sole) player has x identical pieces on a endless row of squares. The pieces start on square 0 and each turn he can move one piece forward one square.

As the data structure I will use a List[Int] were each item is the position (square) of one piece.

To generate the possible moves I came up with:

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

What I don't like is the use of the index loop (0 until start.length). It doesn't seem very "functional" to me. Is this the right way to do this or is there a better way?

Now in my game example all pieces are identical, so in case m1 all three possible moves are also identical and could/should be condensed into one move. I modified moves to sort each move item, so that I could get a list of distinct items:

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

However this requires to data structure to be sortable and in my "real" application, it's most likely not a List[Int], but a Tuple or a case class. What I guess I'd need is a distinct method, that takes an function that defines equality. How would I implement that?

If your pieces are identical, I think you've got the wrong data structure. You want a Map[Int,Int] where the key tells you the index of your square, and the value tells you how many pieces are there (there is no default counted set or this would be even easier). Then

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

This solves all the problems in your toy example (but perhaps not your real one). And it composes nicely:

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

As a minor pick, you can replace (0 until start.length) with start.indices. A recursive solution avoids the use of indices altogether:

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

This has much better performance than using indexed access, and it also has better memory footprint than your solution, as it has a very high re-use of list components. It also uses one common functional technique, which is divide the problem into a known and a recursive step.

Let me explain that a bit. For any non-empty list, one of the elements of the solution will be the a list with the first element increased by one, and all other elements the same. This is the first part of the solution for the non-empty list above:

head + 1 :: tail

Now, all other solutions have in common that the first element will be the same. So, imagine that solutions has all other solutions minus the first element, then the following will recreate the solution:

solutions map (solution => head :: solution)

Or, in a compressed form,

solutions map (head :: _)

Now we only need to compute solutions. As it happens, we already have a method to compute that: moves itself! We only have to feed it the tail of the list:

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

So, if we combine these two together, we get the solution displayed in the code above.

Having said all that, I'm not sure if a list is a good data structure for the this problem either.

As for getting a distinct list of solutions, if you create a class to store the moves, then you could have an equals method that ignored ordering of the elements, in which case methods such as distinct would work fine.

If that isn't viable, you could use a peculiarity of SortedSet -- that they use the implicit Ordering to determine equality -- to solve the problem. For example:

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