Solving Verbal Arithmetic (Ruby / Python Recreation)

At the beginning

Please see the following first.

$ 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

No explanation is necessary for those who know it. Verbal arithmetic is a puzzle that is solved by replacing the alphabet with numbers in this way. Here's a quick rule.

• Alphabet types are within 10 (11 or more have no solution)
• Numbers are decimal and the first letter of the word corresponds to something other than 0 (0123 is not allowed)

This verbal solver uses == for the equal sign instead of = (the reason will be explained later). You can use not only addition but also addition, subtraction, multiplication, division and exponentiation **. If there are multiple solutions, the first one found is displayed.

$ 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

Division uses the mathn library to perform strict fractional calculations.

This is based on the Python 3 version of the Verbal Arithmetic Solver in Dive Into Python 3 Chapter 8, and I think this is quite interesting. I made a Ruby version. There is a repository on github.

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

The original repository is as follows.

https://github.com/diveintomark/diveintopython3

It has more source material and is based on the following Python 2 version. This version does not end with the first solution found and searches all solutions.

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

The Ruby version has only one difference from the Python version, and the first character 0 is allowed only when it is alone. The following example has no solution for the Python version, but has a solution for the Ruby version.

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

Source program

The Ruby version of the Verbal Arithmetic Solver is as follows.

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

The source program for Python 3 is on github.

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

If you say "Read Dive In Python 3", the explanation ends, but that's unfriendly, so I'll give you the point. The code corresponds almost 1: 1 to the Python version, so I will focus on the differences in the functions used.

• First, convert the question sentence to uppercase (puzzle.upper () for Python, puzzle.upcase for Ruby)
• Extract words from question sentences (re.findall (...) for Python, puzzle.scan ... for Ruby)
• Extract the alphabet from words
• Word concatenation is ''. Join (words) for Python and words.join for Ruby (word order is different)
• Set generation is set (...) for Python and Set.new ... for Ruby.
• Abnormal termination if there are more than 10 alphabets (Python assert, Ruby ʻabort)
• Collect first characters (first_letters)
• Python is a set literal {...}, Ruby is Set.new ...
• Only for Ruby version, use select to allow the first character when used alone
• Remember the number of leading (0 prohibited) characters (n = ... part)
• 0 Create a new alphabet array with prohibited characters moved to the front
• Python version has sorted_characters = ... part
• Ruby version has sorted_chars = ... part
• Both use join, but be careful of the difference in the word order of join.
• Both complements are processed with the - operator
• After that, generate a permutation and check 100%
• Python uses ʻitertools.permutations (...) `
• Ruby uses Array .permutation (...)
• Both generate and process permutations guess
• Skip if 0 is included in the first n characters
• Replace the alphabet in the question sentence with a number
• Python is puzzle.translate (...)
• Ruby is puzzle.tr ...
• If the result of ʻevalis true, it is a solution and it is returned (this is why==` is used)

The original Python2 version uses Python2's string.maketrans to generate the substitution table to pass to the translate argument. Python 3 has the same functionality, str.maketrans, which is faster and shorter in code.

However, Dive Into Python 3 does not use maketrans, but first generates an array of character codes characters and processes this withdict (zip (characters, quess)). Of course, the author must not be unaware of maketrans, and I think he does this for the purpose of explaining the internal workings.

Ruby, on the other hand, has a tr (from Perl), which is easier to write than Python.

Security precautions

It uses ʻeval` at the heart, so it's a security hole when used in web applications (this is also mentioned in Dive Into Python 3). Please use it for recreation in the local environment.

You can easily find the Web version of the Verbal Arithmetic Solver by searching for it. I found one made in Japan, so I will introduce it.

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

However, as far as I can see, all sites support only addition-only verbal arithmetic. This is also probably for security reasons.

benchmark

The Dive Into Python 3 repository contains simple test code. So I created a Ruby version of the same functionality and ran it instead of the benchmark to compare the execution times (the README in the github repository has the full output of the test).

Overall, the Ruby version tends to be a little faster. Here is another measurement example.

$ 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 version change
$ 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 version change
$ 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

I've tried a few other things, but there is a clear tendency for the Ruby version to be 1.5-2 times faster than the Python 3 version.

Python3 version makes the replacement table with dict (zip (...)) instead of maketrans. I thought this might be the cause, so I changed the Python3 version and made a source that uses maketrans and tried it. However, when measured and compared, the improvement effect was about 2-3%, which was not as much as I expected. It seems that Ruby is faster for this kind of processing.