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

関連記事

  • ランダムな添え字ランダムな添え字 こんな感じで。 Java /** * 指定した長さの一様分布な重複しないランダムな添え字を作成します。 * @param length * @param seed * @return */ public static int[] getRandomIndex(int length, long seed) […] Posted in アルゴリズム
  • Fizz-Buzz問題を解いてみた!Fizz-Buzz問題を解いてみた! 今日はネットでFizz-Buzz問題という面白そうなものを見つけた。 Fizz-Buzz問題 はじめに どうしてプログラマに・・・プログラムが書けないのか? http://www.aoky.net/articles/jeff_atwood/why_cant_programmers_program.htm かなりの試行錯誤の末に、コードを書こうともがいている人たちとい […] Posted in アルゴリズム
  • Javaで高速に平方根の逆数を求めるJavaで高速に平方根の逆数を求める シェーディング言語について調べてたら 平方根の逆数を高速に求めるrsqrt関数というのがあるらしいことが分かった。 それで、この rsqrt について調べてたら、Fast inverse square rootっていう高速に計算できる記事を見つけた。 日本語だと、井尻さんのサイトの高速根号計算 (fast sqrt […] Posted in アルゴリズム
  • Bresenhamアルゴリズムで線分の計算は早いのかなBresenhamアルゴリズムで線分の計算は早いのかな 以前、直線を描くのにこんなのを作った。 特に工夫点もない、素直な方法である。 #module "linem" #deffunc line2 int line_x1,int line_y1,int line_x2,int line_y2 line_xabs = abs(line_x1-line_x2) line_yabs = […] Posted in アルゴリズム
  • JavaでStringとint[]の相互変換する方法JavaでStringとint[]の相互変換する方法 はじめに charAt1文字を1変数(コードポイントで)に割り当てたい。 そんな要望からStringとint[]との相互変換を行ってみます。 使い方はお察し下さい。 文字列から数値配列へ static public int[] toInteger(String text) { int textlength = text.length(); for (int […] Posted in プログラミング
  • RSA暗号の解説に出てくる数値の逆数のmodRSA暗号の解説に出てくる数値の逆数のmod RSA暗号に紹介には、必ず次のような式がでてきます。 これ 今日は、この式について解説します。 といっても・・・すみません。言い訳になりますが、 数学科出身ではなく、間違ったこというかもしれません。 それをふまえていただいて・・・解説させていただきます。 まず、m = (p - 1)(q - 1) […] Posted in アルゴリズム