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

第10回 柳井政和からの問題(第3回)解説編

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

肝は「規則正しいデータを,プログラムで再現するコードを書けるかどうか」

それではいよいよ,今回の問題のメインディッシュです。

この問題には,バイト数のボトルネックになる場所が用意されています。その場所に気づいて問題解決を行えば,コード量を激減できるようになっています。この「ボトルネックに気づいたかどうか⁠⁠,そして「どのよう問題解決したか」が,この問題の採点の注目ポイントでした。

それでは,問題のコードを確認してください。

プログラムを見た瞬間に,あきらかに冗長な部分があります。⁠pattern」という変数の二次元配列です。ここを削れるかどうかで,解答者のバイト数に大きな開きがありました。

以下,文字数が多かった順に,どういった手法で解答者の方々がボトルネック部分を減らしていたのかを示します。

その1 スペース,タブ文字,改行を削る

p=[[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]];

実は,これではあまり文字数は減っていません。それ以前に,問題の趣旨に気づいていません。文字数を削減する重要なポイントを見逃しています。

その2 1次元配列化する

p=[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];

配列が文字数を削減すべきポイントだと気づいています。しかし,問題の本当の趣旨には気づいていません。

その3 文字列化する

p="012301320213023103120321102310321203123013021320201320312103213023012310301230213102312032013210";

これで文字数が一気に半減しました。文字列の添え字で特定の文字列を取得すれば,配列と同じ手間で値を取得できます。しかし,バイト数はだいぶ減少しましたが,値をそのまま取得しているのは同じです。

文字列化については,さまざま手法が見られました。

まず,上記の数字を文字コードに埋め込み,⁠charCodeAtとビット演算とシフト演算を駆使して数値を取得する」という手法が見られました。

似た手法として,出力結果をすべて文字列に埋め込んで,charCodeAtを利用して取り出している方も少なからずいました。

しかし,そういった手法を駆使しなくても,真っ当に問題に取り組めば,きちんと文字数が削れるように,問題は設計されています。

その4 計算で取得する

これが本命です。

patternの値は,よく見ると規則正しく数値が並んでいます。それもそのはず,この値は,そもそも私がプログラムを書いて出力した数値の組み合わせです。ならば当然,プログラムで生成できるはずです。ここに思い至り,実際にその処理をコードにした方々が上位に入っていました。

規則正しいデータを,プログラムで再現するコードを書けるかどうか

それが,今回のコードゴルフ問題の肝でした。単に文字数を削るだけではすぐに限界が来ます。その壁を突破するには,パターン生成のプログラムを書かないといけなかったのです。

以下,計算でパターンを求める一例です。

特定のマスでのパターン

dir = [[-1, 0], [0, -1], [1, 0], [0, 1]]
x = 50;
y = 4;

d = dir.concat();
for (var i = 0, o=24; i < 4; i ++) {
        v = d.splice((x+3)*(y+5)*7%o/(o=o+3>>2), 1)[0];
        console.log(v)
}

出力結果

[-1, 0]
[1, 0]
[0, 1]
[0, -1]

うまく書けば,40~50バイトぐらいで収まるわけです。最初に無駄な文字を削った時点では240バイト近くあったので,200バイトが一気に減ります。

また,方向のパターンである

[[-1, 0], [0, -1], [1, 0], [0, 1]]

も,以下のように短く書けば,さらにバイト数を削ることができます。

[1,w,-1,-w]

上位者はどのようなコードを書いたか

今回の問題はコードゴルフの問題でもありながら,アルゴリズムを考える問題でもありました。そのため,単純にバイト数を削るスキルだけでは,上位陣に食い込むことはできないようになっていました。

最後に,上位者の方々のコードを掲載して,寸評を加えておきます。

3位(208文字)sapics様のコード

for(var i=w=56,j=24,l=[1,w,-1,-w],q=this.p||(m=[],i*=35,500);i;s=m[i+225]=" ■\n"[i--%w?i%w%54>0&i/w%34>1:2])i<5&&m[p=q-2*l.splice(~q%w*~(q/w)*7%j/(j/=i),1)]<s&&yourCode(m[p]=m[p+q>>1]=s);return m.join("")

計算を簡略化するには,中心点や描画開始点を移動して,座標軸の中心に持ってきたりする手法がよくとられます。sapics様のコードもそういった手法で開始点を移動して,文字数を削っています。

また,出題されたyourCode関数を自身で呼び出して,functionを解答に書かないというアイデアを導入しています。

2位(207文字)hogeover30様のコード

for(x=r="",y=w=56;x<y+w;y<1904?f[++y]=y%w>2:r+=" ■\n"[++x%w?f(276)|f[x+1]:2]);function f(z,o,p){for(p=[1,w,-1,-w],o=24;d=-p.splice(~z%w*~(z/w+4)*7%o/(o=o+3>>2),1);)f[a=z+2*d]&&f(a,f[a]=f[a-d]=0)}return r

「function f」が,for文の実行前に初期化されるために,オブジェクト「f」が存在しているということを利用して,

f[++y]

のように,初期化なしで,関数オブジェクトを配列としても利用しています。最初にこのコードを見た時は,仰け反りました。

1位(206文字)iehn様のコード

for(var z=o,a=1964,d=[1,w=56,-1,-w],i=5;a--;i?b||yourCode(m[o]=m[o+z>>1]=1):d+=" ■\n"[!p+b])o=i?z+d.splice((z%w*7+2)*(0|z/w+9)/(--i>3?6:i-1)%i,1)*2:a,b=(p=o%w)>54|p<2|o>w*34|o<w|m[o];return d}o=1685,m={

「プレイグラウンド上でコードをevalで動かしている」という条件を突いてきたコードです。

まず,⁠}o=1685,m={」で関数をぶった切って,値を初期化しています。そして,yourCodeを再帰的に呼び出しています。問題文にfunctionがあったからこそ,こういった絡め手を思いついたのでしょう。ただ,そういった部分を除いても,非常に切り詰められたコードです。胃が痛くなるような密度になっています。


「コードを削る」ことは,仕事には直結しないスキルです。しかし,⁠パターンを生成するプログラムを作る」ことは,仕事にも役立つスキルです。今回は小さなデータでしたが,実務ではもっと巨大なデータをプログラム的に生成しないといけないこともあるでしょう。

ぜひ,上位者のコードをあらためて自分で読み解いてみてください。いろいろと勉強になる発見がありますよ。

著者プロフィール

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

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

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