覆面算を解く(Ruby/Pythonレクリエーション)

始めに

まずは次をご覧ください。

$ ruby alphametics.rb 'SEND + MORE == MONEY'
SEND + MORE == MONEY
9567 + 1085 == 10652
$ ruby alphametics.rb 'DO + YOU + FEEL == LUCKY'
DO + YOU + FEEL == LUCKY
57 + 870 + 9441 == 10368

ご存知の方には説明不要でしょう。このようにアルファベットを数字に置換して解くパズルが覆面算です。ルールを簡単に示します。

• アルファベットの種類は10以内(11以上は解なし)
• 数は10進で、単語の最初の文字は0以外に対応する(0123はだめ)

この覆面算ソルバは等号に=ではなく==を使います(理由は後で説明します)。足し算だけでなく加減乗除すべてとべき乗の**が使えます。解が複数ある場合は最初に見つかったものを表示します。

$ ruby alphametics.rb 'NORTH / SOUTH == EAST / WEST'
NORTH / SOUTH == EAST / WEST
51304 / 61904 == 7260 / 8760
$ ruby alphametics.rb 'PI * R ** 2 == AREA'
PI * R ** 2 == AREA
96 * 7 ** 2 == 4704

除算はmathnライブラリを用いて厳密な分数計算を行います。

これはDive Into Python 3の8章にあるPython3版の覆面算ソルバが元で、これはなかなか面白いと思いRuby版を作ってみました。githubにリポジトリがあります。

https://github.com/higuma/ruby-alphametics-solver

原著のレポジトリは次の通りです。

https://github.com/diveintomark/diveintopython3

これにはさらに元ネタがあり、次のPython 2版をベースにしています。このバージョンは最初に見つかった解で終了せず全ての解を検索します。

• Alphametics solver (Python recipe): http://code.activestate.com/recipes/576615/

なおRuby版はPython版と一つだけ違いがあり、先頭文字の0は単独の場合に限り許可します。次の例はPython版は解なしですが、Ruby版は解を持ちます。

$ ruby alphametics.rb 'MALCOLM + X == MALCOLM'
MALCOLM + X == MALCOLM
1234531 + 0 == 1234531

ソースプログラム

Ruby版覆面算ソルバは次の通りです。

alphametics.rb

require 'set'
require 'mathn'

module Alphametics
  def solve(puzzle)
    puzzle = puzzle.upcase
    words = puzzle.scan /[A-Z]+/
    chars = Set.new words.join.each_char
    abort 'Too many letters' if chars.size > 10
    first_chars = Set.new words.select {|w| w.size > 1 }.map {|w| w[0] }
    n = first_chars.size
    sorted_chars = first_chars.to_a.join + (chars - first_chars).to_a.join
    %w[0 1 2 3 4 5 6 7 8 9].permutation(chars.size).each do |guess|
      next if guess[0, n].member? '0'
      expr = puzzle.tr sorted_chars, guess.join
      return expr if eval expr
    end
    return
  end
end

if __FILE__ == $PROGRAM_NAME
  include Alphametics
  ARGV.each do |arg|
    puts arg
    solution = solve arg
    puts solution if solution
  end
end

Python3版のソースプログラムはgithubにあります。

https://github.com/diveintomark/diveintopython3/blob/master/examples/alphametics.py

「Dive In Python3をお読み下さい」と言えば説明が終わってしまいますが、それでは不親切なので要点を示します。Python版とほぼ1:1にコードが対応していますので、使用している関数の違いに焦点を当てて説明します。

• まず問題文を大文字に変換(Pythonはpuzzle.upper()、Rubyはpuzzle.upcase)
• 問題文から単語を取り出す(Pythonはre.findall(...)、Rubyはpuzzle.scan ...)
• 単語からアルファベットを抽出
  • 単語の連結はPythonは''.join(words)、Rubyはwords.join(語順が異なる)
  • 集合の生成はPythonはset(...)、RubyはSet.new ...
• アルファベットが10種類より多い場合は異常終了(Pythonはassert、Rubyはabort)
• 先頭文字を収集(first_letters)
  • Pythonは集合リテラル{...}、RubyはSet.new ...
  • Ruby版のみselectを使って単独の場合の先頭文字を許可
• 先頭(0禁止)文字の個数を記憶(n = ...の部分)
• 0禁止文字を手前に移動した新しいアルファベット配列を作成
  • Python版はsorted_characters = ...の部分
  • Ruby版はsorted_chars = ...の部分
  • 両者ともjoinを使うが、こちらもjoinの語順の違いに注意
  • 差集合はどちらも-演算子で処理
• 後は順列を生成して全数検査
  • Pythonはitertools.permutations(...)を使う
  • RubyはArrayの.permutation(...)を使う
  • どちらも順列guessを生成して処理
  • 先頭のn文字までに0が含まれていればスキップ
  • 問題文のアルファベットを数字に置換
    • Pythonはpuzzle.translate(...)
    • Rubyはpuzzle.tr ...
  • evalした結果が真であれば解なのでそれを返す(==を使うのはこのため)

元のPython2版はtranslateの引数に渡す置換テーブルの生成にPython2のstring.maketransを使っています。Python3には同機能のstr.maketransがあり、これを使った方が高速かつコードも短くなります。

しかしDive Into Python 3ではmaketransを使わず、まず最初に文字コードの配列charactersを生成し、これをdict(zip(characters, quess))で処理しています。もちろん著者がmaketransを知らないはずはなく、内部動作を説明する目的でこうしているのだと思います。

一方Rubyには(Perl由来の)trがあり、この部分に関してはPythonより楽に記述できます。

セキュリティ上の注意

心臓部にevalを使っていますから、Webアプリケーションに用いるとセキュリティホールになってします(これはDive Into Python 3にも書いてあります)。あくまでローカル環境でのレクリエーション用としてご利用下さい。

なおWeb版覆面算ソルバは探せば割と簡単に見つかります。日本製をひとつ見つけましたので紹介します。

http://bach.istc.kobe-u.ac.jp/llp/crypt-jp.html

ただし調べた限りではどのサイトも足し算のみの覆面算にしか対応していません。これもおそらくセキュリティ上の理由によるものでしょう。

ベンチマーク

Dive Into Python 3のリポジトリには簡単なテストコードが含まれています。そこで同機能のRuby版を作成してベンチマークの代わりに実行して実行時間を比較しました(githubリポジトリのREADMEにテストの全出力があります)。

	実行時間(秒)
Python3	5.134
Ruby 1.9.3	2.551
Ruby 2.0.0	3.839

全体的にRuby版の方がやや高速に処理できる傾向があります。別の測定例を示します。

$ time python3 alphametics.py 'EARTH + AIR + FIRE + WATER == NATURE'
EARTH + AIR + FIRE + WATER == NATURE
67432 + 704 + 8046 + 97364 == 173546

real    0m35.305s
user    0m35.194s
sys     0m0.024s
$ rbenv local 1.9.3-p448        # rubyバージョン変更
$ time ruby alphametics.rb 'EARTH + AIR + FIRE + WATER == NATURE'
EARTH + AIR + FIRE + WATER == NATURE
67432 + 704 + 8046 + 97364 == 173546

real    0m20.051s
user    0m19.921s
sys     0m0.040s
$ rbenv local 2.0.0-p247        # rubyバージョン変更
$ time ruby alphametics.rb 'EARTH + AIR + FIRE + WATER == NATURE'
EARTH + AIR + FIRE + WATER == NATURE
67432 + 704 + 8046 + 97364 == 173546

real    0m24.925s
user    0m24.834s
sys     0m0.032s

この他にもいくつか試してみましたが、Ruby版の方がPython3版の1.5-2倍程度高速という明確な傾向があります。

Python3版は置換テーブルをmaketransではなくdict(zip(...))で作っています。これが原因かも知れないと考え、Python3版を変更してmaketransを使うソースも作って試してみました。しかし計測して比較したところ改善効果は2-3%程度で思ったほどではありません。この種の処理に限ってはRubyの方が高速と結論していいようです。