## 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)))  main-list))`

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. Anonymous23/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. Anonymous25/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)
(cond
((null? ol) '())
((= (car grouped) (car ol))
(group-similar
(cons (car ol) grouped)
(cdr ol)))
(else
(cons grouped
(group-similar
(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)
(cond
((null? ol) (list grouped))    ; change here
((= (car grouped) (car ol))
(group-similar
(cons (car ol) grouped)
(cdr ol)))
(else
(cons grouped
(group-similar
(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))