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)
4

Find 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 PM

(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))

  (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))