stone-game.md

Stone Game

Aug 3, 2020 · 5 min read

Алиса и Боб играют в игру. Есть стопка из n камней. Алиса ходит первой и может снять со стопки любое ненулевое количество камней, которое является квадратом натурального числа (1, 4, 9, 16, …).

Разумеется нельзя снять камней больше, чем есть в стопке. Дальше ходит Боб и имеет право сделать то же самое. Проигрывает тот, кто не может снять ни одного камня.

Предполагая, что игроки всегда принимают оптимальное решение, узнать сможет ли победить Алиса?

Задача на LeetCode.

Решение #

Во-первых, стоит понять условие при котором участник проигрывает, т.е. что означает «не может снять ни одного камня». Это буквально значит, что осталось ноль камней, потому что иначе мы всегда можем снять как минимум один камень и обязаны сделать свой ход.

Во-вторых, что значит «играет оптимально». Это значит, что игроки просчитывают все будущие ходы наперёд и принимают наиболее выгодное для себя решение. По сути, если Алиса может выиграть — она обязательно выиграет.

Первое, что приходит в голову — поиск в глубину. Всё игру можно представить как дерево возможных ходов. Скажем, для n = 4 можно снять 1 камень или 4, далее из каждого узла можно опять же попробовать снять разрешённое количество камней. Если в этом дереве есть путь, который приводит к листу в котором ходит Боб, а там ноль камней — значит он проиграл и Алиса побеждает.

/**
 * @param {number} n
 * @return {boolean}
 */
var winnerSquareGame = function(n) {
  // поиск в глубину,
  // принимает количество камней и чей сейчас ход
  function loose(n, current) {
    // проверяем все квадраты натуральный чисел
    // и запускаем поиск для нового количества камней
    for (let i = 1; i * i <= n; i++) {
      // чей следующий ход?
      const next = current === 'A' ? 'B' : 'A';
      // если в данной ветке НЕ проиграл текущий игрок,
      // то проиграл следующий
      if (loose(n - i * i, next) !== current) {
        return next;
      }
    }
    // если ни при одном варианте хода следующий не смог проиграть,
    // т.е. во всех ветках дерева, в итоге, он выигрывает,
    // то проигрывает текущий игрок
    return current;
  }
  // Алиса выигрывает если проиграл Боб
  return loose(n, 'A') === 'B';
};

В принципе, писать код было не обязательно. Можно оценить заранее сложность и понять, что при ограничениях n <= 10^5 смысла в этом нет.

Действительно, каждый узел в таком дереве будет иметь деток по количеству квадратов натуральных чисел до количества камней в этом узле. Оценим худший случае, при n = 1e5:

let counter = 0;
for (let i = 1; i * i <= 1e5; i++) {
    counter++;
}
// 316
console.log(counter);

Получается, от самого корня дерева у нас будет 316 узлов, и так далее для каждого узла, с уменьшением количества узлов на один с каждым следующим уровнем. Это явно комбинаторный взрыв.

Можно поступить аналогичным задаче про домино и тримино образом и вкрутить кэш, мемоизацию. В данной задаче нам нужно знать победит ли Алиса для данного количества камней, это определяется однозначным образом и зависит только от количества камней.

Для интереса можно попробовать вкрутить кэш самостоятельно. Делитесь впечатлениями в чате! ;-)

Однако, давайте в этот раз разберём другой подход, “bottom-down” вариант динамического программирования.

В этот момент надо очистить разум, как в фильме «Матрица», и зайти с другой стороны. А что если мы можем решить задачу для небольших n, а для n + 1 и далее — построить ответ из того, что у нас уже есть. Пробуем подняться снизу наверх, от меньшего к большему, а не наоборот. Отсюда и названия “top-down” и “bottom-up”.

Тривиальный случай. Для n = 1 Алиса начинает и выигрывает: снимает один камень и Боб не может сделать ни одного хода. Каким образом перейти к решению для n + 1?

Надо проверить все квадраты от 1 до n. Если где-то есть false это означает, что начиная с этого количества камней игрок проиграет, т.е. всё закончится тем, что он останется без камней. Значит если Алиса может прийти в это состояние, а следующий ход обязан сделать Боб, то проиграет он! Это состояние помечается как true, т.е. Алиса выиграет.

Собственно, это и есть весь алгоритм. Получается O(n^1.5) — для каждого n нужно бегать по квадратам (которых корень из n).

/**
 * @param {number} n
 * @return {boolean}
 */
var winnerSquareGame = function(n) {
  // dp[i] — для данного количества
  // камней Алиса побеждает (true) или проигрывает (false)
  const dp = new Array(n + 1).fill(false);
  // тривиальный случай,
  // точно знаем, что Алиса выиграет
  dp[1] = true;

  // решаем задачу для каждого числа 2..n,
  // таким образом постепенно
  // добираясь до n — нужного нам ответа
  for (let i = 2; i <= n; i++) {
    // проверяем все квадраты,
    // т.е. что будет если попробуем снять
    // такое количество камней — сделать ход
    for (let j = 1; j * j <= i; j++) {
      // если там false делаем ход туда, так
      // мы заставим Боба проиграть, потому что
      // он начнёт ходить с заведомо невыгодного
      // количества камней
      if (!dp[i - j * j]) {
        dp[i] = true;
      }
    }
  }
  return dp[n];
};

Можно немного ускориться, написав всего одну строку кода.

for (let j = 1; j * j <= i; j++) {
  // если там false делаем ход туда, так
  // мы заставим Боба проиграть, потому что
  // он начнёт ходить с заведомо невыгодного
  // количества камней
  if (!dp[i - j * j]) {
    dp[i] = true;
+   break;
  }
}

Действительно, нам нужно найти хотя бы один вариант игры при котором Алиса выиграет. Если их несколько — нам это не важно, поэтому можно не перебирать все квадраты до текущего n.

PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.