「チームラボクイズ2010 やってみた！ Part.2 on Ruby」の追記分がえらい長さになってしまったので，分割します。

前回からの進展を簡単に言うと，かなり高速化しました！
また，便利な良い書き方を見つけたので，それも補足です。

便利な書き方があった

92行目からの以下の部分は，

  s.size.times do |i|<br>    str = str.gsub(MARK[i], s[i])<br>  end<br>

以下のように書くことができます。

  s.each_with_index do |elem, i|<br>    str = str.gsub(MARK[i], elem)<br>  end<br>

このほうが綺麗ですね。

たった１行で高速化！？
このコードのある１箇所を修正するだけで，かなり高速化することがわかりました！

それが93行目の，

    str = str.gsub(MARK[i], elem)<br>

この部分です！！

ここでは，非破壊的メソッドを使っていますが，コードの内容的に破壊的メソッドを利用すべき箇所です。

つまり，以下のように「!」びっくりマークを付けますｗ（代入もしません）

    str.gsub!(MARK[i], elem)<br>

これだけで，

4m22.74s

だった実行速度が，

2m10.38s

となりました！！！

2倍ですよ2倍！！
「！（びっくり）」するような速さですｗｗ！！

いろんなめぐったサイトで「破壊的メソッドの方が非破壊的メソッドを使うよりも速い」ということが書いてあったので，注意はしていたのですが，気づいていませんでした。（もともと，ちょっと違うやり方で書いた部分だったので）

それにしても，これだけの実行速度の差が出るなんて・・・。
「！」1個で，Javaに勝てるｗ（余計な総当りを削ったからですがｗ）
（逆に「！」1個ないと，Javaに負ける）

というわけで，Javaで書いた無駄が多いのよりも，高速化できて満足は・・・してません。

実はまだ総当りには無駄があるのです。
問題文には，

「１は必ず入る」

とあります。 （問題文通りではありませんがｗ）

さらに，実際に問題を読み解いていくと

「正しい式を作るには，’=’が必ず必要じゃね？」

と思いました。

実際にそれを前提で実装していましたがｗ

ということは，

６個の記号のうち２個は’1’か’=’

ですよね。

では，整理してみます。

問題文に書いてある直接的なこと（’1’は必ず入る）から総当りすべき数は，

13P5 * 6 = 926640 通り

となります。

しかし，読み解いたら’=’も必要だということが分かったので，それを加味した場合だと，

6P2 * 12P4 = 356400 通り

となり，2.5倍ほど計算量を減らすことができます。

しかし，最初のJava版では順列を利用せずに，フルの総当りをしました。（順列を作ることまで手が回らなかった）
なので，

14^6 = 7529536 通り

 こんなに多くやっていました。（そこから，1,=が含まれていなければ弾いてはいましたが）
最小評価と比べて２０倍近くあります。

なので，今度はRubyで最小評価でやってみました。
修正を加えたソースコードを以下に貼ります。

ソースコード（最小評価）：

## 定数宣言 ##<br>#問題文<br>STR = "2ABACBDEDFDFDFDCBACDAFB2"<br>#当てはめる文字（記号）<br>CH = ['0', '3', '4', '5', '6', '7', '8', '9', '+', '-', '*', '/']<br>#置き換える文字<br>MARK = ['A', 'B', 'C', 'D', 'E', 'F']<br>#演算記号（計算順）<br>OPE = ['-','+','*','/']<br><br>#文法が正しい<br>def isGrammarOk(str)<br>  #演算記号の右隣が'0'でないか<br>  return false if /[^0-9]0/ =~ str<br> <br>  #演算記号が並んでいないか<br>  return false if /[^0-9]{2}/ =~ str<br> <br>  #不正チェック終了→文法的に正しい<br>  return true<br>end<br><br>#式を計算し値を返す<br>def calc(str)<br>  #演算記号がない場合，パースして値をreturn<br>  return str.to_f unless /[^0-9]/ =~ str<br> <br>  #順番に計算<br>  OPE.each do |ope|<br>    #末尾から先頭に向かって演算記号を探す<br>    if (pos = str.rindex(ope)) != nil<br>      #演算記号に一致した場合<br>     <br>      #左辺，右辺を再帰処理して，数値型に<br>      leftVal = calc(str.slice(0, pos))<br>      rightVal = calc(str.slice(pos+1, str.size))<br>     <br>      #演算記号による分岐<br>      case ope<br>      when "-"<br>        return leftVal - rightVal<br>      when "+"<br>        return leftVal + rightVal<br>      when "*"<br>        return leftVal * rightVal<br>      when "/"<br>        return leftVal / rightVal<br>      end<br>    end<br>  end<br> <br>end<br><br>#'='の左辺と右辺が等しいか<br>def isCorrect(str)<br>  #'='で区切り配列に分ける<br>  equ_array = str.split(/\s*=\s*/)<br>  clear_equ = []<br> <br>  #それぞれの項について<br>  equ_array.each do |equ|<br>    #文字列式から数値に<br>    clear_equ << p = calc(equ)<br>    #一致しなかったらfalse<br>    return false if clear_equ[0] != p<br>  end<br> <br>  #すべて一致したのでtrue<br>  return true<br>end<br><br>#1つにまとめただけ<br>def check(str)<br>  return isGrammarOk(str) && isCorrect(str)<br>end<br><br>#順列の生成<br>#組み合わせ<br>CH.combination(MARK.size-2).each do |b|<br>  #必ず入るものを追加<br>  b << ['1', '='] #必ずあるもの<br> <br>  #追加したもので，順列<br>  b.flatten.permutation.each do |s|<br>    #それぞれの順列について<br>    #問題文に当てはめる<br>    str = STR<br><br>    s.each_with_index do |elem, i|<br>      str.gsub!(MARK[i], elem)<br>    end<br>    #当てはめた式が正しければ出力<br>    puts str if check(str)<br>  end<br>end<br>

6P2 * 12P4 = 356400 通り

という表現を，コード上では

12C4 * 6! = 356400 通り

 という表現で表しています。
この方が組みやすかったので。。。

気になる実行速度は！

修正前： 2m10.38s

が

修正後： 26.174s

１分どころか３０秒を切りました ！！（注：見間違えではない）
やったぁあああああ！！


という訳で，一気に高速化できました。
これで満足・・・今度はJavaで・・・？（え？Cでやれって？）

Rubyの機能で今回は，ここまで高速化できました。

最後に，
Ruby素晴らしい！！

前回（チームラボクイズ2010 やってみた！）はJavaで「チームラボクイズ2010」をやってみました。
かなりゴリ押しだったので，あまり満足していませんでした。

なので，今回は言語を「Ruby」に変えて再挑戦してみました。
ちなみにRubyは初心者です！いろいろ調べながらやりました！

Ruby素晴らしい！！一回作ったというのもありますが，改良を加えたりしても前回より圧倒的に早くコーディングが終わりました。
機能が充実していてとても面白い言語でした。
まだまだ知らないことだらけなので，どんどん学んでいきたいです！

以下より，ソースコードとちょっとしたコメントです。

ソースコード：
teamLabQuiz2010.rb

## 定数宣言 ##<br>#問題文<br>STR = "2ABACBDEDFDFDFDCBACDAFB2"<br>#当てはめる文字（記号）<br>CH = ['0', '1', '3', '4', '5', '6',<br> '7', '8', '9', '+', '-', '*', '/', '=']<br>#置き換える文字<br>MARK = ['A', 'B', 'C', 'D', 'E', 'F']<br><br><br>#文法が正しい<br>def isGrammarOk(str)<br>  #'='を含んでいるか<br>  return false unless /=/ =~ str<br> <br>  #'1'を含んでいるか<br>  return false unless /1/ =~ str<br> <br>  #演算記号の右隣が'0'でないか<br>  return false if /[^0-9]0/ =~ str<br> <br>  #演算記号が並んでいないか<br>  return false if /[^0-9]{2}/ =~ str<br> <br>  #不正チェック終了→文法的に正しい<br>  return true<br>end<br><br>#演算記号（計算順）<br>OPE = ['-','+','*','/']<br><br>#式を計算し値を返す<br>def calc(str)<br>  #演算記号がない場合，パースして値をreturn<br>  return str.to_f if /^[0-9]+$/ =~ str<br> <br>  #順番に計算<br>  OPE.each do |ope|<br>    #末尾から先頭に向かって演算記号を探す<br>    if (pos = str.rindex(ope)) != nil<br>      #演算記号に一致した場合<br>     <br>      #左辺，右辺を再帰処理して，数値型に<br>      leftVal = calc(str.slice(0,pos))<br>      rightVal = calc(str.slice(pos+1, str.size))<br>     <br>      #演算記号による分岐<br>      case ope<br>      when "-"<br>        return leftVal - rightVal<br>      when "+"<br>        return leftVal + rightVal<br>      when "*"<br>        return leftVal * rightVal<br>      when "/"<br>        return leftVal / rightVal<br>      end<br>    end<br>  end<br> <br>end<br><br>#'='の左辺と右辺が等しいか<br>def isCorrect(str)<br>  #'='で区切り配列に分ける<br>  equ_array = str.split(/\s*=\s*/)<br>  clear_equ = []<br> <br>  #それぞれの項について<br>  equ_array.each do |equ|<br>  #文字列式から数値に<br>    clear_equ << calc(equ)<br>    #一致しなかったらfalse<br>    return false if clear_equ[0] != clear_equ[clear_equ.size-1]<br>  end<br> <br>  #すべて一致したのでtrue<br>  return true<br>end<br><br>#1つにまとめただけ<br>def check(str)<br>  return isGrammarOk(str) && isCorrect(str)<br>end<br><br>#順列の生成<br>CH.permutation(MARK.size).each do |s|<br>  #それぞれの順列について<br><br>  #問題文に当てはめる<br>  str = STR<br>  s.size.times do |i|<br>    str = str.gsub(MARK[i], s[i])<br>  end<br> <br>  #当てはめた式が正しければ出力<br>  puts str if check(str)<br>end<br><br>

コメントといっても，便利だったところを挙げるぐらいです。

動的配列イイ！
動的配列はほとんど使ったことがないので，とても便利に感じました。自由に使えるのはいいですね。
縛りがなくて，他のことをいろいろ気にせずにコーディングに集中できました。

デフォルトで順列生成をサポート
Rubyには「順列生成」のクラスが用意されていて，今回はそれを使ってみました。

CH.permutation(MARK.size).each do |s|<br>

この部分ですね。

CHの宣言はこんな感じです。

#当てはめる文字（記号）<br>CH = ['0', '1', '3', '4', '5', '6',<br> '7', '8', '9', '+', '-', '*', '/', '=']<br>

配列からそのまま順列が生成できるのです！！
順列の生成がデフォルトでサポートという。。。素晴らしい！

14P6の順列ですね。
前回は14^6でゴリ押ししたので，差がとても大きいです。

しかーし・・・
計算量を省いたので今回の方が明らかに速いと思ったら・・・
timeコマンドでの測定結果：

Java版: 3m4.13s

Ruby版: 4m22.74s

あれ・・・？遅いだと・・・

たしかにRubyとJavaではもともとの速度が違います。
あと，プログラマの問題ですねｗ
ウエイトの高い処理が多いのでしょう・・・
スクリプト言語を使うときは，「ウエイト」をよく考えてコーディングする必要がありますね。

でも，前回に比べては，書きやすかったし，あとから見返しても読みやすいです。
手軽さから言えば，Rubyの圧勝でした。

正規表現便利！
最後に，今回プログラムの中では初めて「正規表現」を使ってみました！
なかなか便利です。
Java版でも正規表現を取り入れれば，文法チェック周辺がすっきりするかもな～。

順列を使って計算量が減ったかと思えば，逆にちょっと遅くなってるというオチでしたが，Rubyなどのスクリプト言語の便利さやすばらしさ，また正規表現の便利さも学べたのでとても身になりました。

Rubyももっと使えるようにして，自分のツールにしてみたいと思います。
また，視野を広げるためにPythonとかその他の言語にも手を付けていきたいなぁと思っています。

追記（03/28）:
追記を分割しました。
チームラボクイズ2010 やってみた！ Part.2 on Ruby 追記