上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
 
清一色限定版をちょっといじったら出来そうだったので、
makeplex salon:あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定
の清一色限定解除版をやってみました。

言語:C
OS:Linux
開発環境:gcc

例によって国士無双は無視。

所要時間
構想:5分
コーディング:25分
デバッグ:30分
計:1時間

元ソース込みで
計:3時間20分

30分位でいけるかなーと思ったら、バグ出して+30分。
合計3時間をオーバーしちゃいました。
まあ現実はそんなもんです。
よね?

以下ソース

解析速度の為に、重複チェックをしないようになっているのがこの子の売りです。
検索開始位置をインクリしていくので、全パターン検索する場合に比べて倍速以上!
自動的に重複チェックも不要という優れもの。
のはずです。

今回の改造の売りは、従来のデータ構造をそのまま流用しているので工数的にリーズナブル。
牌種間で干渉しないように追加した牌を配置しただけです。
その分、無駄な検索もしちゃってますがご愛嬌。


#include <stdio.h>

// 1次元上に萬子筒子索子字牌を配置
// 塔子として認識しないように別種の牌は距離3以上離して配置
#define MANZU_TILE_OFFSET 0
#define PINZU_TILE_OFFSET 11
#define SOUZU_TILE_OFFSET 22
#define NUM_TILE_MAX_NO 30 // 数牌の上限値

#define EAST_TILE 33
#define SOUTH_TILE 36
#define WEST_TILE 39
#define NORTH_TILE 42
#define HAKU_TILE 45
#define HATU_TILE 48
#define TYUN_TILE 51

#define TILE_MAX_NUM 52 // 牌番号の上限値

typedef struct
{
int rest;
int tiles[TILE_MAX_NUM];
int stair_list[TILE_MAX_NUM];
int kind_list[TILE_MAX_NUM];
int head;
}TILE_ARCH;

// デバッグ用 牌リスト出力
void debug_print_tiles(TILE_ARCH* tile_arch)
{
int i;

for(i=0; i<TILE_MAX_NUM; i++)
{
if(tile_arch->tiles[i] != 0)
{
printf("%d[%d] ", i, tile_arch->tiles[i]);
}
}
printf("\n");
}

// 牌構成作成
int make_tile_arch(TILE_ARCH* tile_arch, char* tiles)
{
int i;
int tile_no;
int tile_offset;
char* ptile;

for(i=0; i<TILE_MAX_NUM; i++)
{
tile_arch->tiles[i] = 0;
tile_arch->stair_list[i] = 0;
tile_arch->kind_list[i] = 0;
}
tile_arch->head = -1;
tile_arch->rest = 0;

tile_offset = MANZU_TILE_OFFSET;
ptile = tiles;
while(*ptile != '\0' && *ptile != '\n')
{
switch(*ptile)
{
// "MPS"で数牌の配置先を切り替え
case 'M': tile_offset = MANZU_TILE_OFFSET; break;
case 'P': tile_offset = PINZU_TILE_OFFSET; break;
case 'S': tile_offset = SOUZU_TILE_OFFSET; break;

// 字牌
case 'e': tile_arch->tiles[EAST_TILE]++; tile_arch->rest++; break;
case 's': tile_arch->tiles[SOUTH_TILE]++; tile_arch->rest++; break;
case 'w': tile_arch->tiles[WEST_TILE]++; tile_arch->rest++; break;
case 'n': tile_arch->tiles[NORTH_TILE]++; tile_arch->rest++; break;
case 'x': tile_arch->tiles[HAKU_TILE]++; tile_arch->rest++; break;
case 'y': tile_arch->tiles[HATU_TILE]++; tile_arch->rest++; break;
case 'z': tile_arch->tiles[TYUN_TILE]++; tile_arch->rest++; break;
// 数牌
default:
tile_no = *ptile - '0' - 1;
if(tile_no < 0 || 9 <= tile_no)
{
fprintf(stderr, "invalid tile no->%d\n", tile_no);
return 0;
}
tile_no += tile_offset;

tile_arch->tiles[tile_no]++;
tile_arch->rest++;
break;
}

ptile++;
}

if(tile_arch->rest != 13)
{
fprintf(stderr, "invalid tile num->%d\n", tile_arch->rest);
return 0;
}

return 1;
}

// 数牌の種別を文字出力
void print_num_tile_type(int tile_no)
{
if(MANZU_TILE_OFFSET <= tile_no && tile_no < (MANZU_TILE_OFFSET + 9))
{
printf("M");
}
else if(PINZU_TILE_OFFSET <= tile_no && tile_no < (PINZU_TILE_OFFSET + 9))
{
printf("P");
}
else if(SOUZU_TILE_OFFSET <= tile_no && tile_no < (SOUZU_TILE_OFFSET + 9))
{
printf("S");
}
}

// 数又は字牌を表示用ASCII文字コードに変換
int tile_no_to_char(int tile_no)
{
if(MANZU_TILE_OFFSET <= tile_no && tile_no < (MANZU_TILE_OFFSET + 9))
{
return tile_no - MANZU_TILE_OFFSET + '1';
}
else if(PINZU_TILE_OFFSET <= tile_no && tile_no < (PINZU_TILE_OFFSET + 9))
{
return tile_no - PINZU_TILE_OFFSET + '1';
}
else if(SOUZU_TILE_OFFSET <= tile_no && tile_no < (SOUZU_TILE_OFFSET + 9))
{
return tile_no - SOUZU_TILE_OFFSET + '1';
}
else
{
switch(tile_no)
{
case EAST_TILE: return 'e';
case SOUTH_TILE: return 's';
case WEST_TILE: return 'w';
case NORTH_TILE: return 'n';
case HAKU_TILE: return 'x';
case HATU_TILE: return 'y';
case TYUN_TILE: return 'z';
default:
return '?';
}
}

return '?';
}

// 牌構成を文字列出力
void print_tile_arch(TILE_ARCH* tile_arch, int rest_tile1, int rest_tile2)
{
int i;
int j;
int ch_tmp;

for(i=0; i<TILE_MAX_NUM; i++)
{
// 刻子出力
for(j=0; j<tile_arch->kind_list[i]; j++)
{
print_num_tile_type(i);
ch_tmp = tile_no_to_char(i);
printf("(%c%c%c)", ch_tmp, ch_tmp, ch_tmp);
}

// 順子出力
for(j=0; j<tile_arch->stair_list[i]; j++)
{
print_num_tile_type(i);
ch_tmp = tile_no_to_char(i);
printf("(%c%c%c)", ch_tmp, ch_tmp+1, ch_tmp+2);
}
}

// 頭出力
if(tile_arch->head != -1)
{
print_num_tile_type(tile_arch->head);
ch_tmp = tile_no_to_char(tile_arch->head);
printf("(%c%c)", ch_tmp, ch_tmp);
}

print_num_tile_type(rest_tile1);
// 塔子待ち出力
if(rest_tile2 != -1)
{
ch_tmp = tile_no_to_char(rest_tile1);
printf("[%c", ch_tmp);
ch_tmp = tile_no_to_char(rest_tile2);
printf("%c]\n", ch_tmp);
}
// 単騎待ち出力
else
{
ch_tmp = tile_no_to_char(rest_tile1);
printf("[%c]\n", ch_tmp);
}
}

// 順子構成可能調査
int stair_constructible(int* tiles, int min)
{
int i;
int stair_count;

stair_count = 0;
for(i=min; i<=NUM_TILE_MAX_NO; i++)
{
if(tiles[i] >= 1)
{
stair_count++;
}
else
{
stair_count = 0;
}

if(stair_count >= 3)
{
return i-2;
}
}

return -1;
}

// 刻子構成可能調査
int kind_constructible(int* tiles, int min)
{
int i;

for(i=min; i<TILE_MAX_NUM; i++)
{
if(tiles[i] >= 3)
{
return i;
}
}

return -1;
}

// 頭構成可能調査
int head_constructible(int* tiles, int min)
{
int i;

for(i=min; i<TILE_MAX_NUM; i++)
{
if(tiles[i] >= 2)
{
return i;
}
}

return -1;
}

// 待ち使用可能調査
int usable_rest_tiles(TILE_ARCH* tile_arch, int* rest_tile1, int* rest_tile2)
{
int i;

*rest_tile1 = -1;
*rest_tile2 = -1;
if(tile_arch->rest == 1)
{
for(i=0; i<TILE_MAX_NUM; i++)
{
if(tile_arch->tiles[i] > 0)
{
*rest_tile1 = i;

return 1;
}
}
}
else if(tile_arch->rest == 2)
{
for(i=0; i<TILE_MAX_NUM; i++)
{
if(tile_arch->tiles[i] >= 2)
{
*rest_tile1 = i;
*rest_tile2 = i;

break;
}
else if(tile_arch->tiles[i] == 1)
{
if(*rest_tile1 == -1)
{
*rest_tile1 = i;
}
else
{
*rest_tile2 = i;
break;
}
}
}

if(
(*rest_tile1 == *rest_tile2) ||
((*rest_tile1+1) == *rest_tile2) ||
((*rest_tile1+2) == *rest_tile2))
{
return 1;
}
}

return 0;
}

// 牌構成解析及び待ち出力
void tile_arch_analysis(TILE_ARCH* tile_arch, int min)
{
int tile_no;
int i;
int result;

if(tile_arch->rest <= 2)
{
int rest_tile1;
int rest_tile2;

result = usable_rest_tiles(tile_arch, &rest_tile1, &rest_tile2);
if(result)
{
print_tile_arch(tile_arch, rest_tile1, rest_tile2);
}
return;
}

for(i=min; i<=NUM_TILE_MAX_NO; i++)
{
tile_no = stair_constructible(tile_arch->tiles, i);
if(tile_no != -1)
{
tile_arch->tiles[tile_no]--;
tile_arch->tiles[tile_no+1]--;
tile_arch->tiles[tile_no+2]--;
tile_arch->stair_list[tile_no]++;
tile_arch->rest -= 3;

tile_arch_analysis(tile_arch, tile_no);

tile_arch->tiles[tile_no]++;
tile_arch->tiles[tile_no+1]++;
tile_arch->tiles[tile_no+2]++;
tile_arch->stair_list[tile_no]--;
tile_arch->rest += 3;

i = tile_no;
}
}

for(i=min; i<TILE_MAX_NUM; i++)
{
tile_no = kind_constructible(tile_arch->tiles, i);
if(tile_no != -1)
{
tile_arch->tiles[tile_no] -= 3;
tile_arch->kind_list[tile_no]++;
tile_arch->rest -= 3;

tile_arch_analysis(tile_arch, tile_no+1);

tile_arch->tiles[tile_no] += 3;
tile_arch->kind_list[tile_no]--;
tile_arch->rest += 3;

i = tile_no;
}
}

if(tile_arch->head == -1)
{
for(i=min; i<TILE_MAX_NUM; i++)
{
tile_no = head_constructible(tile_arch->tiles, i);
if(tile_no != -1)
{
tile_arch->tiles[tile_no] -= 2;
tile_arch->head = tile_no;
tile_arch->rest -= 2;

tile_arch_analysis(tile_arch, tile_no+1);

tile_arch->tiles[tile_no] += 2;
tile_arch->head = -1;
tile_arch->rest += 2;

i = tile_no;
}
}
}
}


int main(int argc, char** argv)
{
char tiles[20];
TILE_ARCH tile_arch;

fgets(tiles, sizeof(tiles), stdin);
if(!make_tile_arch(&tile_arch, tiles))
{
fprintf(stderr, "invalid tiles\n");
return -1;
}

tile_arch_analysis(&tile_arch, 0);

return 0;
}



他の方のもいくつか拝見しましたが、すごい短かったり、文字列のままやってたりいい勉強になりますね。
 

<< フロントミッションオンライン -ゲリラ激闘編- 2005/5~2008/5 | Home | makeplex salonの麻雀問題やてみたよ >>

コメント

コメントの投稿

URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 

トラックバック


この記事にトラックバックする(FC2ブログユーザー)


 BLOG TOP 


template and material by HPテンプレート素材集IFD
  1. 無料アクセス解析
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。