Игра в камни

Серия задач StoneGame на leetcode — образец игры, где требуется просчитать оптимальную стратегию. Выигрыш/проигрыш начинающего партию предопределен, и второй участник лишь может надеяться на ошибку первого.

Но это не наш случай, т.к. по условию задачи игроки не уступают друг другу и не ошибаются.

Здесь целый список задач, где условия немного варьируются, но суть одна и та же — есть линейный массив, который хранит значения ячеек — баллы, а два игрока Alice и Bob по определенным задачей правилам могут делать ходы по очереди, занимая ячейки и тем самым влияя на выбор второго игрока.

  • 877 Stone Game
  • 1140 Stone Game II
  • 1406 Stone Game III
  • 1510 Stone Game IV
  • 1563 Stone Game V
  • 1686 Stone Game VI
  • 1690 Stone Game VII
  • 1872 Stone Game VIII
  • 2029 Stone Game IX

Задачи маркированы как средние и сложные, что довольно странно, так как суть задач не сильно меняется и все они одинаково сложные.

Для примера разберем 1406 Stone Game III, которая отмечена как сложная. Здесь требуется определить победителя — функция должна вернуть имя игрока ‘Alice’ или ‘Bob’, или констатировать ничью, тогда функция возвращает ‘Tie’.

Игроки по очереди, начиная с Alice, могут брать от 1 до 3х камешков, беря их стоимость себе в зачет. Камни могут иметь и отрицательную стоимость. Цена варьируется от -1000 до 1000.

Разбор примера

Рассмотрим пример. Пусть даны три камешка со значениями [-1,-2,-3].

Алиса полностью владеет ситуацией, т.к. ходит первой. Если она берет 3 камня — то общая сумма получается -6, а Боб выходит сухим из воды, т.к. оба игрока изначально имеют нулевой баланс.

Если Алиса берет 2 камня, то Бобу приходится взять последний, т.к. он не может брать менее одного камня. И тогда наступает ничья — оба игрока набирают по -3 балла.

Если Алиса берет 1 камень, то Боб имеет выбор — взять два оставшихся или только один. Очевидно, что Боб возьмет только один камень, т.к. стоимость камней отрицательная, и Боб желает выиграть. Оставшийся камень достаётся Алисе, и она проигрывает как и в первом случае, набирая тут -4 балла.

Решение задачи — это ничья (Алиса берет 2 камня).

Решение JS/TS

Понятно, что это — рекурсивная задача. Мы каждый раз берем какое то кол-во камней, ход переходит к другому игроку, и снова надо брать какое то кол-во камней. Когда камни кончились — рекурсия достигла завершения.

Т.е. решение будет выглядеть вот так:

Как видите, в коде две неизвестные конструкции.

===TOTAL_SCORE=== — это общее число баллов, т.е. просто сумма всех очков. Если Алиса набрала какую то сумму, то Bob взял всё оставшееся.

===SOMETHING=== — нужно немного воображения, чтобы понять что это. Ясно, что мы должны вызвать здесь count, продолжая рекурсию. Но надо как то учесть, что далее следует ход противника. Если мы просто напишем:

то получим сумму всех камней, но нам нужны только «свои» камни.

Т.к. count должна возвращать лучшее значение для указанной позиции, то лучшее значение для противника на указанной позиции — это остаток камней — count(myPos). Мы тоже самое проделали для позиции 0, где вычли ===TOTAL_SCORE=== — count(0) для Боба.

Получается вместо ===SOMETHING=== требуется написать что то вроде

Число оставшихся камней, начиная с позиции myPos, минус лучшее значение для позиции myPos.

Как оказалось, нам не плохо бы иметь суммы остатков камней — totalRest для каждой позиции. Давайте добавим этот код.

Чтобы это работало быстро, нужно позаботиться о кешировании промежуточных результатов. Добавим массив с кешем значений.

Есть ощущение, что можно как то избежать подсчета остатков сумм, делая это на лету. Но решение было принято системой оценки leetcode, т.е. уложилось в положенное время.

Написать комментарий

Мало букафф? Читайте есчо !

Задача о подмножествах

Апрель 21, 2023 г.

В теории программирования большой класс задач связан с перебором подмножеств, и на leetcode как раз попалась пара похожих задач, чтобы можно было их разобрать как пример - 78 Subsets и 90 Subsets II. Формулировка следующая - есть набор (множество) ...

Читать

Задача следующей комбинации (next permutation)

Март 13, 2023 г.

Мне понадобилось какое то время, чтобы понять верный подход к решению, делюсь подробным разбором этой задачи. Ставится она так: есть набор (массив) элементов, чаще всего чисел, требуется найти следующей по порядку возрастания набор этих элементов. ...

Читать

 

Комментарии к «Игра в камни»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: