问题
在扑克牌游戏中,『一手牌』的意思,是指由5张牌组成、且有分大小的,它们之间从最小到最大的牌型,以下列方式排序:
- 散牌:随意的5张牌,以最大的那张牌比较;
- 一对:有2张同点数的牌,其余3张随意;
- 两对:有2对同点数的牌,其余1张随意;
- 三条:有3张同点数的牌,其余2张随意;
- 顺子:5张点数连续的牌,花色不限;
- 同花:5张花色一样的牌,点数不限;
- 葫芦:有3张同点数的牌,其余2张也是同点数;
- 四条:4张同点数牌,其余1张随意;
- 同花顺:5张点数连续的同花色的牌;
- 皇家同花顺:同花色的10、J、Q、K、A。
牌的点数大小按下面顺序排列:
2、3、4、5、6、7、8、9、10、J、Q、K、A
如果过两个玩家之间的两手牌、牌型相同,则比较两手中的形成牌型的那些牌的点数,大的那个赢;举例,一对8赢一对5(请看下面的例子1)。但如果牌型相同、形成牌型的牌点数也相同,则比较散牌中的点数最大的那张(请看下面例子4);如果散牌中最大的那张点数也相同,则比较散牌当中第二大的那张,如此类推。
请参考下面两个玩家各自5手牌的胜负表:
手 | 玩家1 | 玩家2 | 胜方 |
---|---|---|---|
1 | 5♥ 5♣ 6♠ 7♠ K♦ 一对5 |
2♣ 3♠ 8♠ 8♦ T♦ 一对8 |
玩家2 |
2 | 5♦ 8♣ 9♠ J♠ A♣ 大牌A |
2♣ 5♣ 7♦ 8♠ Q♥ 大牌Q |
玩家1 |
3 | 2♦ 9♣ A♠ A♥ A♣ 三条A |
3♦ 6♦ 7♦ T♦ Q♦ 同花♦ |
玩家2 |
4 | 4♦ 6♠ 9♥ Q♥ Q♣ 一对Q、大牌9 |
3♦ 6♦ 7♥ Q♦ Q♠ 一对Q、大牌7 |
玩家1 |
5 | 2♥ 2♦ 4♣ 4♦ 4♠ 葫芦4 |
3♣ 3♦ 3♠ 9♠ 9♦ 葫芦3 |
玩家1 |
(注意,这里用花色图标代替了原文的花色缩写,以便阅读。它们之间对应的是:♥-H、♣-C、♠-S、♦-D。)
文件poker.txt含有两个玩家的1000次随机的两手对决。文件的每一行都有10张牌(以空格隔开):头5张是玩家1的一手牌、后5张则是玩家2的。你可以认为文件里面的每手牌都是有效的(没有无效字符和重复的牌),每个玩家的每手牌都买有特定的顺序、而每次对决都有明确的赢家。
那么请问,这个文件中,玩家1赢了多少手牌?
* 传送门
分析
这题暴力解题不会很难,但有点复杂,对于不擅长玩扑克牌的我来说,简直是灾难……审题都花了我很多时间……这套规则和国内的『锄大地』有点像,但又不一样,这里比较大小不看花色,最大的不是2而是A。
暴力解题需要对每手牌遍历三次:第一次做数值转换和点算重复点数、第二次按点数排序、第三次排查是否有顺子和拆牌。最后通过重复的点数得出牌型。
计算机执行这个过程当然也算快,但人类似乎更厉害一点。像我这种不会打扑克牌的人,也是有能力一瞬间就看出两手牌谁更大的,而我在解这条题目之前,根本没有这么系统性地思考过这个问题,其实是要对一手牌看三遍才知道大小。人类似乎是看一遍便可以知道大小,这提示着我这个问题肯定有更快的解题方法。
论坛上有将这个题目变成数值化每一手牌的解题方法,但本质上和这个暴力解题过程并没有本质区别——他们用Python的两个元组代替我的拆牌过程、好处是直接可以用大于小于比较符,但JS的数组之间直接用比较符进行对比的行为和Python是不一样的,所以就不打算参考他们的方法了。
JS的数组比较符:[2,2] > [11,11],这是因为JS的数组比较符实际上是以字符串进行比较的,即’22’ > ‘1111’;
Python的元/数组比较符:(2,2) < (11,11),这个行为和题目要求的是一致的。
其实只要解题原理是一样的,我往往倾向写更傻、更笨、更长的代码,因为这样比较好理解。
答案
// answer: brute force
const base_char = '2'.charCodeAt(0)
// 将2、3、4、5、6、7、8、9、10、J、Q、K、A映射为0、1、2、3、4、5、6、7、8、9、10、11、12
function card_point_value(card_point) {
const point = card_point.charCodeAt(0) - base_char
if (point < 8)
return point
else if (card_point === 'T')
return 8
else if (card_point === 'J')
return 9
else if (card_point === 'Q')
return 10
else if (card_point === 'K')
return 11
else if (card_point === 'A')
return 12
else
return -1
}
const WIN = 1, LOSE = -1, TIE = 0
// 这里要求left、right都是按小到大顺序排好的点数
function compare_points(left, right) {
for (let i = left.length - 1; i >= 0; --i) {
const l_point = left[i]
const r_point = right[i]
if (l_point > r_point)
return WIN
else if (l_point < r_point)
return LOSE
}
return TIE
}
const STRAIGHT_FLUSH = 8,
FOUR_OF_A_KIND = 7,
FULL_HOUSE = 6,
FLUSH = 5,
STRAIGHT = 4,
THREE_OF_A_KIND = 3,
TWO_PAIRS = 2,
ONE_PAIRS = 1,
HIGH_CARD = 0
class Hand {
constructor(ranked_points, unranked_points, rank) {
this.ranked_points = ranked_points
this.unranked_points = unranked_points
this.rank = rank
}
compare(other_hand) {
// 先比较牌型
if (this.rank > other_hand.rank)
return WIN
else if (this.rank < other_hand.rank)
return LOSE
else {
// 再比较牌型里面的点数
const ranked_points_result = compare_points(this.ranked_points,
other_hand.ranked_points)
if (ranked_points_result == TIE)
// 再比较牌型外的点数
return compare_points(this.unranked_points,
other_hand.unranked_points)
else
return ranked_points_result
}
return TIE
}
static parse(cards) {
const points = []
const suits = {}
const counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
let max_count = 0
// 第一次遍历,值转换、点算重复点数
for (const card of cards.split(' ')) {
const point = card_point_value(card.charAt(0))
points.push(point)
const suit = card.charAt(1)
suits[suit] = suit
const count = ++counts[point]
if (max_count < count)
max_count = count
}
// 第二次遍历,按数值排序;注意:JS的sort方法默认是按字母顺序排序
points.sort((p0, p1) => p0 - p1)
let suit_count = 0
for (const suit in suits)
suit_count++
const flush = (suit_count == 1)
const ranked_points = [], unranked_points = []
let straight = true
// 第三次遍历,拆牌、查是否有顺子
for (let i = 0; i < points.length; ++i) {
const point = points[i]
if (counts[point] == max_count)
ranked_points.push(point)
else
unranked_points.push(point)
if (i > 0)
straight = (straight && point - points[i-1] == 1)
}
let rank = -1
if (max_count == 1) {
if (flush)
rank = (straight ? STRAIGHT_FLUSH : FLUSH)
else
rank = (straight ? STRAIGHT : HIGH_CARD)
}
else if (max_count == 2)
rank = (ranked_points.length == 4 ? TWO_PAIRS : ONE_PAIRS)
else if (max_count == 3)
rank = (unranked_points[0] == unranked_points[1] ? FULL_HOUSE : THREE_OF_A_KIND)
else if (max_count == 4)
rank = FOUR_OF_A_KIND
return new Hand(ranked_points, unranked_points, rank)
}
}
const $ = jQuery
$.get('/_x_.php?' + $('#p054_poker').attr('href'), function(txt) {
const start = Date.now()
let player1_win = 0, player2_win = 0, tie = 0
for (const line of txt.split('\n'))
if (line.length > 0) {
const hand_1 = Hand.parse(line.substring(0, 14))
const hand_2 = Hand.parse(line.substring(15))
const win_or_lose = hand_1.compare(hand_2)
if (win_or_lose == WIN)
player1_win++
else if (win_or_lose == LOSE)
player2_win++
else // 实际上不对花色进行比较真的会出现平手的,例如两手都是皇家同花顺,但那个txt文件里面没有这样的情况
tie++
}
const result = player1_win
alert(result + ', ' + (Date.now() - start) + 'ms')
})
打赏作者