「あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定」
[西尾泰三，ITmedia] 2010年04月03日 00時00分 更新
前回の記事「麻雀の待ち判定問題」の続きです。
バグがあったということで、リベンジしました。今度こそ完成！今回は、「単騎待ち」や値が重複するのを踏まえて設計をし直しました。
以前のバージョンから、さらに1時間半は使いました。
なお、前回と同じくチートイツとフリテンは考えていません。
大体の時間配分
0:00-0:30 アルゴリズム※1を考えた
0:30-1:50 コーディング&デバッグ
1:50-2:20
単騎の事を考えおらず、アルゴリズム※2練り直し
2:20-3:00 コーディング&デバッグ
3:00-3:30 提示された4種のサンプルは通ったが、
「1112223334445」のように被る場合のことを考えておらずアルゴリズム※3を見直す
3:30-4:30 コーディング&デバッグ
※1 効率化を考え、「ソート後に並んだ2つ（待ち碑と仮定）を取り出してから、チェックしていけばいいんじゃないか」といったもの
※2 頭が出来ていない場合などを考えていなかった。2つ取り出す手法の破錠したので、その場の考えで修正案を。
※3 左端から出来ているのを調べる方法では、被る場合に対処できない。結局、正直に3つの塊を作れるかという考えていくことにした。
反省点
コードを書きながら、アルゴリズムを考えるのではなく、
アルゴリズムを考えてからコードを書いてく手法はよかったが、
考えたアルゴリズムが穴だらけだった。
工夫点は、関数や変数名をわかりやすい名前にしたとか。やっていることが見てわかるような感じにした。
追記・isNormal関数を縮めた。
追記：2011年7月10日
satoshii様のご指摘でソースコードの貼付けにミスがあるのに気が付きました。ありがとうございます！！
オリジナルのソースコードは、「ダウンロード」から
改めて見ると、単騎待ちのチェックの取ってつけた感がすごい。
でも時間制限があるし、しょうがないようね！うん！
import java.awt.Graphics;
import java.awt.Toolkit;
import java.awt.image.BufferedImage;
import java.awt.image.IndexColorModel;
import java.awt.image.MemoryImageSource;
import java.awt.image.Raster;
import java.util.ArrayList;
import java.util.Arrays;
public class Mahjong2 {
static BufferedImage repairBufferedImage(BufferedImage image) {
Raster raster = image.getData();
int height = raster.getHeight();
int width = raster.getWidth();
int datasize = width * height;
final int GRAYSIZE = 256;
int[] color = new int[4];
byte[] pallet_grayscale = new byte[GRAYSIZE];
for(int i=0;i<GRAYSIZE;i++) {
pallet_grayscale[i] = (byte)i;
}
IndexColorModel icm = new IndexColorModel(8,GRAYSIZE,pallet_grayscale,pallet_grayscale,pallet_grayscale);
byte[] indexout = new byte[datasize];
int i = 0;
for(int y=0;y<height;y++) {
for(int x=0;x<width;x++) {
raster.getPixel(x,y,color);
indexout[i] = (byte)color[0];
i++;
}
}
BufferedImage out = new BufferedImage(width,height,BufferedImage.TYPE_BYTE_INDEXED,icm);
Graphics g = out.createGraphics();
g.drawImage(Toolkit.getDefaultToolkit().createImage(new MemoryImageSource(width,height,icm,indexout,0,width)),0,0,null);
g.dispose();
g = null;
return(out);
}
public static void main(String[] args) {
String tiles = "1112345678999";
String[] readyhands = Mahjong2.getReadyHands(tiles);
for (int i = 0; i < readyhands.length; i++) {
System.out.println(readyhands[i]);
}
}
/**
* 麻雀の手牌が入力として与えられたとき「待ち」を出力する
*
* @param tiles
* 入力の麻雀の手牌
* @return
*/
static public String[] getReadyHands(String tiles) {
if (!isNormal(tiles)) {
return (new String[0]);
}
char[] data = getSortingCharacters(tiles).toCharArray();
ArrayList out = new ArrayList();
// 隣あった2つが待ちの状態と考えて抜く
char[] machi = new char[2];
char[] buffer = new char[data.length - 2];
for (int i = 0; i < data.length - 1; i++) {
machi[0] = data[i];
machi[1] = data[i + 1];
if (!isMachi(machi)) {
continue;
}
for (int j = 0, k = 0; j < buffer.length; k++) {
if ((i == k) || (i + 1 == k)) {
continue;
}
buffer[j] = data[k];
j++;
}
String[] memo = new String[4];
checkMati(buffer, machi, memo, out, 0);
}
String[] dst = new String[out.size()];
for (int i = 0; i < out.size(); i++) {
dst[i] = out.get(i);
}
return (getSortStrings(dst));
}
/**
* 待ち状態を調べる
*
* @param tiles
* @param machi
* (これがかぶったときは動作しなくてもいいと思う(｡･ω･｡))
* @param memo
* @param out
* 存在する待ちをここに代入する
*/
static private void checkMati(char[] tiles, char[] machi, String[] memo,
ArrayList out, int depth) {
char[] tripleset = new char[3];
char[] nokori;
for (int i = 0; i < 2; i++) {
if (i == 0) {
nokori = getRemoveSheungFast(tiles, tripleset, 0);
} else {
nokori = getRemovePongFast(tiles, tripleset);
}
if (nokori != null) {
memo[depth] = getString(tripleset);
if (nokori.length == 2) {
if (isAtama(nokori)) {
memo[depth + 1] = getString(nokori);
String text = getOutput(memo, getString(machi));
if (!out.contains(text)) {
out.add(text);
}
}
// 単騎（4枚で調べ直す）
else {
String force = getSortingCharacters(getString(nokori)
+ getString(machi));
char[] data = force.toCharArray();
for (int k = 0; k < 3; k++) {
if (k == 0) {
nokori = getRemoveSheungFast(data, tripleset, 0);
} else if (k == 1) {
nokori = getRemoveSheungFast(data, tripleset, 1);
} else {
nokori = getRemovePongFast(data, tripleset);
}
if (nokori != null) {
memo[depth + 1] = getString(tripleset);
String text = getOutput(memo, getString(nokori));
if (!out.contains(text)) {
out.add(text);
}
}
}
}
} else {
checkMati(nokori, machi, memo, out, depth + 1);
}
}
}
}
/**
* 表示用
*
* @param in1
* 順子・刻子・アタマ
* @param in2
* 待ち
* @return
*/
static private String getOutput(String[] in1, String in2) {
String[] sort = getSortStrings(in1);
String text = "";
int j;
for (j = 0; j < sort.length; j++) {
text = text.concat("(" + sort[j] + ")");
}
text = text.concat("[" + in2 + "]");
return (text);
}
/**
* ソートして返す
*
* @param in
* @return
*/
static private String[] getSortStrings(String[] in) {
String[] out = new String[in.length];
System.arraycopy(in, 0, out, 0, in.length);
Arrays.sort(out);
return (out);
}
/**
* 「待ち」に成りえるかどうか調べる。
*
* @param tiles
* @return
*/
static private boolean isMachi(char[] tiles) {
if (tiles.length == 2) {
if (Math.abs(tiles[1] - tiles[0]) <= 2) {
return (true);
}
}
return (false);
}
/**
* 「頭」に成りえるかどうか調べる。
*
* @param tiles
* @return
*/
static private boolean isAtama(char[] tiles) {
if (tiles.length == 2) {
if (tiles[0] == tiles[1]) {
return (true);
}
}
return (false);
}
/**
* 「順子」があるか調べる。あったら消す。
*
* @param tiles
* @param shuntsu
* 消した順子
* @param x
* 見つかっても無視する回数
* @return 順子をぬいたもの
*/
static private char[] getRemoveSheungFast(char[] tiles, char[] shuntsu,
int x) {
int[] tiletable = new int[9];
for (int i = 0; i < tiles.length; i++) {
tiletable[tiles[i] - '1']++;
}
boolean isshuntsu = false;
for (int i = 0, j = 0; i = 1) && (tiletable[i + 1] >= 1)
&& (tiletable[i + 2] >= 1)) {
if (j < x) {
j++;
continue;
}
shuntsu[0] = (char) (i + '1');
shuntsu[1] = (char) (i + '2');
shuntsu[2] = (char) (i + '3');
tiletable[i + 0]--;
tiletable[i + 1]--;
tiletable[i + 2]--;
isshuntsu = true;
break;
}
}
if (!isshuntsu) {
return (null);
}
return (getCharacters(tiletable));
}
/**
* 「刻子」があるか調べる。あったら消す。
*
* @param tiles
* @param kotsu
* 消した刻子
* @return 刻子をぬいたもの
*/
static private char[] getRemovePongFast(char[] tiles, char[] kotsu) {
int[] tiletable = new int[9];
for (int i = 0; i < tiles.length; i++) {
tiletable[tiles[i] - '1']++;
}
int ispong = -1;
for (int i = 0; i = 3) {
ispong = i;
tiletable[i] -= 3;
break;
}
}
if (ispong == -1) {
return (null);
}
for (int i = 0; i < 3; i++) {
kotsu[i] = (char) (ispong + '1');
}
return (getCharacters(tiletable));
}
/**
* テーブル（9種の碑がそれぞれいくつあるか）から文字配列に変換します。
*
* @param characters
* @return
*/
static private char[] getCharacters(int[] tiletable) {
int sum = 0;
for (int i = 0; i < tiletable.length; i++) {
sum += tiletable[i];
}
char[] out = new char[sum];
for (int i = 0, k = 0; i < tiletable.length; i++) {
for (int j = 0; j < tiletable[i]; j++) {
out[k] = (char) (i + '1');
k++;
}
}
return (out);
}
/**
* 文字配列を文字列に変換します。
*
* @param characters
* @return
*/
static private String getString(char[] characters) {
String out = "";
for (int i = 0; i < characters.length; i++) {
out = out.concat(String.valueOf(characters[i]));
}
return (out);
}
/**
* 与えられた麻雀の手牌をソートする
*
* @param tiles
* @return
*/
static private String getSortingCharacters(String tiles) {
char[] data = tiles.toCharArray();
Arrays.sort(data);
return (getString(data));
}
/**
* 与えられた麻雀の手牌が条件にそっているか調べる。
*
* @param tiles
* @return
*/
static private boolean isNormal(String tiles) {
return ((tiles.matches("[1-9]{13}")));
}
}
コメント
コンパイル通りません。
修正ありがとうございました。
他の方にも同じ指摘をしたのですが、
1111777888999
のときに
5枚目の一萬を待っています。
このときは何も出力しないのが正解のはずです。
さとしさんコメントありがとうございます。
返信遅れてすみません。
ご指摘いただいたとおり間違っていますね。
そもそも4つまでというルールがアルゴリズムに抜けているようです。