18.06.2020 12:36
ThomasAlva 7 2400 Источник



Вы, как и я, может, иногда участвуете в мини-соревнованиях по олимпиадному программированию. Обычно на то, чтобы придумать решение, в котором более одной-двух строк с использованием какой-то нестандартной функции, у меня нет времени, но в этот раз задача была в том, чтобы определять старшие (выигрышные) покерные руки, и мне показалось что это из тех задач, которая «должна» быть лёгкой!

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

Конечно же, в данном случае можно воспользоваться map и reduce, чтобы получить необходимую информацию. Вышел действительно удачный пример того, как использовать эти инструменты для решения в несколько шагов практических задач.
EDISON Software - web-development
Компания EDISON всегда рада помочь в исследовательских бизнес-проектах.


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

Речь не только о том, чтобы «дать взаймы». Мы готовы разделить риски и активно содействовать в создании чего-то нового.

Задача


Она состоит в том, чтобы сравнить две покерные руки и определить выигрышную.

Покерные руки представлены строками, содержащими подстроки (обозначающие отдельные карты) по 2 символа, разделённых пробелами. 2H — это двойка червей, TC — крестовая десятка и т.д.

Первый символ означает ранжир.
Все возможные варианты, упорядоченные по старшинству: 2 3 4 5 6 7 8 9 T J Q K A.
С циферными обозначениями всё понятно, что касается букв: 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" // Какая-то комбинация карт

Нам нужны как масть, так и номинал каждой карты. Однако, учитывая, что единственная причина, по которой мы интересуемся мастью, заключается в том, что если масть у всех карт в руке одинакова, то нет надобности сохранять связку номинал/масть. Это делает процесс парсинга довольно-таки простым:

  1. Конвертация входящей строки в последовательность карт.
  2. Определение масти/номинала в каждой подстроке, обозначающей одну карту.

    Однако, если мы намерены сортировать наши карты, нам нужно, чтобы их было легко сравнивать друг с другом. То есть, A> K (туз больше короля), но при этом Q > J (дама выше валета), то есть видим, что классические буквенные обозначения номинала изначально не отвечают старшинству в алфавитном порядке. Поэтому, добавим третий шаг:
  3. Преобразование номинала в легко сравнимое представление.

У нас в руке 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, которая является оптимальным вариантом.

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

Создаём сравнимые данные


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

  1. Проверяем флеш.
  2. Проверяем стрит.
  3. Определяем дубликаты по номиналу — они нужны для всех остальных типов рук.

Проверяем флеш


Это достаточно просто, поскольку мы распарсили входящую строку и отсортировали по мастям. Если масть последней карты совпадает с мастью первой — у нас флеш.

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) возвращает 1, если flush и direct равны true, иначе возвращает false.

Ничейная ситуация


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

  • Пара против пары. Выигрывает пара с более высоким номиналом. Если номиналы совпадают, выигрывает самая высокая следующая карта. (Для двух пар решается аналогично).

    Например, если сравниваем руку «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, легко подготовить всю информацию, которая нам нужна для решения этой задачи.