技術部の遠藤（@mametter）です。おまたせしました、RubyKaigi 2022で出題したクックパッドブースの企画、Cookpad Code Puzzle for RubyKaigi 2022の裏ステージの解説です。
このパズル自体の解説は前編の記事をごらんください。
さっそく11問目から解説していきます。
11問目
p func11(0) #=> -510240563 p func11(1) #=> -171748573 p func11(2) #=> 405559065 p func11("foo") #=> -62024031
何を与えてもよくわからない整数が帰ってきますね。リロードすると結果が変わることにも気づくかもしれません。つまり、これはハッシュ値であろうと当たりがつきます。ということで答えはこちら。
def answer11(v) v.hash end
11問目からは問題文もないし、知らないと解けない問題が多めになります。
12問目
p func12(0) #=> 1 p func12(1) #=> 1 p func12(2) #=> 1
この辺を見てても1ばかり帰ってきますね。1以外になるところを探してみましょう。
300.times { p [_1, func12(_1)] if func12(_1) != 1 }
[11, 2] [22, 2] [33, 2] [44, 2] [55, 2] [66, 2] [77, 2] [88, 2] [99, 2] [100, 2] [101, 2] [110, 2] [111, 3] [112, 2] [113, 2] ...
ゾロ目が目に付きますが、100や101も2になることから、同じ数字の出現数が関係しそうです。確認してみましょう。
p func12(1111) #=> 4 p func12(11111) #=> 5 p func12(111111) #=> 6
では、違う文字が複数ある場合は？
p func12(1122) #=> 4 p func12(111222) #=> 9 p func12(11112222) #=> 16 p func12(11) #=> 2 p func12(11222) #=> 6 (= 2 * 3) p func12(1122233333) #=> 30 (= 2 * 3 * 5)
こういうのとにらめっこすると、文字ごとの出現数の積とあたりがつくのではないでしょうか。なのでこれが答え。
def answer12(n) n.to_s.chars.tally.values.inject(&:*) end
13問目
100.times { p [_1, func13(_1)] }
[0, "AS"] [1, "UT"] [2, "US"] [3, "UT"] [4, "UT"] [5, "UT"] [6, "UT"] [7, "UT"] [8, "UT"] [9, "UT"] ... [22, "IS"] [23, "IS"] [24, "IS"] [25, "IS"] [26, "IS"] [27, "IS"] [28, "IS"] [29, "IS"] [30, "IS"] [31, "IS"] [32, "IS"] [33, "IS"] [34, "IS"] [35, "IS"] [36, "IS"] ...
この問題はもう経験と勘を働かせるしかないです。先頭2文字を取っているのだろうと予想し、"UT"で始まる用語というと、UTCかUTFかな？などと考えます。すると、"IS"は"ISO"と当たりが付き、RubyがサポートしているEncodingの一覧では？と考えついてください。ということで答えです。
def answer13(n) s = Encoding.list[n] s.name[0, 2] if s end
func13からfunc15は、正体に気づかないまま、引数と返り値の対応をすべて記憶してテストを通した人が多かったかもしれません。それもよいと思います。
Table13 = {} 1000.times { Table13[_1] = func13(_1) } def answer13(n) Table13[n] end
14問目
100.times { p [_1, func14(_1)] }
[0, "Z"] [1, "O"] [2, "T"] [3, "T"] [4, "F"] [5, "F"] [6, "S"] [7, "S"] [8, "E"] [9, "N"] [10, "T"] [11, "E"] [12, "T"] ...
これはよくある謎解きです。O→T→T→F→F→S→S→E→? という出題形式が多いかも。
答えを言うと、数字を英語で言ったときの頭文字です。One、Two、Three、Four、Five、……。ということで答え。
def answer14(n) raise "The argument should be an integer from 0 to 1000" if n < 0 || n > 1000 if n <= 20 "ZOTTFFSSENTETTFFSSENT"[n] elsif n < 100 answer14(n / 10) else answer14(n / 100) end end
なお、func14(1000) が "T" になるのは意図してないバグでした。One thousandなので"O"が正しそう。ハマったひとがいたらごめんなさい。
15問目
100.times { p [_1, func15(_1)] }
[0, "AR"] [1, "AR"] [2, "Ar"] [3, "Ar"] [4, "Ba"] [5, "Bi"] ...
この問題も経験と勘です。"RU"で始まるものが多いあたりで"RUBY"と気づけるかどうか。これはトップレベルの定数名の先頭2文字です。ということで答え。
def answer15(n) s = Object.constants.sort[n] s.to_s[0, 2] if s end
16問目
p func16 #=> undefined method `call' for nil:NilClass (NoMethodError)
callというあたりから、ブロック引数を受け取っているのでは、と考えます。
p func16 {} #=> false
falseが帰ってきました。falseを返すからには、trueを返すこともあるはず。ブロックの返り値をいろいろ試してみます。
p func16 { 0 } #=> false
p func16 { 1 } #=> false
p func16 { "foo" } #=> false
falseから変わりません。ブロックに引数が渡されているのでしょうか？
func16 {|*a| p a } #=> []
なにも渡されていない……いや、可変長引数で見えない引数がありますね。たとえばselfです。
func16 { p self } #=> main
残念、selfは変わっていませんでした。もうひとつ見えない引数があります。ブロック引数です。
func16 {|&b| p b } #=> #<Proc:0x0141b684 secret2.rb:66>
ビンゴ。ブロックが渡されてるようなので呼んでみましょう。
p func16 {|&b| b.call } #=> true
やった、返り値がtrueに変わりました。ということで答え。
def answer16(&blk) flag = false blk.call { flag = true } flag end
たぶんこれが一番むずかしい問題だったのではないかと思います。ブロックにブロック引数を渡すこと自体がマイナーだし、気づきにくいですよね。解けた人はすごい。
17問目
func17(0)
実行するとJSのalert("0")が出てきます。この問題はRuby on WasmのJS連携を試してもらいたくていれました。
Ruby on Wasmのドキュメントを頑張って読み始めてもいいですが、適当な関数でテストを走らせてみるとRuby on WasmのJS.evalへのURLが出てきます。
def answer17(n) end
--- testing answer17 test17.rb:10:in `test17': JS's alert must be called (Hint: https://github.com/ruby/ruby.wasm/blob/194f4a1dfe9036018fef9810d71e23a24cd97bd9/ext/js/js-core.c#L81) (RuntimeError)
ということで答え。
def answer17(s) JS.eval("alert(#{ s.to_s.dump })") end
18問目
func18をいろいろ呼んでもよいですが、この問題は適当なanswer18を定義したほうが早かったかもしれません。
def answer18(s) end
--- testing answer18
test18.rb:4:in `block in test18': answer18("0") != func18("0") (RuntimeError)
from test18.rb:2:in `upto'
from test18.rb:2:in `test18'
テストの通り、"0"を渡してみましょう。
p func18("0") #=> [0]
整数にして配列にする？ということで試します。
def answer18(s) [s.to_i] end
--- testing answer18
test18.rb:10:in `block (2 levels) in test18': answer18("80+41") != func18("80+41") (RuntimeError)
from test18.rb:8:in `each'
from test18.rb:8:in `block in test18'
from test18.rb:6:in `times'
from test18.rb:6:in `test18'
"80+41"も渡されるようです。
p func18("80+41") #=> [80, "+", 41]
これを繰り返すうちに、文字列を分解すればいいのだとわかります。ということで答え。
def answer18(s) s.scan(/\d+|[+\-*\/()]/m).map {|s| s =~ /\d+/ ? s.to_i : s } end
これは「字句解析」と言われる処理です。
19問目
18問目と同様にテストの失敗を観察していくと、こういうような挙動をすることがわかります。
p func19([2, "*", "(", 3, "+", 4, ")"]) #=> ["*", ["value", 2], ["+", ["value", 3], ["value", 4]]]
これは構文解析ですね。「再帰下降パーサ」で検索するとCでのコード例が見つかります。これを移植したらOK。
def factor(tokens) t = tokens.shift if t.is_a?(Integer) ["value", t] elsif t == "(" r = expr(tokens) tokens.shift r else "unknown: #{ t }" end end def term(tokens) r = factor(tokens) t = tokens.first while t == "*" || t == "/" r = [tokens.shift, r, factor(tokens)] t = tokens.first end r end def expr(tokens) r = term(tokens) t = tokens.first while t == "+" || t == "-" r = [tokens.shift, r, term(tokens)] t = tokens.first end r end def answer19(tokens) expr(tokens) end
この問題が一番面倒くさかったのではないかと思います。
20問目
ここまで来た人なら、func20はこういう挙動だとわかるでしょう。
p func20(func19(func18("2*(3+4)"))) #=> 14
ということで、func18、func19、func20は四則演算の字句解析、構文解析、評価器という構成でした。答えはこんな感じ。
def answer20(e) case e[0] when "value" e[1] when "+" answer20(e[1]) + answer20(e[2]) when "-" answer20(e[1]) - answer20(e[2]) when "*" answer20(e[1]) * answer20(e[2]) when "/" answer20(e[1]) / answer20(e[2]) else raise "unknown operator: #{ e[0] }" end end
これで全問突破です！おめでとうございます！
まとめ
前後編の長い記事になってしまいましたが、Cookpad Code Puzzle for RubyKaigi 2022の解説でした。
隠された関数の定義を当てるという問題形式 *1 は、いくらでも難しい問題を作れてしまうので、事前に社内でテストプレイをするなどして難易度調整に腐心しました。思ったより多くの人がfunc20まで解いてくれたのでホッとしました。
クレジット：一部の問題は同僚のささださんの発案だったり、@hirekokeさんの発案だったりします。
おまけ：チート対策
Rubyにはこの手のパズルを台無しにするいろんな機能があります。このパズルでは、それらの機能をそこそこ無効にしていました。ただ、潰しきれなかった機能もあります。どのような対策をしたか、それを乗り越えるチート方法などを紹介します。
テスト入力を盗み見る
answerの中で引数を出力させることで、テスト入力を盗み見ることができます。
def answer1(n) p n #=> 826 end
7問目以降ではこのチートは禁止してあります。
def answer7(n) p n #=> in `write': No writing in stdout during answer :-) (RuntimeError) end
$stderrを使ってもダメです。
def answer7(n) $stderr.puts n.inspect #=> in `write': Are you trying me? I've also closed the stderr loophole! (But there is actually a way to see the secret test input. Do you know how to do it? (RuntimeError) end
$stdout.writeを上書きしていることに気づけば、いくらでも回避方法があります。たとえば、事前に $stdout.method(:write)を取り出しておくのが簡単でしょう。
Write = $stdout.method(:write) def answer7(n) Write.call(n.inspect + "\n") end
ほかには、IO.for_fd(1)を使って$stdoutを開いたり、見たい文字列をraiseの引数として呼び出したりすれば回避できます。あまりRuby環境を汚さない回避方法としては、JS連携を使ってconsole.logを呼び出すという技もありました。
error_highlightを使う
NoMethodErrorを引き起こすことで、該当行のソースが見えてしまいます。
p func2(1)
secret.rb:6:in `func2': undefined method `upcase' for 1:Integer (NoMethodError)
s.upcase
^^^^^^^
from code.rb:1:in `main'
これは意図しなくても発動してしまうので、対策として、func4以降ではerror_highlightをわざと止めてあります。error_highlight便利ですね！
answerXからfuncXに移譲する
次のようにすれば、func1の中身を推測しなくてもanswer1は完全に同じ挙動にできてしまいそうです。
def answer1(...) func1(...) end
しかし、これは塞いであります。
--- testing answer1
secret.rb:1:in `func1': Do not use func1 during answer :-) (RuntimeError)
from code.rb:2:in `answer1'
from test1.rb:3:in `[]'
from test1.rb:3:in `block in test1'
from test1.rb:2:in `each'
from test1.rb:2:in `test1'
どうしているかというと、func1の先頭に次のようなコードを仕込んでありました。
raise "Do not use func1 during answer :-)" if caller.any? { _1.include?("answer") }
つまり、バックトレース中に"answer"を含むメソッド名があったら例外にしています。
ちなみに後で報告されたことですが、この対策はFiberを使うことで回避できました。なるほどなあ。
def proxy1(...) Fiber.new { func1(...) }.resume end def answer1(...) proxy1(...) end
チートに使えそうな機能を使う
RubyVM::InstructionSequence.of(method(:func1)).disasm などをすると func1 のバイトコードが覗けてしまうので、このようなメソッドは大体remove_methodしておきました。TracePointは定数を上書きしておきました。
ただ、ObjectSpace.each_objectを対策するのが抜けてました。報告された中で一番豪快なチートは、次のようにすれば正解の定義がすべて抜き出せてしまうというものでした。
ObjectSpace.each_object(String) {|s| puts s if s.start_with?("def func") }
いやー抜けてたなあ。
リバースエンジニアリングへの道（CTFに興味ある人向け）
このパズルはすべてブラウザで動いているので、正解のデータもすべて当然ブラウザ上に入っています。よって、リバースエンジニアリングをすれば理論上はすべてがわかります。
JSのソースコードを見ると/src/app.datというファイルを参照していることがわかります。このファイルは、RubyKaigi 1日目のキーノートでも少し出てきたwasi-vfsを使ってwasmファイルに埋め込んであるので、パズルのコードからでも読めます。
p File.binread("/src/app.dat") #=> "YARB\x03\x00\x00\x00..."
これはRubyのバイトコードをダンプしたデータで、RubyVM::InstructionSequence.load_from_binaryを使ってロードすることができます。
このダンプデータは環境依存なので、WasmのRubyでないとload_from_binaryできません。しかし、パズルのWasmではRubyVM::InstructionSequence.load_from_binaryをremove_methodしておいたので、別途wasmtimeなどでwasm32のRubyを動かしてdisasmを見る必要があるでしょう。また、正解のコード部分はAES暗号化されています（パズルではJS連携を使ってWebCrypto APIで復号しています）。腕に覚えがある人は、解読を頑張ってみてください。
*1:この問題形式は、International Conference of Functional Programming（ICFP）という学会で開催れているプログラミングコンテスト（ICFP Programming Contest）の2013年の問題にインスパイアされています。詳しくは自分のICFPc 2013参加体験記などをご覧ください。この問題から理論っぽい要素を抜いて、代わりにRuby知識を前提にするという発想で作りました。
