Googleの入社問題（数字当てクイズ）

昨日、会社のリスクマネジメント研修とやらを受けさせられたのだが
その中で講師の人が講義の時間の間を埋めるのに以下の問題をGoogleの入社試験だと出題したのだった。

1
11
21
1211
111221
?
【?に入る数字をこたえよ】

自分は結局答えが分からなかったのだけど。
回答が分かれば、コードで出力する問題としては暇つぶしに手頃なサイズだったので以下のアプリで書いてみた。

Javascript-1

以下、ねたばれ注意



HTMLの中に埋め込む形式で書いたのだけど、HTMLの部分は本質ではないので省いている。
HTML付きでブラウザで表示するだけで回答が見れるコードは以下。

https://gist.github.com/1828081

iPhoneのソフトウェアキーボードでコード打ち込みながらdocument.write()するデバッグは辛かった・・・。
最初、自分でnumber型をresにpushしていながら
6行目で癖で===で比較していたため値は一致しても型不一致で期待通りに動いていなかったという＼(^o^)／

以下、回答。一応、文字を白にしとくんで、見たい人は文字選択してください。

1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
1 1 1 3 2 1 3 2 1 1
3 1 1 3 1 2 1 1 1 3 1 2 2 1
1 3 2 1 1 3 1 1 1 2 3 1 1 3 1 1 2 2 1 1

以下が回答を紹介しているページ。

http://ntakei.cocolog-nifty.com/pam/2006/04/post_231f.html

一言で言うと、文字と文字数を並べていくだけなんだけど、これってどこかで見たことある・・・と思って検索したら、正体は「ランレングス圧縮」だったのであった。
# 大学の情報理論の授業で習ったはず
# 久しぶりにハフマン符号化とか調べてしまった

連長圧縮（ランレングス圧縮、RLE：Run Length Encoding）

連長圧縮では、ある連続したデータを、そのデータ一つ分と連続した長さで表現することで圧縮している。
例えば、「A A A A A B B B B B B B B B A A A」は「A 5 B 9 A 3」と表せる。これは、Aが5回続き、そのあとにBが9回、そしてAが3回続いていることを表している（連続回数を、元のデータを表す符号の前に記録することもある。その場合、符号化した後は「5 A 9 B 3 A」と表される）。

講師の人は、Googleはこういう柔軟な発想が出来る人がごろごろいるのでしょうかねーと言っていた。
そういう発想の柔軟さもそうなのかもしれないけれど裏に隠れているコンピュータサイエンスの基礎理論を見抜いて解ける人もまたターゲットにしているのかも。

まあ、最近のシリコンバレーのジョブインタビューは（一時期流行った）こういうクイズめいた問題は実際の業務では役に立たん！とあまり出題されないらしいけど。

# 2012/2/19 Array.join()を使用するよう変更