史上最大のコーディングスキル判定 #makeplex

あなたのスキルで飯は食えるか？　史上最大のコーディングスキル判定というものをやってみた。

丁度2時間くらいで完了。
出題の出力例を比べても問題なさそう。

あと1時間あれば、バッファオーバフローの危険があるところ、マジックナンバーとか変数名を直して、コメントとか整形して、アタマとメンツの修正を一個のロジックにまとめるようなリファクタリングを行えるかな？

考えたポイントは以下。

• パターンマッチの量が大した数じゃないので、単純な総当たりのパターンマッチにしよう。
• 全体でアタマは必ず一個と限定できるので、アタマを最初に固定するパターンと最後にアタマを調べる2パターンに分けると計算量が減らせそう。
• 再帰で実装するが、出力を重複させないため、使用済みパターンを覚えておかないと(コーディング中に気づいたが、パターンを単純な配列でループによる比較にしてたため、容易に実装できたw。)
• これもコーディング中に気づいたのだが、シュンツとアンコを区別する必要はない（からソースのコメントがひどいことにｗ）。

perlとかでやればコーディングの時間はもうちょっと縮められそう。

kuma@localhost ~
$ ./a
1112224588899
(99)(111)(222)(888)[45]

kuma@localhost ~
$ ./a
1122335556799 :
(55)(123)(123)(567)[99]
(99)(123)(123)(567)[55]
(99)(123)(123)(555)[67]

kuma@localhost ~
$ ./a
1112223335559
(123)(123)(123)(555)[9]
(111)(222)(333)(555)[9]

kuma@localhost ~
$ ./a
1223344888999
(123)(234)(888)(999)[4]
(234)(234)(888)(999)[1]
(44)(123)(888)(999)[23]

kuma@localhost ~
$ ./a
1112345678999
(234)(567)(111)(999)[8]
(234)(678)(111)(999)[5]
(345)(678)(111)(999)[2]
(11)(123)(456)(789)[99]
(11)(123)(456)(999)[78]
(11)(123)(678)(999)[45]
(11)(345)(678)(999)[12]
(99)(123)(456)(789)[11]
(99)(234)(567)(111)[89]
(99)(234)(789)(111)[56]
(99)(456)(789)(111)[23]

続きにソースをぺたり。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// アタマ待ち(タンキ)※ノベタンはタンキ待ち二つで表現
int wait_head[] = {1,2,3,4,5,6,7,8,9};//9

// シュンツ待ち(リャンメン、ペンチャン、カンチャン)
int wait_mem[] = {11, 12, 13, 22, 23, 24, 33, 34, 35, 44, 45, 46, 55, 56, 57, 66, 67, 68, 77, 78, 79, 88, 89, 99};//24

int master[9] = {0};

int head_pt[] = {11,22,33,44,55,66,77,88,99};//9
int mem_pt[] = {123,234,345,456,567,678,789, 111,222,333,444,555,666,777,888,999};//16

int match_vals(int target, int *vals)
{
	int test[9];
	memcpy(test, vals, sizeof(test));

	while(target){
		int tmp = (target % 10) -1;
		target /= 10;
		test[tmp]--;
		if(test[tmp] < 0) return 0;
	}
	return 1;
}

void sub_vals(int target, int *vals)
{
	while(target){
		int tmp = (target % 10) -1;
		target /= 10;
		vals[tmp]--;
	}
	return;
}

int is_last(int *vals)
{
	int tmp = 0;
	int i;
	for(i = 0; i < 9; i++){
		tmp += vals[i];
	}
	if(tmp == 1 || tmp == 2) return 1;
	else if(tmp > 2) return 0;
	else return -1;
}

void match_head(char *base, int *vals, int lastmem)
{
	int i;
	char tmp[100];
	if(is_last(vals)){
		for(i = 0; i < 9; i++){
			if(match_vals(wait_head[i], vals)){
				printf("%s[%d]\n", base, wait_head[i]);
				// 他にマッチしようがない
				return;
			}
		}
	} else {
		for(i = lastmem; i < 16; i++){
			if(match_vals(mem_pt[i], vals)){
				int test[9];
				char out[100];
				strcpy(out, base);
				memcpy(test, vals, sizeof(test));
				sprintf(tmp, "(%d)", mem_pt[i]);
				strcat(out, tmp);
				sub_vals(mem_pt[i], test);
				match_head(out, test, i);
			}
		}
	}
	return;
}

void match_mem(char *base, int *vals, int lastmem)
{
	int i;
	char tmp[100];
	if(is_last(vals)){
		for(i = 0; i < 24; i++){
			if(match_vals(wait_mem[i], vals)){
				printf("%s[%d]\n", base, wait_mem[i]);
				// 他にマッチしようがない
				return;
			}
		}
	} else {
		for(i = lastmem; i < 16; i++){
			if(match_vals(mem_pt[i], vals)){
				int test[9];
				char out[100];
				strcpy(out, base);
				memcpy(test, vals, sizeof(test));
				sprintf(tmp, "(%d)", mem_pt[i]);
				strcat(out, tmp);
				sub_vals(mem_pt[i], test);
				match_mem(out, test, i);
			}
		}
	}
	return;
}

int getdata(void)
{
	int i;
	int tmp;
	for(i = 0; i < 13; i++){
		tmp = getchar();

		if(tmp == EOF) return -1;
		tmp = tmp - 0x30 - 1;
		if(tmp < 0 || tmp > 8) return -1;
		master[tmp]++;
	}

	return 0;
}

int main(int argc, char *argv[])
{
	char out[100] = {0};
	if(getdata() != 0) return -1;

	// アタマ待ちのパターン
	match_head(out, master, 0);

	// シュンツ待ちのパターン
	// 先にアタマを確定させる
	int i;
	for(i = 0; i < 9; i++)
	{
		if(match_vals(head_pt[i], master)){
			int test[9];
			sprintf(out, "(%d)", head_pt[i]);
			memcpy(test, master, sizeof(test));
			sub_vals(head_pt[i], test);
			match_mem(out, test, 0);
		}
	}

	return 0;
}

Tags: c/c++