Вы, как и я, может, иногда участвуете в мини-соревнованиях по олимпиадному программированию. Обычно на то, чтобы придумать решение, в котором более одной-двух строк с использованием какой-то нестандартной функции, у меня нет времени, но в этот раз задача была в том, чтобы определять старшие (выигрышные) покерные руки, и мне показалось что это из тех задач, которая «должна» быть лёгкой!
Получившийся у меня результат корректен, лаконичен и читабелен (по крайней мере, гораздо короче, чем решения, предложенные другими участниками).
Конечно же, в данном случае можно воспользоваться map и reduce, чтобы получить необходимую информацию. Вышел действительно удачный пример того, как использовать эти инструменты для решения в несколько шагов практических задач.
Компания EDISON всегда рада помочь в исследовательских бизнес-проектах.
На протяжении многих лет мы делаем инвестиции в стартапы, помогая средствами и технической поддержкой в реализации свежих нестандартных идей.
Речь не только о том, чтобы «дать взаймы». Мы готовы разделить риски и активно содействовать в создании чего-то нового.
Задача
Она состоит в том, чтобы сравнить две покерные руки и определить выигрышную.
Покерные руки представлены строками, содержащими подстроки (обозначающие отдельные карты) по 2 символа, разделённых пробелами. 2H — это двойка червей, TC — крестовая десятка и т.д.
Первый символ означает ранжир.
Все возможные варианты, упорядоченные по старшинству:
С циферными обозначениями всё понятно, что касается букв: T — это 10 (Ten), J — валет (Jack), Q — дама (Queen), K — король (King), A — туз (Ace).
Второй символ определяет масть.
Возможные варианты: H — черви (Hearts), C — кресты (Clubs), S — пики (Spades), D — бубны (Diamonds).
Например, такая полная строка для руки «2C 5C 3C 4C 6C» — в данном случае, это крестовый стрит-флеш от двойки до шестёрки.
Ранжирование рук взято как в Техасском холдеме.
Нужно понимать, что здесь присутствуют скрытые сложности — использование дополнительных карт для разрешения ничейных ситуаций, использование номинальной стоимости пар и т.д.
Решение
Итак, как же решить эту задачу? Сначала нужно определить способ сравнения, который решает вопрос ранжирования рук, а затем, если ранжирование совпадает, победитель определяется, если это возможно, путём сравнения дополнительных карт.
Поскольку постановка задачи предполагает, что масти равнозначны, используем простой объект для представления ранжирования рук:
{
rank: 1, // Значение в диапазоне от 1 до 9, для ранжирования руки, чем меньше тем выше
value: 'ABCDE' // Пример строки, для сравнения номиналов всех пяти карт в руке, буквы с меньшим ASCII-кодом обозначают более старшие карты
}Теперь мы можем написать простую функцию для сравнения двух рук, представленных в виде этой структуры:
function compareHands(h1, h2) {
let d1 = getHandDetails(h1)
let d2 = getHandDetails(h2)
if (d1.rank === d2.rank) {
if (d1.value < d2.value) {
return "ВЫИГРЫШ"
} else if (d1.value > d2.value) {
return "ПРОИГРЫШ"
} else {
return "НИЧЬЯ"
}
}
return d1.rank < d2.rank ? "ВЫИГРЫШ" : "ПРОИГРЫШ"
}Так что теперь всё, что нам нужно сделать, это создать объект из руки — и вот тут начинается самое интересное!
Разбираем покерную руку на составные части
В подобных случаях необходимо определить основные данные, необходимые для решения задачи. Здесь наша первая проблема — расставить руки по старшинству.
Покерные руки могут быть стритом, флешом или комбинацией нескольких карт с одинаковым номиналом. Наша задача — сначала собрать эту информацию из нашей входной строки. Первый шаг — решить, как распарсить эти данные.
Распарсиваем входящие данные
const input = "AH KS TC 9D 3S" // Какая-то комбинация картНам нужны как масть, так и номинал каждой карты. Однако, учитывая, что единственная причина, по которой мы интересуемся мастью, заключается в том, что если масть у всех карт в руке одинакова, то нет надобности сохранять связку номинал/масть. Это делает процесс парсинга довольно-таки простым:
- Конвертация входящей строки в последовательность карт.
- Определение масти/номинала в каждой подстроке, обозначающей одну карту.
Однако, если мы намерены сортировать наши карты, нам нужно, чтобы их было легко сравнивать друг с другом. То есть, A> K (туз больше короля), но при этом Q > J (дама выше валета), то есть видим, что классические буквенные обозначения номинала изначально не отвечают старшинству в алфавитном порядке. Поэтому, добавим третий шаг: - Преобразование номинала в легко сравнимое представление.
У нас в руке 5 карт, нам в итоге нужно, чтобы значения рук для разрешения ничейных коллизий можно было сравнить в одной операции — поэтому это должна быть именно строка. Поэтому будем переводить номинал наших карт в символы, чтобы потом их можно было вернуть в строку. В общем, нам нужно сделать так, чтобы туз был A, король — B, дама — С, валет — D, десятка — E, девятка — G и т.д.
const order = "23456789TJQKA" //Порядок ранжирования по номиналу во входящей строке
const cards = hand.split(" ") //Разделяем входящую строку на отдельные карты
const faces = cards.map(a => String.fromCharCode([77 - order.indexOf(a[0])])).sort()
const suits = cards.map(a => a[1]).sort()Итак, здесь мы разделили на отдельные карты и выделили в каждой из них её номинал и масть. При этом мы преобразовали номинал в однобуквенное строковое представление, начиная с A (являющееся обозначением для туза, остальные следующие литеры по порядку соответствовали меньшим по номиналу картам). Для этого подсмотрели номер позиции номинала в строковой константе order, отняли это число от 77 и преобразовали обратно в строку. 65 — это код для A, поэтому получаем сопоставимую строку, начинающуюся с A, которая является оптимальным вариантом.
Мы также отсортировали по номиналу и по масти, чтобы позволяет сделать следующий шаг!
Создаём сравнимые данные
Отлично, но теперь нужно сгенерировать ещё немного данных, чтобы можно было написать код для ранжирования рук.
- Проверяем флеш.
- Проверяем стрит.
- Определяем дубликаты по номиналу — они нужны для всех остальных типов рук.
Проверяем флеш
Это достаточно просто, поскольку мы распарсили входящую строку и отсортировали по мастям. Если масть последней карты совпадает с мастью первой — у нас флеш.
const flush = suits[0] === suits[4]Проверяем стрит
Стрит ненамного сложнее — если все карты (независимо от масти) имеют последовательный номинал, то это он и есть.
Мы начинаем с первой карты в руке и для каждой следующей проверяем, является ли значение её номинала последовательным по отношению к предыдущей карте. Используя при этом индекс, переданный через обратный вызов, следующим образом:
const first = faces[0].charCodeAt(0)
const straight = faces.every((f, index) => f.charCodeAt(0) - first === index)Определяем дубликаты
Этот шаг несколько сложнее. Надо посчитать количество для каждого номинала в нашей руке. А также нужен какой-то способ определения пар, троек и т.д., чтобы упростить ранжирование руки таким вот образом:
- Подсчёт количества для каждого номинала
- Преобразование подсчёта в такое предсавление, в котором можно искать.
Нужно добиться того, чтобы можно было определять наличие «четвёрки» (каре) или тройки в руке, количество пар (ни одной, одна или две) и т.д.
Итак, сначала подсчитываем, сколько раз встречаются карты каждого достоинства:
const counts = faces.reduce(count, {})
function count(c, a) {
c[a] = (c[a] || 0) + 1
return c
}И затем производим поиск по этим подсчётам, в прямом смысле «подсчитывая подсчёты».
const duplicates = Object.values(counts).reduce(count, {})Ранжирование рук
Теперь у нас есть вся информация, необходимая для ранжирования рук, пока что без учёта возможных ничейных ситуаций.
let rank =
(flush && straight && 1) || /* Стрит-флеш, в том числе и флеш-рояль - пять последовательных по номиналу карт одной масти */
(duplicates[4] && 2) || /* Каре - четыре карты одного номинала */
(duplicates[3] && duplicates[2] && 3) || /* Фулл-хаус - тройка + пара */
(flush && 4) || /* Флеш - пять непоследовательных карт одной масти */
(straight && 5) || /* Стрит - пять разномастных последовательных по номиналу карт */
(duplicates[3] && 6) || /* Тройка - три карты одного номинала */
(duplicates[2] > 1 && 7) || /* Две пары */
(duplicates[2] && 8) || /*Пара - две карты одного номинала */
9 /* Ни одна из комбинаций выше, просто старшая карта в руке */Таким образом, стрит-флеш является самой сильной комбинацией с рангом 1 (чтобы не усложнять, считаем что возможна ничья, если у кого-то флеш-рояль), затем каре, фулл-хаус и т.д.
При этом причудливо используется оператор &&, который просматривает до последнего значения, если значения в предыдущих скобках верны. Таким образом,
(flush && direct && 1) Ничейная ситуация
Если две руки имеют одинаковый ранг, победитель определяется дополнительно по номиналу карт, если это возможно. С этим связаны некоторые правила.
- Пара против пары. Выигрывает пара с более высоким номиналом. Если номиналы совпадают, выигрывает самая высокая следующая карта. (Для двух пар решается аналогично).
Например, если сравниваем руку «2H 2D AH KC 3D» с рукой «4H 4C JC TC 3H», то выигрывают четвёрки из второй руки, хотя в первой руке самая старшая карта имеет наивысший номинал — туз. - Фул-хаус против фул-хауса. Побеждает тройка с бо́льшим номиналом. Если номиналы троек в обеих руках равны, то смотрим на номиналы двоек.
- Аналогично действуем при сравнении любых рук с одинаковым рангом — решает номинал старшей карты в комбинации.
Поэтому нам нужно сначала отсортировать по количеству, а затем по номиналу в нашей исходящей строке. Помните, используется вся строка из пяти символов для того, чтобы решать случаи с совпадениями рангов рук.
let value = faces.sort(byCountFirst).join("")
function byCountFirst(a, b) {
//Подсчёт в обратном порядке - чем больше, тем лучше
const countDiff = counts[b] - counts[a]
if(countDiff) return countDiff //Если количество не совпадает, возвращаем разницу
return b > a ? -1 : b === a ? 0 : 1
}И это все!
Весь шебанг
const order = "23456789TJQKA"
function getHandDetails(hand) {
const cards = hand.split(" ")
const faces = cards.map(a => String.fromCharCode([77 - order.indexOf(a[0])])).sort()
const suits = cards.map(a => a[1]).sort()
const counts = faces.reduce(count, {})
const duplicates = Object.values(counts).reduce(count, {})
const flush = suits[0] === suits[4]
const first = faces[0].charCodeAt(0)
const straight = faces.every((f, index) => f.charCodeAt(0) - first === index)
let rank =
(flush && straight && 1) || /* Стрит-флеш, в том числе и флеш-рояль - пять последовательных по номиналу карт одной масти */
(duplicates[4] && 2) || /* Каре - четыре карты одного номинала */
(duplicates[3] && duplicates[2] && 3) || /* Фулл-хаус - тройка + пара */
(flush && 4) || /* Флеш - пять непоследовательных карт одной масти */
(straight && 5) || /* Стрит - пять разномастных последовательных по номиналу карт */
(duplicates[3] && 6) || /* Тройка - три карты одного номинала */
(duplicates[2] > 1 && 7) || /* Две пары */
(duplicates[2] && 8) || /*Пара - две карты одного номинала */
9 /* Ни одна из комбинаций выше, просто старшая карта в руке */
return { rank, value: faces.sort(byCountFirst).join("") }
function byCountFirst(a, b) {
//Подсчёт в обратном порядке - чем больше, тем лучше
const countDiff = counts[b] - counts[a]
if(countDiff) return countDiff //Если количество не совпадает, возвращаем разницу
return b > a ? -1 : b === a ? 0 : 1
}
function count(c, a) {
c[a] = (c[a] || 0) + 1
return c
}
}
function compareHands(h1, h2) {
let d1 = getHandDetails(h1)
let d2 = getHandDetails(h2)
if (d1.rank === d2.rank) {
if (d1.value < d2.value) {
return "ВЫИГРЫШ"
} else if (d1.value > d2.value) {
return "ПРОИГРЫШ"
} else {
return "НИЧЬЯ"
}
}
return d1.rank < d2.rank ? "ВЫИГРЫШ" : "ПРОИГРЫШ"
}Итог
Как видите, если мы аккуратно разберём всё по полочкам, можно, применив map и reduce, легко подготовить всю информацию, которая нам нужна для решения этой задачи.
