2023/03/04（土）修整：Problem#solve_dfsとProblem#dfsを高速化
2023/03/06（月）修整：Questionクラスをリファクタリング
目次
多重ループを避ける方法
Rubyで多重ループを避ける方法には、Array#productを使う方法があります。 しかし、この方法では不要な計算をスキップすることができません。
そこでおすすめするのが深さ優先探索(バックトラック法, DFS)です。 この方法では、ループをネストする代わりに再帰関数を呼び出すことで多重ループを避けることができます。
この記事では、覆面算を解くプログラムを例に長大な10重ループを小さな再帰関数に書き換える様子をお見せします。
覆面算とは
覆面算とは数字の代わりにアルファベットが書かれた筆算の式が与えられ、そのアルファベットに当てはまる数字を当てるというものです。 有名な例は、以下になります。
SEND +) MORE -------- MONEY
ちなみに、答えは以下のようになります。
9567 +) 1085 -------- 10652
覆面算の解き方
覆面算では、問題がアルファベットの式で与えられます。 それぞれのアルファベットには、数字の0~9が当てはまります。 これを総当たりで解こうとすると、各アルファベットごとに0~9の数字をそれぞれ試すことになります。 そのため、使われているアルファベットの数だけのループ処理が必要になります。 例題のSEND+MORE=MONEYでは8つのアルファベットが使われているので0~9の繰り返しが8重必要になります。
実際には、異なるアルファベット同士で同じ数字になることはないため、そのときには繰り返しをスキップ(next)できます。
また、最大10重ループ必要ですが8重ループで済むときには、9重ループ目以降はループを飛ばす(break)ことができます。
10重ループと深さ優先探索の比較
まず、覆面算を解くプログラム中の10重ループを抜き出したコードが以下になります。
各ループ中では、特定の条件に合致したらループを飛ばしたり(break)、次の繰り返しにスキップ(next)したりして、ループ数を減らしています。
def solve (0...10).each do |x0| next if @table[0][:head?] and x0 == 0 @table[0][:num] = x0 (0...10).each do |x1| next if x0 == x1 next if @table[1][:head?] and x1 == 0 @table[1][:num] = x1 (0...10).each do |x2| next if [x0, x1].include?(x2) next if @table[2][:head?] and x2 == 0 @table[2][:num] = x2 answer if @table.size == 3 (0...10).each do |x3| break if @table.size == 3 next if [x0, x1, x2].include?(x3) next if @table[3][:head?] and x3 == 0 @table[3][:num] = x3 answer if @table.size == 4 (0...10).each do |x4| break if @table.size == 4 next if [x0, x1, x2, x3].include?(x4) next if @table[4][:head?] and x4 == 0 @table[4][:num] = x4 answer if @table.size == 5 (0...10).each do |x5| break if @table.size == 5 next if [x0, x1, x2, x3, x4].include?(x5) next if @table[5][:head?] and x5 == 0 @table[5][:num] = x5 answer if @table.size == 6 (0...10).each do |x6| break if @table.size == 6 next if [x0, x1, x2, x3, x4, x5].include?(x6) next if @table[6][:head?] and x6 == 0 @table[6][:num] = x6 answer if @table.size == 7 (0...10).each do |x7| break if @table.size == 7 next if [x0, x1, x2, x3, x4, x5, x6].include?(x7) next if @table[7][:head?] and x7 == 0 @table[7][:num] = x7 answer if @table.size == 8 (0...10).each do |x8| break if @table.size == 8 next if [x0, x1, x2, x3, x4, x5, x6, x7].include?(x8) next if @table[8][:head?] and x8 == 0 @table[8][:num] = x8 answer if @table.size == 9 (0...10).each do |x9| break if @table.size == 9 next if [x0, x1, x2, x3, x4, x5, x6, x7, x8].include?(x9) next if @table[9][:head?] and x9 == 0 @table[9][:num] = x9 answer end end end end end end end end end end end
そして、上のコードを深さ優先探索で書き換えたものが以下になります。 66行のコードがわずか17行にまで減りました。
def solve_dfs xs = (0...10).to_a xs.each do |x| dfs(0, x, xs) end end def dfs(i, x, xs) return if @table[i][:head?] and x == 0 @table[i][:num] = x return answer if i + 1 == @table.size ys = xs - [x] ys.each do |y| dfs(i + 1, y, ys) end end
※覆面算を解くプログラムのソースコード全体が知りたい方は、下にソースコードを貼っておくので参考にしてみてください。
dfsでは繰り返さない場合には、早期にreturnしています。
dfsの引数xsには配列を渡しています。配列の中の各値xs[i]は、@table[i][:num]に代入しています。
xsには各繰り返しで試しているアルファベットの候補の数字が入っています。
dfsの最後では、0~9の値でループしてdfs自身を再起的に呼び出しています。
dfsの再帰の様子を下の図にしました。各dfsでは10回dfsを呼び出しており、その呼び出されたdfsの中でも10回呼び出しています。
覆面算を解くプログラムのソースコード全文
class Object def deep_clone Marshal.load(Marshal.dump(self)) end end class Question REG = /([a-z]+)([+*])([a-z]+)=([a-z]+)/ def initialize(question) m = REG.match(question) @expr0 = m[0] @expr1 = m[1] @op = m[2] @expr2 = m[3] @expr3 = m[4] @heads = [@expr1[0], @expr2[0], @expr3[0]].uniq end def to_s @expr0 end def head?(c) @heads.include?(c) end def answer?(table) expr1 = expr_str_to_num(@expr1, table) expr2 = expr_str_to_num(@expr2, table) expr3 = expr_str_to_num(@expr3, table) op_lambda.call(expr1, expr2) == expr3 end def display(table) printf "\n%15d\n", expr_str_to_num(@expr1, table) print "#{@op})" printf "%13d\n", expr_str_to_num(@expr2, table) puts "-----------------" printf "%15d\n", expr_str_to_num(@expr3, table) end private def expr_str_to_num(expr_str, table) expr_str .each_char .map { |c| table .find { |letter| letter[:name] == c } .fetch(:num) } .join("") .to_i end def op_lambda case @op when "+" then ->(x, y) { x + y } when "*" then ->(x, y) { x * y } end end public class << self def valid?(question) max_ten_char = question .each_char .select {|c| /[a-z]/.match?(c) } .uniq .size <= 10 REG.match?(question) and max_ten_char end end end class Problem def initialize(question) @question = Question.new(question) @table = Problem.make_table(@question) @answers = [] end def solve_dfs xs = (0...10).to_a xs.each do |x| dfs(0, x, xs) end end def dfs(i, x, xs) return if @table[i][:head?] and x == 0 @table[i][:num] = x return answer if i + 1 == @table.size ys = xs - [x] ys.each do |y| dfs(i + 1, y, ys) end end def solve (0...10).each do |x0| next if @table[0][:head?] and x0 == 0 @table[0][:num] = x0 (0...10).each do |x1| next if x0 == x1 next if @table[1][:head?] and x1 == 0 @table[1][:num] = x1 (0...10).each do |x2| next if [x0, x1].include?(x2) next if @table[2][:head?] and x2 == 0 @table[2][:num] = x2 answer if @table.size == 3 (0...10).each do |x3| break if @table.size == 3 next if [x0, x1, x2].include?(x3) next if @table[3][:head?] and x3 == 0 @table[3][:num] = x3 answer if @table.size == 4 (0...10).each do |x4| break if @table.size == 4 next if [x0, x1, x2, x3].include?(x4) next if @table[4][:head?] and x4 == 0 @table[4][:num] = x4 answer if @table.size == 5 (0...10).each do |x5| break if @table.size == 5 next if [x0, x1, x2, x3, x4].include?(x5) next if @table[5][:head?] and x5 == 0 @table[5][:num] = x5 answer if @table.size == 6 (0...10).each do |x6| break if @table.size == 6 next if [x0, x1, x2, x3, x4, x5].include?(x6) next if @table[6][:head?] and x6 == 0 @table[6][:num] = x6 answer if @table.size == 7 (0...10).each do |x7| break if @table.size == 7 next if [x0, x1, x2, x3, x4, x5, x6].include?(x7) next if @table[7][:head?] and x7 == 0 @table[7][:num] = x7 answer if @table.size == 8 (0...10).each do |x8| break if @table.size == 8 next if [x0, x1, x2, x3, x4, x5, x6, x7].include?(x8) next if @table[8][:head?] and x8 == 0 @table[8][:num] = x8 answer if @table.size == 9 (0...10).each do |x9| break if @table.size == 9 next if [x0, x1, x2, x3, x4, x5, x6, x7, x8].include?(x9) next if @table[9][:head?] and x9 == 0 @table[9][:num] = x9 answer end end end end end end end end end end end def display_answers @answers.each_with_index do |table, i| printf "\n正解【%2d】\n", i + 1 table.each_with_index do |letter, j| printf "%10c = %d", letter[:name], letter[:num] print "\n" if j % 2 == 1 end @question.display(table) end end private def answer @answers << @table.deep_clone if @question.answer?(@table) end class << self def make_problem loop do puts "↓の例のように文字を入力して下さい。" puts "例：send+more=money" puts "例：send*sp=money" print "> " question = gets.chomp.downcase return Problem.new(question) if Question.valid?(question) end end def make_table(question) question .to_s .each_char .select {|c| /[a-z]/.match?(c) } .uniq .sort .map {|c| {name: c, num: 0, head?: question.head?(c)} } end end end def main loop do p = Problem.make_problem start_time = Time.now # p.solve p.solve_dfs end_time = Time.now p.display_answers printf "\n計測時間：%.1f秒\n", (end_time - start_time) print "もう一度繰り返しますか？はい…（0）／いいえ…（1）：" break if gets.to_i == 1 end end if __FILE__ == $PROGRAM_NAME then main end
おわりに
どうでしたか。深さ優先探索を用いることで多重ループを避ける方法を紹介しました。
ソースコードは、短くなりますが基本的には全探索に近いことをやっているので多重ループの時と計算量は変わりません。
SEND+MORE=MONEYの場合回の繰り返しが必要になります。
計算量を抑えることはできませんが、ソースコードを短くできるので皆さんもぜひ多重ループを避けるときには、深さ優先探索を試してみてください。
ちなみに、この覆面算を解くプログラムは昔C言語で書いたことがあって、それをRubyに移植したものになります。
最後にgcc -O3でコンパイルしたものとの実行速度の比較を下に載せておきます。
| 言語 | 実行時間 |
|---|---|
| C言語 | 0.2秒 |
| Ruby | 25.9秒 |
