OneDay

40歳からプログラマとして生活しています。

久々にCodeIQの問題にチャレンジした[Ruby]

codeiq.jp

先日、0から始めるRuby というプログラミングスクールに行ってきた - ノグレブ管理人のblogというのに参加し、講師の方からRailsのスキルを上げるためにはRubyを勉強したほうが良いというアドバイスをいただきました。Railsは何か実装したいと思ったら、Googleで調べるとなんらか有効なGemがありそれを組み入れることで開発工数は劇的にあがります。時間が掛かるのは、CSS周り。デザインには答えがないので、際限なく時間がかかる傾向にあります。

Railsの思想「設定よりも規約」に従うことでアウトプットという点ではものすごく恩恵に預かっています。自分が作ったアプリケーションのModelなんて最低限のvalidationだけだったり、Controllerもほぼindex/show/new/create/edit/update/destroyで収まっています。Viewもしかりである。そんなに多くないコード量でWebアプリケーションが作れるRailsは凄いと思わざるを得ないです。

しかし、コードの記述を簡潔にしたい場合などはRuby力があった方がいいし、配列やハッシュでのちょっと上手な使い方もRubyで演習積んでメソッドなどを覚えていったほうがRailsで行えることの幅が広がると思います。ということでRailsの開発と同時にRuby力向上のためRubyの書籍読んだり、CodeIQの問題解いたりしていきます。

冒頭のCodeIQ問題にチャレンジしてみました。想定時間30分。えぇーと一日半くらい費やしました。しかも自動で採点されるのですが間違っていました。自分が作ったコードはたかだか30行です。この問題考えるのに配列と正規表現をテキストを開きました。懐かしのたのしいRuby 第4版です。お風呂の中やお布団の中でもどうしたらよいか、考えました。アプリケーション作っていく時にこういう過程は大切だと思います。


この問題を通して役に立ったことを2つメモに残しておきます。


repeated_permutation
[1,0,-1]という3つの数字があって、3桁の組み合わせをすべて出したいとき、permutationというメソッドがあります。

[1] pry(main)> [1,0,-1].permutation(3).to_a
=> [[1, 0, -1], [1, -1, 0], [0, 1, -1], [0, -1, 1], [-1, 1, 0], [-1, 0, 1]]
[2] pry(main)> [1,0,-1].combination(3).to_a
=> [[1, 0, -1]]

ちなみにpermutationで出力するものは順列を数え上げるというようです。combinationは組合せを数え上げるです。参照元Array - Rubyリファレンス

今回欲しかったのは、[1,0,-1]という数字を使って4桁の組み合わせをすべて出したかったのです。[-1,0,1,0],[1,0,-1,0]など入るべき数字の組み合わせと順序も全部。配列の一番目で[1,0,-1]、二番目で[1,0,-1]のように繰り返しを使って、すべての組み合わせを出そうとしたけど、10桁だと自動的に10回繰り返し出来るメソッドを作れなかったため、何か良い方法がないかArray - Rubyリファレンスで探しました。

repeated_combination : 重複組合せを数え上げる。Ruby 1.9.2
repeated_permutation : 重複順列を数え上げる。Ruby 1.9.2

というものがありましたので、pryで試してみます。

[15] pry(main)> [1,0,-1].repeated_permutation(4).to_a.to_s
=> "[[1, 1, 1, 1], [1, 1, 1, 0], [1, 1, 1, -1], [1, 1, 0, 1], [1, 1, 0, 0], [1, 1, 0, -1], [1, 1, -1, 1], [1, 1, -1, 0], [1, 1, -1, -1], [1, 0, 1, 1], [1, 0, 1, 0], [1, 0, 1, -1], [1, 0, 0, 1], [1, 0, 0, 0], [1, 0, 0, -1], [1, 0, -1, 1], [1, 0, -1, 0], [1, 0, -1, -1], [1, -1, 1, 1], [1, -1, 1, 0], [1, -1, 1, -1], [1, -1, 0, 1], [1, -1, 0, 0], [1, -1, 0, -1], [1, -1, -1, 1], [1, -1, -1, 0], [1, -1, -1, -1], [0, 1, 1, 1], [0, 1, 1, 0], [0, 1, 1, -1], [0, 1, 0, 1], [0, 1, 0, 0], [0, 1, 0, -1], [0, 1, -1, 1], [0, 1, -1, 0], [0, 1, -1, -1], [0, 0, 1, 1], [0, 0, 1, 0], [0, 0, 1, -1], [0, 0, 0, 1], [0, 0, 0, 0], [0, 0, 0, -1], [0, 0, -1, 1], [0, 0, -1, 0], [0, 0, -1, -1], [0, -1, 1, 1], [0, -1, 1, 0], [0, -1, 1, -1], [0, -1, 0, 1], [0, -1, 0, 0], [0, -1, 0, -1], [0, -1, -1, 1], [0, -1, -1, 0], [0, -1, -1, -1], [-1, 1, 1, 1], [-1, 1, 1, 0], [-1, 1, 1, -1], [-1, 1, 0, 1], [-1, 1, 0, 0], [-1, 1, 0, -1], [-1, 1, -1, 1], [-1, 1, -1, 0], [-1, 1, -1, -1], [-1, 0, 1, 1], [-1, 0, 1, 0], [-1, 0, 1, -1], [-1, 0, 0, 1], [-1, 0, 0, 0], [-1, 0, 0, -1], [-1, 0, -1, 1], [-1, 0, -1, 0], [-1, 0, -1, -1], [-1, -1, 1, 1], [-1, -1, 1, 0], [-1, -1, 1, -1], [-1, -1, 0, 1], [-1, -1, 0, 0], [-1, -1, 0, -1], [-1, -1, -1, 1], [-1, -1, -1, 0], [-1, -1, -1, -1]]"
[16] pry(main)> [1,0,-1].repeated_permutation(4).to_a.size
=> 81
[17] pry(main)> [1,0,-1].repeated_combination(4).to_a.to_s
=> "[[1, 1, 1, 1], [1, 1, 1, 0], [1, 1, 1, -1], [1, 1, 0, 0], [1, 1, 0, -1], [1, 1, -1, -1], [1, 0, 0, 0], [1, 0, 0, -1], [1, 0, -1, -1], [1, -1, -1, -1], [0, 0, 0, 0], [0, 0, 0, -1], [0, 0, -1, -1], [0, -1, -1, -1], [-1, -1, -1, -1]]"
[18] pry(main)> [1,0,-1].repeated_combination(4).to_a.size
=> 15

[1,0,-1]の3つの数字で4桁作った場合の重複順列は3 x 3 x 3 x 3の81通りあるということですね。

このrepeated_***は4つのうち2つを選んでといった使い方ももちろんできます。

[22] pry(main)> [1,2,3,4].repeated_permutation(2).to_a
=> [[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3, 2], [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4]]
[23] pry(main)> [1,2,3,4].repeated_combination(2).to_a
=> [[1, 1], [1, 2], [1, 3], [1, 4], [2, 2], [2, 3], [2, 4], [3, 3], [3, 4], [4, 4]]

正規表現
つぎにものすごく苦労したのは、さきほどの組み合わせから配列の中で[-1,1]という並びのものを見つけ出すというもの。-1のあとは必ず1があって、この条件を満たさないものは除外したいのです。当初は配列を1つずつ取り出す

ary.size.times do |i|
  if ary[i] == -1 && ary[i+1]
(略)

みたいな感じで構築しようとしました。しかし、[0,-1,1,0,0,1,0,-1,0,1]のように最初の[-1,1]の並びはOKだが後半の[1,0]はNGなので除外したい場合、配列のイリテーターではなかなか期待通りのメソッドが作れませんでした。これを正規表現でやったら結構うまくいきました。さきほどの[1,0,-1].repeated_permutation(4).to_aから[-1,1]のならびでないものを削り落とします。

result =[]
[1,0,-1].repeated_permutation(4).to_a.each do |ary|
    unless /-1[0-]/ === ary.join('')
      result << ary
    end
end

ary.join('')でArrayをStringにして"-1"のあとが'0'と'-'の場合はfalseとなり、'1'の場合だけ取り込まれます。最終的にはメソッドにして、いろんな条件を正規表現で入れ込むことが出来ました。正規表現を使うと配列で実現できなかった条件設定が柔軟に出来るようになった気がします。

def filtering(n)
  result = []
  [1,0,-1].repeated_permutation(n).to_a.each do |ary|
    if ary.inject(:+) == 0                          #配列の要素を足すとゼロになる
      if /^0*-1|^0*$/ === ary.join('')        #-1もしくは0で始まった後-1または全部ゼロならばOK
        unless /-1[0-]/ === ary.join('')      #-1のあと1だけを拾う。-1のあと0と-の要素はNG
          unless /-10*$/ === ary.join('')    # 最後が-1で終わる、もしくは-1のあと0が来て終わる要素はNG
            result << ary
         end
        end
      end
  end
  result
end


とスゴく勉強になった記事を書いたのですが、肝心のテストは「左右反転は同じものとしてカウントします」ということを考慮しておらず落第しています。あとこのコードでは処理が遅くてNGとなりました。本当にプログラミングは奥が深いですが、知っていくとやれることが広がるので面白いです。パーフェクトRuby読み返します。

パーフェクトRuby (PERFECT SERIES 6)

パーフェクトRuby (PERFECT SERIES 6)