Tuesday, June 24, 2008

99 lisp problems. Some are hard!

This much publicised set of 99 Lisp problems (taken from an original set of Prolog problems) seems like a nice step for me to take in learning Lisp as a novice to the language.

I figured the first few would be really easy with a smooth learning curve as the questions get more difficult. Certainly, I didn't expect to spend at least two hours screwing up question 9; an ostensibly straightforward problem requiring you to convert a sequence into a list of sublists, grouped by consecutively equal elements (i.e. (1 4 4 8 1 9 1 1 1 2 2 3) -> ((1) (4 4) (8) (1) (9) (1 1 1) (2 2) (3))).

After trying to solve this one a few different ways, I rejected a recursive approach and simply looped through all the elements, doing dirty stuff:
(defun pack (list)
(let (a main-list)
(dolist (x list)
(if (and (not (null a)) (eq x (car (last a))))
(setf a (append a (list x)))
(if (null a)
(setf a (list x))
(progn (setf main-list (append main-list (list a)))
(setf a (list x))))))
(setf main-list (append main-list (list a)))

I had a quick peek at the solution provided on the site and didn't bother going through it except to note that it was indeed recursive (and not tail-recursive). Partly because some of the identifier names are in Portuguese and partly because it looks similar to the mess I had when I tried to do it recursively; I'm just not comfortable with how lists work yet - I was getting stuff like ((1 (1 (2 3)))) and ((1 (1 (2))) . 3) and all sorts of other crap.
I'm sure I could have done this quicker (and much longer and uglier) in Java, but not figuring it out properly in Lisp is making me feel a bit stupid. Wah.


  1. ratboy66623/8/08 02:46

    Try this: It's probably not the best solution.

    (define (merge e l)
    (cond ((null? l) (list (list e)))
    ((= (caar l) e)
    (cons (cons e (car l)) (cdr l)))
    (else (cons (list e) l))))

    (define (enc l1 l2)
    (cond ((null? l1) l2)
    (else (enc (cdr l1) (merge (car l1) l2)))))

    (define (encode l)
    (reverse (enc l '())))

    (pp (encode '(1 4 4 8 1 9 1 1 1 2 2 3)))

  2. ratboy66625/8/08 03:46

    Commenting for the solution...

    The function encode() creates the RLE list of lists encoding. The new encoding must be held somewhere, so we immediately call a helper function enc(). The first parameter to enc is the remainder to be done, and the second is the built of list-of-lists encoding.

    enc() simply "cdr's" down the first list, merging the built up solution with the new first element, using the merge() function. As a bonus, enc() is then fully tail recursive.

    The merge() function is the "heart" of the routine. It is passed the element, and the list-of-lists built to date. If the list-of-lists is empty, the return is trivially (list (list e)). Otherwise, we look at the first element of the first sublist of the list-of-lists. If it matches, build a sublist one longer, and return the cons of that new list and the remainder of the list-of-lists. The last case (no match) simply adds a new sublist to the front of the list-of-lists.

    Unfortunately, the result is built in the "wrong" order; the encode() function then reverse()s the list-of-lists before returning it.

    I finally had a peek at the questions -- this framework is easy to modify to accommodate. EG. A representation like
    ((5 A) B (2 C)) -- use pair?() to tell what it is, and cadr() to extract the element for testing.

  3. Hi Ratboy, thanks for your comment. Although I'm even less experienced with Scheme than I am with Common Lisp, your solution is much cleaner than mine and nicely tail-recursive too.
    I haven't run it yet, but I'll give it a shot in Gambit-C Scheme after some sleep. Good stuff!

  4. (define (group-similar grouped ol)
       ((null? ol) '())
       ((= (car grouped) (car ol))
         (cons (car ol) grouped)
         (cdr ol)))
        (cons grouped
               (cons (car ol) '())
               (cdr ol))))))

    (group-similar '(1) '(4 4 8 1 9 1 1 1 2 2 3))

    hopefully the code is easy to understand.

    as a side not, is there an easy way to preserve code formatting in blogger comments. i had to put nbsp, lots of it :(

  5. ciju:

    Thanks for that - it's far neater than my solution, but it does fall down on a lot of input:

    > (group-similar '(1) '(1 2 3 3 3 3 3 3 3))
    ((1 1) (2))

    I tried using <pre> but Blogger doesn't like it.. doh :/

  6. oops, fixed the bug in this one.

    (define (group-similar grouped ol)
       ((null? ol) (list grouped))    ; change here
       ((= (car grouped) (car ol))
         (cons (car ol) grouped)
         (cdr ol)))
        (cons grouped
               (cons (car ol) '())
               (cdr ol))))))

    (group-similar '(1) '(1 2 3 3 3 3 3 3 3))

    > ((1 1) (2) (3 3 3 3 3 3 3))