Ruby でナゾ解き? 任天堂 Code Puzzle 解説&裏話

書いた人: 任天堂株式会社ネットワーク開発運用部 Code Puzzle 作問担当者

Code Puzzle って?

2013 年 5 月末の RubyKaigi 2013 の会場で、ひっそりと以下のようなフライヤーが配られていました。

CodePuzzle_RubyKaigi2013_flyer.jpg

これを見て、「なんだろう?」と思っていただけたのであれば、あなたは Code Puzzle がターゲットとしているエンジニアです!

今すぐに解いてみたい! という方は http://cp1.nintendo.co.jp/ruby.html へどうぞ。なお、2 問目以降はページの右下にヒントページへのリンクを用意しています。こうしたナゾ解きに慣れていないと、ノーヒントでは何をすればいいのかすらわからないほど難しい問題もあるかもしれません。複数のヒントが上から順に並んでいますので、ご自分のペースで使ってみてください。

さて、Code Puzzle は、簡単に言えば、広義の「パズル」を、プログラムを道具として使って解いていこう、というもの。クリアしても賞品も特典も何もありません。「プログラマによるプログラマのための遊び」として、解くこと自体を純粋に楽しんでいただければと、業務の合間に作問して公開したものでした。

今回、ご縁がありまして、るびまへ記事を書く機会を頂きましたので、Code Puzzle の解説や、ちょっとした裏話などをご紹介できればと考えていますが、その前に、少しだけ背景についてお話ししましょう。

Code Puzzle 実施のわけ

任天堂は京都に本社があり、開発機能の多くも京都に集まっています。そんな中、私の所属する「東京ネットワークシステム開発グループ」が東京にできてから 3 年になります。ネットワークシステムおよびネットワークサービス開発のスペシャリストとして、関東圏のエンジニアを広く集め、東京近辺の IT 関連企業と密に協業することをミッションとしたグループです。

Code Puzzle を企画したきっかけは、キャリア採用で入社した同僚たちが口を揃えていうひと言でした。

「任天堂が社内でこんなに開発しているとは思っていなかった」と。

社内でけっこう開発しています

任天堂はエンタテインメントの会社です。同じ事をやっていては、良い意味での驚きを提供することはできません。つまり、常に新しいことに挑戦し続ける必要があり、それはネットワークサービスでも同じです。

そんな状況だと、仕様書を書いて、それを外部委託し、検収して終わり、といった開発スタイルがなかなか取れません。サービス開発であれば面白くなるまで試行錯誤を繰り返しますし、システム開発であったとしても、いくつもの新しいアイデアの中から一番良いものを探りながら開発していきます。

さらに、現行ハードの「ニンテンドー 3DS」も「Wii U」もネットワーク接続率は高く、ニンテンドーネットワークと呼ばれるネットワークサービスの重要性は増すばかりです。

そのことを伝えたくて

そうなると、必然、社内に多くの優れたエンジニアが必要となるわけですが、そもそも任天堂が社内にエンジニアを抱えていること自体が、 ゲーム業界外のエンジニアの皆さまにあまり知られていないらしい、ということがだんだん分かってきました。

もちろん、普通に広報活動をすればいいわけですが、それではつまらないあまり広く気付いていただけないということで、エンジニアに向けた少し特殊な広報活動として、Code Puzzle が生まれることになりました。

(しかし、途中から、そうした目的そっちのけで、プログラマだけが楽しめる新しいエンタテインメントの提案として、少々作り込みすぎてしまった気もするのですが……)

Ruby 版 Code Puzzle "decode the answer"

Code Puzzle の初回は 2012 年 9 月に Python のカンファレンス PyCon JP に合わせて実施しましたので、今回の Ruby 版は 2 回目となりますが、この順番は時期的な巡り合わせによるものです。社内の開発では、LL 言語や LL ではない言語をひっくるめ、さまざまなプログラミング言語を適材適所で使っています。

Ruby は任天堂にとって重要な言語の一つです。近年、サーバ管理には Ruby は欠かせないものになってきていますし、それだけではなく、ニンテンドーネットワークの一部のサービスも Ruby で書かれています。任天堂は国内での開発の比重が高いため、Ruby の日本語情報が豊富なことも魅力ですね。

特に、今年は Ruby 2.0 が出た記念すべき年。そんな気合いを入れながら、Ruby 版 Code Puzzle を実施することになりました。

Code Puzzle で大事にしているもの

Code Puzzle の制作では、何より、自分がこんなものをやったら楽しいだろうな、と思えるものを作ろうと心がけています。具体的には、以下のようなポイントを大事にしています。

「遊び」としてのプログラミング

皆さんご存じの通り、プログラミングは本来とても楽しいもののはず。しかし、仕事や課題に追われ、義務として PC に向かい続けていると、つい、その楽しさを忘れがちになることもあるのではないでしょうか。

何の義務も無く、ただコーディングを「遊び」としてだけ楽しむ時間を作れたら。それが Code Puzzle の一番の根っこにある想いです。

閃きファースト

また、もう一つ、大事にしていることは、プログラムを人間の思考を拡張する道具として駆使する感覚です。

何をすればいいのかすら明らかではない中、まず自分の頭でやるべき事を考える。すると、「こうすれば解けるかも?」と閃きます。その閃きを確認・実現するために、プログラミングを行い、解答を得る。この過程で、思考をコンピュータで拡張するような感覚を感じられれば、プログラミングの楽しさを再認識するきっかけになるのではないかと考えています。

コードで語る

Code Puzzle では、丁寧に文章で問題を説明するのではなく、コードで問題を語ります。やるべき事は問題中のコードで、制限や仕様はテストコードで。コードさえあれば、我々の間に他に言葉は必要ない。

……と信じて出題していますが、力及ばずコードで語り切れていない部分は、ヒントページという形で補足をしています。ヒントを見るのは恥ではありません。勝手を掴むまでは、ぜひヒントページを自分のペースでご活用ください。

全体を貫くもの

Code Puzzle では複数の問題を出しますが、試験ではないのでただ問題の羅列になったらつまらないなぁ、ということはいつも考えています。せっかく遊んでいただくのですから、全部解いたら、ひと繋がりの体験としてまとまるような構成となるのが理想です。

そのためには、全体を貫く何かのテーマ (ネタ) が必要になるのですが、そのネタ探しでいつもあれこれ悩むことになるのです (もっとも、この時間が一番楽しかったりもします)。

【ネタバレあり】全体設計のはなし

ネタ探し

さて、今回の制作の話に移りましょう。

Ruby 2.0 記念ということで、何かゆかりのものを題材にしたいとは最初から考えていました。2.0 らしい機能は何か。いろいろ検討したものの、1.8 以前のユーザが 2.0 に乗り換える最大の動機は、(1.9 から入っていますが) 新しい RubyVM が安定して動いていることでしょう。

ということで、当初は、最終的に mini RubyVM のようなスタックマシンを Ruby で自作して、それを使ってパズルを解く、といった展開で全体構成を考えていました。……が、しかし、これがなかなかうまくまとまりません。機能を削りすぎると RubyVM の名残が残りませんし、かといってローカル変数など Ruby らしさを反映した仕様を残すと、1から作るには少々大きすぎます。

前作の Python 版 "let's take tea break" では、表問題は実は前座で、裏問題で真の姿が見えて最終問題となる、という全体のまとめ方でしたので、今回もそれを狙ってしばらくウンウン唸っていたのですが、毎回同じ構成もつまらない、と思い直したのが転機となりました。そもそも、裏問題まで到達する方は少ないので、表部分だけで十分に完結した方がよいと判断したこともあります。

そこで、Code Puzzle というタイトルからの言葉遊びで、今回は「一般的なパズルをコードを書いて解く」「コード (暗号) を使ったパズル」の 2 つを指針として問題をデザインし、Ruby 2.0 に関しては、その高速性を活かした探索系課題を多くすることと、あとは (最後まで行けば分かりますが) Ruby 2.0 にちなんだ大事なキーワードを使わせていただく形で問題をまとめることにしました。

今回、パズルらしいパズルを題材にしようと考えた背景には、前回の Python 版の裏テーマが「セルオートマトンが一方向ハッシュに使えると聞きかじった人が間違った構成で電子署名を実装したらたいへんなことになっちゃった」というマニアックすぎるものだったため、今回はもう少し多くの人に分かり易いネタにしようと思ったからということもあります。

もっとも、最後の最後まで行けば分かる今回の裏テーマも、違う意味でかなりマニアックですが……。

全体構成

表問題・裏問題とさらっと書きましたが、ここで Code Puzzle の問題構成について簡単にご説明します。

表ルート

最初にご紹介したフライヤーの問題を解くと、次の問題の URL が導かれます。そこからは、問題の答をサイト上の回答フォームに入力すると、次の問題が表示される、ということを何回か繰り返し、やがてクリアページにたどり着きます。ここまでを表ルートと呼んでいます。この表ルートは、「遊び」としてのコーディングを多くの方に楽しんでいただきたいと思いながら制作しています。

Code Puzzle では、コードで問題を語るという、閃き重視の問題提示をしています。しかし、この出題形式だと、フィーリングが合う方はすぐに取り組んでいただけるのですが、勝手が分からないと余計な所で詰まってしまったりします。

ナゾ解きだと考えれば、この詰まる部分も含めて遊びになるのですが、Code Puzzle のメインは、あくまでもコーディングの楽しみです。そこで、ギャップを埋めるものとして、2 問目以降では問題ページの右下から飛べるヒントページを用意しています。腕に自信がある方は、ヒントを一つ二つ読むだけで解き始めてもらえますし、慣れていない方はヒントを全部じっくり読んでからトライしていただいても OK です。

表ルートだけでも、色々な閃きが必要となる、歯ごたえのある問題を揃えているつもりですので、ぜひチャレンジしてみてください。

裏ルート

では、裏ルートとは何かといいますと、簡単に言えば、難易度高の追加ステージです。裏ルートには、表の最終問題を別解釈した解答を入力することで入ることができますが、ヒントはほぼありません。観察力と閃きが要求されます。そして、裏ルートには1問だけ、とても難しい裏問題が待ち構えています。

裏問題に関しては、ヒントページは用意されていません。自力で解けた人は、プログラミングの腕も、閃き力も素晴らしい、スーパープログラマーと言えるでしょう。

参考までに、前作 "let's take tea break" では、裏ルートへの入り方は、なぜ "a" が無いかなども含めて "take tea break" をどう解釈するかというウルトラ C の発想の飛躍が必要でした。表のクリアページから進める隠しページの問題を解くと追加ヒントが得られたとはいえ、良く言えば水平思考、悪く言えば屁理屈のこじつけが必要で、かなり辛口のご意見をいただいたポイントでもあります (私はこういうのも好きなのですけれども!)。

その批判も鑑みまして、今作 "decode the answer" では、比較的に素直な裏ルートへの分岐になっているかと思います。それでも、気付くには閃きが要るかもしれません……。

裏ルートに関しては、これ以上語るのは野暮というものでしょう。裏ルートの入り方に関しては、口づてで教え合っていただければ、隠した甲斐がありますので嬉しいです!

【ネタバレあり】表問題 各問解説

それでは、表ルートの全 5 問を順番に解説していきましょう。

フライヤー問題

CodePuzzle_RubyKaigi2013_flyer.jpg

参加者が最初に解くのは、このフライヤーの問題 (再掲) です。赤い下矢印は、上の情報に、解答に必要な手続きを適用することを示しています。

def trans_table
  alphabets = ["A".."Z", "a".."z", "0".."9"].map{|r| r.to_a.join}
  alphabets.map{|ab| [ab, ab[KEY%ab.size..-1] + ab[0, KEY%ab.size]]}.
    transpose.map{|a| a.join}
end

ここが一見ややこしいですが、実は変換が 1:1 の文字置き換えであることさえ推測できれば、赤い手書き文字を変換表として、コードを読まずに vekvi は変換することが可能です。ykkg:// が http だろうというところもヒントです。

一方、真面目にコードを読もうと思うと、trans_table は Ruby 1.9.2 以降であれば以下のように書き換えることができます。

def trans_table
  alphabets = [?A..?Z, ?a..?z, ?0..?9].map(&:to_a)
  alphabets.map{|ab| [ab, ab.rotate(KEY)]}.transpose.map(&:join)
end

A-Z, a-z, 0-9 をいっぺんに処理しようとしているのでコードが読みにくいですが、結果として整数 KEY だけ位置をずらした文字列とのペアを返します。この返り値を引数として String#tr を呼び出すことで、KEY をキーとするシーザー暗号を適用することになります。

KEY の値はピンに隠れて読めませんが、シーザー暗号であることが分かれば、赤い手書き文字の対応で何文字ずれているか数えるだけで逆算できますね。

ちなみに、社内の声として、コードは Ruby 2.0 専用でいいじゃないか、という根強い意見があったのですが、今回は Ruby 1.8 以上対応ということで作問しています。前回、Code Puzzle を解くために Python を勉強してくださった方もいらっしゃいましたので、今回もこれをきっかけに Ruby を勉強する方がいらっしゃるかもしれないと配慮してのことでした。ただし、2 問目以降は utility.rb で足りないユーティリティメソッドを足して、実質 2.0 くらいの気持ちでコードを書いています。

3 枚パズル Step1

前回の反省として、表ルートの問題がいつまで続くかわかりにくい、というものがありました。そこで、今回は 2 問目以降は、一つのセットとなったパズルを解いていく形式としました。

CodePuzzle_Ruby_Puzzles.jpg

9×9 のマスと、駒のイラストと、ランダムに見える文字列。これを組み合わせて解いていくと、最終的には 11 文字の言葉が出てきます。以上の条件だけでも頑張れば解けるはずですが、ただのナゾ解きになってしまいますので、今回の Code Puzzle では、これをステップ毎に分解して、プログラマーの特技を活かしながら解いていくことになります。

まず、Step1 では一番取っつきやすい 9×9 のマスを解きます。もちろん、これはナンバープレイスパズルです。世界的には sudoku という呼び名で愛されている大人気パズルですね。手でも解けますが、普段、なかなかナンバープレイスを解くプログラムを書く機会はないでしょうから、ぜひコーディングしてみてください。ヒントにはだいぶん核心部分までコード断片をご用意しています。

注意点として、今回は一貫して右上が (1, 1) で、左下が (9, 9) の座標系が使われていることには気をつけてください。これは、次の問題のヒントとなります。

なお、ヒント通りに作ったコードは、この問題を解くには十分ですが、改造の余地はたくさんあります。そこをいろいろいじってみるのも、遊びとしてのプログラミングならではの寄り道です。テストケースにコメントアウトされた状態で難しい問題も用意していますので、ご利用ください。

回答フォームに入力する答は、ナンプレの最初の1行です。

3枚パズル Step2

ナンプレが解けたら、今度は将棋の駒の絵の意味を考えることになります。描かれているのは「竜馬」という、角が成った駒です。斜めにはどこまでも進め、上下左右には1マスだけ進めます。

「竜馬」の周りには「*1」から 2, 3, 4... と順番に矢印が進み、9 から「*1」に戻る、という円が描かれています。この「*1」は、先ほど解いたナンプレの一番左上のコマと何か関係がありそうです。……と、ここまでくれば、何をすればいいかピンと来る方もいるかもしれません。将棋盤は縦 9 マス×横 9 マス。ちょうど一致してますね。

さて、

paths = HoursesTour::Solver.new($grid).solve(9, 1)
raise "paths.size != 1" if paths.size != 1

問題ページのコードにはこのような記述がありますので、 HoursesTour::Solver を作る必要がありそうです。ちなみに、solve の引数 (9, 1) は「9一」の位置から開始することを指示しています。

Hourse's Tour の元ネタは、Knight's Tour というチェス盤とナイトを使った有名な数学パズルです。将棋でナイトに相当する桂馬は残念ながら後ろに戻れませんので、竜馬の出番となりました。同時に、移動可能なマスの制約もオリジナルとはだいぶん異なったものになっています。

このパズルも人力で解くことも可能ですが、目がチカチカしますし、せっかくなのでコーディングしてみましょう。これを解けば、前の問題と合わせて、再帰プログラミングはばっちりかと思います。こちらもヒントにたっぷりコード断片をご用意しています。

さて、Hourse's Tour が解けたら、あとはもうひと変換すれば答が出ます。「*1」のアスタリスクは特徴的な 5 つの線で出来た星でした。このアスタリスク、どこか他でも見かけなかったでしょうか。それに気付けば、あとは馬が辿ったマスの順に拾っていくと、Step2 の答となります。

3 枚パズル Step3

ここからは、いよいよコンピュータの助けがないと解けない問題となってきます。

聞き慣れない単語が出てきたので、インターネット検索してみると、ある古典的な暗号方式の名前であることが分かります。暗号文はおそらくこのランダムっぽい英字列でしょう。しかし、鍵のヒントはまったくありません。さてどうしよう、というのがこの問題となります。

答は、現代の PC にかかれば古典暗号くらい楽勝で解析できるヨ、でした。

ノーヒントでも一般の単語辞書を持ってきて試行錯誤すればなんとかなるはずですが、

def the(s) s[0..3].upcase end
$plain_text = decode_vigenere($text, (the $password))

というコード片から、鍵は 4 文字に切り詰められていることがわかります。それがわかれば、あとは 26 の 4 乗の探索空間からの条件マッチです。

さらには、generate_oracle.rb というオラクル (神託) を出力する CGI が用意されており、平文の一部を教えてくれます。オラクルというのは、情報科学用語で、どんな原理か分からないけれども正しい情報を教えてくれる情報源、とでも思ってください。この generate_oracle.rb は、自分自身のソースコードを textarea 内に出力するという機能も持っています (Quine の一種です)。そのコードを読み解くと、オラクルは IP アドレス毎に異なるものが出力され、しかも 6 時間毎に切り替わるということが分かります。

つまり、解析のための平文情報を手に入れたい場合は、他の人と協力してオラクルを集める、もしくは、時間経過による更新を待つ、のどちらかが必要となります。また、Twitter のつぶやきボタンもページについており、#codepuzzle で簡単に情報共有できるようにもなっていました。

お分かりでしょうか。この「#codepuzzle 上で協力しながら、わいわい解いてもらえたら嬉しいな」という制作者の気持ちが。

しかし、プログラマーの孤高の誇りを甘く見てはいけませんでした。結果として、Twitter 上ではほとんど平文の情報が共有されることはなく、伝え聞いた話によると、複数 IP を駆使し、一人で複数個の情報をいかに手に入れるかのテクニック勝負となっていたようです。ええ、もちろん、それでもいいのです。解き方は参加者の自由ですから。実際に、一人プレイでも発想次第でちょっとした追加情報が分かるような裏口も用意していました。

とはいいましても、ちょっぴり残念な気持ちになったのは間違いありません。「もし次の機会があれば、今度こそ協力必須にしよう」と、密かに心に誓ったとか誓ってないとか。

さて、Step3 の解答は、暗号解読後の文字列の、(KEY*2) 文字目から KEY 文字。この KEY は、実は回りまわって最初のフライヤーのコードが require されている、ということに気付く必要がありました。

3 枚パズル Step4

暗号も解読し、いよいよ表ルートの最後のステップです。暗号解読結果の指示に従い、最後の 11 文字を導出します。

なお、解読文は文字数などの制約により、かなりわかりにくい表現になっているので、ヒントページの和訳を参照してもらったほうがスムーズでしょう。『約数を持たない。』が曖昧に感じる部分があるかもしれませんが、全部で 22 個になるように、常識的な条件を想定していただければ OK です。また、問題ページのコードを読めば自明ですが、箱を数える順番は文字列を流し込んだ時と同じように左上から、x と y は最初から使ってきた右上基準の座標系です。

そして、座標が分かった上で、どこから文字を拾うべきかが最後の関門ですが、候補はいくつもありません。試行錯誤し、よく知っている英単語が出てきたら、見事、表ルートのクリアです!

そして裏ルートへ

裏問題は万人向けではありませんので今回は深く触れませんが、どうしても裏が気になるという方に、ちょっとだけ裏ルートへの入り方のヒントをお教えしましょう。

裏に入るために必要な情報は、表ルートのいくつかの問題の中に隠れていますが、特に、一番注意深く観察すべきは、表のクリアページです。見えないものを見つけてください。

分岐点は、表ルートの最終問題です。

Q&A

最後に、Twitter 上の感想などでいただいた質問をこの機会にお答えしてみます。

何重にも情報が埋め込まれた問題があるのですが、どうやって作っているのですか?
根性と運です。実際、解答のために必要なコードの何倍も、作問のためにコードを書いています。あとは、何かが下りてくるのを待ちます。
「おしい!」って出たのですが……?
主に裏ルートに入る段階で、発想の方向性は合っているものの、手順が一部間違っている回答に対して出る表示です。諦めずに頑張ってください!
minihint は何種類あるのですか?
「おしい!」とは別に、一部の誤答や、一部のページアクセスに対して、minihint という特殊なヒントが表示されることがあります。このファイル名に通し番号が振られており、Python 版には 0 から 5 の 6 種、Ruby 版には今のところ 1 から 7 + α の 8 種存在しています。参考までに、今回の "decode the answer" では、最初に裏クリアした方が、どうやらそのままの勢いで minihint もコンプされていったようです。たいへん感服いたしました。スゴイ!
ヒントページに出てくる人たちにはモデルはいるのですか?
ヒントページには新人さん・先輩さん・大先輩さんという 3 人の人物が出てきますが、彼らは本当にいるのかもしれません。いないのかもしれません。でも、新人さんはもう少し色々頑張った方がいいですね……。
裏問題が何日かけても終わりません!
実は SAT ソルバーを使って解くという裏技もあるのですが、正攻法でどうしても終わらない場合は、この記事を最後まで読んでいただけると、何か道が開けるかもしれません。

おわりに

Code Puzzle についてご説明してきましたが、いかがでしたでしょうか。「プログラマによるプログラマのための遊び」として楽しみながら作っている様子を少しでもお伝えできたのであれば幸いです。

毎回、次のことは考えずに作っていますので、今後の予定は立っていませんが、皆さまの好評の声があれば、もしかしたらまたどこかで、新人さんと先輩たちのプログラミング問答をお見せできるかもしれません。そのときには、ぜひ皆さまのチャレンジを楽しみにお待ちしています。

それでは、最後になりましたが、改めまして、Ruby 20 周年、おめでとうございます! 今後も Ruby と Ruby コミュニティの発展を心より願っております。

CodePuzzle_Ruby20thAnniv.png

著者について

任天堂株式会社ネットワーク開発運用部東京ネットワークシステム開発グループ所属。秋葉原徒歩圏内にあるオフィスにて、サービスを設計したり、ゲーム仕様を一緒に考えたりと、ニンテンドーネットワークに関するさまざまな案件に取り組んでいる。

Code Puzzle の企画・作問は、キャリア採用活動の一環のお仕事ということになっている。「Code Puzzle を見て応募しました!」と言ってもらえるのが密かな夢。

Zuletzt geändert:2013/07/31 21:05:34
Stichworte:
Referenzen:[Rubyist Magazine 0043 号] [0043 号 巻頭言] [Rubyist Magazine 九周年] [分野別目次] [各号目次]