Cookpad Code Puzzle for RubyKaigi 2022の解説（裏ステージ）

技術部の遠藤（@mametter）です。おまたせしました、RubyKaigi 2022で出題したクックパッドブースの企画、Cookpad Code Puzzle for RubyKaigi 2022の裏ステージの解説です。

このパズル自体の解説は前編の記事をごらんください。

techlife.cookpad.com

さっそく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知識を前提にするという発想で作りました。