Re: あなたのスキルで飯は食えるか？　史上最大のコーディングスキル判定

Program

あなたのスキルで飯は食えるか？　史上最大のコーディングスキル判定
Twitterでこんなものを見かけたので解いてみました。
以下ネタバレ注意。

Code

#include <iostream>

using namespace std;

enum{ N=12, S, K, H };

struct tuple{ int type, n; };
bool operator<(const tuple &a, const tuple &b){
  if(a.type==b.type) return a.n < b.n;
  return a.type<b.type;
}


ostream& operator<<(ostream &os, const tuple &t){
  if(t.type == S)
    return os << '(' << t.n << t.n+1 << t.n+2 << ')';
  else if(t.type == K)
    return os << '(' << t.n << t.n << t.n << ')';
  else
    return os << '(' << t.n << t.n << ')';
}

void rec(int v[], int n, tuple t[], int tn){
  if(n==1){
    // tanki
    for(int i=1;i<=9;++i) 
      if(v[i]) 
	cout << t[0] << t[1] << t[2] << t[3] << '[' << i << ']' << endl;
  }

  if(n==2){
    for(int i=1;i<=9;++i){
      // penchan, ryanmen
      if(v[i] && v[i+1])
	cout << t[0] << t[1] << t[2] << t[3] << '[' << i << i+1 << ']' << endl; 
      
      // kanchan
      if(v[i] && v[i+2])
	cout << t[0] << t[1] << t[2] << t[3] << '[' << i << i+2 << ']' << endl; 

      // shabo
      if(v[i]>=2)
	cout << t[0] << t[1] << t[2] << t[3] << '[' << i << i << ']' << endl; 
    }
  }

  for(int i=1;i<=9;i++){
    if(v[i]>=3){
      v[i]-=3;
      t[tn]=(tuple){K, i};
      if(!(tn && t[tn]<t[tn-1]))
	rec(v, n-3, t, tn+1);
      v[i]+=3;
    }

    if(v[i] && v[i+1] && v[i+2]){
      v[i]--; v[i+1]--; v[i+2]--;
      t[tn]=(tuple){S, i};
      if(!(tn && t[tn]<t[tn-1]))
	rec(v, n-3, t, tn+1);
      v[i]++; v[i+1]++; v[i+2]++;
    }
  }

  if(n==4){
    // to non-tanki
    for(int i=1;i<=9;i++){
      if(v[i]>=2){
	v[i]-=2;
	t[tn]=(tuple){H, i};
	rec(v, n-2, t, tn+1);
	v[i]+=2;
      }
    }
  }
}

int main(){
  string str;
  while(cin >> str){
    int v[N];
    tuple t[4];
    
    for(int i=0;i<N;++i) v[i]=0;

    for(int i=0;i<str.length();++i)
      v[str[i]-'0']++;
    
    //for(int i=0;i<N;++i) cout << v[i]; cout << endl;

    rec(v,13,t,0);
    cout << endl;
  }
  return 0;
}

Output for sample input



(111)(222)(888)(99)[45]
(123)(123)(555)(99)[67]

(123)(123)(567)(55)[99]

(123)(123)(567)(99)[55]
(111)(222)(333)(555)[9]

(123)(123)(123)(555)[9]
(123)(234)(888)(999)[4]

(123)(888)(999)(44)[23]

(234)(234)(888)(999)[1]
(123)(456)(789)(11)[99]

(123)(456)(789)(99)[11]

(123)(456)(999)(11)[78]

(123)(678)(999)(11)[45]

(234)(567)(111)(999)[8]

(234)(567)(111)(99)[89]

(234)(678)(111)(999)[5]

(234)(789)(111)(99)[56]

(345)(678)(111)(999)[2]

(345)(678)(999)(11)[12]

(456)(789)(111)(99)[23]

Notes

  • 所要時間は約40分。
    • いくらなんでも時間掛けすぎだorz
    • 競技プログラミングではないので REP を封印してみたら、コーディング時間が伸びた上にコードが汚くなりました。
      • ガチで REP 完全解禁することを検討してみる頃合いかもしれない。
      • まぁ、競技プログラミング以外で C++ を使うことは現状全然ないのだけど。
  • 方針はただのバックトラック。
    • 残り1枚なら 単騎待ち
    • 残り2枚なら ペンチャンカンチャンシャボ待ち
    • 残り4枚なら 面子かアタマを探す
    • それ以外なら 面子を探す
  • 面子3つをバックトラックで探索して、残り4牌の処理は愚直に書いた方が簡単だったかもしれない。
  • 実は待ちを探す問題を解くのは初めてではない。
    • 高校の頃、麻雀っぽいゲーム (いわゆる17歩) を作ったことがあるので。
    • あと、パソコン甲子園にも同じ問題が出ていたはず。
      • 確か2004年本選だったような。
      • こちらは待ちの形を出すのではなく、待ち牌を全列挙する問題だったけど。
    • そういえばUVaにもあったな。
      • 11210: Chinese Mahjong [link]
      • こっちも待ちを全列挙。ただし萬子索子筒子字牌の区別がある。
    • これだけ書いたことがあるのに40分も掛けるとは終わってる。
  • 工夫した点といえば、入力の持ち方ぐらいか。
    • そのまま持つのではなく、 v[i] = 牌 i の所持枚数 の形で持つ。
    • 範囲外アクセスのチェックをサボるために、配列はちょっと長めにとってみるとか。
  • 何度見直しても汚い。