Bitte sehen Sie zuerst das Folgende.
$ 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
Für diejenigen, die es wissen, ist keine Erklärung erforderlich. Die maskierte Berechnung ist ein Rätsel, das gelöst wird, indem auf diese Weise Alphabete durch Zahlen ersetzt werden. Hier ist eine kurze Regel.
Dieser maskierte Löser verwendet für die Gleichheit "==" anstelle von "=" (der Grund wird später erläutert). Sie können nicht nur Addition, sondern auch Addition, Subtraktion, Multiplikation, Division und Potenz von ** verwenden. Wenn es mehrere Lösungen gibt, wird die erste gefundene angezeigt.
$ 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
Beim Teilen werden mithilfe der Mathn-Bibliothek strenge Bruchberechnungen durchgeführt.
Dies basiert auf der Python 3-Version des maskierten Berechnungslösers in Dive Into Python 3 Kapitel 8, und ich denke, dass dies ziemlich interessant ist. Ich habe eine Ruby-Version gemacht. Es gibt ein Repository auf Github.
https://github.com/higuma/ruby-alphametics-solver
Das ursprüngliche Repository lautet wie folgt.
https://github.com/diveintomark/diveintopython3
Es enthält mehr Quellmaterial und basiert auf der folgenden Python 2-Version. Diese Version endet nicht mit der ersten gefundenen Lösung und durchsucht alle Lösungen.
- Alphametics solver (Python recipe): http://code.activestate.com/recipes/576615/
Die Ruby-Version hat nur einen Unterschied zur Python-Version, und das erste Zeichen 0 ist nur zulässig, wenn es alleine ist. Das folgende Beispiel enthält keine Lösung für die Python-Version, jedoch eine Lösung für die Ruby-Version.
$ ruby alphametics.rb 'MALCOLM + X == MALCOLM'
MALCOLM + X == MALCOLM
1234531 + 0 == 1234531
Die Ruby-Version des maskierten Lösers lautet wie folgt.
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
Das Quellprogramm für Python 3 ist auf Github.
https://github.com/diveintomark/diveintopython3/blob/master/examples/alphametics.py
Wenn Sie "Read Dive In Python 3" sagen, endet die Erklärung, aber das ist unfreundlich, also gebe ich Ihnen den Punkt. Der Code entspricht fast 1: 1 der Python-Version, daher werde ich mich auf die Unterschiede in den verwendeten Funktionen konzentrieren.
puzzle.upper () für Python, puzzle.upcase für Ruby)re.findall (...) für Python, puzzle.scan ... für Ruby)select, um das erste Zeichen zuzulassen, wenn es alleine verwendet wirdn = ... Teil)sorted_characters = ... Teilsorted_chars = ... Teil- verarbeitet.permutation (...)puzzle.translate (...)puzzle.tr ...Die ursprüngliche Python2-Version verwendet Python2s "string.maketrans", um die Substitutionstabelle zu generieren, die an das translate-Argument übergeben wird. Python 3 hat die gleiche Funktionalität, "str.maketrans", die im Code immer schneller ist.
Dive Into Python 3 verwendet jedoch keine Maketrans, sondern generiert zunächst ein Zeichencode-Array "Zeichen" und verarbeitet dieses mit "dict (zip (Zeichen, Quess))". Natürlich darf der Autor Maketrans nicht übersehen, und ich denke, er tut dies, um die internen Abläufe zu erklären.
Ruby hingegen hat ein "tr" (abgeleitet von Perl), das einfacher zu schreiben ist als Python.
Da wir im Herzen "eval" verwenden, ist dies eine Sicherheitslücke, wenn es in Webanwendungen verwendet wird (dies wird auch in Dive Into Python 3 erwähnt). Bitte verwenden Sie es nur zur Erholung in der Umgebung.
Sie können die Webversion des maskierten Lösers leicht finden, indem Sie danach suchen. Ich habe eine in Japan hergestellt gefunden, daher werde ich sie vorstellen.
http://bach.istc.kobe-u.ac.jp/llp/crypt-jp.html
Soweit ich untersucht habe, unterstützen jedoch alle Websites nur die maskierte Berechnung der Addition. Dies ist wahrscheinlich auch aus Sicherheitsgründen.
Das Dive Into Python 3-Repository enthält einfachen Testcode. Also habe ich eine Ruby-Version mit derselben Funktionalität erstellt und sie anstelle des Benchmarks ausgeführt, um die Ausführungszeiten zu vergleichen (die README-Datei im Github-Repository enthält die vollständige Ausgabe des Tests).
| Ausführungszeit(Sekunden) | |
|---|---|
| Python3 | 5.134 |
| Ruby 1.9.3 | 2.551 |
| Ruby 2.0.0 | 3.839 |
Insgesamt ist die Ruby-Version tendenziell etwas schneller. Hier ist ein weiteres Messbeispiel.
$ 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 #Änderung der Ruby-Version
$ 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 #Änderung der Ruby-Version
$ 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
Ich habe ein paar andere Dinge ausprobiert, aber es gibt eine klare Tendenz, dass die Ruby-Version 1,5 bis 2 Mal schneller ist als die Python 3-Version.
Die Python3-Version erstellt die Ersatztabelle mit dict (zip (...)) anstelle von maketrans. Ich dachte, dies könnte die Ursache sein, also änderte ich die Python3-Version und erstellte eine Quelle, die Maketrans verwendet, und versuchte es. Beim Messen und Vergleichen betrug der Verbesserungseffekt jedoch etwa 2-3%, was nicht so viel war, wie ich erwartet hatte. Es scheint, dass Ruby für diese Art der Verarbeitung schneller ist.
Recommended Posts