多重ループを避ける方法（深さ優先探索）【Rubyで覆面算】

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秒

C言語はRubyより実に129.5倍高速でした。

参考

• 深さ優先探索アルゴリズムを実装 部分和問題を解く | 404 motivation not found