Generating game moves functionally with Scala

Question

I'm trying to understand writing strategy games using Scala functionally, but unfortunately I seem to 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?

Answer 1

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