Once again I am late to the party. Cedric posted a coding challenge on his blog. It looks like Crazy Bob took the prize for most creative (and fastest) implementation. I would like to think that I could have come up with a similar solution, but then again, I also like to think that I could look like Schwarzenegger if I ever started working out.
However, Cedric posted a follow up, “Port Bob's code to your language.” Bob’s code was in Java. However, I am a Java programmer, so that sort of rules out a port. But I was able to make a few performance enhancements. Instead of a doubly linked list, I used a singly linked list and thus was able to prevent a few unnecessary assignments and eliminate a few checks. In addition, once the max has been found, I use a Throwable to unwind the stack. On my Intel MacBook, I see performance enhancements of 10-20%. The code can be found here: ModifiedBeustSequence. Or for the comparison, see here: CompareBeustSequence.
But sticking to the assignment, I did do a straight port of my modified version into Common Lisp, which I have been toying with lately (The port can be found here: beust.lisp). I’m sure that any respectable Lisp programmer could come up with a much more Lisp-like solution. If you go to the trouble, I would love to see it.
I believe there is a missing argument in the lisp example at line 11, map-beust-sequence expects a function and a max.
Also, what lisp implementation was this tested on? The recursion blows the stack on SBCL for even small values of max.
rl-oid
November 20, 2008 5:17 PMMy apologies. I should have included a usage example. The function that MAP-BEUST-SEQUENCE expects is intended to respond to the next number in the sequence (eg. print it out or set to some variable). Here is an example that will count the entire base 10 sequence and output the largest number.
(defparameter *x* 0)
(map-beust-sequence
(lambda (x) (setf *x* x))
10000000000)
(format t "~d" *x*)
TECHHEAD
December 1, 2008 6:23 PM