Наконец попалась задача не про простые числа :)
Задача
В карточной игре покер ставка состоит из пяти карт и оценивается от самой младшей до самой старшей в следующем порядке:
- Старшая карта: Карта наибольшего достоинства
- Одна пара: Две карты одного достоинства
- Две пары: Две различные пары карт
- Тройка: Три карты одного достоинства
- Стрейт: Все пять карт по порядку, любые масти
- Флаш: Все пять карт одной масти
- Фул-хаус: Три карты одного достоинства и одна пара карт
- Каре: Четыре карты одного достоинства
- Стрейт-флаш: Любые пять карт одной масти по порядку
- Роял-флаш: Десятка, валет, дама, король и туз одной масти
Достоинство карт оценивается по порядку:
2, 3, 4, 5, 6, 7, 8, 9, 10, валет, дама, король, туз.
Если у двух игроков получились ставки одного порядка, то выигрывает тот, у кого карты старше: к примеру, две восьмерки выигрывают две пятерки. Если же достоинства карт у игроков одинаковы, к примеру, у обоих игроков пара дам, то сравнивают карту наивысшего достоинства; если же и эти карты одинаковы, сравнивают следующие две и т.д.
Файл poker.txt содержит одну тысячу различных ставок для игры двух игроков. В каждой строке файла приведены десять карт (отделенные одним пробелом): первые пять - карты 1-го игрока, оставшиеся пять - карты 2-го игрока. Можете считать, что все ставки верны (нет неверных символов или повторов карт), ставки каждого игрока не следуют в определенном порядке, и что при каждой ставке есть безусловный победитель.
Сколько ставок выиграл 1-й игрок?
Примечание: карты в текстовом файле обозначены в соответствии с английскими наименованиями достоинств и мастей: T - десятка, J - валет, Q - дама, K - король, A - туз; S - пики, C - трефы, H - червы, D - бубны.
Решение
Задача жирная. Начну, вопреки традиции, с основной программы, которую затем уточним.
Структура типа Hand очевидно содержит информацию о карточной руке. С помощью функции parse_hand() структура заполняется 5-ю значениями карт. Значения берутся из строки. Файл я читать не стал. Я бы всё равно прочитал его в строку, поэтому просто поместил эту строку в программу. Плюс в том, что так программу можно будет запустить в онлайне.
Считав две руки hand1 и hand2, сравниваем их состояния state. Если первое состояние больше второго, первый игрок выиграл. Если они равны, производим дополнительную проверку состояний функцией compare_states().
Теперь рассмотрим подробности.
Во-первых, собственно состояния, которые мы сравниваем:
Это enum-константы, которые идут в порядке возрастания и поэтому можно сравнивать одно состояние с другим.
Структура типа Hand:
Она содержит своё состояние state и значение этого состояния state_value (например, пара 2-2 имеет значение 2, а тройка 8-8-8 значение 8). Это нужно для сравнения, когда состояния одинаковы. Поле sorted_vals содержит 5 значений карт, отсортированных по убыванию. Нужно опять же для поиска наибольшего значения в спорных ситуациях. Поле value_counts содержит счётчики для каждого значения карты. Так как отдельные масти в этой задаче роли не играют, требуется информация только о том, что все карты одной масти или нет. Поэтому поле last_suit отвечает за последнюю найденную масть, а поле suit_cnt за количество этой масти.
Теперь посмотрим, как собственно считывается рука:
С помощью memset() очищаем содержимое структуры. Первоначальное состояние всегда ST_HIGHEST. Также сразу запоминаем первую найденную масть в last_suit. Далее считываем 5 кодов карт, соcтоящих из значения и масти. Значение преобразуется из исходной кодировки типа A, K, Q, J, T... в обычные числа с помощью get_val():
Если масть совпадает с last_suit, увеличиваем счётчик suit_cnt. Добавляем считанное значение в руку с помощью hand_add_val(), а затем исправляем текущее состояние с помощью adjust_state().
Как происходит добавление значения карты в руку:
С помощью сортировки пузырьком очередное значение загоняется в отсортированный массив sorted_vals. Также увеличивается счётчик для этого значения value_counts[val].
Осталось понять, в каком состоянии находится рука. Я реализовал что-то вроде конечного автомата, когда при добавлении каждой следующей карты состояние руки может меняться в зависимости от этой карты и предыдущего состояния.
Придётся смотреть функцию adjust_state() по частям:
Итак, если после добавления текущего значения его счётчик стал равен 2, мы очевидно имеем пару. Но если мы до этого уже имели состояние "пара", значит это ещё одна пара, и мы получаем состояние "две пары". Если же до этого было состояние "тройка", то получаем тройку и пару, иначе говоря фулл-хауз. Если же ничего не было, тогда это состояние просто "пара".
Одновременно надо запомнить значение состояния state_value для последующих проверок.
Если счётчик достиг 3, и было состояние "две пары", у нас опять фулл-хауз. Если же двух пар не было, у нас образовалась "тройка". Опять запомним значение состояния state_value.
Если счётчик достиг 4, это состояние "каре" и иначе быть не может.
Ветка default по факту обозначает счётчик 1. Если уже существует какое-то состояние, отличное от базового ST_HIGHEST, то ничего не делаем. Иначе обновляем максимальное значение состояния state_value. Далее специальные случаи. Если добавлена последняя карта (card_idx == 4), то пора проверить на состояние ST_STRAIGHT:
Здесь просто сравниваем попарно все 5 отсортированных значений, а разница между ними должна быть 1.
Наконец, если накопилось 5 карт одной масти (suit_cnt == 5), то проверяем на состояния, связанные с одинаковой мастью:
Проверка на ST_STRAIGHT была сделана ранее, и если она была удачной, то имеем флаш-рояль либо стрейт-флаш. Рояль отличается тем, что в нём не просто какие-то карты по порядку, а именно A, K, Q, J, T и т.д. Так как значения карт отсортированы по убыванию, и мы знаем, что они расположены по порядку, достаточно проверить счётчик value_counts[12], соответствующий карте A. Если она есть, то есть и остальные карты для рояля.
Если же карты вообще не расположены по порядку, то имеем обычный флаш.
Вот и всё. Каждая рука парсится, получаются состояния, состояния сравниваются. Загвоздка возникает, когда они одинаковы. Тогда делаем дополнительные проверки:
Для начала сравниваем state_value. Кто больше, тот и победил. Если и они оказались одинаковые, тогда идём по отсортированному массиву из каждой руки и сравниваем их попарно. Из сравнения исключаются те значения, которые участвовали в state_value.
Ссылка на онлайн-компилятор языка C с текстом программы
Заключение
На мой взгляд, интересная задача, но тестовые данные у неё очень плохие. Они не покрывают всех возможных ситуаций, и мало того, некоторые состояния вообще не встречаются. Спрашивается, ради чего всё делалось? Это позволяет написать такую программу, которая будет содержать ошибки, но на этих данных эти ошибки не проявятся.
Подборка всех задач:
