Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。

CodeIQ に出した「メソッド名を当てる空欄補充問題」の解説・解題

CodeIQ に「メソッド名を当てる空欄補充問題」( https://codeiq.jp/ace/nabetani_takenori/q595 )という問題を出した。
挑戦の募集はすでに締めきっている。
というわけで、「メソッド名を当てる空欄補充問題」という問題の解説・解題。

で。

この問題を出したわけ

ruby を書くのは楽しい。
どこが楽しいのか考えてみると、まあたくさんあるんだけど、ひとつにはコンテナ操作の気持ちよさというのがある。
コンテナ操作ってのは、配列のようなものに入っているデータを加工すること。並べ替えたり、選び出したり、視点を変えたり。

特に、ブロック付きメソッドでのコンテナ操作が楽しいと感じる。楽しい反面、Java や C から ruby に来たひとには理解しにくい点だとも思う。

というわけで、ブロック付きメソッドを活かしたコンテナ操作に関する簡単な問題を出そうということになった。

問題のルール

ルールは簡単で、空欄にメソッド名を入れるというもの。
メソッド名じゃないもの入れられない。

〈例〉first_letters

# 最初の文字をつなげた文字列
#
# @param [ Array ] strings 文字列の配列
# @return [ String ] 引数 strings に含まれる文字列の1文字目をつなげたもの
# @note strings に空文字入っている場合、無視する。
# @example
#  first_letters([]) #=> ""
#  first_letters(["foo","","bar","","baz","hoge"]) #=> "fbbh"
#  first_letters(["Read","Out","Your","Good","Book","In","Verse"]) #=> "ROYGBIV"
#  first_letters(["Oh","Be","A","Fine","Girl","Kiss","Me"]) #=> "OBAFGKM"
#  first_letters(["Fat","Cats","Go","Down","Alleys","Eating","Bats"]) #=> "FCGDAEB"
def first_letters( strings )
  strings.【空欄〈例〉】{|s| s[0] }.join
end

例題は、map にしてみた。別名 collect。
詳しい仕様なんかは
http://docs.ruby-lang.org/ja/2.0.0/class/Enumerable.html#I_COLLECT
を参照のこと。
ruby を使っている方は知っていると思うんだけど、この map というのがもう決定的に便利で、しかもわかりやすい。
もし使い慣れてない方がいたら、是非この機会に何度も使ってみることをおすすめする。

〈A〉bounding_box

# 外接矩形
#
# @param [ Array ] points 「x座標, y座標 の2要素からなる配列」の配列。
# @return [ Array ] 4要素からなる配列。順に、左端、右端、上端、下端。
# @note 座標系は、右と下が正の方向。
# @example
#  bounding_box([[0,10]]) #=> [0,0,10,10]
#  bounding_box([[1,2],[3,4],[5,6]]) #=> [1,5,2,6]
#  bounding_box([[3,14],[1,59],[2,65],[3,58]]) #=> [1,3,14,65]
#  bounding_box([[7,10000],[-2,100],[4,123]]) #=> [-2,7,100,10000]
#  bounding_box([[8,40],[9,50],[3,30],[5,70],[9,80],[4,20],[6,20]]) #=> [3,9,20,80]
def bounding_box( points )
  points.【空欄A】.map( &:minmax ).flatten
end

利用頻度のあまり高くないメソッドが答えになる問題を最初にしてしまったのはまずかったかもしれないとちょっと思ったけど、あとのカーニバル。

この問題では

  メソッド.map( &:minmax )

という表記を読み解くことが大事かなと思っている。人によっては見慣れないと感じるに違いない表記なので、ここで調べて慣れるといいと思う。
簡単に説明すると、

  メソッド.map{ |x| x.minmax }

と同じ意味になる。
で。
これが読み解けると空欄に入れるメソッドが

[[1, 2], [3, 4], [5, 6]]

を

 [[1, 3, 5], [2, 4, 6]]

に変換していることがわかると思う。
で。
配列を行列と見立てて転置する

transpose

というメソッドがある。
詳しくは
http://docs.ruby-lang.org/ja/2.0.0/class/Array.html#I_TRANSPOSE
を参照のこと。
「行列と見立てて転置する」とか言われると、使い道がほとんどないメソッドのような気分になるかもしれないけど、この例のように

  • 配列の配列という形でデータが提供されている
  • 内側の配列の要素数は一定で、インデックスに意味がある。

という条件を満たしていると、だいたいいつも役に立つ。
今回の例だと、内側の配列は必ず2要素で、[0]がx座標、 [1]がy座標という具合にインデックスに意味がある。

使いどころはそれほど多くないんだけど、使える場面ではかなり便利なので頭に入れておくといいと思う。

〈B〉chars_in_all

# すべての文字列に含まれている文字
#
# @param [ Array ] strings 文字列の配列
# @return [ Array ] で示された文字列全てに含まれている文字の配列。昇順にソート済み。
# @note strings が [] の場合は [] を返す。
# @example
#  chars_in_all([]) #=> []
#  chars_in_all(["tottori"]) #=> ["i","o","r","t"]
#  chars_in_all(["nbetani","tetromino"]) #=> ["e","i","n","t"]
#  chars_in_all(["gold_dragon","were_wolf","gorgon"]) #=> ["o","r"]
#  chars_in_all(["80386","68030","uPD70116"]) #=> ["0","6"]
def chars_in_all( strings )
  (strings.map{ |i| i.split(//) }.【空欄B】(&:&) || []).uniq.sort
end

この問題の場合は、処理の流れを先に想像すると楽に解ける気がする。
やるべきことは、

  • a. すべての文字列に含まれている文字をあつめる
  • b. 昇順にソートする
  • c. 重複を排除する

こんな感じ。b と c については末尾にある

.uniq.sort

で済んでいるので、a の「すべての文字列に含まれている文字をあつめる」を考える。
一方、【空欄B】の前の部分にある

strings.map{ |i| i.split(//) }

で 

["80386","68030","uPD70116"]

を

[ %w(8 0 3 8 6), %w(6 8 0 3 0), %w(u P D 7 0 1 1 6) ]

に変換しているので、この文字の配列の配列を、文字の配列にすれば良いということになる。
空欄Bのメソッドの引数は、

&:&

という、見慣れないひとにとっては暗号のような内容になっているが、これは

  • 最初の & は、実引数をブロックとして渡すための &
  • まんなかの : は、シンボルリテラルの開始文字
  • 最後の & は、シンボルリテラルの内容
  • Procでないものに & をつけると、to_proc によって Proc に変換されてからメソッドに渡される

ということになっている。冗長に書くと

&(("&".to_sym).to_proc)

ということになる。
んで。
配列と配列を & で結ぶと

 %w( 3 1 4 1 ) & %w( 1 2 4 8 ) #=> ["1", "4"]

という具合に共通部分が抽出される。
というわけで、「【空欄B】.(&:&)」が

 %w(8 0 3 8 6) & %w(6 8 0 3 0) & %w(u P D 7 0 1 1 6) #=>["0", "6"]

という意味になるとうまくいく。
というわけで、【空欄B】は、inject(別名 reduce) ということになる。

ちなみに、inject(別名 reduce) は、他のメソッドと異なり、シンボルを受け取ったら to_proc するという仕様もあるので実引数は (&:&) ではなく (:&) でもよい。つまり、

  (strings.map{ |i| i.split(//) }.inject(:&) || []).uniq.sort

でもちゃんと動く。しかし、私見では、非推奨。

あと。
& でつなげると重複が排除されるので一見 uniq は不要に見えるけど、配列の要素数が 1 の時に必要になる。
それと。
inject(&:&) のあとの

|| []

は、引数が [] だったときに inject が nil を返すので、その対策。

この inejct(別名 reduce) は、抽象性が高いので慣れないとなかなか使える場所が見つからない。
しかし実は汎用性が極めて高く、使える場所はどこにでもある。
慣れておくといいことがたくさんあるメソッドだと思う。

inject については
http://docs.ruby-lang.org/ja/2.0.0/class/Enumerable.html#I_INJECT
を参照のこと。

〈C〉count_all_chars

# 文字をキーとし、文字の出現回数を値とする Hash
#
# @param [String] string 調査対象の文字列
# @return [ Hash ] 文字をキーとし、文字の出現回数を値とする Hash
# @example
#  count_all_chars("") #=> {}
#  count_all_chars("William") #=> {"W"=>1,"i"=>2,"l"=>2,"a"=>1,"m"=>1}
#  count_all_chars("Mississippi") #=> {"M"=>1,"i"=>4,"s"=>4,"p"=>2}
#  count_all_chars("PeterPiper") #=> {"P"=>2,"e"=>3,"t"=>1,"r"=>2,"i"=>1,"p"=>1}
#  count_all_chars("doodle_doo") #=> {"d"=>3,"o"=>4,"l"=>1,"e"=>1,"_"=>1}
def count_all_chars( string )
  string.chars.【空欄C】(Hash.new(0)){ |c,h| h[c]+=1 }
end

ruby力の高い熟練者でも意外とこのメソッドは知らなかったと言われたのがこの問題。
ぱっと見 inject と似たような処理をしているんだけど、ブロックは

{ |c,h| h[c]+=1 }

なので、inject ではうまくいかない。
ちなみに inject でも書くことはできて、たとえば

string.chars.inject( Hash.new(0) ){ |h,c| h.tap{ |h| h[c]+=1 } }

こんな感じになる。こうしてみると、ブロック引数の順序も inject とは違うことがわかる。
で。
【空欄C】のメソッドは何かというと、each_with_object。
each_with_index の仲間だと思うと、ブロック引数の順序も納得感がある。

each_with_object は

  1. ループの前にオブジェクトを準備
  2. ループ内でオブジェクトを加工
  3. 加工の結果が必要

という場合使う。
今回の処理を each_with_object なしで書くと

h = Hash.new(0)
# 危険！ここでは h は未完成
string.chars.each{ |c| h[c]+=1 }
return h

こんな感じになる。
each_with_object を使うことにより、作り途中のオブジェクト（上記の例では、「# 危険！ここでは h は未完成」と書いた場所に作り途中の h が見えてしまう場所がある）がオブジェクトを作っている人以外から見えなくなる。

メソッド名が長いのが難点だけど、使いどころの多いメソッドなのでおすすめ。

each_with_object については
http://docs.ruby-lang.org/ja/2.0.0/class/Enumerable.html#I_EACH_WITH_OBJECT
を参照のこと。

〈D〉farthest_distance_square

# 最も遠く離れた二点の距離の自乗
#
# @param [Array] points 「x座標, y座標 の2要素からなる配列」の配列。points.size は 2 以上。
# @return [Numeric] points 内の二点間の距離の最大値の自乗
# @example
#  farthest_distance_square([[0,10],[3,14]]) #=> 25
#  farthest_distance_square([[0,10],[0,10],[0,10],[0,10]]) #=> 0
#  farthest_distance_square([[0,10],[0,10],[0,10],[1,12]]) #=> 5
#  farthest_distance_square([[1,2],[1,7],[10,2],[10,7]]) #=> 106
#  farthest_distance_square([[5,0],[3,3],[7,9],[3,5],[2,4],[7,6],[8,8],[1,6],[7,7],[8,1]]) #=> 85
def farthest_distance_square( points )
  points.【空欄D】(2).map{ |a,b| (a[0]-b[0])**2 + (a[1]-b[1])**2 }.max
end

この farthest_distance_square は、combination なんかのメソッドがないと

points.size.times.inject(0){ |m,ia|
  a = points[ia]
  ia.times.inject(m){ |m,ib|
    b=points[ib]
    [m,(a[0]-b[0])**2 + (a[1]-b[1])**2 ].max
  }
}

などと書くところなんだけど、ruby には combination がある。
combination(n) というのは配列の中から n 個を選ぶ組み合わせをすべて列挙するという便利なメソッド。
実のところ、C や Java で同じような関数を書くのはそれなりにしんどい。この処理が必要な場面に遭遇すると、ruby を使っているということの幸せを噛みしめることができる。
combination には repeated_combination, repeated_permutation, permutation という仲間がいてどれでも正解になるんだけど、combination 以外は計算量に無駄が生じるので combination が好ましい。

ruby 1.9 と ruby 2.0

出題の直前に気づいたんだけど、ruby1.9 と ruby2.0 で chars の返す値の型がちがう。

chars each_char split(//)
ruby2.0 Array Enumerator Array
ruby1.9 Enumerator Enumerator Array

それで、chars_in_all の方は慌てて chars を split(//) に変えたんだけど、count_all_chars の方は変え忘れて、ちょっとわかりにくい感じになってしまった。

どうわかりにくいかというと。
Enumerator であれば、each_with_object の他に with_object も使える。

Array Enumerator
with_object n/a available
each_with_object available available

というわけで、count_all_chars の【空欄C】は

each_with_object with_object
ruby2.0 OK エラー
ruby1.9 OK OK

という状況になっていて、やや曖昧な出題になってしまったんだけど、もちろん両方正解にした。

出してみて

勉強になったとか、このメソッドは知らなかったとか、そういう声をたくさん頂いた。
出してよかった。

inject vs reduce

さて。皆様お待ちかね。inject vs reduce の結果発表！

inject reduce 両方
人数 21 10 1

こんな感じ。「両方」というのは、「inject でも reduce でもよい」という趣旨のことを書いた方がいらっしゃったのでそれ。
「両方」の分は inject にも reduce にも算入されてるので、母集団は 30名。
というわけで、inject の圧勝。私も inject 派。

歴史的経緯などについては Rubyist Magazine の
map と collect、reduce と inject ―― 名前の違いに見る発想の違い
をご覧いただくのが良いと思う。

宣伝

今は
【アルゴリズム】最大公約フィボナッチ数(?)
という問題を出していて、挑戦者募集中。

あと。
1/10(金) の オフラインリアルタイムどう書く ( http://atnd.org/events/46348 ) も参加者募集中。
今回は初めて、人数が多かったら適当にペアプロをして頂く予定。予定は未定。