すっかり旬がすぎた感がありますが, コーディングスキル判定をやってみました.

makeplex salon：あなたのスキルで飯は食えるか？　史上最大のコーディングスキル判定 (1/2) - ITmedia エンタープライズ

制限時間は3時間とのことなんですが, ながら作業 + ふだんと違う環境でやっていたのでかなり時間がかかってしまいました. いつもの環境で集中してやれば3時間以内でできた...はず...

以下ネタバレになるので, まだ問題をやってなくてこれからチャレンジするつもりのある方は気をつけてください.

問題

麻雀の手牌が与えられるので, "待ち"を出力する. 雀牌は萬子のみ. 待ちが複数あるときは全部出力する. その他細かい条件は上記サイトをみてください.

問題文にけっこうあいまいな部分が多いんですが, 一般的な麻雀のルール(同一牌は4枚とか)にのっとっていると仮定し, ルール的にありえない配牌はないということにしました. また特に明記はされてなかったんですが, 実装が面倒なのでトイトイ(ニコイチの牌だけの役)は無視しました.

方針

ストレートにバックトラックで解きました. 手牌の数と雀牌の数字は決まっているので, (ちゃんとは計算してないんですが)計算量はたいしたことないだろうと考え, dfsで全探索です.

雀牌をソートし, 作ることができるすべての面子・待ちについて分岐させて探索します. 考慮した場合分けは

• 雀頭 or 双碰待ち
• 順子
• 刻子
• 単騎待ち
• 両面 or 辺張待ち
• 嵌張待ち

です. なんらかの待ちが2つ以上重なった場合はそこで探索を打ち切っています. ここで考慮漏れがなければ大丈夫なはずなんですが, テストケース(次で説明)も弱いし正直漏れが無いか若干不安です.

テストケース

テストケースは問題文のサイトにあったサンプル5つと, あとは面倒なのでテンパイになっていない配牌の自作ケース1つだけしか作りませんでした.

テストケースの正答も用意するのが面倒だったので, サイトの解答と出力を目diffしてすませました.

実装

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 13;
vector <int> pais;
vector int> > results;

bool filled(vector <int> &label) {
  int i, n = label.size();
  for (i=0; iif (label[i] == 0)
      return false;
  return true;
}

int r(vector <int> label, bool hasJangToh, int color) {
  int head = 0;
  bool hasMachi = false;
  int i;

  if (filled(label)) {
    results.push_back(label);
    return 0;
  }

  for (i=N-1; i>=0; i--)
    if (label[i] == 0)
      head = i;
    else if (label[i] == 5)
      hasMachi = true;

  int samePos1 = -1, samePos2 = -1, nextPos1 = -1, nextPos2 = -1;
  for (i=head + 1; iif (label[i] == 0) {
      if (pais[i] == pais[head])
        if (samePos1 == -1)
          samePos1 = i;
        else
          samePos2 = i;
      else if (pais[i] == pais[head] + 1)
        nextPos1 = i;
      else if (pais[i] == pais[head] + 2)
        nextPos2 = i;
    }

  // 刻子
  if (samePos1 != -1 && samePos2 != -1) {
    label[head] = label[samePos1] = label[samePos2] = color + 1;
    r(label, hasJangToh, color + 1);
    label[head] = label[samePos1] = label[samePos2] = 0;
  }

  // 順子
  if (nextPos1 != -1 && nextPos2 != -1) {
    label[head] = label[nextPos1] = label[nextPos2] = color + 1;
    r(label, hasJangToh, color + 1);
    label[head] = label[nextPos1] = label[nextPos2] = 0;
  }

  // 雀頭
  if (samePos1 != -1)
    if (hasJangToh && !hasMachi) {
      // 待ち扱い(シャンポン待ち)
      label[head] = label[samePos1] = 5;
      r(label, hasJangToh, color);
      label[head] = label[samePos1] = 0;
    } else if (!hasJangToh && hasMachi) {
      // 雀頭扱い
      label[head] = label[samePos1] = color + 1;
      r(label, true, color + 1);
      label[head] = label[samePos1] = 0;
    } else if (!hasJangToh && !hasMachi) {
      // 雀頭扱い
      label[head] = label[samePos1] = color + 1;
      r(label, true, color + 1);
      label[head] = label[samePos1] = 0;
      // 待ち扱い(シャンポン待ち)
      label[head] = label[samePos1] = 5;
      r(label, hasJangToh, color);
      label[head] = label[samePos1] = 0;
    }

  // 待ち
  if (!hasMachi) {
    // 単騎
    label[head] = 5;
    r(label, hasJangToh, color);
    label[head] = 0;

    // 両面 or 辺張
    if (nextPos1) {
      label[head] = label[nextPos1] = 5;
      r(label, hasJangToh, color);
      label[head] = label[nextPos1] = 0;
    }

    // 嵌張
    if (nextPos2) {
      label[head] = label[nextPos2] = 5;
      r(label, hasJangToh, color);
      label[head] = label[nextPos2] = 0;
    }
  }

  return 0;
}

set  run(void) {
  set  ret;
  vector <int> label(N, 0);
  int i, j;
  results.clear();

  r(label, false, 0);

  for (i=0; i sortedPais(5, "");
    string tmp;
    for (j=0; j1] += pais[j] + '0';
    sort(sortedPais.begin(), sortedPais.end()-1);
    for (j=0; j<4; j++)
      tmp += "(" + sortedPais[j] + ")";
    tmp += "[" + sortedPais[4] + "]";
    ret.insert(tmp);
  }

  return ret;
}

int main(void) {
  string line;
  int i;

  while (getline(cin, line)) {
    pais.clear();
    for (i=0; i'0');
    set  res = run();
    for (set ::iterator i=res.begin(); i!=res.end(); i++)
      cout << *i << ", ";
    cout << endl;
  }

  return 0;
}

雑感

この問題ができたから優秀な人材とは限らないけれど、できない人は“ほぼ確実に”優秀ではない

この言葉の通り, 確かに実装は若干面倒だけど普通の探索なので, アルゴリズム系の問題に慣れている人ならば難なく解ける問題だと思いました(逆にそうでない場合は, べつに時間がかかっても普通じゃないかなと思います). ただ, 今の20代前後の世代にとって麻雀はあまりポピュラーじゃないらしく, 自分のまわりでも麻雀がよくわからないという理由で問題に手を出せていない人が何人かいたので, 少し残念だなと感じました.

自分の出来について. 方針を立てるのはまあ良かったんですが, やはり実装とデバッグに時間がとられました. こういう, 練習さえすればある意味機械的に向上する能力は, 早めにきちんと押さえておきたいです. あとは普段emacs派なんですが, 今回はほぼ生のvimでやったので効率が天と地ほど違いました(言い訳). 普段使うツールに気を配ることは本当に大事です.