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

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

JavaScriptで文字数を削減する11のポイント

じつは今回のコードゴルフ問題、ただ文字数を削るだけでは駄目で、上位に食い込むには自分でアルゴリズムを工夫しないといけないように設計されていました。

それはどこでしょうか?

その答えはメインディッシュとして後に置いておき、まずは前菜として、JavaScriptの文字数を削る手法をいくつか紹介します。今回順位が振るわなかった方々の多くが、JavaScriptの仕様レベルで文字数を削減できる部分を取りこぼしていたためです。

文字数を削減すると、難読化を招き、可読性が低下し、仕事においてはデメリットにしかなりません。しかし、コードゴルフではこれらの手法は有効です。パズルを解くためのツールのようなものです。

ポイントは以下の11個です。

その1 動作に影響しない文字を削る

具体的には以下がポイントです。

  • 変数宣言のvarを削る(ただし、再帰関数内の変数は変数宣言が必要なので注意)
  • 無駄なスペースやタブ文字、改行や末尾のセミコロンは削除する
  • 変数名は1文字にする
var res = "";

 ↓

r=""

その2 配列は[]で初期化し、要素数は指定しない

JavaScriptは、配列を[]で初期化できます。また、配列の要素数を指定しなくても自動でサイズを拡張してくれるので、初期化する時の要素数の指定は省略できます。

maze = new Array(w * h);

 ↓

m=[]

その3 for文の棘括弧({})を削り、処理はカンマで連結する

for (~) {
        処理1
        処理2
}

      ↓

for(~)処理1,処理2

その4 if文を条件演算子にする

if (maze[x + w * y] == 1) {
        res += "■";
} else {
        res += " ";
}

   ↓

res+=maze[x+w*y]==1?"■":" "

その5 文字列内の特定の1文字は添え字で取得する

res+=maze[x+w*y]==1?"■":" "

  ↓

res+=" ■"[maze[x+w*y]]

その6 booleanは数値演算する(0,1になる)

console.log(0+true)     // 1と出力

その7 |0で整数を表現する

console.log(2.345|0)    // 2と出力

その8 0をfalseの代わりに、0以外をtrueの代わりに使う

for(i=10;i--;)console.log(i);   // 9~0が出力

その9 空文字を数値演算で0にする

i="";console.log(++i);          // 1と出力
i="";console.log(i++);          // 0と出力
i="";console.log(i);            // 空文字が出力

その10 要素数1の配列は中身をそのまま使う

i=[100];console.log(++i);       // 101と出力
i=[100];console.log(i++);       // 100と出力
i=[100];console.log(i);         // [100]が出力
i=[];console.log(++i);          // 1と出力
i=[];console.log(i++);          // 0と出力
i=[];console.log(i);            // []が出力

その11 変数を初期化する場所を変える

// 初期化
i=[j=9,k=l=((m=8)/2)]

// 出力
console.log("i=" + i);  // i=9,4と出力
console.log("j=" + j);  // j=9と出力
console.log("k=" + k);  // k=4と出力
console.log("l=" + l);  // l=4と出力
console.log("m=" + m);  // m=8と出力

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

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

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

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

プログラムを見た瞬間に、あきらかに冗長な部分があります。⁠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があったからこそ、こういった絡め手を思いついたのでしょう。ただ、そういった部分を除いても、非常に切り詰められたコードです。胃が痛くなるような密度になっています。


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

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

おすすめ記事

記事・ニュース一覧