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.
Try this: It's probably not the best solution.
ReplyDelete(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)))
Commenting for the solution...
ReplyDeleteThe 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.
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.
ReplyDeleteI haven't run it yet, but I'll give it a shot in Gambit-C Scheme after some sleep. Good stuff!
(define (group-similar grouped ol)
ReplyDelete(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 :(
ciju:
ReplyDeleteThanks 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 :/
oops, fixed the bug in this one.
ReplyDelete(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))