Генерация игровых ходов функционально с помощью Scala

Question

Я пытаюсь понять, как писать стратегические игры с использованием 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], а класс Tuple или case.Думаю, мне понадобится метод distinct, который принимает функцию, определяющую равенство.Как бы я это реализовал?

Answer 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

Answer 2

Если ваши части идентичны, я думаю, что вы неправильно указали структуру данных. Вам нужна карта [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)))