エンジニアのスキルを試すコードパズル ─この問題,あなたは解けますか?

第3回 迷路でコードゴルフ~同じ処理を最短コードで書くには─柳井政和からの問題

この記事を読むのに必要な時間:およそ 2 分

問題

コードゴルフ:迷路

「コードゴルフ」は,ゴルフがカップインまでの打数を競うように,プログラムのソースコードの文字数を削って,なるべく短くプログラムを書く遊びです。

たとえば以下は,1から100の整数を全て足すプログラムです。上のコードは77文字ですが,同じ動作を下のように38文字で書くこともできます。

// 1から100の整数を全て足す(77文字)⁠

var res = 0;
for (var i = 1; i <= 100; i ++) {
	res += i;
}
console.log(res);

// 1から100の整数を全て足す(38文字)⁠

for(r=i=0;i<=99;r+=++i);console.log(r)

// 出力
5050

JavaScriptを使って,このコードゴルフにチャレンジしてください。

以下の関数yourCode()は「穴掘り法」という手法を使い,迷路を自動で生成しています。

yourCode()

function yourCode() {
    var res = "";
    
    // 迷路の初期化
    var w = 55;
    var h = 35;
    var maze = new Array(w * h);
    for (var y = 1; y < h - 1; y ++) {
        for (var x = 1; x < w - 1; x ++) {
            maze[x + w * y] = 1;
        }
    }
    
    // 開始位置と方向とパターン
    var startX = w - 5;        // コードゴルフ用:固定位置
    var startY = 4;            // コードゴルフ用:固定位置
    var dir = [[-1, 0], [0, -1], [1, 0], [0, 1]];
    var pattern = 
        [[0, 1, 2, 3]
        ,[0, 1, 3, 2]
        ,[0, 2, 1, 3]
        ,[0, 2, 3, 1]
        ,[0, 3, 1, 2]
        ,[0, 3, 2, 1]
        ,[1, 0, 2, 3]
        ,[1, 0, 3, 2]
        ,[1, 2, 0, 3]
        ,[1, 2, 3, 0]
        ,[1, 3, 0, 2]
        ,[1, 3, 2, 0]
        ,[2, 0, 1, 3]
        ,[2, 0, 3, 1]
        ,[2, 1, 0, 3]
        ,[2, 1, 3, 0]
        ,[2, 3, 0, 1]
        ,[2, 3, 1, 0]
        ,[3, 0, 1, 2]
        ,[3, 0, 2, 1]
        ,[3, 1, 0, 2]
        ,[3, 1, 2, 0]
        ,[3, 2, 0, 1]
        ,[3, 2, 1, 0]];
    
    // 穴掘り法
    function dig(x, y) {
        // コードゴルフ用:ランダムを使わずに生成
        var type = (x + 3) * (y + 5) * 7 % pattern.length;
        for (var i = 0; i < dir.length; i++) {
            var next = dir[pattern[type][i]];
            if (maze[(x + next[0] * 2) + w * (y + next[1] * 2)] == 1) {
                maze[(x + next[0] * 2) + w * (y + next[1] * 2)] = 0;
                maze[(x + next[0]    ) + w * (y + next[1]    )] = 0;
                dig(x + next[0] * 2, y + next[1] * 2);
            }
        }
    }
    dig(startX, startY);
    
    // 出力結果生成
    for (var y = 0; y < h; y ++) {
        for (var x = 0; x < w; x ++) {
            if (maze[x + w * y] == 1) {
                res += "■";
            } else {
                res += " ";
            }
        }
        res += "\n";
    }
    
    return res;
        
}

yourCode()の実行結果は以下になります。

画像

関数yourCode()の中のコードは1440バイトですが,これと同じ文字列を返す処理をなるべく少ないバイト数で書いてください。バイト数が短いほど,評価が高くなります。

まずは約半分の700バイト以下になるように,がんばってください。どこまで短くできるか,頭を柔らかくして考えてください。

迷路を作るのは楽しく,私も過去に全自動迷路というものを作り,画像の形に合わせた迷路を自動で生成するプログラムを開発しています。


難易度
★☆☆☆(当該領域で,基礎的なことができれば解けると思われるレベル)
言語/領域(Perl,Pythonなど)
JavaScript
解答形式
ファイルアップロード形式
解答評価のポイント
可能な限り短い文字数で,同じ処理結果を出力できることです。まずは700バイト以下になるように,がんばってください。
挑戦を開始する前にご準備いただきたいもの

解答は,テキストファイルを解答画面からアップロードしていただきます。作成したJavaScriptのコードをテキストファイルに貼り付けて提出してください。あらかじめ「設問1.txt」とテキストファイルを作成しておくと,スムーズです。事前にご準備ください。

なお,CodeIQの受付ページにて,コードの文字数確認と,実行結果と合っているかどうかを確認できるフォームを用意していますので,ぜひご利用ください。

その他注意事項
  • 一度挑戦を開始すると,解答を送信しなかった場合でも,1回目のチャレンジは終了となります。
  • 何度でも挑戦できます。
  • 白紙に近いなど,採点不能なものは,フィードバックいたしかねます。
  • この問題の正解及びコードレビューは,技術評論社のサイトこの連載上にて行います。
  • 優秀な解答をした人や面白解答した人はニックネーム,解答内容,解答フィードバック内容を公開させて頂く可能性があります。ご了承ください。
  • コードゴルフの暫定順位は,CodeIQ公式ブログにて公開していく予定です。
    URL:http://codeiq.hatenablog.com/
解答受付先
https://codeiq.jp/ace/yanai_masakazu/q154
掲載期間(開始~終了)
12月27日(木)~1月24日(木)
採点可能人数
200人
想定時間(分)
10分~
制限時間
なし

著者プロフィール

柳井政和(やないまさかず)

横浜で物を作る会社『クロノス・クラウン合同会社』代表社員。2002年に起業して,オンラインソフト,携帯ゲーム,Webアプリの開発,IT情報の記事,マンガの執筆,書籍の作成などを中心に活動しています。いろいろなものを企画して作るのがお仕事です。著書に『マンガでわかるJavaScript』(2010年10月,秀和システム)他。

Webサイトは『クロノス・クラウン』
URL:http://crocro.com/

コメント

コメントの記入