Google Developer Day 2011のDevQuizにチャレンジした(2)

(1)からの続き。

スライドパズル

スライドパズルはTwitterにて他の挑戦者のつぶやきを見てると問題解析に結構時間がかかるみたいなので終了間近に参戦した自分としては処理速度優先でLL言語を使うのは最初から放棄。C言語にて作成する事にしました。

プログラム作成に取り掛かる時点でのボーダーラインは100点。スライドパズルはまったく手を付けていない参加者多数と判断し、取り敢えず1問でも解いておけば参加できる可能性が高くなると判断。

まずは人力でスライドを解けるプログラムを作成。それがこちら。

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

static char log[1000000];

typedef struct {
	struct res_t *next;
	char *control;
}res_t;

typedef struct {
	int currentNum;
	int cw, ch;
	int cnt_l;
	int cnt_r;
	int cnt_u;
	int cnt_d;
	int zero_x;
	int zero_y;
	char startData[36];
	char currentData[36];
}game_data_t;

void getZeroPos(game_data_t* game_data) {
	int x, y;
	for(y=0; y<game_data->ch; y++) {
		for(x=0; x<game_data->cw; x++) {
			if (game_data->currentData[y*game_data->cw+x] == '0') {
				game_data->zero_x = x;
				game_data->zero_y = y;
				printf("zero pos:%d, %d\n", x, y);
			}
		}
	}
}

void showData(game_data_t* game_data) {
	int i;
	int x, y;
	printf("input:\n");
	for(i=0; i<game_data->currentNum; i++) {
		printf("%c", log[i]);
	}
	printf("\n");
	for(y=0; y<game_data->ch; y++) {
		for(x=0; x<game_data->cw; x++) {
			printf("%c", game_data->currentData[y*game_data->cw+x]);
		}
		printf("\n");
	}
}

int changeBlankOnly(int mx, int my, game_data_t* game_data) {
	int changeErr = 0;
	int change_x = game_data->zero_x+mx;
	int change_y = game_data->zero_y+my;
	int cw = game_data->cw;
	int ch = game_data->ch;
	char c;
	
	if (change_x < 0 || change_x >= cw ||
		change_y < 0 || change_y >= ch) {
		changeErr = 1;
	} else {
		c = game_data->currentData[change_y*cw+change_x];
		if (c == '=') {
			changeErr = 1;
		}
	}
	if (!changeErr) {
		char tmp = game_data->currentData[game_data->zero_y*cw+game_data->zero_x];
		printf("chang:%c %c\n", game_data->currentData[game_data->zero_y*cw+game_data->zero_x],
			   game_data->currentData[change_y*cw+change_x]);
		game_data->currentData[game_data->zero_y*cw+game_data->zero_x] = game_data->currentData[change_y*cw+change_x];
		game_data->currentData[change_y*cw+change_x] = tmp;
		game_data->zero_x = change_x;
		game_data->zero_y = change_y;
	}
	return changeErr;
}

int changeBlank(int mx, int my, game_data_t* game_data) {
	int changeErr = changeBlankOnly(mx, my, game_data);
	if (!changeErr) {
		if (mx == -1) {
			log[game_data->currentNum++] = 'L';
		} else if (mx == 1) {
			log[game_data->currentNum++] = 'R';
		} else if (my == -1) {
			log[game_data->currentNum++] = 'U';
		} else if (my == 1) {
			log[game_data->currentNum++] = 'D';
		}
	}

	return changeErr;
}

void undo(game_data_t* game_data) {
	int idx = game_data->currentNum-1;
	char c;
	int mx, my;
	mx = my = 0;
	if (idx < 0) {
		printf("no log\n");
	} else {
		c = log[game_data->currentNum-1];
		if (c == 'U') {
			my = 1;
		} else if (c == 'D') {
			my = -1;
		} else if (c == 'L') {
			mx = 1;
		} else if (c == 'R') {
			mx = -1;
		}
	}
	if (changeBlankOnly(mx, my, game_data) == 0) {
		game_data->currentNum--;
	}
}

int main (int argc, const char * argv[]) {
	res_t res;
	game_data_t game_data;
	game_data.currentNum = 1;
	int allNum;
	FILE *fp = fopen("../../in.txt", "r");
//	FILE *fpLog = fopen("../../log.txt", "w");
	if (fp) {
		int l, r, u, d;
		system("clear");
		fscanf(fp, "%d %d %d %d\n", &l, &r, &u, &d);
		fscanf(fp, "%d\n", &allNum);
		while (fscanf(fp, "%d,%d,%s\n", &game_data.cw, &game_data.ch, game_data.startData) != EOF) {
			printf("----\n");
			printf("%d:%d %d %s\n", game_data.currentNum, game_data.cw, game_data.ch, game_data.startData);
			memcpy(game_data.currentData, game_data.startData, game_data.cw*game_data.ch);
			getZeroPos(&game_data);
			showData(&game_data);
			while (1) {
				char c;
				int input_err = 1;

//				c = getchar();
				scanf(" %c", &c);
//				fgets(&c, 1, stdin);
				if (c == 'w') { // up
					input_err = changeBlank(0, -1, &game_data);
				} else if (c == 's') { // down
					input_err = changeBlank(0, 1, &game_data);
				} else if (c == 'a') { // left
					input_err = changeBlank(-1, 0, &game_data);
				} else if (c == 'd') { // right
					input_err = changeBlank(1, 0, &game_data);
				} else if (c == 'z') { // undo
					input_err = 0;
					undo(&game_data);
				}
				printf("zero pos:%d, %d\n", game_data.zero_x, game_data.zero_y);
				printf("input : %c(%d)\n", c, input_err);
				if (!input_err) {
					system("clear");
				} else {
					printf("*** ERR ***\n");
				}
				showData(&game_data);
			}
		}

		fclose(fp);
	} else {
		printf("file read err.");
	}
    return 0;
}

最近はC言語はさっぱり使って無いので「コマンドラインからキーボードの入力取るのはどうするんだったけ?」というレベルの内容まで調べながら作成。しかし、ちょっとプログラムを進めてると勘を取り戻してきて予想より短期間で完成。一番小さい3x3の問題を幾つか解き、取り敢えず提出。

次に自動処理で解析するプログラムを作成しました。それがこちら

#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
#include <assert.h>

//#define DEBUG_ 1
//#define DEBUG2_ 1
//#define DEBUG3_ 1
//#define DEBUG_BOARD_SIZE_	1

#define BOARD_DATA_SIZE	36
#define ADD_ROUTE_SIZE	1024
#define HISTORY_BOARD_SIZE	1024*1024

typedef struct route_t_{
	size_t bef_node_num;
	char board[BOARD_DATA_SIZE];
	char blank_x;
	char blank_y;
	char move_dir;
	char skip;
	int node_num;
}route_t;

char board_w, board_h;
route_t* routeArray = NULL;
int full_route_num = 0;
int enable_route_num = 0;
int checked_route_num = 0;
int added_chkpnt_num = 0;
char cleared_borad[BOARD_DATA_SIZE];
char history_full = 0;
int ins_history_idx = 0;
char history_borad[HISTORY_BOARD_SIZE][BOARD_DATA_SIZE];

void showBoard(char *board);

void copyBoardData(char* board_a, char* board_b) {
	memcpy(board_a, board_b, board_w*board_h);
}

int isGameClear(char* board) {
	if (cleared_borad[0] == board[0]) {
		return memcmp(cleared_borad, board, board_w*board_h);
	} else {
		return -1;
	}
}

void addRoute(char move_dir) {
	if (!routeArray) {
		routeArray = (route_t*)calloc(ADD_ROUTE_SIZE, sizeof(route_t));
		full_route_num = ADD_ROUTE_SIZE;
	} else if (enable_route_num >= full_route_num) {
		full_route_num = enable_route_num+ADD_ROUTE_SIZE;
#ifdef DEBUG_BOARD_SIZE_
		printf("size : %d\n", full_route_num);
#endif
		routeArray = (route_t*)realloc(routeArray, full_route_num*sizeof(route_t));
		assert(routeArray != NULL);
		/*
		int i;
		printf("-- %d\n", enable_route_num);
		for (i=0; i<full_route_num; i++) {
			printf("--\n");
			showBoard(routeArray[i].board);
		}*/
		memset(&routeArray[full_route_num-ADD_ROUTE_SIZE], 0, ADD_ROUTE_SIZE*sizeof(route_t));
		/*
		printf("--- af\n");
		for (i=0; i<full_route_num; i++) {
			printf("--\n");
			showBoard(routeArray[i].board);
		}
		printf("stop");
		 */
	}
	route_t *bef_node = NULL;
	if (enable_route_num != 0 && enable_route_num >= added_chkpnt_num) {
		bef_node = &routeArray[added_chkpnt_num];
#ifdef DEBUG_
		static int count = 0;
		count++;
				
		printf("***[%d]addRoute %d dir: %c bef_node_num: %d\n", enable_route_num, count, 
			   move_dir, bef_node->node_num);
		showBoard(bef_node->board);
#endif
		routeArray[enable_route_num] = *bef_node;
		routeArray[enable_route_num].skip = 0;
		routeArray[enable_route_num].node_num = enable_route_num;
		routeArray[enable_route_num].move_dir = move_dir;
#ifdef DEBUG_
		printf("%d -> %d\n", routeArray[enable_route_num].node_num, bef_node->node_num);
#endif
		routeArray[enable_route_num].bef_node_num = bef_node->node_num;
	}
	enable_route_num++;
}

void getBlankPos(route_t* route) {
	char x, y;
	for(y=0; y<board_h; y++) {
		for(x=0; x<board_w; x++) {
			if (route->board[y*board_w+x] == '0') {
				route->blank_x = x;
				route->blank_y = y;
#ifdef DEBUG_
				printf("blank pos: %d, %d\n", route->blank_x, route->blank_y);
#endif
			}
		}
	}
}

void showBoard(char *board) {
#ifdef DEBUG_
	char x, y;
//	printf("[board]\n");
	for(y=0; y<board_h; y++) {
		for(x=0; x<board_w; x++) {
			printf("%c", board[y*board_w+x]);
		}
		printf("\n");
	}
#endif
}

void getGameClearBoardData(char *board) {
	char x, y;
	char maxChar = '1';
	char allCharArray[] = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	for(y=0; y<board_h; y++) {
		for(x=0; x<board_w; x++) {
			if (maxChar < board[y*board_w+x]) {
				maxChar = board[y*board_w+x];
			}
		}
	}
	for(y=0; y<board_h; y++) {
		for(x=0; x<board_w; x++) {
			if (board[y*board_w+x] == '=') {
				cleared_borad[y*board_w+x] = '=';
			} else {
				cleared_borad[y*board_w+x] = allCharArray[y*board_w+x];
			}
		}
	}
	cleared_borad[board_w*board_h-1] = '0';
#ifdef DEBUG_
	printf("clear board\n");
	showBoard(cleared_borad);
#endif
}

int checkClear(char *board) {
	return memcmp(cleared_borad, board, board_w*board_h);
}

void changeBlank(int mx, int my, route_t* route) {
	int idx1 = route->blank_y*board_w+route->blank_x;
	int idx2 = (route->blank_y+my)*board_w+route->blank_x+mx;
	char tmp = route->board[idx1];
	route->board[idx1] = route->board[idx2];
	route->board[idx2] = tmp;
	route->blank_x += mx;
	route->blank_y += my;
}

int addCheckPoint() {
	int i;
	char dirArray[] = "UDLR";
	char d;
	char mx;
	char my;
	route_t *route;
	char enableRoute = 0;
	while (!enableRoute) {
		if (added_chkpnt_num+1 >= full_route_num) {
			printf("add check point not found.");
			return -1;
		}
		route = &routeArray[added_chkpnt_num];
		if (route->skip == 0) {
			enableRoute = 1;
		} else {
			added_chkpnt_num++;
		}
	}
	for (i=0; i<4; i++) {
		route_t *route = &routeArray[added_chkpnt_num];
		char bef_dir = route->move_dir;
		char check_x = route->blank_x;
		char check_y = route->blank_y;

		d = dirArray[i];
		if (d == 'U' && bef_dir == 'D') {
			continue;
		} else if (d == 'D' && bef_dir == 'U') {
			continue;
		} else if (d == 'L' && bef_dir == 'R') {
			continue;
		} else if (d == 'R' && bef_dir == 'L') {
			continue;
		}
		
		mx = my = 0;
		if (d == 'U') {
			my = -1;
		} else if (d == 'D') {
			my = 1;
		} else if (d == 'L') {
			mx = -1;
		} else if (d == 'R') {
			mx = 1;
		}
		char new_check_x = check_x+mx;
		char new_check_y = check_y+my;
		if (new_check_x < 0 || new_check_x >= board_w) {
			continue;
		}
		if (new_check_y < 0 || new_check_y >= board_h) {
			continue;
		}
		if (route->board[new_check_y*board_w+new_check_x] == '=') {
			continue;
		}
//		printf("added_chkpnt_num:%d %p dir:%c\n", added_chkpnt_num-1, route, d);
		addRoute(d);
	}
	added_chkpnt_num++;

	return 0;
}

int checkCheckPoint() {
	int i;
	int max;
	char mx = 0;
	char my = 0;
	while (enable_route_num <= checked_route_num) {
#ifdef DEBUG_
		printf("**add check point\n");
#endif
		if (addCheckPoint() != 0) {
			return -1;
		}
	}
	route_t* route = &routeArray[checked_route_num];
#ifdef DEBUG2_
	printf("**check %d\n", checked_route_num);
#endif
#ifdef DEBUG_
	if (route->board[0] == 0) {
		printf("err");
	}
	showBoard(route->board);
#endif
	if (route->move_dir == 'U') {
		my = -1;
	} else if (route->move_dir == 'D') {
		my = 1;
	} else if (route->move_dir == 'L') {
		mx = -1;
	} else if (route->move_dir == 'R') {
		mx = 1;
	}
	changeBlank(mx, my, route);
	if (history_full) {
		max = HISTORY_BOARD_SIZE;
	} else {
		max = ins_history_idx;
	}
#ifdef DEBUG3_
	printf("history %d\n", ins_history_idx);
#endif
	for (i=0; i<max; i++) {
		if (memcmp(route->board, &history_borad[i], board_w*board_h) == 0) {
#ifdef DEBUG3_
			printf("****dup\n");
			showBoard(route->board);
			showBoard(history_borad[i]);
			fflush(stdin);
#endif
			route->skip = 1;
			break;
		}
	}
	if (route->skip == 0) {
		copyBoardData(history_borad[ins_history_idx], route->board);
		ins_history_idx++;
		if (ins_history_idx >= HISTORY_BOARD_SIZE) {
			history_full = 1;
			ins_history_idx = 0;
		}
#ifdef DEBUG_
		printf("-full route ");
		route_t* r = route;
		while (r != routeArray) {
			//		printf("[%d]", r->node_num);
			printf("%c", r->move_dir);
			r = &routeArray[r->bef_node_num];
		}
		printf("\n");
		printf("-changed %c\n", route->move_dir);
		showBoard(route->board);
#endif
		if (isGameClear(route->board) == 0) {
			return 1;
		}
	}
	checked_route_num++;
	return 0;
}

int main (int argc, const char * argv[]) {
	int i;
	char borad[BOARD_DATA_SIZE];
	int w, h;
	
	if (argc <= 1) {
		printf("no data.");
		return 0;
	}
	
	sscanf(argv[1], "%d,%d,%s", &w, &h, borad);
	board_w = w;
	board_h = h;
#ifdef DEBUG_
	printf("input data: %d %d %s\n", board_w, board_h, borad);
#endif
	addRoute(' ');
	copyBoardData(routeArray[0].board, borad);

	showBoard(borad);
	getBlankPos(&routeArray[0]);
	routeArray[0].bef_node_num = -1;
	getGameClearBoardData(borad);
	enable_route_num = 1;
	checked_route_num = 1;
	routeArray[0].move_dir = ' ';
	addCheckPoint();
	/*
#ifdef DEBUG_
	for (int i=0; i<full_route_num; i++) {
		printf("---\n");
		printf("node num: %d", routeArray[i].node_num);
		printf(" dir: %c", routeArray[i].move_dir);
		printf("\n");
		showBoard(routeArray[i].board);
	}
#endif
	 */
	/*
	for (int i=0; i<1000; i++) {
		if (checkCheckPoint() != 0) break;
	}
	 */
	while (1) {
		if (checkCheckPoint() != 0) break;
	}
	int game_clear_node_num = 0;
	route_t* bef_node_ = &routeArray[routeArray[checked_route_num].node_num];
	while (bef_node_ != routeArray) {
		bef_node_ = &routeArray[bef_node_->bef_node_num];
		game_clear_node_num++;
	}
	char* res_route = (char*)malloc((game_clear_node_num+1)*sizeof(char));
	bef_node_ = &routeArray[routeArray[checked_route_num].node_num];
	for (int i=game_clear_node_num-1; i>=0; i--) {
		if (!bef_node_) {
			res_route[0] = 0;
			break;
		}
		res_route[i] = bef_node_->move_dir;
		bef_node_ = &routeArray[bef_node_->bef_node_num];
	}
	showBoard(routeArray[checked_route_num].board);
	if (res_route[0] != 0) {
		res_route[game_clear_node_num] = 0;
		for (i=0; i<board_w*board_h; i++) {
			printf("%c", borad[i]);
		}
		printf(",%s\n", res_route);
	}
	free(res_route);
	if (routeArray) free(routeArray);
    return 0;
}

プログラムの解説

総当り。 0 の位置から上下左右で移動出来るところ全てを移動させて最終的なゲームクリアの盤面になっているかをチェック
完全に幅優先で作成

途中、「あれっ？どっかでメモリ破壊やらかした？」という場面が有りました。バグ調査した所、原因は「reallocから返されるアドレスは以前のアドレスから変更される事が有る事を考慮してない」というものでした。C言語のプログラムは大変です(^_^;)

上記のプログラムの1つ前バージョンのプログラムだと解けるのは3x4くらいまででした。それより大きなボード(盤面)の場合はメモリを2G以上消費し、メモリ不足でOSがハングする危機に…

残り時間は少ないし、根本的なアルゴリズムの変更などはデバッグの面からも選択したくない。少々考えた後、ある程度過去のボードの状態を保存しておいてそれと同じ盤面が発生していた時はその手順には無駄が有ると判断し、以降のそのルートの解析を中断するという処理を入れました。

最初は保存する盤面の履歴は100パターン、256パターン位と試してみたところ増加の速度はゆっくりとはなりましたがまだまだ現実的なメモリ使用量に収まってはいませんでした。

100*1024位で現実的な消費量になりましたが並列で実行させる事を考慮し、1024*1024パターンまで履歴を保存する設定にしました。ちなみにそれ以上のパターンが発生した場合は古いものから上書きする作りにしました。

このプログラムはコマンドラインから問題を引数として渡すプログラムと成っています。以下の様なシェルスクリプトを実行して平行に実行させました。

#!/bin/sh

while read LINE; do
  `./Quiz2/build/Debug/Quiz2 ${LINE} >> res.txt &`
done < devquiz2.txt

devquiz2.txt には問題を以下の様に格納しています。ここでは 3,4 のボードの問題に成っていますが実際にはボードサイズが小さいものから順番になるようにソート後、ボードサイズの小さいものから順番に並列で実行させて解析しました。

3,4,021369B475A8
3,4,0392=B8A6147
3,4,082A=3416B79
3,4,09B38267A154
3,4,1264=B9370A8
3,4,16=2457A908B
3,4,16=478B29=05
3,4,175463A209B8

途中まではこの方法で順調だったのですが 3,5 位のボードサイズになってからは全然解析が終了するものが現れなくなりました。

以下の様な5分間解析を実行し、それで解析出来なかったらその問題を諦めて次の問題を解析する様に変更しました。

#!/bin/sh

while read LINE; do
  chk=`ps -ef | grep "./Quiz" | grep -v grep | wc -l`
  if [ $chk -ge 5 ]; then
    sleep 300
    killall Quiz2
  else
    ./Quiz2/build/Debug/Quiz2 ${LINE} >> res.txt &
  fi
done < devquiz2.txt

これはWebGameは途中にカード数が少ない問題も有ったのでスライドパズルにもボードサイズは大きいけど手数は少ない問題があるんじゃないかという期待を込めての作成です。

結果は惨敗、世の中そんなに甘く無いです。そんな美味しい問題は有りませんでしたorz

うーん、次回までに探索アルゴリズムを幾つか頭に入れとかないと次回くらいにはまったく歯が立たないとかなりかねないなぁ。という感想で2011年のDevQuizは終了しました。アルゴリズムの知識重要!!