Générer des mouvements de jeu fonctionnellement avec Scala

Question

J'essaie de comprendre les jeux de stratégie d'écriture en utilisant Scala fonctionnellement, mais malheureusement, je semble être coincé à la base même. (Ce n'est pas le travail à domicile, mais mes tentatives pour apprendre quelque chose de nouveau, à savoir la programmation fonctionnelle "pure".)

Prenons le suivant "jeu" simple: le joueur (seul) a x pièces identiques sur une ligne sans fin de carrés. Les pièces commencent au carré 0 et chaque tour, il peut déplacer une pièce en avant d'un carré.

Comme la structure de données, je vais utiliser un List[Int] où chaque élément est la position (carré) d'une seule pièce.

Pour générer les mouvements possibles, je suis venu avec:

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

Ce que je n'aime pas est l'utilisation de la boucle d'index (0 until start.length). Cela ne me semble pas très "fonctionnel". Est-ce la bonne façon de le faire ou existe-t-il un meilleur moyen?

---

Maintenant, dans mon exemple de jeu toutes les pièces sont identiques, en cas m1 les trois mouvements possibles sont également identiques et pourraient/devraient être condensés en un seul mouvement. J'ai modifié moves pour trier chaque élément de déplacement, de sorte que je puisse obtenir une liste d'éléments distincts:

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

Cependant, cela nécessite à la structure de données triables et dans mon application « réelle », il est très probablement pas un List[Int] , mais un Tuple ou une classe de cas. Ce dont j'aurais besoin, c'est d'une méthode distinct, qui prend une fonction qui définit l'égalité. Comment pourrais-je l'implémenter?

Answer 1

Si vos pièces sont identiques, je pense que vous avez la mauvaise structure de données. Vous voulez une carte [Int, Int] où la clé vous indique l'index de votre carré, et la valeur vous indique combien de pièces sont présentes (il n'y a pas d'ensemble compté par défaut ou ce serait encore plus facile). Puis

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

Cela résout tous les problèmes dans votre exemple de jouet (mais peut-être pas votre vrai). Et il compose bien:

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

Answer 2

En tant que choix mineur, vous pouvez remplacer (0 until start.length) avec start.indices. Une solution récursive évite l'utilisation d'indices au total:

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

Cela a beaucoup de meilleures performances que d'utiliser un accès indexé, et il a également une meilleure empreinte mémoire que votre solution, car il a une réutilisation très élevée des composants de la liste . Il utilise également une technique fonctionnelle commune, qui divise le problème en une étape connue et récursive. Permettez-moi d'expliquer cela un peu. Pour toute liste non vide, l'un des éléments de la solution sera une liste avec le premier élément augmenté de un, et tous les autres éléments identiques. Ceci est la première partie de la solution pour la liste non-vide au-dessus:

head + 1 :: tail 

Maintenant, toutes les autres solutions ont en commun que le premier élément sera le même.Alors, imaginez que solutions a toutes les autres solutions moins le premier élément, alors ce qui suit va recréer la solution:

solutions map (solution => head :: solution) 

Ou, sous une forme compressée,

solutions map (head :: _) 

Maintenant, nous ne devons calculer solutions . Comme il arrive, nous avons déjà une méthode pour calculer cela: moves lui-même! Il suffit de nourrir la tail de la liste:

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

Donc, si nous combinons ces deux ensemble, nous obtenons la solution affichée dans le code ci-dessus. Ayant dit tout cela, je ne suis pas sûr si une liste est une bonne structure de données pour ce problème non plus. Pour obtenir une liste de solutions distincte, si vous créez une classe pour stocker les déplacements, vous pouvez utiliser une méthode equals qui ignore l'ordre des éléments, auquel cas des méthodes telles que distinct fonctionneront correctement.

Si ce n'est pas viable, vous pouvez utiliser une particularité de SortedSet - qu'ils utilisent le Ordering implicite pour déterminer l'égalité - pour résoudre le problème. Par exemple:

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