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

В нашей предыдущей статье мы разработали код, полезный для реализации игры в покер, но случается, что карточные игры также полезны для иллюстрации нескольких важных алгоритмов CS (компьютерных наук), которые можно применять в самых разных контекстах:

  • Выборка – это процедура, которая позволяет случайным образом выбирать некоторые элементы из набора, придавая каждой возможной комбинации одинаковую вероятность.
  • Перетасовка позволяет рандомизировать порядок группы элементов, снова создавая все возможные перестановки с равными шансами.
  • Сортировка хорошо известна; Учитывая группу элементов, вы хотите расположить их в определенном порядке.

Все эти алгоритмы распространены в информатике, но они встречаются и в карточных играх!

  • Раздача карт (или процедура фокусника «выбери любую карту», ​​которая запускает фокус) являются примерами выборки.
  • Каждая игра начинается с перетасовки колоды (или колод), чтобы обеспечить случайную игру.
  • Большинство игроков применяют алгоритм сортировки, чтобы расположить карты в руках по некоторому правилу.

Итак, в этой статье мы будем использовать пример колоды карт, чтобы предоставить примеры алгоритмов, упомянутых выше. Тестирование этих алгоритмов также важно, но мы понимаем, что эта конкретная задача на самом деле довольно сложна из-за всех имеющихся случайных аспектов; подробнее об этом в следующей статье!

Некоторые определения

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

const RANKS = [
 'A', '2', '3' , '4', '5', '6', '7',
 '8', '9', '10', 'J', 'Q', 'K'
];

const SUITS = ['♥', '♦', '♠', '♣'];

type Card = { rank: number; suit: number };

type Deck = Card[];

Внутренне ранг и масть карты будут соответствовать позициям в массивах RANKS и SUITS. Есть и другие возможности; проверьте раздел Улучшение кода, чтобы найти альтернативу, и рассмотрите возможность включения джокеров в колоду. Для колоды нам не понадобится какая-либо сложная структура данных; подойдет простой массив.

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

const listCards = (hand: Hand) => {
 hand.forEach((c) =>
   console.log(RANKS[c.rank] + SUITS[c.suit])
 );
};

Для нескольких алгоритмов нам понадобится случайная функция, которая возвращает случайное неотрицательное целое число, меньшее заданного предела K, и подойдет следующее.

const randomInt = (k: number): number =>
 Math.floor(k * Math.random());

(Вопрос: понимаете, почему это работает? В качестве подсказки рассмотрим диапазон значений, возвращаемых Math.random(), и диапазон результата умножения.)

Теперь все готово: переходим к алгоритмам.

Создание полной колоды карт

Начнем с самого простого алгоритма: генерации колоды карт.

Создание колоды — это всего пара циклов:

const makeDeck = (): Deck => {
 const deck: Deck = [];
 for (let s = 0; s < SUITS.length; s++) {
   for (let r = 0; r < RANKS.length; r++) {
     deck.push({ rank: r, suit: s });
   }
 }
 return deck;
};

По сути, мы создаем колоду по масти, и для каждой масти мы создаем карты в порядке возрастания, от туза до короля. Эта логика очень проста, и в ней трудно ошибиться. Возможно, вам придется добавить в колоду джокеров; об этом см. раздел Улучшение кода.

Однако созданная последовательность не очень хороша для воспроизведения! (Это эквивалент колоды, которую вы получаете при открытии новой упаковки.) Итак, давайте сразу перейдем к алгоритмам перетасовки, чтобы у нас был интересный игровой процесс.

Перетасовать колоду

Как перетасовать колоду? Фишер-Йейтс — простой, но идеальный способ случайного перетасовки колоды. Базовый алгоритм можно описать в псевдокоде следующим образом:

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

Мы могли бы сделать это, используя два массива: один для исходной колоды, а другой для размещения карт. Однако мы можем добиться большего и не использовать дополнительный массив. Если массив имеет размерность N, подойдет следующее:

for I starting at N-1, going down to 1:
  let J be a random number between 0 and I, inclusive
  exchange the elements at positions I and J

(Вопрос: почему цикл переходит к 1, а не к 0? Будет ли алгоритм работать, если вы позволите I стать 0? Что произойдет на последнем шаге?)

Алгоритм перетасовки теперь такой:

function shuffle(deck: Deck): Deck {
 for (let i = deck.length - 1; i > 0; i--) {
   const j = randomInt(i + 1);
   [deck[i], deck[j]] = [deck[j], deck[i]];
 }
 return deck;
}

Мы можем быстро взглянуть на случайный прогон.

const ddd = makeDeck();
shuffle(ddd);
listCards(ddd);

// Output, edited for clarity

9♦ 10♥  9♣  5♥  J♥  J♦  2♠  J♠  9♥  A♦  9♠  4♥  Q♥
Q♦  7♣  4♦  3♥ 10♣  7♠  3♠  7♦  3♣  4♠  K♣  8♠ 10♠
A♣  6♠  K♥  Q♣  8♣  5♣  6♥  6♣  5♠  Q♠  2♣  A♥  5♦
K♠ 10♦  2♦  2♥  4♣  3♦  6♦  7♥  8♥  K♦  8♦  J♣  A♠

Хорошо, это кажется случайным… но так ли это на самом деле? Или есть какой-то баг? Как мы можем проверить, действительно ли этот алгоритм работает? Это довольно интересный вопрос, который мы рассмотрим в следующей статье серии, обещаю! А пока давайте перейдем к выбору карт.

Выберите карту, любую карту…

Предположим, вы хотите создать случайную карту; как ты делаешь это?

Для первого решения даже не нужна колода; мы можем случайным образом сгенерировать ранг и масть карты. (Вопрос для размышления: что, если в колоде есть джокеры? Несколько вопросов см. в разделе Улучшение кода.)

for several questions.)

const randomRank = (): number => randomInt(RANKS.length);

const randomSuit = (): number => randomInt(SUITS.length);

const randomCard = (): Card => ({
 rank: randomRank(),
 suit: randomSuit()
});

Это очень похоже на компьютерный способ работы — не то, чем вы бы занимались в реальной жизни. Фокусник не просит вас подобрать случайную пару ранга и масти; он предлагал вам колоду, и вы либо выбирали случайную карту из колоды, либо, в противном случае, вы могли перетасовать всю колоду, а затем просто выбрать верхнюю карту. Давайте запомним эти идеи, потому что вы можете захотеть раздать карты, и тогда нам придется быть более осторожными.

Вся необходимая деталь в одном месте

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

Разберись с ними!

Представьте, что вы раздаете покерные руки. Можете ли вы использовать алгоритм из предыдущего раздела? Есть очевидная проблема: если вы просто используете randomCard() пять раз подряд, по чистой случайности вы можете получить два пиковых туза... а наличие дубликатов карт может нанести вред вашему здоровью! Значит, нам нужно нечто большее.

Идеи в конце последнего раздела действительно работают. Учитывая колоду в качестве входных данных (неважно, перетасована она или нет), мы можем выбрать случайную карту, удалить ее из колоды, раздать, а затем повторить процесс столько раз, сколько необходимо.

function randomCardFromDeck(deck: Deck): Card {
 const c = randomInt(deck.length);
 const l = deck.length - 1;
 [deck[c], deck[l]] = [deck[l], deck[c]];
 return deck.pop() as Card;
}

Мы выбираем случайную карту (в позиции c), меняем ее на последнюю позицию в колоде и pop() удаляем карту из колоды. Легкий! Теперь мы можем написать функцию для раздачи руки с указанным количеством карт:

function randomHand(deck: Deck, cards: number): Hand {
 const hand = [] as Deck;
 while (cards > 0) {
   hand.push(randomCardFromDeck(deck));
   cards--;
 }
 return hand;
}

Мы также можем выполнить альтернативную работу, сначала перетасовав колоду; это упрощает задачу, потому что мы можем просто выбирать карты с самого начала, воспользовавшись преимуществом метода splice().

function randomHand2(deck: Deck, cards: number): Hand {
 shuffle(deck);
 return deck.splice(0, cards);
}

Если вы раздавали карты в игре в бридж (в которой четыре игрока, определенные по сторонам света, получают по 13 карт каждый), вы могли бы сделать следующее:

const deck = makeDeck();
const handN: Hand = randomHand2(deck, 13);
const handE: Hand = randomHand2(deck, 13);
const handS: Hand = randomHand2(deck, 13);
const handW: Hand = randomHand2(deck, 13);

(Вопрос: колода опустеет после раздачи последней руки; понимаете, почему?)

В качестве альтернативы вы можете написать функцию, которая разыгрывает все руки одновременно, взяв вдохновение из предыдущего кода randomHand2(). Обратите внимание, как наша функция dealBridgeHands() возвращает кортеж.

function dealBridgeHands(): [Hand, Hand, Hand, Hand] {
 const deck = makeDeck();
 shuffle(deck);
 const handN: Hand = deck.splice(0, 13);
 const handE: Hand = deck.splice(0, 13);
 const handS: Hand = deck.splice(0, 13);
 const handW: Hand = deck; // the remaining 13 cards!
 return [handN, handE, handS, handW];
}

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

Закончим статью сортировкой карточек несколькими способами.

Сортировка карточек

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

Сортировать только по одному полю (скажем, по рангу, как во многих карточных играх) легко — мы используем функцию sortByRank() в sortByRank() для сортировки по соответствующему полю.

const sortByRank = (a: Card, b: Card): number =>  b.rank - a.rank;

function sortByRank(hand: Hand): Hand {
 hand.sort(sortByRank);
 return hand;
}

Обратите внимание, мы написали сортировку в бесточечном стиле, как в еще одной статье серии. Если хотите, вы можете альтернативно написать:

function sortByRank(hand: Hand): Hand {
 hand.sort((a, b) => sortByRank(a, b);
 return hand;
}

Что, если мы хотим отсортировать по рангу, а затем по масти? Мы также можем сделать это за один проход. Нам также понадобится функция для сравнения по мастям.

const sortBySuit = (a: Card, b: Card): number => b.suit - a.suit;

function sortByRankAndSuit(hand: Hand): Hand {
 hand.sort((a, b) => sortByRank(a, b) || sortBySuit(a, b));
 return hand;
}

Как это работает? Если две карты имеют одинаковый ранг, то sortByRank() возвращает ноль, а оператор || тогда возвращает результат сравнения по мастям. Если две карты имеют разные ранги, то sortByRank() возвращает ненулевое значение, а sortBySuit() даже не вызывается.

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

Улучшение кода

Мы можем рассмотреть некоторые улучшения кода, чтобы лучше обеспечить поддержку некоторых конкретных игр.

  • Мы использовали числа (на самом деле целые числа) для рангов и мастей; а как насчет использования enum типов?
  • Во многих играх есть 1 или 2 джокера; как бы вы изменили определение типа Card, чтобы включить их? Убедитесь, что все, что вы делаете, позволяет сортировать колоду; Джокеры идут до или после других карт?
  • В нашем алгоритме генерации случайных карт мы рассматриваем только карты определенного ранга и масти; как бы вы изменили его, чтобы он также генерировал джокеров?
  • Канаста (популярная карточная игра, придуманная на моей родине, в Уругвае!) использует двойную колоду и четыре джокера; можете ли вы написать makeCanastaDeck(), который будет генерировать необходимые карточки?

Заключение

В этой статье мы использовали карточки, чтобы показать несколько важных алгоритмов CS, имеющих множество применений, помимо очевидных игр. Мы использовали TypeScript и предоставили полную типизацию данных для всех примеров, просто для более четкого кода. Если вы хотите запрограммировать какое-нибудь приложение для игры в карты, вам пора уже в путь; просто начни!

Эй… а как насчет тестирования?

Модульное тестирование чистых функций (тех, которые при одних и тех же аргументах всегда возвращают один и тот же результат) простое; вы просто предоставляете некоторые известные аргументы и проверяете ожидаемый результат. Но как нам работать со всеми рассмотренными выше функциями, которые целенаправленно возвращают случайно меняющиеся результаты? (Хорошо, давайте будем честными; сортировка не такая, но перетасовка, выбор и раздача по своей сути случайны.) Это гораздо более сложный вопрос, поэтому мы рассмотрим его в следующей статье серии!

Оригинально опубликовано на https://blog.openreplay.com.