2015年4月9日
Ruby

遠い世界の数式をRubyで解いてみた

はてなブックマークで見つけた、遠い世界の数式という問題を Ruby で解いてみました。Ruby の演算子のうち、優先順位が以下のように変更になったうえで、数式を評価して答えを導き出すのが問題。

↑優先順位高
| ビット or
& ビット and
+ 加算
* 乗算
↓優先順位低

問題の詳細は、リンク先を参照お願いします。

思いついた戦略

とりあえずノーヒントでチャレンジ。考えついた方法は…

1. 数式の文字列を、数値と演算子からなる配列に変換する。
2. 優先順位の高い演算子から順に該当箇所を計算していく。
3. 逆ポーランド記法の計算のような stack の pop と push を使う。

多分誰でも考えつく単純な方法で、Ruby 力低めな回答かもしれない（笑。

書いた回答コード

上の戦略を元に書いたコード。10分位でできましたが、コードを短くするためのリファクタリングとかはしてません。

#!/usr/bin/env ruby

# 遠い世界の数式 http://nabetani.sakura.ne.jp/kanagawa.rb/evalex/
def solve_unknown_expression(str)
  # "4*5+6&7|8" => ["4", "*", "5", "+", "6", "&", "7", "|", "8"]
  numbers = str.scan(/\d+/)
  operators = str.scan(/[|&+*]/)
  expression = numbers.zip(operators).flatten.compact

  # calculate in operator priority order
  stack = []
  %w[| & + *].each do |operator|
    stack = []
    until expression.empty? do
      item = expression.shift
      if item == operator
        res = stack.pop.to_i.send( operator, expression.shift.to_i )
        stack.push res.to_s
      else
        stack.push item
      end
    end
    expression = stack
  end

  stack.first
end

data = [
  # [ id, input, expected ],
  [ 0, "4*5+6&7|8", "44" ],    
  [ 1, "15*5", "75" ],    
  [ 2, "15+5", "20" ],    
  [ 3, "15&5", "5" ],    
  [ 4, "15|5", "15" ],    
  [ 5, "30*15*5", "2250" ],    
  [ 6, "30*15+5", "600" ],    
  [ 7, "30*15&5", "150" ],    
  [ 8, "30*15|5", "450" ],    
  [ 9, "30+15*5", "225" ],    
  [ 10, "30+15+5", "50" ],    
  [ 11, "30+15&5", "35" ],    
  [ 12, "30+15|5", "45" ],    
  [ 13, "30&15*5", "70" ],    
  [ 14, "30&15+5", "19" ],    
  [ 15, "30&15&5", "4" ],    
  [ 16, "30&15|5", "14" ],    
  [ 17, "30|15*5", "155" ],    
  [ 18, "30|15+5", "36" ],    
  [ 19, "30|15&5", "5" ],    
  [ 20, "30|15|5", "31" ],    
  [ 21, "1+2+3+4+5+6+7+8+9+10", "55" ],    
  [ 22, "1*2*3*4*5*6*7*8*9*10", "3628800" ],    
  [ 23, "1+2+3+4+5*6+7+8+9+10", "600" ],    
  [ 24, "1*2*3*4*5+6*7*8*9*10", "1330560" ],    
  [ 25, "1|2|4|8|16|32|64|128|256|512", "1023" ],    
  [ 26, "2046&2045&2043&2039&2031&2015&1983&1919&1791&1535", "1024" ],    
  [ 27, "3|0*6&0", "0" ],    
  [ 28, "6&9|2+4", "6" ],    
  [ 29, "9+5&0*0", "0" ],    
  [ 30, "0|8+4+2*9", "126" ],    
  [ 31, "63|75+35*53", "8586" ],    
  [ 32, "29+14|50&68*87", "2871" ],    
  [ 33, "7&26+25&22|9+67", "94" ],    
  [ 34, "19|8583&53+34&32", "53" ],    
  [ 35, "313&513+896|316*209", "200013" ],    
  [ 36, "0|3+4*9+3|9|1&2&5*4&0", "0" ],    
  [ 37, "59+26&76*71&87|39|43*76", "361532" ],    
  [ 38, "714*706&728&738+670+657", "1450134" ],    
  [ 39, "30|7*57|2+7|7+91850&32&94", "2046" ],    
  [ 40, "89+27*43|1|82&94*96|26+84", "2150640" ],    
  [ 41, "99782&561*68|369137+80&41", "0" ],    
  [ 42, "6602&5785|2288+2|7424+1527", "15297" ],    
  [ 43, "166*648&288|418+778|279*655", "100792710" ],    
  [ 44, "70*13+36&23+22+66|92|95*53&9", "9380" ],    
  [ 45, "23+174&56&179408|6727*724*626", "10424152" ],    
  [ 46, "13&84&43*6+77|56+59|15&24+9*66", "0" ],    
  [ 47, "928&728*151+695&321*369|845+771", "161873920" ],    
  [ 48, "5984|86*8519&43184&7183+401*48|6629+97|852", "18135297180" ],    
  [ 49, "217|999&112+511+357+514&98*796|718*715|442&682", "663026760" ],    
  [ 50, "461&424&462+557+855|656|924*234*557&451*884|322", "402208560" ],    
]

data.each do |item|
  result = solve_unknown_expression(item[1])
  puts "#{item[0]}: #{result}"
end

data.each do |item|
  result = solve_unknown_expression(item[1])
  unless result == item[2]
    puts "*** error: #{item[0]}: \"#{item[1]}\" should be \"#{item[2]}\" ***"
  end
end

#!/usr/bin/env ruby

# 遠い世界の数式 http://nabetani.sakura.ne.jp/kanagawa.rb/evalex/

def solve_unknown_expression(str)

# "4*5+6&7|8" => ["4", "*", "5", "+", "6", "&", "7", "|", "8"]

numbers = str.scan(/\d+/)

operators = str.scan(/[|&+*]/)

expression = numbers.zip(operators).flatten.compact

# calculate in operator priority order

stack = []

%w[| & + *].each do |operator|

stack = []

until expression.empty? do

item = expression.shift

if item == operator

res = stack.pop.to_i.send( operator, expression.shift.to_i )

stack.push res.to_s

else

stack.push item

end

expression = stack

end

stack.first

end

data = [

# [ id, input, expected ],

[ 0, "4*5+6&7|8", "44" ],

[ 1, "15*5", "75" ],

[ 2, "15+5", "20" ],

[ 3, "15&5", "5" ],

[ 4, "15|5", "15" ],

[ 5, "30*15*5", "2250" ],

[ 6, "30*15+5", "600" ],

[ 7, "30*15&5", "150" ],

[ 8, "30*15|5", "450" ],

[ 9, "30+15*5", "225" ],

[ 10, "30+15+5", "50" ],

[ 11, "30+15&5", "35" ],

[ 12, "30+15|5", "45" ],

[ 13, "30&15*5", "70" ],

[ 14, "30&15+5", "19" ],

[ 15, "30&15&5", "4" ],

[ 16, "30&15|5", "14" ],

[ 17, "30|15*5", "155" ],

[ 18, "30|15+5", "36" ],

[ 19, "30|15&5", "5" ],

[ 20, "30|15|5", "31" ],

[ 21, "1+2+3+4+5+6+7+8+9+10", "55" ],

[ 22, "1*2*3*4*5*6*7*8*9*10", "3628800" ],

[ 23, "1+2+3+4+5*6+7+8+9+10", "600" ],

[ 24, "1*2*3*4*5+6*7*8*9*10", "1330560" ],

[ 25, "1|2|4|8|16|32|64|128|256|512", "1023" ],

[ 26, "2046&2045&2043&2039&2031&2015&1983&1919&1791&1535", "1024" ],

[ 27, "3|0*6&0", "0" ],

[ 28, "6&9|2+4", "6" ],

[ 29, "9+5&0*0", "0" ],

[ 30, "0|8+4+2*9", "126" ],

[ 31, "63|75+35*53", "8586" ],

[ 32, "29+14|50&68*87", "2871" ],

[ 33, "7&26+25&22|9+67", "94" ],

[ 34, "19|8583&53+34&32", "53" ],

[ 35, "313&513+896|316*209", "200013" ],

[ 36, "0|3+4*9+3|9|1&2&5*4&0", "0" ],

[ 37, "59+26&76*71&87|39|43*76", "361532" ],

[ 38, "714*706&728&738+670+657", "1450134" ],

[ 39, "30|7*57|2+7|7+91850&32&94", "2046" ],

[ 40, "89+27*43|1|82&94*96|26+84", "2150640" ],

[ 41, "99782&561*68|369137+80&41", "0" ],

[ 42, "6602&5785|2288+2|7424+1527", "15297" ],

[ 43, "166*648&288|418+778|279*655", "100792710" ],

[ 44, "70*13+36&23+22+66|92|95*53&9", "9380" ],

[ 45, "23+174&56&179408|6727*724*626", "10424152" ],

[ 46, "13&84&43*6+77|56+59|15&24+9*66", "0" ],

[ 47, "928&728*151+695&321*369|845+771", "161873920" ],

[ 48, "5984|86*8519&43184&7183+401*48|6629+97|852", "18135297180" ],

[ 49, "217|999&112+511+357+514&98*796|718*715|442&682", "663026760" ],

[ 50, "461&424&462+557+855|656|924*234*557&451*884|322", "402208560" ],

]

data.each do |item|

result = solve_unknown_expression(item[1])

puts "#{item[0]}: #{result}"

end

data.each do |item|

result = solve_unknown_expression(item[1])

unless result == item[2]

puts "*** error: #{item[0]}: \"#{item[1]}\" should be \"#{item[2]}\" ***"

end

一応、正しく解けまして一安心。解いた後に、遠い世界の数式 – 実装例を見てみましたが、うーん..なるほどなあ。正規表現使う方法や、演算子をオープンクラスで置換する方法とか、面白いです。チャレンジされてみてください！

私は以下の本で Ruby を覚えました。メタプログラミングRubyは入門を超える内容で難しめです。

たのしいRuby 第4版

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

メタプログラミングRuby

<< 前の記事 : Getty Images APIでRubyを使って画像検索

ブログ更新の励みになりますので、お役に立てたらぜひシェアをお願いします！

Twitterを使っていますのでフォローお願いたします！ブログの更新情報もつぶやいてます＾＾

Follow @taka222

Follow @takafumir (英語学習用)

遠い世界の数式をRubyで解いてみた

思いついた戦略

書いた回答コード

Leave Your Message! コメントをキャンセル