Tuesday, May 20, 2008

Neophyte/Unoptimized version of Euler Number 42 in Common Lisp

;; Author: Berlin Brown <berlin dot brown @ gmail.com>
;; Overview: Euler Example Number 42 (neophyte version)
;; Target Environment: Common Lisp -> Clisp/Sbcl
;; Date: 5/19/2008
;; --------------
;; The nth term of the sequence of triangle numbers is given
;; by, tn = 0.5 * n * (n+1); so the first ten triangle numbers are:
;; 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
;; By converting each letter in a word to a number corresponding to
;; its alphabetical position and adding these values we form a word value.
;; For example, the word
;; value for SKY is 19 + 11 + 25 = 55 = t10. If the word value
;; is a triangle number then we shall call the word a triangle word.
;; Using words.txt (right click and 'Save Link/Target As...'),
;; a 16K text file containing nearly two-thousand common English words,
;; how many are triangle words?
;; References:
;; [1] http://www.lispworks.com/documentation/HyperSpec/Front/X_Master.htm
;; [2] http://www.unixuser.org/~euske/doc/cl/loop.html
;; [3] http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/node154.html
;; [4] http://cl-cookbook.sourceforge.net/strings.html

(defconstant *max-tri-n* 30)

(defun split (string delim)
"Returns a list of substrings of string
divided by ONE space each.
Note: Two consecutive spaces will be seen as
if there were an empty string between them. E.g. #\Space"

(loop for i = 0 then (1+ j)
as j = (position delim string :start i)
collect (subseq string i j)
while j))
(defun triangle-num (n)
" (0.5 * n * (n + 1))"
(loop for i from 1 to n
collect (floor (* 0.5 (* i (1+ i))))))

(defun str-triangle (tri str)
"Determine if a string is a triangle number"
(if (member (loop for i across str
sum (- (char-code i) 64)) tri)
1 0))
(defun euler-items (items)
(loop for str in items
sum (str-triangle (triangle-num *max-tri-n*)
(subseq str 1 (1- (length str))))))
(defun euler-line (line)
(print (euler-items (split line #\Comma))))

(defun read-words ()
(with-open-file (stream "./words.txt")
(do ((line (read-line stream nil)
(read-line stream nil)))
((null line))
(euler-line line))))
(defun main ()
" Euler problem number 42"
(format t "INFO: Running Project Euler~%")
(time (read-words))
(format t "~%INFO: Done~%"))


Rainer said...

str-triangle should just return the value of the call to member.

In euler-items use COUNT instead of SUM then.

In euler-items you are computing the triangle-numbers for each word. Either you compute that list once and pass it to euler-items, or you memoize the result of triangle-num. If you want to test of membership in a set, then you might want not to create a list, but a hash-table or bit-vector.

Instead of your READ-WORDS, I would write a MAP-FN-OVER-LINES and give it a function that would be called for each line.

I would also not make *max-tri-n* a constant. Use DEFPARAMETER. If you use a global parameter, don't use it directly. Put it in the parameter list of the functions. Like in (defun foo (bar &optional (n *baz*)) ... ). This way you can test the function easier, since it has a defined interface.

Berlin Brown said...

Thanks for the suggestion. I am going to put "Neophyte/Unoptimized" on a couple more examples. Basically, this is my catch-all for saying that I am not as fluent in lisp as I should be (lazy) and will welcome suggestions.

Rainer said...

here is another version of Euler 42 in Lisp...

Berlin Brown said...

cool, thanks for the update.