Hi,
I'm trying to teach myself Common Lisp. I've got the following small
program working to solve the Josephus problem (n people in a circle,
go aread killing each mth person - what's the order in which they
die?). The program works, but I'm not really satisfied with it, due
to the duplicate nthcdr and (cadr before-dead) calls. If anyone has
any advice on a better way to write the program using common lisp, I'd
appreciate it.
(defun josephus (n m)
(do* ((lst (make-circ-list n) (cdr before-dead))
(before-dead (nthcdr (- m 2) lst) (nthcdr (- m 2) lst))
(dead-items (list (cadr before-dead))
(append dead-items (list (cadr before-dead)))))
((eq (cdr lst) lst) dead-items)
(setf (cdr before-dead) (cddr before-dead))
))
(defun make-circ-list (n)
(labels
((make-numbered-list (n)
(if (= n 0)
'()
(append (make-numbered-list (- n 1))
(list n))))
(make-circular (lst)
(setf (cdr (last lst)) lst)
lst))
(let ((lst (make-numbered-list n)))
(make-circular lst))))
Thanks,
Dan
"Dan Becker" <·····@yahoo.com> wrote in message ·································@posting.google.com...
> Hi,
>
> I'm trying to teach myself Common Lisp. I've got the following small
> program working to solve the Josephus problem (n people in a circle,
> go aread killing each mth person - what's the order in which they
> die?). The program works, but I'm not really satisfied with it, due
> to the duplicate nthcdr and (cadr before-dead) calls. If anyone has
> any advice on a better way to write the program using common lisp, I'd
> appreciate it.
>
> (defun josephus (n m)
> (do* ((lst (make-circ-list n) (cdr before-dead))
You can use 'list' as a variable name instead of 'lst', it's one of the
advantages of CL. Numerous varients of this problem show up in the online
ACM programming contest, it's a shame they don't allow CL as one of the
languages...
*fiddle, fiddle*
(defun josephus (n m)
(let ((list (loop for x from 1 upto n collect x))
(m-2 (- m 2))
(dead-list '()))
(if (= m 1)
list
(labels ((eliminate (list)
(let ((before-dead (nthcdr m-2 list)))
(push (cadr before-dead) dead-list)
(if (eq (cdr list) list)
(nreverse dead-list)
(eliminate (setf (cdr before-dead)
(cddr before-dead)))))))
(eliminate (setf (cdr (last list)) list))))))
--
Geoff
"Kalle Olavi Niemitalo" <···@iki.fi> wrote in message ···················@Astalo.kon.iki.fi...
> (defun josephus (count steps)
> (let* ((list (loop for x from 1 upto count collect x))
> (before-dead (last list)))
> (setf (cdr before-dead) list)
> (loop repeat count
> do (setq before-dead (nthcdr (- steps 1) before-dead))
> collect (pop (cdr before-dead)))))
Oh, steaming piles of cow-pies! It would have never occurred
to me to use POP. Nicely done, I knew there was a simplifiction
there, I was just to thick to see it. :-(
--
Geoff
Kalle Olavi Niemitalo <···@iki.fi> wrote in message news:<··············@Astalo.kon.iki.fi>...
> (defun josephus (count steps)
> (let* ((list (loop for x from 1 upto count collect x))
> (before-dead (last list)))
> (setf (cdr before-dead) list)
> (loop repeat count
> do (setq before-dead (nthcdr (- steps 1) before-dead))
> collect (pop (cdr before-dead)))))
Interesting. I knew there had to be a better way to make the initial
circular list of numbers. But that call to POP ... so POP is smart
enough to retain the circular nature of the list? I will have to play
with this.
Dan
"Dan Becker" <·····@yahoo.com> wrote in message ································@posting.google.com...
> Kalle Olavi Niemitalo <···@iki.fi> wrote in message news:<··············@Astalo.kon.iki.fi>...
> > (defun josephus (count steps)
> > (let* ((list (loop for x from 1 upto count collect x))
> > (before-dead (last list)))
> > (setf (cdr before-dead) list)
> > (loop repeat count
> > do (setq before-dead (nthcdr (- steps 1) before-dead))
> > collect (pop (cdr before-dead)))))
>
> Interesting. I knew there had to be a better way to make the initial
> circular list of numbers. But that call to POP ... so POP is smart
> enough to retain the circular nature of the list? I will have to play
> with this.
>
POP doesn't have to be smart, think about the place that's getting setf'ed.
I was just too used to thinking about PUSH and POP in terms of a stack to
see the now obvious use in splicing/removing things to/from a list.
--
Geoff
"Geoffrey Summerhayes" <·············@hotmail.com> wrote in message news:<·····················@news20.bellglobal.com>...
>
> POP doesn't have to be smart, think about the place that's getting setf'ed.
> I was just too used to thinking about PUSH and POP in terms of a stack to
> see the now obvious use in splicing/removing things to/from a list.
Yes, once I sat down and thought about it, I see what's happening.
Thanks for the help!
Dan