[quiz] [QUIZ #1] Solution by Stuart Sierra
This is very similar to Joseph Abrahamson's solution. The main difference is that I use separate databases for each part of the question: the initial set-up, the operation (addition or subtraction), and the final question. I also got a little silly with the text of the questions. This code can be extended to other operations by adding to the *operations* list and creating another *Xstrings* list, where X is the symbol name of the operation (e.g. +, -, *, ...). My goal was to add enough "noise" to the question that it could not be solved by simple text calculators such as Google. It's still pretty easy to crack this once you know the algorithm -- just scan the question string for numbers, add or subtract them, and you've got a 50% chance of getting the right answer. Code attached. -Stuart ;; CAPTCHA.TEXT.ARITHMETIC ;; version 1, released 3 May 2006 ;; A text-based CAPTCHA (completely automated public Turing test to ;; tell computers and humans apart) in ANSI Common Lisp. ;; This Lisp package has one public function, GENERATE-CAPTCHA, called ;; with no arguments. It returns two strings, the first containing a ;; question and the second containing the answer. The answer will ;; always be in the form of numerical digits. ;; Example: ;; > (generate-captcha) ;; "You started out with three Lisp Machines. You bought ten. In the ;; end, how many did you have?" ;; "13" ;; Copyright 2006 Stuart Sierra ;; This program is free software; you can redistribute it and/or modify ;; it under the terms of the GNU General Public License as published by ;; the Free Software Foundation; either version 2 of the License, or ;; (at your option) any later version. ;; This program is distributed in the hope that it will be useful, ;; but WITHOUT ANY WARRANTY; without even the implied warranty of ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;; GNU General Public License for more details. ;; You should have received a copy of the GNU General Public License ;; along with this program; if not, write to the Free Software ;; Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA ;; CAPTCHA is a trademark of Carnegie Mellon University (in-package :common-lisp-user) ;; package names should be descriptive ;) (defpackage :com.stuartsierra.captcha.text.arithmetic (:nicknames :captcha) (:use :common-lisp) (:export #:generate-captcha)) (in-package :com.stuartsierra.captcha.text.arithmetic) (defvar *min-initial-value* 12) (defvar *max-initial-value* 50) (defvar *min-delta-value* 2) (defvar *max-delta-value* 10) (defvar *operations* (list '+ '-)) (defvar *initial-state-strings* (list "You started out with ~a." "Before, you had ~a." "In the beginning, there were ~a." "Once upon a time, you had ~a." "You were in possession of ~a." "In the vague, distant past, ~a were your pride and joy.")) (defvar *+strings* (list "Beneficent aliens from planet Grog gave you ~a." "Your third cousin Warrl died and you inherited his ~a." "By devious and suble means, you acquired an additional ~a." "You quit your job and got ~a as part of your severance package." "You lost them all in a stock deal, but then you got them all back plus ~a." "You bought ~a.")) (defvar *-strings* (list "When you least expected it, your best friend turned on you and stole ~a." "Just as you were starting to enjoy them, ~a ran away." "But, tragically, ~a went off to that big something-or-other in the sky." "However, ~a didn't feel like sticking around, and left." "After a few years, ~a and you didn't get along any more, so they left." "Not through any fault of your own, you lost ~a.")) (defvar *question-strings* (list "When all is said and done, what did you end up with?" "How many did you have after that?" "By the end of the story, you had how many?" "Years later, when you were reflecting on this whole sordid process, you counted up how many you had. What was the result?" "What number did you have then, after you got over the emotional shock?" "Tell me how many you had when you finished.")) (defvar *nouns* (list "apples" "ponies" "pieces of fruit" "PDP-10s" "laptops" "clones of William Shatner" "Lisp Machines" "ice cream cones" "lollipops" "oranges" "brown paper packages tied up with string" "first-edition Superman comic books" "pairs of stiletto heels")) (defun pick-random (list) (nth (random (length list)) list)) (defun random-range (min max) (+ min (random (- max min)))) (defun format-quantity (number noun) (format nil "~r ~a" number noun)) (defun generate-initial-state-string (initial-value noun) (format nil (pick-random *initial-state-strings*) (format-quantity initial-value noun))) (defun generate-change-string (operation delta-value noun) (format nil (pick-random (symbol-value (find-symbol (concatenate 'string "*" (symbol-name operation) (symbol-name :strings*)) ; to allow for lowercase readers :com.stuartsierra.captcha.text.arithmetic))) (format-quantity delta-value noun))) (defun generate-question (operation initial-value delta-value) (let ((noun (pick-random *nouns*))) (format nil "~a ~a ~a" (generate-initial-state-string initial-value noun) (generate-change-string operation delta-value noun) (pick-random *question-strings*)))) (defun generate-answer (operation initial-value delta-value) (format nil "~d" (funcall operation initial-value delta-value))) (defun generate-captcha () (let ((initial-value (random-range *min-initial-value* *max-initial-value*)) (operation (pick-random *operations*)) (delta-value (random-range *min-delta-value* *max-delta-value*))) (values (generate-question operation initial-value delta-value) (generate-answer operation initial-value delta-value))))
Is it possible to suggest that the CAPTCHA must be "easily" localizable ? By abstarcting the translatable strings for ex ? I would see another problem, namely the structure of the end string. This structure should be also abstracted to a certain point so that languages that do not use a structure similar to English (Japanese for ex) could still make use of the code. How hard would that be to have a "source" file including things like key=value for the localizable strings: initial-state-string_1="something in English" initial-state-string_1="something else in English" that would be parsed for display, and easily translatable to any other language and a "pattern" model that would be parsed to create the "generate- question" code ? (I am asking because I am not a programmer by any stretch of the imagination, I am just here to look at some short code and learn from it, and I don't intend to be disruptive with my questions, but it happens that I am also a translator in real life and that it is one of the reasons I got interested in Lisp) Sincere regards, Jean-Christophe Helary On 2006/05/04, at 0:07, Stuart Sierra wrote:
This is very similar to Joseph Abrahamson's solution. The main difference is that I use separate databases for each part of the question: the initial set-up, the operation (addition or subtraction), and the final question. I also got a little silly with the text of the questions.
This code can be extended to other operations by adding to the *operations* list and creating another *Xstrings* list, where X is the symbol name of the operation (e.g. +, -, *, ...).
My goal was to add enough "noise" to the question that it could not be solved by simple text calculators such as Google. It's still pretty easy to crack this once you know the algorithm -- just scan the question string for numbers, add or subtract them, and you've got a 50% chance of getting the right answer.
Code attached. -Stuart ;; CAPTCHA.TEXT.ARITHMETIC
;; version 1, released 3 May 2006
;; A text-based CAPTCHA (completely automated public Turing test to ;; tell computers and humans apart) in ANSI Common Lisp.
;; This Lisp package has one public function, GENERATE-CAPTCHA, called ;; with no arguments. It returns two strings, the first containing a ;; question and the second containing the answer. The answer will ;; always be in the form of numerical digits.
;; Example:
;; > (generate-captcha) ;; "You started out with three Lisp Machines. You bought ten. In the ;; end, how many did you have?" ;; "13"
;; Copyright 2006 Stuart Sierra
;; This program is free software; you can redistribute it and/or modify ;; it under the terms of the GNU General Public License as published by ;; the Free Software Foundation; either version 2 of the License, or ;; (at your option) any later version.
;; This program is distributed in the hope that it will be useful, ;; but WITHOUT ANY WARRANTY; without even the implied warranty of ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;; GNU General Public License for more details.
;; You should have received a copy of the GNU General Public License ;; along with this program; if not, write to the Free Software ;; Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
;; CAPTCHA is a trademark of Carnegie Mellon University
(in-package :common-lisp-user)
;; package names should be descriptive ;) (defpackage :com.stuartsierra.captcha.text.arithmetic (:nicknames :captcha) (:use :common-lisp) (:export #:generate-captcha))
(in-package :com.stuartsierra.captcha.text.arithmetic)
(defvar *min-initial-value* 12) (defvar *max-initial-value* 50) (defvar *min-delta-value* 2) (defvar *max-delta-value* 10)
(defvar *operations* (list '+ '-))
(defvar *initial-state-strings* (list "You started out with ~a." "Before, you had ~a." "In the beginning, there were ~a." "Once upon a time, you had ~a." "You were in possession of ~a." "In the vague, distant past, ~a were your pride and joy."))
(defvar *+strings* (list "Beneficent aliens from planet Grog gave you ~a." "Your third cousin Warrl died and you inherited his ~a." "By devious and suble means, you acquired an additional ~a." "You quit your job and got ~a as part of your severance package." "You lost them all in a stock deal, but then you got them all back plus ~a." "You bought ~a."))
(defvar *-strings* (list "When you least expected it, your best friend turned on you and stole ~a." "Just as you were starting to enjoy them, ~a ran away." "But, tragically, ~a went off to that big something-or-other in the sky." "However, ~a didn't feel like sticking around, and left." "After a few years, ~a and you didn't get along any more, so they left." "Not through any fault of your own, you lost ~a."))
(defvar *question-strings* (list "When all is said and done, what did you end up with?" "How many did you have after that?" "By the end of the story, you had how many?" "Years later, when you were reflecting on this whole sordid process, you counted up how many you had. What was the result?" "What number did you have then, after you got over the emotional shock?" "Tell me how many you had when you finished."))
(defvar *nouns* (list "apples" "ponies" "pieces of fruit" "PDP-10s" "laptops" "clones of William Shatner" "Lisp Machines" "ice cream cones" "lollipops" "oranges" "brown paper packages tied up with string" "first-edition Superman comic books" "pairs of stiletto heels"))
(defun pick-random (list) (nth (random (length list)) list))
(defun random-range (min max) (+ min (random (- max min))))
(defun format-quantity (number noun) (format nil "~r ~a" number noun))
(defun generate-initial-state-string (initial-value noun) (format nil (pick-random *initial-state-strings*) (format-quantity initial-value noun)))
(defun generate-change-string (operation delta-value noun) (format nil (pick-random (symbol-value (find-symbol (concatenate 'string "*" (symbol-name operation) (symbol-name :strings*)) ; to allow for lowercase readers :com.stuartsierra.captcha.text.arithmetic))) (format-quantity delta-value noun)))
(defun generate-question (operation initial-value delta-value) (let ((noun (pick-random *nouns*))) (format nil "~a ~a ~a" (generate-initial-state-string initial-value noun) (generate-change-string operation delta-value noun) (pick-random *question-strings*))))
(defun generate-answer (operation initial-value delta-value) (format nil "~d" (funcall operation initial-value delta-value)))
(defun generate-captcha () (let ((initial-value (random-range *min-initial-value* *max- initial-value*)) (operation (pick-random *operations*)) (delta-value (random-range *min-delta-value* *max-delta-value*))) (values (generate-question operation initial-value delta-value) (generate-answer operation initial-value delta-value)))) _______________________________________________ quiz mailing list quiz@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/quiz
How hard would that be to have a "source" file including things like key=value for the localizable strings:
The way this is done in, say, Cocoa is to have a localisation file containing format strings: English: "what is ~S times ~S?" Greeble: "~S dfsiiikkkkkk ~S!" and bind the format strings at runtime after loading the appropriate file. Better still is to allow the order of arguments to change. I can't remember how Cocoa gets around this, but I'm sure it does. The key is to parameterise the output, and make all output conditional on the language. FORMAT is actually a reasonable way to do this, as one can always jump around in the input. -R
On 2006/05/04, at 2:11, Richard Newman wrote:
How hard would that be to have a "source" file including things like key=value for the localizable strings:
The way this is done in, say, Cocoa is to have a localisation file containing format strings:
Well, I don't think thinking in terms of platform specific methods would do the trick. Just making sure that there is a part of the code that is easily understandable as localizable would do I suppose. When I write small scripts for my work, I always take care to separate string values from the code so that eventually, anyone could just take the code, identify the localizable strings, translate them and run the script natively. Also, in the case of Lisp, it looks like there is not "one" way to prepare an app for localization, but that also means that not a lot of people actually have localization issues in mind (by default). They sometimes have to consider the l10n issue, and it may be easier to deal with that in Lisp than in any other language, but it then looks like ad-hoc measures rather that strategies from the ground up. Regards, Jean-Christophe
Jean-Christophe Helary wrote:
Is it possible to suggest that the CAPTCHA must be "easily" localizable ? By abstarcting the translatable strings for ex ? that would be parsed for display, and easily translatable to any other language
Abrahamson and I put our strings into global variables, which is fairly easy to translate. The only problem is making (format "~r") multi-lingual, e.g. (format "~r" 2) => "deux"
and a "pattern" model that would be parsed to create the "generate- question" code ?
That's a bit trickier, especially when you get into issues of word order. FORMAT is pretty good at this, but I don't think you can change the order of the arguments, at least not without some ugly hacks.
I am also a translator in real life and that it is one of the reasons I got interested in Lisp)
See also CL-I10L at http://common-lisp.net/project/cl-l10n/ -Stuart
Stuart Sierra writes:
Jean-Christophe Helary wrote:
Is it possible to suggest that the CAPTCHA must be "easily" localizable ? By abstarcting the translatable strings for ex ? that would be parsed for display, and easily translatable to any other language
Abrahamson and I put our strings into global variables, which is fairly easy to translate. The only problem is making (format "~r") multi-lingual, e.g. (format "~r" 2) => "deux"
It cannot and it must not. Not until there's a new CL standard at least. But within the current standard, you can write: (format t "~/localization:format-number-in-french/" 2) ;; or: (format t "~V/localization:format-number-language/" (localization:language-index :french) 2)
and a "pattern" model that would be parsed to create the "generate- question" code ?
That's a bit trickier, especially when you get into issues of word order. FORMAT is pretty good at this, but I don't think you can change the order of the arguments, at least not without some ugly hacks.
And you don't need, since FORMAT is pretty good at skipping around the argument list.
I am also a translator in real life and that it is one of the reasons I got interested in Lisp)
See also CL-I10L at http://common-lisp.net/project/cl-l10n/
-Stuart
-- __Pascal Bourguignon__ http://www.informatimago.com/ THIS IS A 100% MATTER PRODUCT: In the unlikely event that this merchandise should contact antimatter in any form, a catastrophic explosion will result.
participants (4)
-
Jean-Christophe Helary -
Pascal Bourguignon -
Richard Newman -
Stuart Sierra