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.

6 comments:

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

    ReplyDelete
  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.

    ReplyDelete
  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!

    ReplyDelete
  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 :(

    ReplyDelete
  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 :/

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

    ReplyDelete