Hatena::Grouprubyist

Ruby初心者prinyの学習帳 RSSフィード

2008-12-08Send + More = Money

krystalさんの日記Send + More = Money を解くものを Array#permutation を使って書いてみる。

# 0 から 9 までの数字から 8 個を順に取り出す組み合わせのリスト
num_permutation = (0..9).to_a.permutation(8).to_a

# Send + More = Money のチェック
def check(s, e, n, d, m, o, r, y)
  send = s * 1000 + e * 100 + n * 10 + d
  more = m * 1000 + o * 100 + r * 10 + e
  money = m * 10000 + o * 1000 + n * 100 + e * 10 + y
  if send + more == money && s * m > 1 
    return true
  else
    return false
  end
end

num_permutation.each do |comb|
  s, e, n, d, m, o, r, y = comb[0, 8]
  if check(s, e, n, d, m, o, r, y) == true
    puts "Send = #{s}#{e}#{n}#{d}, More = #{m}#{o}#{r}#{e}, Money = #{m}#{o}#{n}#{e}#{y}"
    exit
  end
end

実行したら、コマンドラインでカーソルが 20 回近く点滅してた。
4 桁の整数 + 4 桁の整数の最大値は 9,999 + 9,999 = 19,998 で、M = 1 なのはすぐにわかるから、それ以外の数字を求めるようにしてみよう。

# 0 と 2 から 9 までの数字から 7 個を順に取り出す組み合わせのリスト
num_permutation_list = [0, *2..9].permutation(7).to_a

# Send + More = Money のチェック
def check(s, e, n, d, o, r, y)
  send = s * 1000 + e * 100 + n * 10 + d
  more = 1000 + o * 100 + r * 10 + e
  money = 10000 + o * 1000 + n * 100 + e * 10 + y
  if send + more == money && s != 0
    return true
  else
    return false
  end
end

num_permutation_list.each do |comb|
  s, e, n, d, o, r, y = comb[0, 7]
  if check(s, e, n, d, o, r, y) == true
    puts "Send = #{s}#{e}#{n}#{d}, More = 1#{o}#{r}#{e}, Money = 1#{o}#{n}#{e}#{y}"
    exit
  end
end

ほとんど待たずに(カーソルの点滅は 2 回だった)、結果が出た。1 文字減るだけで、こんなに差が出るとは。

holysugarholysugar2008/12/08 16:52大筋はとてもよいんじゃないかと思います。冗長な部分をより簡潔に書けるようになるともっといいかも?

krystalkrystal2008/12/08 19:26Prinyさんすごい! > 4 桁の整数 + 4 桁の整数の最大値は 9,999 + 9,999 = 19,998 で、M = 1 なのはすぐにわかる

cuziccuzic2008/12/08 20:54一文字減ることも大きいですが、10^n か n!/(9-n)! かで大幅な高速化を実現できていますね。

rubikitchrubikitch2008/12/10 07:00ベンチマークを比較してみた。
http://d.hatena.ne.jp/rubikitch/20081210/1228858392

prinypriny2008/12/11 11:15コメントをありがとうございます。
書き方で処理時間がかなり変わるんですね。冗長さに気づく、なくすができるよう、精進します。