Rubyでビックリ階乗を解こう! 〜人間の実働時間を最適化する

ブログを下記に移転しました。デザイン変更により移転先では記事が一層読みやすくなっていますので、よろしければ移動をお願い致します。

- - - - -

「ビックリ階乗(Exclamatory Factorial)」って知ってますか？
ええ　知るわけないです
なぜならいま僕が
次のツイートの解に命名したばかりの言葉だからです*1

なかなか意味深なツイートですが
自分が先生だったらこの解答に
◯を付けざるを得ないでしょう
答えにビックリマークを付ける人はいませんからね!

さて
プログラムする身としては
文系理系両者の反応よりも
このような「ビックリ階乗」が
どれくらい奇跡的なものなのかが気になります
つまりa - (b / c) の解(先の例では24)と
(a - b) / c の解の階乗(4!)とが
一致する組み合わせは
果たしてどれくらいあるのでしょうか

数学的に書くとこういうことです

$f1 = a - (b \div c)$
$f2 = (a - b) \div c$

$f1 == f2!$

そんな思いは当然僕だけではありませんでした*2

「40 - 32 / 2 = 4!」 - エンジニアのソフトウェア的愛情

このブログより1000以下の数字で
15組のビックリ階乗があることがわかっています
ここで1000までの数を考えたときa b c の組み合わせ数は
10億通り( $1000^3$ )にもなりますからその確率は..

$15 \div 10{,}0000{,}0000=0.000000015$

ビックリ階乗は奇跡的な組み合わせなんですね!

しかしそれにしても10億通りの組み合わせとなると
まじめにそのすべてを試してみると当然に
その実行時間が問題になります
先のブログでは試行錯誤して最初のプログラムから
1800倍の高速化を実現して0.1秒以下で答えがでます
手元でRuby版も試して見ましたが0.037秒でした
ステキすぎます!

でこれ以上僕のできることは何も無いのですが
コードの実行時間というものを完全に無視して
コードの読み易さつまり
人間の実働時間の最適化という一点に焦点を合わせて
Rubyでコードを書いてみようと思います^^;

さて
ビックリ階乗の数式をもう一度確認します

$f1 = a - (b \div c)$
$f2 = (a - b) \div c$

$f1 == f2!$

これをRubyの式に置き換えます

f1 = ->a,b,c{  a - b  / c }
f2 = ->a,b,c{ (a - b) / c }

a, b, c = 40, 32, 2

f1[a,b,c] == factorial(f2[a,b,c]) # => true

メソッドでもいいですが
ここでは一行で済むProcを使います

このコードは一見よさそうですが
一部に問題があります

10 / 3 # => 3

そうですRubyでは整数同士の除算は
余りを無視してしまいます

しかしこの問題はrequire 'mathn'
することで解決します

require 'mathn'

10 / 3 # => (10/3)

次にfactorialメソッドってのがダサいですね
こうしましょう

class Integer
  def !
    (1..self).inject(:*)
  end
end

4.! # => 24

require 'mathn'

f1 = ->a,b,c{  a - b  / c }
f2 = ->a,b,c{ (a - b) / c }

a, b, c = 40, 32, 2

f1[a,b,c] == f2[a,b,c].! # => true

良くなりましたね!

次にa b c についての
10億の組み合わせを作ります

set = [*2..1000].repeated_permutation(3) # => #<Enumerator: [2, 3, 4..]:repeated_permutation(3)>

そこから先の条件に見合うものだけ
セレクトします

selected = set.select { |abc| f1[*abc] == f2[*abc].! }

結果をプリントします

pp = ->abc{
  print "(%i - %i) / %i = %i\n"         % [*abc, f2[*abc]]
  print " %i - %i  / %i = %i! = %i\n\n" % [*abc, f2[*abc], f1[*abc]]
}

selected.each { |abc| pp[abc] }

さあこれらを組み合わせて!

require "mathn"
class Integer
  def !
    (1..self).inject(:*)
  end
end

f1 = ->a,b,c{  a - b  / c }
f2 = ->a,b,c{ (a - b) / c }

pp = ->abc{
  print "(%i - %i) / %i = %i\n"         % [*abc, f2[*abc]]
  print " %i - %i  / %i = %i! = %i\n\n" % [*abc, f2[*abc], f1[*abc]]
}

[*2..1000].repeated_permutation(3)
          .select { |abc| f1[*abc] == f2[*abc].! }
          .each { |abc| pp[abc] }

完成です! exclamation.rbで保存して
実行してみましょう!
いきなり1000もなんですから
まずは[*2..100]から..

% time ruby exclamation.rb
(25 - 5) / 5 = 4
 25 - 5  / 5 = 4! = 24

(30 - 18) / 3 = 4
 30 - 18  / 3 = 4! = 24

(40 - 32) / 2 = 4
 40 - 32  / 2 = 4! = 24

ruby exclamation.rb  3.25s user 0.03s system 99% cpu 3.287 total

おおっ
良い感じじゃないですか!

では1000で..

% time ruby exclamation.rb


  ...



  ...



  ...

全く反応ありません^^;

仕方が無いので require 'mathn' はやめて
a <= b, (b % c) != 0, ((a - b) % c) != 0
の条件だけ入れて足切りします

[*2..1000].repeated_permutation(3)
          .select { |a,b,c|
            next if a <= b || (b % c) != 0 || ((a - b) % c) != 0
            f1[a,b,c] == f2[a,b,c].!
           }
          .each { |abc| pp[abc] }

いざ!

% time ruby exclamation.rb


  ...


  ...

ちょっとトイレ行ってきます..

% time ruby exclamation.rb


  ...


  ...

お茶飲んできます..

でましたよ!

(25 - 5) / 5 = 4
 25 - 5  / 5 = 4! = 24

(30 - 18) / 3 = 4
 30 - 18  / 3 = 4! = 24

(40 - 32) / 2 = 4
 40 - 32  / 2 = 4! = 24

(138 - 108) / 6 = 5
 138 - 108  / 6 = 5! = 120

(230 - 220) / 2 = 5
 230 - 220  / 2 = 5! = 120

(721 - 103) / 103 = 6
 721 - 103  / 103 = 6! = 720

(728 - 416) / 52 = 6
 728 - 416  / 52 = 6! = 720

(731 - 473) / 43 = 6
 731 - 473  / 43 = 6! = 720

(735 - 525) / 35 = 6
 735 - 525  / 35 = 6! = 720

(748 - 616) / 22 = 6
 748 - 616  / 22 = 6! = 720

(756 - 648) / 18 = 6
 756 - 648  / 18 = 6! = 720

(765 - 675) / 15 = 6
 765 - 675  / 15 = 6! = 720

(816 - 768) / 8 = 6
 816 - 768  / 8 = 6! = 720

(833 - 791) / 7 = 6
 833 - 791  / 7 = 6! = 720

(952 - 928) / 4 = 6
 952 - 928  / 4 = 6! = 720

ruby exclamation.rb  349.56s user 0.72s system 99% cpu 5:51.87 total

6分!!!

使い捨てプログラムとしては許容できる範囲...
判断は各人にお任せします..

*1:https://twitter.com/#!/Chigami/status/96606063931047936

*2:ホントのことを言えば、このブログから先のツイートを知ったのでした^^;