原创干货!麻将平胡算法
此算法基本可以通用于所有麻将的平胡规则,即满足m * ABC + n * AAA + AA(其中m、n可为0)的胡牌公式,红黑字牌也可由此算法演变。
首先,我们要约定每张麻将都可以由一个数字表示,比如11表示一万,12表示二万,21表示一条,22表示二条,31表示一筒,32表示二筒……
即所有牌用两位数表示,表示万条筒的两位数个位为牌点,十位为牌类型,其它表示非字牌的两位数与牌类型相同,以下用一个枚举类定义:
import java.util.HashMap; import java.util.Map; /** * 麻将类型枚举 * * @author zkpursuit */ public enum CardType { wan(1, "万"), tiao(2, "条"), tong(3, "筒"), dong(40, "东风"), nan(41, "南风"), xi(42, "西风"), bei(43, "北风"), zhong(44, "中"), fa(45, "发"), ban(46, "白板"); //类型 private final int value; //牌名 private final String name; private CardType(int value, String name) { this.value = value; this.name = name; } public int getValue() { return value; } public String getName() { return name; } private static final Map<Integer, String> numMap = new HashMap<>(); private static final Map<Integer, CardType> types = new HashMap<>(); private static final Map<Integer, String> typeNames = new HashMap<>(); static { numMap.put(1, "一"); numMap.put(2, "二"); numMap.put(3, "三"); numMap.put(4, "四"); numMap.put(5, "五"); numMap.put(6, "六"); numMap.put(7, "七"); numMap.put(8, "八"); numMap.put(9, "九"); CardType[] enums = CardType.values(); for (CardType cardType : enums) { types.put(cardType.getValue(), cardType); typeNames.put(cardType.getValue(), cardType.getName()); } } /** * 获取牌类型枚举 * * @param typeValue 牌类型值 * @return 牌类型枚举 */ public static final CardType getCardType(int typeValue) { return types.get(typeValue); } /** * 获取牌的类型名 * * @param typeValue 牌类型 * @return 牌类型名 */ public static final String getCardTypeName(int typeValue) { return typeNames.get(typeValue); } /** * 获取牌类型数值表示 * * @param card 牌号 * @return 牌类型数值表示 */ public static final int getCardTypeValue(int card) { if (card < 40) { return HandCards.getCardLeftValue(card); } return card; } /** * 将牌数据转换为现实中可读的牌 * * @param card 牌数据 * @return 现实中可读的牌 */ public static final String getCardName(int card) { if (card < 40) { int type = HandCards.getCardLeftValue(card); int point = HandCards.getCardRightValue(card); StringBuilder sb = new StringBuilder(); sb.append(numMap.get(point)); sb.append(getCardTypeName(type)); return sb.toString(); } return getCardTypeName(card); } }
以上定义了各张牌的数字表示,接下来我们分析手牌的存储结构,手牌可以用一个数组表示,数组下标号能除尽10的数组元素为保留位,不用于存储任何数据。举例解释此数组存储牌的数据结构:
0号下标保留位
1~9号下标为万字牌牌点,其对应的数组元素为牌的张数
10号下标保留位
11~19号下标为条字牌牌点,其对应的数组元素为牌的张数
20号下标为保留位
21~29号下标为筒字牌牌点,其对应的数组元素为牌的张数
40~46号下标分别表示东、南、西、北、中、发、白的存储位。
根据以上的定义,则可以根据数组下标获得万条筒字牌的类型和牌点,(下标/10 + 1) 则为字牌类型,(下标%10) 则为字牌点数。
具体定义一个手牌类,里面定义了各种静态的换算函数,可参看注释。
/** * 手牌 * * @author zkpursuit */ public class HandCards { /** * 获取牌号最左边的一位数,如果牌为筒、条、万,则返回值为牌类型数值 * * @param card 牌号 * @return 牌号从左至右第一位数(十位数) */ public final static int getCardLeftValue(int card) { return card / 10; } /** * 获取牌号最右边的一位数,如果牌为筒、条、万,则返回值为牌点数 * * @param card 牌号 * @return 牌号从右至左第一位数(个位数) */ public final static int getCardRightValue(int card) { return card % 10; } /** * 获取牌号最左边的一位数,如果牌为筒、条、万,则返回值为牌类型数值 * * @param idx 牌在归类数组中的索引位置 * @return 牌号从左至右第一位数(十位数) */ public final static int getCardLeftValueByClusterIndex(int idx) { return idx / 10 + 1; } /** * 获取牌号最右边的一位数,如果牌为筒、条、万,则返回值为牌点数 * * @param idx 牌在归类数组中的索引位置 * @return 牌号从右至左第一位数(个位数) */ public final static int getCardRightValueByClusterIndex(int idx) { return idx % 10; } /** * 根据牌号取得其所在的牌归类数组中的索引 * * @param card 牌号 * @return 牌归类数组中的索引 */ public final static int getClusterIndexByCard(int card) { int left = getCardLeftValue(card); int right = getCardRightValue(card); int idx = (left - 1) * 10 + right; return idx; } /** * 根据十位数和个位数确定牌在聚合数组中的索引位置 * * @param leftValue 十位数 * @param rightValue 个位数 * @return 聚合数组中的索引位置 */ public final static int getClusterIndex(int leftValue, int rightValue) { return (leftValue - 1) * 10 + rightValue; } /** * 归类牌<br> * 数组索引 / 10 + 1 表示牌类型<br> * 数组索引 % 10 表示牌点数<br> * 数组索引位置的值表示牌数量 */ private int[] cardClusterArray; /** * 起始有效的索引位置<br> * 第一个值不为0的索引位置<br> */ private int startIndex; /** * 归类牌数组的有效索引位置,因为有可能后面的位置全是0<br> * 此索引的后续索引位置的值全部为0,即最后一个值不为0的索引位置<br> */ private int lastIndex; /** * 所有的牌数量 */ private int cardTotals; /** * 构造方法 */ public HandCards() { cardClusterArray = new int[40]; startIndex = 1000; lastIndex = -1; cardTotals = 0; } /** * 构造方法 * * @param cards 未归类的牌数组 */ public HandCards(int[] cards) { this(); if (cards != null) { setCards(cards); } } /** * 重置数据 */ public void reset() { if (cardTotals != 0) { int len = getClusterValidLength(); for (int i = 0; i < len; i++) { cardClusterArray[i] = 0; } } startIndex = 1000; lastIndex = -1; cardTotals = 0; } /** * 清除数据 */ public void clear() { reset(); } /** * 重置数据并以传入的牌数据再次初始化数据 * * @param cards 牌数据 */ public final void setCards(int[] cards) { reset(); for (int card : cards) { addCard(card); } } /** * 添加num张牌 * * @param card 添加的牌号 * @param num 添加的数量 * @return true添加成功;false添加失败 */ public boolean addCard(int card, int num) { int idx = getClusterIndexByCard(card); int lastNum = cardClusterArray[idx] + num; if (lastNum > 4) { return false; } cardClusterArray[idx] = lastNum; if (idx > lastIndex) { lastIndex = idx; } if (idx < startIndex) { startIndex = idx; } cardTotals += num; return true; } /** * 添加一张牌 * * @param card 牌号 * @return true添加成功;false添加失败 */ public boolean addCard(int card) { return addCard(card, 1); } /** * 添加牌集合 * * @param cards 牌集合,比如 [11, 23, 33, 33, 33, 34] * @return true添加成功,只要有一张添加失败则全部失败 */ public boolean addCards(int... cards) { for (int card : cards) { int idx = getClusterIndexByCard(card); int lastNum = cardClusterArray[idx] + 1; if (lastNum > 4) { return false; } } for (int card : cards) { addCard(card); } return true; } /** * 移除num张牌 * * @param card 移除的牌号 * @param num 移除的数量 * @return true移除成功;false移除失败 */ public boolean removeCard(int card, int num) { int idx = getClusterIndexByCard(card); if (cardClusterArray[idx] < num) { return false; } cardClusterArray[idx] -= num; if (cardClusterArray[idx] == 0) { if (idx == startIndex) { startIndex = 1000; for (int i = idx; i < cardClusterArray.length; i++) { if (cardClusterArray[i] > 0) { startIndex = i; break; } } } if (lastIndex == idx) { int start = startIndex; if (start >= cardClusterArray.length) { start = 0; } lastIndex = -1; for (int i = idx; i >= start; i--) { if (cardClusterArray[i] > 0) { lastIndex = i; break; } } } } cardTotals -= num; return true; } /** * 移除一张牌 * * @param card 牌号 * @return true移除成功;false移除失败 */ public boolean removeCard(int card) { return removeCard(card, 1); } /** * 移除牌号对应的所有牌 * * @param card 牌号 * @return true移除成功;false移除失败 */ public boolean removeCardOfAll(int card) { int num = getCardNum(card); if (num >= 0) { return removeCard(card, num); } return true; } /** * 移除牌 * * @param cards 需要移除的牌 * @return true表示移除成功,只要有一张牌移除失败则整个失败 */ public boolean removeCards(int... cards) { for (int card : cards) { int idx = getClusterIndexByCard(card); if (cardClusterArray[idx] < 1) { return false; } } for (int card : cards) { removeCard(card); } return true; } /** * 是否有指定的牌 * * @param card 牌号 * @return true表示存在 */ public boolean hasCard(int card) { return getCardNum(card) > 0; } /** * 获取牌号对应的数量 * * @param card 牌号 * @return 牌号对应的数量 */ public int getCardNum(int card) { int idx = getClusterIndexByCard(card); return cardClusterArray[idx]; } /** * 获取归类的牌数据,整除10的索引位置为保留位,不参与任何实际运算<br> * 数组索引从0开始,有效长度(后面全部为0)结束<br> * 此数组为数据副本,其中的任何数据变动都不会改变原数组<br> * 数组索引 / 10 + 1 表示牌类型<br> * 数组索引 % 10 表示牌点数<br> * * @return 归类的牌数据 */ public int[] getCardClusterArray() { int[] array = new int[getClusterValidLength()]; System.arraycopy(cardClusterArray, 0, array, 0, array.length); return array; } /** * 根据提供的索引位置获取牌数量 * * @param idx 牌归类数组中的索引位置 * @return 牌数量 */ public int getCardNumByClusterIndex(int idx) { return cardClusterArray[idx]; } /** * 根据索引位置定位对应的牌 * * @param idx 归类牌数组中的索引位置 * @return -1表示找不到对应的牌,否则返回牌号 */ public int getCardByClusterIndex(int idx) { if (cardClusterArray[idx] <= 0) { return -1; } int left = getCardLeftValueByClusterIndex(idx); int right = getCardRightValueByClusterIndex(idx); return left * 10 + right; } /** * 归类牌数组中起始有效索引 * * @return 起始有效索引,第一个值不为0的索引位置 */ public int getClusterValidStartIndex() { if (cardTotals == 0) { return 1; } return startIndex; } /** * 归类牌数组中最终的有效索引 * * @return 最终有效索引,其后的值全为0 */ public int getClusterValidEndIndex() { return lastIndex; } /** * 归类牌数组的有效长度<br> * 有效的起始索引到有效的最后索引之前的长度<br> * * @return 有效长度,因为归类数组中后面可能有很多无效的0 */ public int getClusterValidLength() { return lastIndex + 1; } /** * 所有牌的张数 * * @return 总张数 */ public int getCardTotals() { return cardTotals; } /** * 获取所有的牌数据,未归类 * * @return 未归类的牌数据,两位数的牌号数组 */ public int[] getCards() { if (cardTotals <= 0) { return null; } int len = getClusterValidLength(); int[] cards = new int[cardTotals]; int idx = 0; for (int i = getClusterValidStartIndex(); i < len; i++) { int left = getCardLeftValueByClusterIndex(i); int right = getCardRightValueByClusterIndex(i); int count = cardClusterArray[i]; int card = left * 10 + right; for (int j = 0; j < count; j++) { cards[idx] = card; idx++; } } return cards; } @Override public HandCards clone() { HandCards copy = new HandCards(); copy.cardTotals = this.cardTotals; copy.lastIndex = this.lastIndex; copy.startIndex = this.startIndex; if (cardClusterArray != null) { int[] copyCardClusterArray = new int[cardClusterArray.length]; System.arraycopy(cardClusterArray, 0, copyCardClusterArray, 0, cardClusterArray.length); copy.cardClusterArray = copyCardClusterArray; } return copy; } }
准备工作都做好了,怎么使用上面定义的数据结构实现平胡算法呢?平胡满足m * ABC + n * AAA + AA(其中m、n可为0)的胡牌公式,分析此公式,AA表示一对牌,则算法必然需要分析手牌中是否含有一对牌,ABC表示三张相同类型且连续的牌,AAA表示三张相同类型且牌点也相同的牌。
依据公式,我们用递归思路编写一个平胡胡牌算法(其中包含简单的测试用例):
import java.util.Arrays; /** * * @author zkpursuit */ public final class AI { /** * 递归方式判断平胡 * * @param cardClusterArray 牌号和牌数量的簇集对象集合 * @param len 所有牌数量 * @return true表示可以胡牌 */ private static boolean isPingHu(int[] cardClusterArray, int startIndex, int len) { if (len == 0) { return true; } int i; if (len % 3 == 2) { //移除一对(两张牌),胡牌中必须包含一对 for (i = startIndex; i < cardClusterArray.length; i++) { if (cardClusterArray[i] >= 2) { cardClusterArray[i] -= 2; if (AI.isPingHu(cardClusterArray, startIndex, len - 2)) { return true; } cardClusterArray[i] += 2; } } } else { //是否是顺子 int loopCount = cardClusterArray.length - 2; for (i = startIndex; i < loopCount; i++) { int idx1 = i + 1; int idx2 = i + 2; int type1 = HandCards.getCardLeftValueByClusterIndex(i); int type2 = HandCards.getCardLeftValueByClusterIndex(idx1); int type3 = HandCards.getCardLeftValueByClusterIndex(idx2); if (cardClusterArray[i] > 0 && cardClusterArray[idx1] > 0 && cardClusterArray[idx2] > 0 && type1 < 4 && type2 < 4 && type3 < 4) { cardClusterArray[i] -= 1; cardClusterArray[idx1] -= 1; cardClusterArray[idx2] -= 1; if (AI.isPingHu(cardClusterArray, startIndex, len - 3)) { return true; } cardClusterArray[i] += 1; cardClusterArray[idx1] += 1; cardClusterArray[idx2] += 1; } } //三个一样的牌(暗刻) for (i = startIndex; i < cardClusterArray.length; i++) { if (cardClusterArray[i] >= 3) { cardClusterArray[i] -= 3; if (AI.isPingHu(cardClusterArray, startIndex, len - 3)) { return true; } cardClusterArray[i] += 3; } } } return false; } /** * 递归方式判断平胡 * * @param mycards 手牌 * @return true表示可以胡牌 */ public static boolean isPingHu(HandCards mycards) { int[] cardClusterArray = mycards.getCardClusterArray(); int totals = mycards.getCardTotals(); if (totals % 3 != 2) { return false; } return AI.isPingHu(cardClusterArray, mycards.getClusterValidStartIndex(), totals); } public static void main(String[] args) { HandCards handCards = new HandCards(new int[]{11, 12, 13, 22, 23, 24, 33, 33, 33, 36, 36}); System.out.println(Arrays.toString(handCards.getCardClusterArray())); System.out.println(Arrays.toString(handCards.getCards())); for (int i = handCards.getClusterValidStartIndex(); i <= handCards.getClusterValidEndIndex(); i++) { int card = handCards.getCardByClusterIndex(i); if (card > 0) { int num = handCards.getCardNum(card); System.out.println(num + "张 " + CardType.getCardName(card)); } } boolean bool = isPingHu(handCards); System.out.println("是否胡牌:" + bool); } }
![](/img/my/wx.png)
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
cassandra百亿级数据库迁移实践
迁移背景 cassandra集群隔段时间出现rt飙高的问题,带来的影响就是请求cassandra短时间内出现大量超时,这个问题发生已经达到了平均两周一次的频率,已经影响到正常业务了。而出现这些问题的原因主要有以下3点: 当初设计表的时候partition key设计的不是很合理,当数据量上去(最大的单表行数达到百亿级)之后,出现了一些数据量比较大的partition。单partition最多的数据量达到了上百万行(cassandra不支持mysql的limit m, n的查询),当查询这个partition的数据时,会带来比较大的压力。 cassandra本身的墓碑机制,cassandra的一大特性就是快速写入,如果遇到delete一条记录时,cassandra并不会实时的对这条记录做物理删除,而是在这行记录上添加一个逻辑删除的标志位,而下次查询会load出这些已经删除了的记录,再做过滤。这样就可能带来及时某个partition的查询出的数据量不大,但是墓碑比较多的时候会带来严重的性能问题。 公司dba也不推荐使用cassandra,出现问题的时候,难于定位解决问题。所以决定将cass...
- 下一篇
Sentinel Dashboard同步Apollo存储规则
在之前的两篇教程中我们分别介绍了如何将Sentinel的限流规则存储到Nacos和Apollo中。同时,在文末的思考中,我都指出了这两套整合方案都存在一个不足之处:不论采用什么配置中心,限流规则都只能通过Nacos界面或Apollo界面来完成修改才能得到持久化存储,而在Sentinel Dashboard中修改限流规则虽然可以生效,但是不会被持久化到配置中心。而在这两个配置中心里存储的数据是一个Json格式,当存储的规则越来越多,对该Json配置的可读性与可维护性会变的越来越差。所以,下面我们就来继续探讨这个不足之处,并给出相应的解决方案。本文以Apollo存储为例,下一篇介绍Nacos的改在示例。 问题分析 在实际操作之前,我们先通过下图了解一下之前我们所实现的限流规则持久化方案的配置数据流向图: 蓝色箭头代表了限流规则由配置中心发起修改的更新路径 橙色箭头代表了限流规则由Sentinel Dashboard发起修改的更新路径 从图中可以很明显的看到,Sentinel Dashboard与业务服务之间本身是可以互通获取最新限流规则的,这在没有整合配置中心来存储限流规则的时候就已经存在...
相关文章
文章评论
共有0条评论来说两句吧...