Veuillez d'abord lire ce qui suit.
$ 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
Aucune explication n'est nécessaire pour ceux qui la connaissent. Le calcul masqué est un puzzle qui est résolu en remplaçant les alphabets par des nombres de cette manière. Voici une règle rapide.
Ce solveur masqué utilise == au lieu de = pour l'égalité (la raison sera expliquée plus tard). Vous pouvez utiliser non seulement l'addition mais aussi l'addition, la soustraction, la multiplication, la division et la puissance de «**». S'il existe plusieurs solutions, la première trouvée s'affiche.
$ 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
La division utilise la bibliothèque mathn pour effectuer des calculs fractionnaires stricts.
Ceci est basé sur la version Python 3 du solveur de calcul masqué dans Dive Into Python 3 Chapter 8, et je pense que c'est assez intéressant. J'ai fait une version Ruby. Il existe un référentiel sur github.
https://github.com/higuma/ruby-alphametics-solver
Le référentiel d'origine est le suivant.
https://github.com/diveintomark/diveintopython3
Il a plus de matériel source et est basé sur la version Python 2 suivante. Cette version ne se termine pas avec la première solution trouvée et recherche toutes les solutions.
- Alphametics solver (Python recipe): http://code.activestate.com/recipes/576615/
La version Ruby n'a qu'une seule différence par rapport à la version Python, et le premier caractère 0 n'est autorisé que lorsqu'il est seul. L'exemple suivant n'a pas de solution pour la version Python, mais a une solution pour la version Ruby.
$ ruby alphametics.rb 'MALCOLM + X == MALCOLM'
MALCOLM + X == MALCOLM
1234531 + 0 == 1234531
La version Ruby du solveur masqué est la suivante.
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
Le programme source de Python 3 est sur github.
https://github.com/diveintomark/diveintopython3/blob/master/examples/alphametics.py
Si vous dites "Read Dive In Python 3", l'explication se termine, mais ce n'est pas convivial, donc je vais vous donner le point. Le code correspond presque à 1: 1 à la version Python, je vais donc me concentrer sur les différences dans les fonctions utilisées.
puzzle.upper () pour Python, puzzle.upcase pour Ruby)re.findall (...) pour Python, puzzle.scan ... pour Ruby)pour Python et words.join` pour Ruby (l'ordre des mots est différent)set (...) pour Python et Set.new ... pour Ruby. pour Python, ʻabort pour Ruby){...}, Ruby est Set.new ...select pour autoriser le premier caractère lorsqu'il est utilisé seuln = ...)sorted_characters = ...sorted_chars = ...-.permutation (...)guesspuzzle.translate (...)puzzle.tr ...est vrai, c'est une solution et il est retourné (c'est pourquoi==` est utilisé)La version originale de Python2 utilise string.maketrans de Python2 pour générer la table de substitution à passer à l'argument translate. Python 3 a la même fonctionnalité, str.maketrans, qui est de plus en plus rapide dans le code.
Cependant, Dive Into Python 3 n'utilise pas maketrans, mais génère d'abord un tableau de codes de caractères caractères et le traite avec dict (zip (caractères, quess)). Bien sûr, l'auteur ne doit pas ignorer les maketrans, et je pense qu'il le fait dans le but d'expliquer le fonctionnement interne.
Ruby, d'autre part, a un tr (dérivé de Perl), qui est plus facile à écrire que Python.
Il utilise «eval» au cœur, c'est donc une faille de sécurité lorsqu'il est utilisé dans les applications Web (cela est également mentionné dans Dive Into Python 3). Veuillez l'utiliser uniquement pour les loisirs dans l'environnement local.
Vous pouvez facilement trouver la version Web du solveur de calcul masqué en la recherchant. J'en ai trouvé un fabriqué au Japon, je vais donc le présenter.
http://bach.istc.kobe-u.ac.jp/llp/crypt-jp.html
Cependant, d'après ce que j'ai étudié, tous les sites ne prennent en charge que le calcul masqué de l'addition. C'est aussi probablement pour des raisons de sécurité.
Le référentiel Dive Into Python 3 contient du code de test simple. J'ai donc créé une version Ruby de la même fonctionnalité et l'ai exécutée à la place du benchmark pour comparer les temps d'exécution (le README dans le référentiel github a la sortie complète du test).
| Temps d'exécution(Secondes) | |
|---|---|
| Python3 | 5.134 |
| Ruby 1.9.3 | 2.551 |
| Ruby 2.0.0 | 3.839 |
Dans l'ensemble, la version Ruby a tendance à être un peu plus rapide. Voici un autre exemple de mesure.
$ 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 #changement de version de 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 #changement de version de 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
J'ai essayé quelques autres choses, mais la version Ruby a clairement tendance à être 1,5 à 2 fois plus rapide que la version Python 3.
La version Python3 fait la table de remplacement avec dict (zip (...)) au lieu de maketrans. J'ai pensé que cela pourrait en être la cause, alors j'ai changé la version Python3 et créé une source qui utilise maketrans et l'ai essayé. Cependant, mesuré et comparé, l'effet d'amélioration était d'environ 2-3%, ce qui n'était pas autant que je m'y attendais. Il semble que Ruby soit plus rapide pour ce type de traitement.
Recommended Posts