MTK编程挑战赛《麻将》

tags: soj 联发科技杯 编程挑战赛

2017 “联发科技杯”编程挑战赛决赛 第6题 《还说不是炸胡?》

题目描述

麻将是国粹,更是成都的生活重心。作为一个成都人,一定要把麻将发扬光大。现在组织有一个重要的任务要交给你:请你设计一个判断是否炸和的程序。

什么是炸和?

炸和(和读作胡),是指达不到和牌条件就把牌推倒了。 那什么是和牌呢? 和牌代表你赢了。当你手上的牌符合三种和牌牌型之一时,就是和牌,可以推倒牌收钱啦。

三种和牌牌型

  1. 普通牌型,14张牌,形如:3+3+3+3+2。其中数字2代表两张相同的牌可成一组,形如XX。数字3代表三张相同或者连续的牌可成一组,形如XXX、XYZ。
  2. 龙七对,14张形如:2+2+2+2+2+2+2。
  3. 带杠,即普通牌型里三张一样的牌XXX可以升级成XXXX,称为一道杠。每多一道杠,牌总数可以增加一张。最多可以有4道杠,因此带杠的和牌,牌总数最多可以达18张。

牌的表示方式

ABCDEFGHI代表一到九萬,abcdefghi代表一到九条,123456789代表一到九饼。

先来练习一下:

  • ABCeee345456DD 和牌,组牌方式为 ABC+eee+345+456+DD,普通牌型。
  • ABeeee345456DD 炸和,因为AB两张牌未能形成组牌。
  • AAAABC123456333 炸和,虽然看似组牌OK(AAA+ABC+124+345+456+333)但是不符合任何一种和牌牌型。
  • AADDFF1133aagg 和牌,龙七对。
  • AAAABBBBCCCCDDDD88 和牌,3+3+3+3+2牌型,升级了4道杠。
  • AAA123789 炸和,不符合任何一种牌型。
  • AAA111345666DEF88 炸和,不符合任何一种牌型。

现在给你一副牌,请用你的程序来判断这副牌是和牌还是炸和。

输入说明

在程序当前目录下存在execute.stdin文件,程序从execute.stdin中取得输入数据。 execute.stdin为单行文件,里面存放着一个字符串,代表一副牌。参考上面牌的表示方式。 注意:牌序是乱的,请自己组牌。

输出说明

若这副牌已经和牌,输出GOOD,炸和则输出BAD。

样例

execute.stdin内容:123BCD999abd66
输出:BAD

分析

不难看出,这道题的核心就在于组牌。

很容易想到的一个思路:每次从牌里抽走一组,若最后剩下牌无法形成组牌,则判负。若没有牌剩下,再判断当前牌型是否属于和牌牌型。

思路简单明了,但是答案没有那么简单。

1. 杠牌的处理

题目里对杠牌的描述具有一定诱导性。如果你顺着“AAA升级成AAAA”的思路去思考,就会把问题搞复杂了。最简单的处理办法就是将AAAA、AAA、AA三种牌型等价并列。

2. 将牌的处理

所谓将牌,就是AA型的牌,除了龙七对这种和法,其它和牌方式都要求有且仅有一对将牌。题目描述有意的避开了将牌的说法,但是会打麻将的人难免会意识到它,于是倾向于单独处理将牌,结果让代码复杂了不少。

事实上根本不需要特殊对待将牌,它就是普通的AA型牌。我们只需要在判断牌型那一关防守好就行了。

3. 抽牌顺序可能导致误判

比如AAAABC这6张牌,按抽牌的顺序,可以出现好几种情况:

  • ABC+AAA (YES)
  • AAA+ABC (YES)
  • AA+AA+BC (NO)
  • AAAA+BC (NO)

后面两种情况显然因为抽牌顺序的原因导致了误判。我们并没有简单可靠的手段来预知某种抽牌方式是对是错。考虑到组牌的规模很小,我们完全可以用试错的方式来进行。所以,如果发现某种抽牌方式无法达成和牌,不能直接判负,而是要继续尝试其它的可能

想清楚上面三个问题后,思路就逐渐清晰了。根据题述规则,可知有以下组牌方式:

  • 三张连续,称为ABC。
  • 两张相同,称为AA。
  • 三张相同,称为AAA。
  • 四张相同,称为AAAA。

可以设计如下的递归算法:

  1. 按某种组牌方式从当前剩余牌中抽走一组牌。重复此步骤,直到:
    • 所有牌被抽走。此时判断牌型是否和牌。若和牌,程序结束。若未和牌,执行步骤2。
    • 剩下牌无法成组。执行步骤2。
  2. 将上一组抽走的牌放回,重复第1步,但要换一种抽牌方式。
  3. 若尝试过所有的组牌方式仍然无法和牌,最终判负。

参考代码

/**************************************************************
 *
 * Hua Shao <nossiac@163.com>
 *
 * MediaTek 2017 Coding Contest, Final, "Mahjong".
 *
 **************************************************************/

#include <iterator>
#include <string>
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>

using namespace std;

class Pattern
{
public:
    vector<char> ABC;
    vector<char> AAAA;
    vector<char> AAA;
    vector<char> AA;
    vector<string> seq;
    void dump()
    {
        vector<string>::const_iterator i;
        for (i = this->seq.begin(); i!=this->seq.end(); ++i)
            cout<<(*i)<<" ";
    }
};

bool make_pair(list<char> &x, Pattern &pattern)
{
    list<char>::iterator i, j, k;

    // looks good, final judge!
    if (x.empty())
    {
        if (7 == pattern.AA.size() &&
            0 == (pattern.AAAA.size() + 
                  pattern.AAA.size() + 
                  pattern.ABC.size()))
        {
            // pattern.dump();
            return true;
        }
        else if (1 == pattern.AA.size() &&
                 4 == (pattern.AAAA.size() + 
                       pattern.AAA.size() + 
                       pattern.ABC.size()))
        {
            // pattern.dump();
            return true;
        }
        else
            return false;
    }

    char a = x.front();

    // AAAA
    if (x.size() >= 4)
    {
        i = ++(x.begin());
        j = ++i;
        k = ++j;
         if(i != x.end() && *i == a &&
            j != x.end() && *j == a &&
            k != x.end() && *k == a)
         {
            x.pop_front();
            x.pop_front();
            x.pop_front();
            x.pop_front();
            pattern.AAAA.push_back(a);
            pattern.seq.push_back(string(4, a));
            if (make_pair(x, pattern)) return true;
            pattern.AAAA.pop_back();
            pattern.seq.pop_back();
            x.push_front(a);
            x.push_front(a);
            x.push_front(a);
            x.push_front(a);
         }

    }

    // AAA
    if (x.size() >= 3)
    {
        i = ++(x.begin());
        j = ++i;

        if (i != x.end() && *i == a && j != x.end() && *j == a)
        {
            x.pop_front();
            x.pop_front();
            x.pop_front();
            pattern.AAA.push_back(a);
            pattern.seq.push_back(string(3, a));
            if (make_pair(x, pattern)) return true;
            pattern.AAA.pop_back();
            pattern.seq.pop_back();
            x.push_front(a);
            x.push_front(a);
            x.push_front(a);
        }
    }


    // ABC
    if (x.size() >= 3)
    {
        i = find(x.begin(), x.end(), a + 1);
        j = find(x.begin(), x.end(), a + 2);
        if(i != x.end() && j != x.end())
        {
            x.pop_front();
            x.erase(i);
            x.erase(j);
            pattern.ABC.push_back(a);
            char tmp[4] = {a, static_cast<char>(a+1), static_cast<char>(a+2),0};
            pattern.seq.push_back(string(tmp));
            if (make_pair(x, pattern)) return true;
            pattern.ABC.pop_back();
            pattern.seq.pop_back();
            x.push_front(a + 2);
            x.push_front(a + 1);
            x.push_front(a);
            x.sort();
        }
    }

    // AA
    if (x.size() >= 2)
    {
        i = ++(x.begin());
        if(i != x.end() && *i == a)
        {
            x.pop_front();
            x.pop_front();
            pattern.AA.push_back(a);
            pattern.seq.push_back(string(2,a));
            if (make_pair(x, pattern)) return true;
            pattern.seq.pop_back();
            pattern.AA.pop_back();
            x.push_front(a);
            x.push_front(a);
        }
    }

    // no more to try
    return false;
}


bool judge(string str)
{
    unsigned i = 0;
    list<char> M;
    Pattern pattern;

    if (str.length()<14 || str.length() > 18)
        return false;

    for (i = 0; i<str.length(); i++)
        M.push_back(str[i]);

    M.sort();

    return make_pair(M, pattern);
}


int main(int argc, char const *argv[])
{

    string p[] =
    {
        "ABCeee345456DD",
        "ABeeee345456DD",
        "AAAABC123456333",
        "AADDFF1133aagg",
        "AAAABBBBCCCCDDDD88",
        "AAA123789",
        "AAA111345666DEF88",
        "AD3Bee55e4D64C",
        "BeAD5De443e5e6",
        "5AC3623331ABA4A",
        "DF1Ag3a3D1gFaA",
        "D8ADCCB8CAABCBABDD",
        "13A279AA8",
        "8E14AFD6A681351A6",
        "3A1414A2433122",
        "53514362243455",
        "11112333345666",
        "AAAABBBBCCCCDD"
    };
    vector<string> testdata(p, p + 18);
    vector<string>::const_iterator i;

    for (i = testdata.begin(); i != testdata.end(); ++i)
    {
        if (judge(*i))
            cout << (*i) << "=" << "GOOD" << endl;
        else
            cout << (*i) << "=" << "BAD" << endl;
    }

    return 0;
}

后记

尽管我用心地简化了麻将和牌规则,并尽可能的用简单明了的话来表述,我仍然担心有些同学理解题意有困难,尤其是很多选手都不是四川人,根本不会打麻将。。。。。我在身边找到了两位不会打麻将的朋友,让他们阅读理解。他们看了不到五分钟,说已经学会打麻将了。哈哈哈哈,我放心了。

然而,这道题决赛通过率只有7%。

很多人都想到了抽牌的办法,但是他们想得还不够深,不够全面。同时,也欠缺了将思路转化成代码的能力

找对了思路又没成功的选手,基本上都在组牌的细节上钻了牛角尖。比如很多人都在下面这两组测试数据上吃了亏:

53514362243455 # 123+234+345+456+55
11112333345666 # 111+123+333+456+66

原因是一些人想单独处理杠牌,或者单独处理将牌。实则把问题复杂化了,然后代码随之变得很复杂,迟迟未能形成最终解法。

想多了一般都是坏事。