January 10, 2007

99 Problems But malloc Ain't One

Joao Meidanis has a list of “Ninety-nine Lisp Problems” that might be a nice way to learn some Lisp ways of thinking.

P10 (*) Run-length encoding of a list.- Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.

Example:

* (encode '(a a a a b c c a a d e e e e))

((4 A) (1 B) (2 C) (2 A) (1 D)(4 E))

[...]

P34 (**) Calculate Euler's totient function phi(m).- Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r < m) that are coprime to m.
Example: m = 10: r = 1,3,7,9; thus phi(m) = 4. Note the special case: phi(1) = 1.

* (totient-phi 10)

4Find out what the value of phi(m) is if m is a prime number. Euler's totient function plays an important role in one of the most widely used public key cryptography methods (RSA). In this exercise you should use the most primitive method to calculate this function (there are smarter ways that we shall discuss later).

The list is based on Werner Hett's Ninety-Nine Prolog Problems (link is to the Wayback Machine version; the original seems to be dead), and so has that Prologian emphasis on logic (and I can't help but think of Joyce's quote, “If Programming 101 classes started with social software rather than math problems and competitive games, more women might discover an unexpected interest”). Joao's Lisp translation is incomplete, with solutions provided for only the first few problems and quite a bit of Prolog phrasing remaining.

I wonder what “Ninety-Nine Unix Problems” would look like. Or “Ninety-Nine Regex Problems” (hold me, I'm scared).

I feel like I'm taking a big risk with the Jay-Z reference, but I'm living dangerously these days.

Posted by jjwiseman at January 10, 2007 02:02 PMComments

Speaking of regex problems: http://www.xkcd.com/c208.html

I read about half of "Mastering Regular Expressions" by Jeffrey Friedl in the past couple months, and yes, I've seen half a dozen nails I decided to hit with that particular hammer. Guilty as charged.

Posted by: Michael H. on January 10, 2007 04:48 PMI believe it is an Ice-T reference, Mr. Wiseman

Posted by: Andy Wingo on January 14, 2007 05:50 AMOh, I do hope this will attract the same fan base that your BeyoncĂ© post did. It is just the sort of thing that I love about the Internet.

Posted by: Coty on January 15, 2007 06:33 AMThat 'encode' function is unexpectedly hard to write. Reasonable, but ugly solution took me almost 30 minutes:

(defmethod encode ((in list))

(labels ((encode (in result &aux (c 0))

(if in

(encode (member-if-not

(lambda (e) (if (eql (car in) e) (incf c))) in)

(cons (list (car in) c) result))

(nreverse result))))

(encode in nil)))

(defmethod encode ((in vector))Posted by: szymon on January 15, 2007 05:11 PM

(loop for pos = 0 then next-pos

for next-pos = (position (aref in pos) in :test-not #'eql :start pos)

collect (list (aref in pos) (- (or next-pos (length in)) pos))

while next-pos))

At first I could have sworn that was young Wiseman in the far left of that photo, but the flickr set seems to discredit this belief.

Posted by: cody on January 19, 2007 12:50 PMPost a comment