Generación de movimientos de juego funcionalmente con Scala

Question

Estoy tratando de entender cómo escribir juegos de estrategia usando Scala funcionalmente, pero desafortunadamente parezco estar pegado a lo básico. (Esto no es trabajo a domicilio, pero mis intentos de aprender algo nuevo, es decir, la programación funcional "pura".)

Tomemos siguiente sencillo "juego": la (única) jugador tiene x piezas idénticas en una fila sin fin de cuadrados. Las piezas comienzan en el cuadrado 0 y cada turno puede mover una pieza hacia adelante un cuadrado.

Como la estructura de datos que va a utilizar un List[Int] eran cada elemento es la posición (cuadrado) de una sola pieza.

para generar los movimientos posibles que se me ocurrió:

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

Lo que no me gusta es el uso del bucle índice (0 until start.length). No me parece muy "funcional". ¿Es esta la manera correcta de hacer esto o hay una mejor manera?

---

Ahora en mi ejemplo del juego todas las piezas son idénticas, por lo que en caso m1 los tres posibles movimientos también son idénticas y pueden/deben ser condensados ​​en un solo movimiento. He modificado moves para ordenar cada elemento de movimiento, por lo que podría conseguir una lista de elementos distintos:

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

Sin embargo, esto requiere que la estructura de datos para ser clasificable y en mi aplicación "real", es muy probable que no un List[Int] , pero una Tuple o una clase de caso. Lo que supongo que necesitaría es un método distinct, que toma una función que define la igualdad. ¿Cómo implementaría eso?

Answer 1

Si sus piezas son idénticas, creo que tiene una estructura de datos incorrecta. Desea un Mapa [Int, Int] donde la clave le indique el índice de su cuadrado, y el valor le indica cuántas piezas hay (no hay un conjunto de conteos predeterminado o esto sería aún más fácil). Entonces

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

Esto resuelve todos los problemas en su ejemplo de juguete (pero tal vez no el real). Y se compone muy 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

Como un pico menor, se puede reemplazar con (0 until start.length)start.indices. Una solución recursiva evita el uso de índices por completo:

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

Esto tiene un rendimiento mucho mejor que el uso de acceso indexado, y también tiene una mejor capacidad de memoria de su solución, ya que tiene una muy alta reutilización de los componentes de la lista . También utiliza una técnica funcional común, que es dividir el problema en un paso conocido y recursivo.

Déjenme explicar eso un poco. Para cualquier lista que no esté vacía, uno de los elementos de la solución será una lista con el primer elemento aumentado en uno y todos los demás elementos iguales. Esta es la primera parte de la solución para la lista no vacía de arriba:

head + 1 :: tail 

Ahora, todas las demás soluciones tienen en común que el primer elemento será el mismo.Por lo tanto, imaginar que solutions tiene todas las otras soluciones menos el primer elemento, entonces el siguiente volverá a crear la solución:

solutions map (solution => head :: solution) 

O, en una forma comprimida,

solutions map (head :: _) 

Ahora sólo tenemos que calcular solutions . Da la casualidad que ya tenemos un método para calcular eso: ¡moves en sí mismo! Sólo tenemos que darle de comer al tail de la lista:

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

Por lo tanto, si combinamos estos dos juntos, obtenemos la solución que se muestra en el código de seguridad.

Habiendo dicho todo eso, tampoco estoy seguro de si una lista es una buena estructura de datos para este problema.

En cuanto a obtener una lista distinta de soluciones, si crea una clase para almacenar los movimientos, entonces podría tener un método equals que ignoraba el orden de los elementos, en cuyo caso métodos como distinct funcionarían bien.

Si eso no es viable, puede utilizar una peculiaridad de SortedSet - que utilizan el implícito Ordering para determinar la igualdad - para resolver el problema. Por ejemplo:

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