なたで日記

いろいろな思ったこと書きますヽ(^▽^ゞ) by natade

Posts Tagged ‘正規表現

麻雀の待ち判定問題 リベンジ

with 3 comments


あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定
[西尾泰三,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}")));
	}
}

Written by なたで

2010年4月6日 at 16:39