Серия задач 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
Понятно, что это — рекурсивная задача. Мы каждый раз берем какое то кол-во камней, ход переходит к другому игроку, и снова надо брать какое то кол-во камней. Когда камни кончились — рекурсия достигла завершения.
Т.е. решение будет выглядеть вот так:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
function stoneGameIII(stoneValue: number[]): string { // общее число камней const n = stoneValue.length; // рекурсивная функция, которая // вычисляет лучший результат для указанной // позиции в массиве камней const count = (pos: number): number => { // камни кончились? if (pos >= n) return 0; // по условиям задачи -1000 - это минимум цены камня // а камней можно взять за раз только 3, // потому best я взял с запасом -10000 как // стартовое значение для поиска максимума. let best = -10000 // суммируем камни на очередной итерации в sum let sum = 0 // вспомогательная переменная для отслеживания позиции let myPos = pos for (let i = 1; i <= 3 && pos + i <= n; i ++) { sum += stoneValue[myPos ++] best = Math.max(best, sum + ===SOMETHING===) } return best; } // Алиса начинает const Alice = count(0) const Bob = ===TOTAL_SCORE=== - Alice // далее определяем победителя if (Alice === Bob) return 'Tie'; if (Alice > Bob) return 'Alice'; return 'Bob'; }; |
Как видите, в коде две неизвестные конструкции.
===TOTAL_SCORE=== — это общее число баллов, т.е. просто сумма всех очков. Если Алиса набрала какую то сумму, то Bob взял всё оставшееся.
===SOMETHING=== — нужно немного воображения, чтобы понять что это. Ясно, что мы должны вызвать здесь count, продолжая рекурсию. Но надо как то учесть, что далее следует ход противника. Если мы просто напишем:
|
1 |
sum + count(myPos) |
то получим сумму всех камней, но нам нужны только «свои» камни.
Т.к. count должна возвращать лучшее значение для указанной позиции, то лучшее значение для противника на указанной позиции — это остаток камней — count(myPos). Мы тоже самое проделали для позиции 0, где вычли ===TOTAL_SCORE=== — count(0) для Боба.
Получается вместо ===SOMETHING=== требуется написать что то вроде
|
1 |
totalRest[myPos] - count(myPos) |
Число оставшихся камней, начиная с позиции myPos, минус лучшее значение для позиции myPos.
Как оказалось, нам не плохо бы иметь суммы остатков камней — totalRest для каждой позиции. Давайте добавим этот код.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
function stoneGameIII(stoneValue: number[]): string { const n = stoneValue.length; // подсчет суммы оставшихся камней для каждой позиции, // дополнительно добавим ячейку с нулем в самом конце const totalRest: number[] = new Array(n + 1).fill(0); for (let i = n - 1; i >= 0; i --) { totalRest[i] = stoneValue[i] + totalRest[i + 1]; } const count = (pos: number): number => { if (pos >= n) return 0; let best = -10000, sum = 0, myPos = pos; for (let i = 1; i <= 3 && pos + i <= n; i ++) { sum += stoneValue[myPos ++] best = Math.max(best, sum + totalRest[myPos] - count(myPos)) } return best; } const Alice = count(0), Bob = totalRest[0] - Alice if (Alice === Bob) return 'Tie'; if (Alice > Bob) return 'Alice'; return 'Bob'; }; |
Чтобы это работало быстро, нужно позаботиться о кешировании промежуточных результатов. Добавим массив с кешем значений.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
function stoneGameIII(stoneValue: number[]): string { const n = stoneValue.length; // создадим кеш const cache: number[] = new Array(n); const totalRest: number[] = new Array(n + 1).fill(0); for (let i = n - 1; i >= 0; i --) { totalRest[i] = stoneValue[i] + totalRest[i + 1]; } const count = (pos: number): number => { if (pos >= n) return 0; // вернем значение из кеша if (cache[pos] !== undefined) return cache[pos]; let best = -10000, sum = 0, myPos = pos; for (let i = 1; i <= 3 && pos + i <= n; i ++) { sum += stoneValue[myPos ++] best = Math.max(best, sum + totalRest[myPos] - count(myPos)) } return cache[pos] = best; } const Alice = count(0), Bob = totalRest[0] - Alice if (Alice === Bob) return 'Tie'; if (Alice > Bob) return 'Alice'; return 'Bob'; }; |
Есть ощущение, что можно как то избежать подсчета остатков сумм, делая это на лету. Но решение было принято системой оценки leetcode, т.е. уложилось в положенное время.