11210 - Chinese Mahjong

[hi!man!]

I got WA several times but I do not know why
Here are some test cases.
Input:

Code: Select all

1S 1S 2S 2S 2S 3S 3S 3S 7S 8S 9S FA FA
1S 2S 3S 4S 5S 6S 7S 8S 9S 1T 3T 5T 7T
1W 2W 3W 3W 4W 4W 5W 5W 6W 7W 8W 8W 8W
2W 2W 3W 3W 4W 4W 4W 5W 6W 6W 7W 8W 8W
1W 2W 3W 3W 4W 4W 4W 5W 6W 6W 7W 8W 8W
0

My AC output:

Code: Select all

Case 1: 1S 4S FA
Case 2: Not ready
Case 3: 1W 3W 4W 6W 7W 9W
Case 4: 5W 8W
Case 5: 7W

Are there more tricky cases?
thanks in advance.

[little joey]

Your output is correct.

Code: Select all

4T 5T 6T 6T 6T 6T 7T 7T 8T 8T 9T BAI BAI
0

You should find only 3 waiting tiles.

[hi!man!]

After I modified my program, my output of your input is 3T 9T and BAI,
I think this is correct.
but still WA

Maybe there are a lot of tricky inputs that I can't notice.

Here are other test cases.
Input:

Code: Select all

4T 5T 6T 6T 6T 6T 7T 8T 9T 9T 9T BAI BAI
4T 5T 6T 6T 6T 6T 7T 8T 9T 9T 9T 1W 1W
2T 3T 3T 3T 4T 4T 4T 5T 5T 6T 6T 7T 7T
1T 1T 2T 2T 2T 3T 3T 3T 4T 4T 5T 5T 5T
1T 1T 1T 2T 2T 3T 3T 3T 4T 4T 5T 5T 5T
1T 1T 1T 2T 2T 3T 3T 3T 4T 4T 5T 5T 6T
1T 1T 1T 2T 2T 3T 3T 3T 4T 4T 5T 6T 6T
1T 1T 1T 2T 2T 3T 3T 3T 4T 4T 6T 6T 6T
1T 1T 1T 2T 2T 3T 3T 3T 4T 5T 6T 6T 6T
1T 1T 1T 2T 2T 3T 3T 4T 4T 5T 6T 6T 6T
1T 1T 2T 2T 2T 3T 3T 4T 4T 5T 6T 6T 6T
1T 1T 2T 2T 3T 3T 3T 4T 4T 5T 6T 6T 6T
1T 1T 2T 2T 3T 3T 4T 4T 4T 5T 6T 6T 6T
1T 1T 2T 2T 3T 4T 4T 4T 4T 5T 6T 6T 6T
1T 2T 2T 2T 2T 3T 4T 4T 4T 5T 6T 6T 6T
2T 2T 2T 2T 3T 3T 4T 4T 4T 5T 6T 6T 6T
2T 2T 2T 2T 3T 3T 4T 4T 4T 5T 5T 6T 6T
1T 2T 2T 2T 3T 3T 4T 4T 4T 5T 6T 6T 6T
1T 1T 2T 2T 2T 3T 4T 4T 4T 5T 6T 6T 6T
1T 2T 2T 2T 3T 4T 4T 4T 5T 6T 6T 6T 7T
0

My AC output:

Code: Select all

Case 1: 3T 9T BAI
Case 2: 3T 9T 1W
Case 3: 1T 2T 3T 4T 6T 7T
Case 4: 1T 3T 4T 6T
Case 5: 1T 2T 3T 4T 5T
Case 6: 1T 2T 3T 4T 6T 7T
Case 7: 1T 4T 5T 6T
Case 8: 2T 3T 4T 5T
Case 9: 1T 2T 3T 4T 6T
Case 10: 1T 2T 3T 4T 5T 6T 7T
Case 11: 1T 2T 3T 5T
Case 12: 1T 2T 4T 5T
Case 13: 1T 3T 4T 5T 6T 7T
Case 14: 1T 2T 3T
Case 15: 3T 4T 5T 6T 7T
Case 16: 1T 3T 4T 5T 6T
Case 17: 1T 3T 4T 6T 7T
Case 18: 2T 3T 4T
Case 19: 1T 4T
Case 20: 2T 6T

[rujialiu]

well i cannot think about any tricky test case besides the reason why little joy's test case has only 3 waiting tiles.

maybe you're ordering waiting tiles in a wrong way, or you mispelled something (if you don't know Chinese Characters it's easy to make mistakes). So I suggest you review your code first.

anyway, try these two test cases

Code: Select all

ZHONG ZHONG FA FA BAI BAI BAI DONG DONG DONG NAN NAN NAN
BEI 6T 6T 7T 7T 7T 7T 8T 8T 8T 8T 9T 9T

the output should be

Code: Select all

Case 1: ZHONG FA
Case 2: BEI

[hi!man!]

Thank you for your reply.
I already checked my code for misspelling, but nothing wrong.

Do I need post my code here?

[rujialiu]

yes you can

[rio]

Your second testcases outputs inlcluding wrong answers.
For example, for seventh case:

Code: Select all

1T 1T 1T 2T 2T 3T 3T 3T 4T 4T 5T 6T 6T

You could also wait with 1T and 6T.

Code: Select all

(1,2,3) (2,3,4) (3,4,5) (1,1) (6,6)

----
Rio

[rujialiu]

Oh, i just did not check his second test sets since I don't have my program now

[hi!man!]

ok, I know where is my bug.
now I have to think how to determine the answers.

[EDIT] Finally I got a AC

[kn]

Hi guys, I have been trying different test cases for many times... My code passed all available test cases, and I have been checking the code again and again... but I still don't have any idea on how my program could be wrong. Would anyone please take a look on my code?

The comment should be clear enough.

Code: Select all

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
#define x first
#define y second
typedef pair<int,int> P;
void bug(int x){
                                        for(int i=0;i<13;i++)
                                        putchar((x&(1<<i))?'1':'0');
                                        puts(""); }
map<int,int> mp;
P p[13];
int f2(char *p){ return (*p-'A') * 26 + p[1]-'A'; }
const int M = 1<<13;
char tile[] = "TSW";
char fan[7][6] = {"DONG", "NAN", "XI", "BEI", "ZHONG", "FA", "BAI"};
int toPai(P p){
        putchar(' ');
        if(p.x <= 2){ printf("%d%c", p.y, tile[p.x]); }
        else            { printf("%s", fan[p.y]); }
}
int main(){
        // "style" mapping
        {
                for(int r=0; r<3; r++)
                mp[tile[r]] = r;
                for(int r=0; r<7; r++)
                mp[f2(fan[r])] = r;
        }

        int Zz = 0;
        char s[14][7];
        while(scanf("%s",s[0]), s[0][0]!='0'){
                for(int r=1; r<13; r++)
                        scanf("%s", s[r]);
                
                for(int r=0; r<13; r++)
                {
                        if(isdigit(s[r][0])){
                                p[r].x = mp[s[r][1]];
                                p[r].y = s[r][0] - '0';
                        }else{
                                p[r].x = 3;
                                p[r].y = mp[f2(s[r])];
                        }
                }
                
                sort(p, p+13);
                
                vector<int> a3, a6, a9, a2;
                // a2, a3 (pong)
                for(int a=0; a<13; a++)
                for(int b=a+1; b<13; b++){
                        if(p[b]!=p[a])  continue;
                        int t = (1<<a) | (1<<b);
                        a2.push_back(t);
                        for(int c=b+1; c<13; c++){
                                if(p[c]!=p[b])  continue;
                                a3.push_back(t | (1<<c));
                        }
                }
                
                // a3 (chow)
                for(int a=0; a<13 && p[a].x<3; a++)
                for(int b=a+1; b<13; b++){
                        if(p[b].x != p[a].x)    continue;
                        if(p[b].y != p[a].y+1)  continue;
                        for(int c=b+1; c<13; c++){
                                if(p[c].x != p[b].x)    continue;
                                if(p[c].y != p[b].y+1)  continue;
                                int t = (1<<a) | (1<<b) | (1<<c);
                                a3.push_back(t);
                        }
                }

                // a6
                for(int a=0; a<a3.size(); a++)
                for(int b=a+1; b<a3.size(); b++){
                        int t = a3[a] | a3[b];
                        if( t== a3[a] + a3[b] )
                                a6.push_back(t);
                }

                // a9
                for(int a=0; a<a6.size(); a++)
                for(int b=0; b<a3.size(); b++){
                        int t = a6[a] | a3[b];
                        if( t== a6[a] + a3[b] )
                                a9.push_back(t);
                }

                vector<P> ans;
                // a11
                for(int a=0; a<a2.size(); a++)
                for(int b=0; b<a9.size(); b++){
                        int t = a2[a] | a9[b];
                        if( t== a2[a] + a9[b] ){
                                int res = ~t;
                                
                                int x=0;
                                while(((1<<x)&res)==0)  x++;
                                int y=x+1;
                                while(((1<<y)&res)==0)  y++;
                                
                                if(p[x].x != p[y].x)    continue;
                                else{
                                        if(p[x].y==p[y].y)
                                                ans.push_back(p[x]);
                                        else if(p[x].x < 3){
                                                if(p[x].y==p[y].y-2)    // "Ka Loong"
                                                        ans.push_back(P(p[x].x, p[x].y+1));
                                                else if(p[y].y==p[x].y+1){      // "Double Fly"
                                                        int a[2] = {p[x].y-1, p[x].y+2};
                                                        for(int k=0; k<2; k++)
                                                                if(a[k]>=1 && a[k]<=9)
                                                                        ans.push_back(P(p[x].x, a[k]));
                                                }
                                        }
                                }
                        }
                }
                
                // a12
                for(int a=0; a<a3.size(); a++)
                for(int b=0; b<a9.size(); b++)
                {
                        int t = a3[a] | a9[b];
                        if( t== a3[a] + a9[b] ){
                                int res = ~t;
                                int x = 0;
                                while(!(res&(1<<x))) x++;
                                ans.push_back(p[x]);
                        }
                }

//              printf("a2=%d a3=%d a6=%d a9=%d\n",
//                      a2.size(), a3.size(), a6.size(), a9.size());
                
                printf("Case %d:", ++Zz);
                if(ans.size()){
                        sort(ans.begin(), ans.end());
                        vector<P>::iterator ed = unique(ans.begin(), ans.end());
                        for(vector<P>::iterator it = ans.begin(); it != ed; ++it){
                                // Chk whether there are 4 already
                                int cnt = 0;
                                for(int i=0; i<13; i++) cnt += *it==p[i];
                                if(cnt < 4)
                                toPai(*it);
                        }
                        puts("");
                }else{
                        puts(" Not ready");
                }
        }
        return 0;
}

[kn]

Let me explain a little bit of my algorithm:

First of all, I use 13-bit-pattern to represent a combination.

e.g. 1110011100000 means 1+2+3+6+7+8 piece.

Algorithm:
1) I search for "Chow" and "Pong" (3 pieces), store them in vector<int> a3.
2) Then I search for pair (2 pieces), store them in vector<int> a2
2) Then, I group every 2 compatible combinations in a3, to form an element in vector<int> a6.
e.g. 1110000000000 + 0001110000000 -> 1111110000000
3) Then, I use similar method to search a6, a9, a12, a11
a6 + a3 --> a9
a6 + a6 --> a12
a2 + a9 --> a11
4) Last of all, for each element in a12 and a11 respecitively, I know what Mahjong should I need.
5) I sort all "needed" Mahjong and print them out.

Is my algorithm correct?