DevQuiz最後の難関となったスライドパズルです。
最終的にはスライドパズルの点数(0点～50点)がGoogle Developer Dayへの参加権のボーダーとなりました。(公表されているボーダーラインは101点なので、スライドパズル以外ではほぼ100点が取れていると思いますので、スライドパズルで少なくとも1点を取る必要があったと言えます。)
出題されるパズルの数は5000問、1問あたりの点数が0.01点。(最大で50点満点)
スライドパズルの盤面は縦横3～6の組み合わせで構成されており、特殊ルールとして「壁」と呼ばれる動かせないピースが存在します。また、ピースを移動する手数が制限されています。
問題文はテキストファイルで与えられ、結果は空ピースを動かした方向の上下左右をUDRLの文字に当てはめて問題番号と同じ行数のテキストファイルに出力して提出します。
私の結果は4126/5000問の回答で、回答できた部分については間違いは無しでした。(回答した行数と得点が一致していました。)
手数制限にはまだまだ余裕がありましたが、ロジックが悪かった為、6×6の盤面では回答を得るのに1日も掛かってしまうことがありました。
よって、この得点は単純にタイムオーバーとなってしまった時点での得点となります。
使用したマシンはCore i3 2100のPCで、C++で作ったEXEファイルを実行したところ2コア2スレッドの1プロセス分しか使ってくれず、CPU使用率は25%で張り付いたままでした。
(EXEファイルを全てのパワーを使い切って実行する方法があったら教えてください・・・)
既に満点を取られた方が回答PGを公開していますので、私のPGは参考になりませんが、ここで恥をさらしておけば次回のやる気に繋がるということで公開したいと思います。
//————————————————————–
// puzzule(スライドパズルの最短解を求める/本当のスペルはpuzzle)
//————————————————————–
// GDD/DevQuizのスライドパズル回答PG
//
// [UPDATE]:テキストファイルで与えられた問題を解析し盤配列に設定
// [UPDATE]:盤の大きさに連動した処理の変更
// [UPDATE]:壁判定の追加
// [UPDATE]:タイムアウトの追加
//————————————————————–
#include
#include
#include
using namespace std;
#define LIMIT 65 // 1問題あたりの最大手数の設定
// パズル構造体の定義
struct Puzzle{ char cont[36]; int space; };
// グローバルエリア定義
Puzzle puzzle;
int limit, path[LIMIT], MD[36][36];
// 壁情報の格納
// 盤の壁位置に0x40(@)が格納される。それ以外は0x00(null)が格納される
char kabe[36];
// 上下左右の移動定義
static const int dx[4] = {-1, 0, 1, 0};
static const int dy[4] = {0, -1, 0, 1};
static const char direction[4] = {‘U’, ‘L’, ‘D’, ‘R’};
// 現在回答中の盤の大きさ
int width = 0;
int height = 0;
// 残り手数格納
int CONTROL[4];
// タイムアウト設定
#define TIMEOUT 600 // 10分でタイムアウト設定
time_t start_time; // 問題処理開始時間
time_t now_time; // 現在の時間
//————————————————————–
// getHeuristic
//————————————————————–
// 現在位置からの総手数を算出
//
// 引数:Nothing
// 戻値:現在位置から回答までの最短総手数
//————————————————————–
int getHeuristic()
{
int sum = 0;
for ( int i = 0; i < (width * height); i++ )
{
if ( puzzle.cont[i] == 'z' )
{
continue;
}
sum += MD[i][puzzle.cont[i]-'A'];
}
return sum;
}
//--------------------------------------------------------------
// isTarget
//--------------------------------------------------------------
// 完了チェック
//
// 引数:Nothing
// 戻値:盤が完成したか否かのチェックを行う
//--------------------------------------------------------------
bool isTarget()
{
// 盤を先頭からチェックし連続した文字コードで並んでいることをチェックする
for ( int i = 0; i < ((width * height) - 1); i++ )
{
// 文字コードが連続していなければ盤は完成していないと判断
if ( puzzle.cont[i] != 'A' + i )
{
return false;
}
}
// ループが最後まで回れば盤が完成していると判断
return true;
}
//--------------------------------------------------------------
// dfs
//--------------------------------------------------------------
// 評価関数
//
// 引数:深度,直前の手
// 戻値:上下左右へ動ける可能性のある位置へピースを移動させる
//--------------------------------------------------------------
bool dfs(int depth, int prev)
{
// 盤完成チェック
if ( isTarget() )
{
return true;
}
// タイムアウトチェック
time(&now_time);
if ((start_time + TIMEOUT) < now_time){ return false;}
// 最大手数チェック
if ( depth + getHeuristic() > limit )
{
return false;
}
// ピースの移動
int px, py, tx, ty;
Puzzle tmp;
// 動かせるピースの現在位置の取得
px = puzzle.space / width;
py = puzzle.space % width;
// 上・左・下・右への移動(それぞれがrの0・1・2・3と合致する)
for ( int r = 0; r < 4; r++ )
{
// 移動
tx = px + dx[r];
ty = py + dy[r];
// 直前の手を比較
if ( max(prev, r)-min(prev, r) == 2 )
{
continue;
}
// 枠外に出る場合は動かさない
if ( tx < 0 || ty < 0 || tx >= height || ty >= width )
{
continue;
}
// 壁判断
if (kabe[tx*width+ty] == 0x40)
{
continue;
}
tmp = puzzle;
// ピースの移動
puzzle.cont[px*width+py] = puzzle.cont[tx*width+ty];
puzzle.cont[tx*width+ty] = ‘z’;
puzzle.space = tx*width+ty;
// 評価関数呼び出し
if ( dfs( depth+1, r ) )
{
path[depth] = r;
return true;
}
puzzle = tmp;
}
return false;
}
//————————————————————–
// solve
//————————————————————–
// 回答算出処理
//
// 引数:Nothing
// 戻値:Nothing
//————————————————————–
void solve()
{
// 最大手数までのチェック処理を行う
for ( limit = getHeuristic(); limit <= LIMIT; limit += 2 ){
if ( dfs(0, -100) )
{
for ( int i = 0; i < limit; i++ ) cout << direction[path[i]];
cout << endl;
return;
}
}
// 結果が求められなかった場合は空行を表示する
cout << "" << endl;
}
//--------------------------------------------------------------
// main
//--------------------------------------------------------------
// エントリーポイント
//
// 引数:Nothing
// 戻値:Nothing
//--------------------------------------------------------------
void main(void)
{
// 結果ファイルの書き出し
// リダイレクト出力で対応するためコメント化
/*
FILE *answers_fp;
if ((answers_fp = fopen("./answers.txt", "w")) == NULL)
{
return;
}
*/
// 問題ファイルの読み込み変数の定義
FILE *prolems_fp;
char problem[256];
// 盤サイズ格納領域([0]に横幅/[1]にカンマ/[2]に縦幅が格納される)
char problem_size[4];
// 問題ファイルの読み込み
if ((prolems_fp = fopen("./problems.txt", "r")) == NULL)
{
// 読み込み失敗時は終了
return;
}
// 問題を１行ずつ読み込み開始
int problem_cnt = 0;
while (fgets(problem, 256, prolems_fp) != NULL)
{
// 問題読込数インクリメント
problem_cnt++;
int control_cnt = 0;
// 最初の2行(総手数・問題数)の取得処理
switch(problem_cnt)
{
case 1: // 総手数
// スペース区切りの数字を取得する
char temp_cnt[10];
char temp_temp[2];
memset(temp_cnt, 0x00 ,sizeof(temp_cnt));
// 空白区切りの総手数の取得
for (unsigned int cnt = 0 ; cnt < strlen(problem) ; cnt++ )
{
if (problem[cnt] == ' ')
{
control_cnt++;
CONTROL[control_cnt - 1] = atoi(temp_cnt);
memset(temp_cnt, 0x00 ,sizeof(temp_cnt));
continue;
}
temp_temp[0] = problem[cnt];
temp_temp[1] = 0x00;
strcat(temp_cnt, temp_temp);
}
CONTROL[3] = atoi(temp_cnt);
// 取得した総手数の表示(リダイレクトでの出力を行う為コメントアウト)
// printf("残手数 左:%d 右:%d 上:%d 下:%d\n", CONTROL[0], CONTROL[1], CONTROL[2], CONTROL[3]);
continue;
case 2: // 問題数
// なにもしない(現状は問題文のある限り読み込んで回答を出力している為/必要であればこの回数分だけループする処理に変更する必要あり)
continue;
}
// 先頭3文字から問題サイズの取得
for (int cnt = 0 ; cnt < 3 ; cnt++)
{
problem_size[cnt] = problem[cnt];
}
problem_size[3] = 0x00;
width = problem_size[0] - '0';
height = problem_size[2] - '0';
// 壁情報の取得
memset(kabe ,0x00 , sizeof(kabe));
// ボードに数値を格納していく
memset(puzzle.cont, 0x00 ,sizeof(puzzle.cont));
for (int cnt = 4 ; problem[cnt] != 0x00 ; cnt++)
{
char num = 0;
// 問題の数値・英字情報を計算しやすいように文字コードに置き換える
// (とりあえず小文字のzまでの大きさの盤に対応させる)
if (problem[cnt] == '0'){ num = 'z'; puzzle.space = cnt - 4;} // 空白ピース
if (problem[cnt] == '1'){ num = 'A'; } // 1ピース
if (problem[cnt] == '2'){ num = 'B'; } // 2ピース
if (problem[cnt] == '3'){ num = 'C'; } // 3ピース
if (problem[cnt] == '4'){ num = 'D'; } // 4ピース
if (problem[cnt] == '5'){ num = 'E'; } // 5ピース
if (problem[cnt] == '6'){ num = 'F'; } // 6ピース
if (problem[cnt] == '7'){ num = 'G'; } // 7ピース
if (problem[cnt] == '8'){ num = 'H'; } // 8ピース
if (problem[cnt] == '9'){ num = 'I'; } // 9ピース
if (problem[cnt] == 'A'){ num = 'J'; } // Aピース
if (problem[cnt] == 'B'){ num = 'K'; } // Bピース
if (problem[cnt] == 'C'){ num = 'L'; } // Cピース
if (problem[cnt] == 'D'){ num = 'M'; } // Dピース
if (problem[cnt] == 'E'){ num = 'N'; } // Eピース
if (problem[cnt] == 'F'){ num = 'O'; } // Fピース
if (problem[cnt] == 'G'){ num = 'P'; } // Gピース
if (problem[cnt] == 'H'){ num = 'Q'; } // Hピース
if (problem[cnt] == 'I'){ num = 'R'; } // Iピース
if (problem[cnt] == 'J'){ num = 'S'; } // Jピース
if (problem[cnt] == 'K'){ num = 'T'; } // Kピース
if (problem[cnt] == 'L'){ num = 'U'; } // Lピース
if (problem[cnt] == 'M'){ num = 'V'; } // Mピース
if (problem[cnt] == 'N'){ num = 'W'; } // Nピース
if (problem[cnt] == 'O'){ num = 'X'; } // Oピース
if (problem[cnt] == 'P'){ num = 'Y'; } // Pピース
if (problem[cnt] == 'Q'){ num = 'Z'; } // Qピース
if (problem[cnt] == 'R'){ num = 0x5b; } // Rピース
if (problem[cnt] == 'S'){ num = 0x5c; } // Sピース
if (problem[cnt] == 'T'){ num = 0x5d; } // Tピース
if (problem[cnt] == 'U'){ num = 0x5e; } // Uピース
if (problem[cnt] == 'V'){ num = 0x5f; } // Vピース
if (problem[cnt] == 'W'){ num = 0x60; } // Wピース
if (problem[cnt] == 'X'){ num = 'a'; } // Xピース
if (problem[cnt] == 'Y'){ num = 'b'; } // Yピース
if (problem[cnt] == 'Z'){ num = 'c'; } // Zピース
// 壁判定
if (problem[cnt] == '=')
{
// 壁の位置に本来設置されるべき文字コードを設定
num = 'A' + cnt - 4;
// 壁判定に壁情報の格納
kabe[cnt - 4] = 0x40;
}
// 値の代入
puzzle.cont[cnt - 4] = num;
}
// テーブルサイズから移動ピースからの移動距離一覧を算出する
for ( int i = 0; i < (width * height); i++ ){
for ( int j = 0; j < (width * height); j++ ){
// 正方形テーブルの手数一覧
MD[i][j] = abs(i/width-j/width) + abs(i%width-j%width);
}
}
// 盤番号の表示(リダイレクト表示に邪魔な為コメントアウト)
// printf("%d問目\n",(problem_cnt - 2));
// 問題開始時間の取得
time(&start_time);
// 解を求める
solve();
// 回答出力(リダイレクトでの出力を行う為コメントアウト)
//printf("%s\n", ANSWER);
//printf("残手数 左:%d 右:%d 上:%d 下:%d\n", CONTROL[0], CONTROL[1], CONTROL[2], CONTROL[3]);
//fprintf(answers_fp, "%s\n", ANSWER);
}
fclose(prolems_fp);
// fclose(answers_fp); // リダイレクトでの出力を行う為コメントアウト
}
[/cpp]
結果ファイルの書き出し処理が面倒だった為、リダイレクトで結果を吐き出すという手段にでました。
なぜか文字コードで盤面の正解を導いていますが、数値を入れた方が良かったなぁ・・という感じです。
なお、正解確認用にPHPで確認PGも製作しました。
[php]
puzzle
[/php]
twitterで見かけたコメントに「日本の電力消費量を押し上げたDevQuizのスライドパズル」というものがありましたが、まさにうちの電力消費量も上がった事でしょう。。。
でも、私の場合はロジックが悪い＝処理が遅い＝電力消費が高い・・・という原因なので、節電の為にはロジックを良くするという手段もあるんだなぁ・・・と思ったり思わなかったり。
ということで、今回でDevQuizのソースコード晒しは終了です。
DevQuizに参加された皆様、本当にお疲れ様でした。
