I am having trouble on writing a recursive function in LISP which does the
following:
returns a list which is nested deepest in a given input list. For example:
* (deepest '(1 (2 (3)))) returns (3)
Any help would be appreciated.
Thanks,
Dave
david nathan katcher <········@students.uiuc.edu> writes:
> I am having trouble on writing a recursive function in LISP which does the
> following:
>
> returns a list which is nested deepest in a given input list. For example:
>
> * (deepest '(1 (2 (3)))) returns (3)
What should (deepest '(1 (2 (3)) (4 (5)))) return?
Regards
Henrik
That would return either (3) or (5). It doesn't matter which one.
Dave
On 12 Feb 2003, Henrik Motakef wrote:
> david nathan katcher <········@students.uiuc.edu> writes:
>
> > I am having trouble on writing a recursive function in LISP which does the
> > following:
> >
> > returns a list which is nested deepest in a given input list. For example:
> >
> > * (deepest '(1 (2 (3)))) returns (3)
>
> What should (deepest '(1 (2 (3)) (4 (5)))) return?
>
> Regards
> Henrik
>
david nathan katcher <········@students.uiuc.edu> writes:
> On 12 Feb 2003, Henrik Motakef wrote:
>
> > david nathan katcher <········@students.uiuc.edu> writes:
> >
> > > I am having trouble on writing a recursive function in LISP which does the
> > > following:
> > >
> > > returns a list which is nested deepest in a given input list. For example:
> > >
> > > * (deepest '(1 (2 (3)))) returns (3)
> >
> > What should (deepest '(1 (2 (3)) (4 (5)))) return?
> That would return either (3) or (5). It doesn't matter which
> one.
How about this:
(defun deepest (list)
(labels ((deepest-rec (list depth)
(flet ((helper (best next)
(let ((value (deepest-rec next (1+ depth))))
(cond ((null best) value)
((and value (> (car value) (car best))) value)
((and value (= (car value) (car best)))
(cons (car best) (nconc (cdr best) (cdr value))))
(t best)))))
(cond ((atom list) nil)
((and (atom (car list)) (null (cdr list)))
(list depth list))
(t (or (reduce #'helper list :initial-value nil)
(list depth list)))))))
(let ((result (deepest-rec list 0)))
(values (cdr result) (car result)))))
Regards,
--
Nils G�sche
Ask not for whom the <CONTROL-G> tolls.
PGP key ID #xD26EF2A0
Nils Goesche <···@cartan.de> wrote in message news:<··············@darkstar.cartan>...
> david nathan katcher <········@students.uiuc.edu> writes:
>
> > On 12 Feb 2003, Henrik Motakef wrote:
> >
> > > david nathan katcher <········@students.uiuc.edu> writes:
> > >
> > > > I am having trouble on writing a recursive function in LISP which does the
> > > > following:
> > > >
> > > > returns a list which is nested deepest in a given input list. For example:
> > > >
> > > > * (deepest '(1 (2 (3)))) returns (3)
> > >
> > > What should (deepest '(1 (2 (3)) (4 (5)))) return?
>
> > That would return either (3) or (5). It doesn't matter which
> > one.
How about this:
(defun deepest (tree)
(labels ((do-deepest (tree &optional (current-depth 0))
(cond ((atom tree) 'nil)
((every #'atom tree) (list (list
current-depth tree)))
(t (mapcan (lambda (x)
(do-deepest x (+ current-depth 1))) tree)))))
(cadar (sort (do-deepest tree) #'> :key #'car))))
The trick was when I realized that to be a "deepest" subtree, you had
to be a list. If you have any conses in you, than there is something
deeper than you.
So, do-deepest does the following:
If the tree is actually not a tree, return 'nil. This breaks the
recursion and works great with mapcan.
If the tree is all atoms, making it a leaf, than return a list of it's
depth, and the list itself.
Otherwise, recurse on the tree with mapcan and the depth incremented.
So, we end up with a list of every leaf of the tree and it's depth.
The result is sorted in descending order by the depth and the first
entry's list is returned.
It may not be the most efficient way to tackle the problem, but it's
not that bad. And it IS really short.
Justin Dubs
······@eos.ncsu.edu (Justin Dubs) writes:
> How about this:
>
> (defun deepest (tree)
> (labels ((do-deepest (tree &optional (current-depth 0))
> (cond ((atom tree) 'nil)
> ((every #'atom tree) (list (list
> current-depth tree)))
> (t (mapcan (lambda (x)
> (do-deepest x (+ current-depth 1))) tree)))))
> (cadar (sort (do-deepest tree) #'> :key #'car))))
> It may not be the most efficient way to tackle the problem, but
> it's not that bad. And it IS really short.
Well, if you really only want to return the ``deepest�� list, my
solution could be simplified, too:
(defun deepest (list)
(labels ((deepest-rec (list depth)
(when (consp list)
(or (reduce (lambda (best next)
(let ((value (deepest-rec next (1+ depth))))
(cond ((null best) value)
((and value (> (car value) (car best)))
value)
(t best))))
list :initial-value nil)
(cons depth list)))))
(cdr (deepest-rec list 0))))
However, I think the best one is the one that used
MULTIPLE-VALUE-BIND instead of arbitrary consing (although I
really like my REDUCE *sniff*).
Regards,
--
Nils G�sche
Ask not for whom the <CONTROL-G> tolls.
PGP key ID #xD26EF2A0
"david nathan katcher" <········@students.uiuc.edu> wrote in message
············································@ux13.cso.uiuc.edu...
> I am having trouble on writing a recursive function in LISP which does the
> following:
>
> returns a list which is nested deepest in a given input list. For example:
>
> * (deepest '(1 (2 (3)))) returns (3)
>
> Any help would be appreciated.
>
> Thanks,
> Dave
This function returns two values:
1. A list of all lists that are at the deepest depth in the argument list.
2. The deepest depth, where the argument list is at depth 0.
(defun deepest (list)
(let ((deepest-depth 0)
(deepest-lists (list list))
(current-depth 0))
(labels ((deepest-aux (list)
(dolist (elt list)
(when (listp elt)
(incf current-depth)
(cond ((= current-depth deepest-depth)
(push elt deepest-lists))
((> current-depth deepest-depth)
(setf deepest-depth current-depth
deepest-lists (list elt))))
(deepest-aux elt)
(decf current-depth)))))
(deepest-aux list)
(values (nreverse deepest-lists) deepest-depth))))
(deepest '(1 (2 (3)))) =>
((3))
2
(deepest '(1 (2 (3)) (4 (5)))) =>
((3) (5))
2
Regards,
jag
"david nathan katcher" <········@students.uiuc.edu> ha scritto nel messaggio
············································@ux13.cso.uiuc.edu...
> I am having trouble on writing a recursive function in LISP which does the
> following:
>
> returns a list which is nested deepest in a given input list. For example:
>
> * (deepest '(1 (2 (3)))) returns (3)
>
> Any help would be appreciated.
What should (DEEPEST '(1 2 3)) return?
(defun deepest (l)
(cond ((atom l) (values l 0))
((every #'atom l) (values l 0))
(t (multiple-value-bind (item1 deepth1) (deepest (car l))
(multiple-value-bind (item2 deepth2) (deepest (cdr l))
(if (> (1+ deepth1) deepth2)
(values item1 (1+ deepth1))
(values item2 deepth2)))))))
[3]> (deepest '(1 (2 (3))))
(3) ;
2
[4]> (deepest '(1 2 3))
(1 2 3) ;
0
P.
That is what it is supposed to return. just the list or atom at the
deepest nested spot in the given input list. Thanks for all of your help
everybody.
Dave
On Thu, 13 Feb 2003, Pierpaolo BERNARDI wrote:
>
> "david nathan katcher" <········@students.uiuc.edu> ha scritto nel messaggio
> ············································@ux13.cso.uiuc.edu...
> > I am having trouble on writing a recursive function in LISP which does the
> > following:
> >
> > returns a list which is nested deepest in a given input list. For example:
> >
> > * (deepest '(1 (2 (3)))) returns (3)
> >
> > Any help would be appreciated.
>
> What should (DEEPEST '(1 2 3)) return?
>
> (defun deepest (l)
> (cond ((atom l) (values l 0))
> ((every #'atom l) (values l 0))
> (t (multiple-value-bind (item1 deepth1) (deepest (car l))
> (multiple-value-bind (item2 deepth2) (deepest (cdr l))
> (if (> (1+ deepth1) deepth2)
> (values item1 (1+ deepth1))
> (values item2 deepth2)))))))
>
>
> [3]> (deepest '(1 (2 (3))))
>
> (3) ;
> 2
> [4]> (deepest '(1 2 3))
>
> (1 2 3) ;
> 0
>
>
> P.
>
>
>
On Wed, 12 Feb 2003 21:58:04 -0600, david nathan katcher
<········@students.uiuc.edu> wrote:
I just hope your professor isn't reading this news group. as you have
absolutely broken the academic honesty code.
cheers
cj
>That is what it is supposed to return. just the list or atom at the
>deepest nested spot in the given input list. Thanks for all of your help
>everybody.
>
>Dave
>
>On Thu, 13 Feb 2003, Pierpaolo BERNARDI wrote:
>
>>
>> "david nathan katcher" <········@students.uiuc.edu> ha scritto nel messaggio
>> ············································@ux13.cso.uiuc.edu...
>> > I am having trouble on writing a recursive function in LISP which does the
>> > following:
>> >
>> > returns a list which is nested deepest in a given input list. For example:
>> >
>> > * (deepest '(1 (2 (3)))) returns (3)
>> >
>> > Any help would be appreciated.
>>
>> What should (DEEPEST '(1 2 3)) return?
>>
>> (defun deepest (l)
>> (cond ((atom l) (values l 0))
>> ((every #'atom l) (values l 0))
>> (t (multiple-value-bind (item1 deepth1) (deepest (car l))
>> (multiple-value-bind (item2 deepth2) (deepest (cdr l))
>> (if (> (1+ deepth1) deepth2)
>> (values item1 (1+ deepth1))
>> (values item2 deepth2)))))))
>>
>>
>> [3]> (deepest '(1 (2 (3))))
>>
>> (3) ;
>> 2
>> [4]> (deepest '(1 2 3))
>>
>> (1 2 3) ;
>> 0
>>
>>
>> P.
>>
>>
>>
>
--
===============================================================================
Christopher Jon Miller Drink and dance and laugh and lie
Parallel Systems Engineer Love, the reeling midnight through
For tomorrow we shall die!
(But, alas, we never do.)
-- Dorothy Parker, "The Flaw in Paganism"
===============================================================================
Hi Dave,
> I am having trouble on writing a recursive function in LISP
> which does the following:
>
> returns a list which is nested deepest in a given input list.
> For example:
>
> * (deepest '(1 (2 (3)))) returns (3)
>
> Any help would be appreciated.
This is problem number 3 on your first homework assignment in
CS348. If you want people to help you on your homework, it's good
practice to say upfront that your question is homework. Also, it's
good to post what you have done so far. People are usually quite
willing to give you a helpful nudge or two when you've done this,
but please don't expect people to do your homework for you. Keep
in mind that your instructor could very well be reading this group
too.
Ted
--
Edward O'Connor
·······@soe.ucsd.edu
david nathan katcher <········@students.uiuc.edu> writes:
> I am having trouble on writing a recursive function in LISP which does the
> following:
>
> returns a list which is nested deepest in a given input list. For example:
>
> * (deepest '(1 (2 (3)))) returns (3)
>
> Any help would be appreciated.
>
> Thanks,
> Dave
>
May I propose:
(defun deepest-rec (trees)
(let ((subtrees (delete-if (function atom) trees)))
(cond
((null subtrees) trees)
((every (lambda (item) (every (function atom) item)) subtrees)
(car subtrees))
(t
(deepest (apply 'concatenate 'list subtrees))))))
(defun deepest-iti (trees)
(do* ((trees trees (apply 'concatenate 'list subtrees))
(subtrees (delete-if (function atom) trees)
(delete-if (function atom) trees)))
((or (null subtrees)
(every (lambda (item) (every (function atom) item)) subtrees))
(if (null subtrees) trees (car subtrees)))))
(mapcar (lambda (trees)
(show (deepest-rec trees) (deepest-iti trees)))
'( (1 2 3)
(1 (2 3))
((1 (nil) 4) 5 (6 ))
((1 (nil) (2 (7 8)) 4) 5 (6 ))
((1 (2 3) 4) (5 (7 (8) (9))) (6))
((1 (2 3) 4) (5 (7)) (((((((9))))))) (6)) ))
==> (#1=(1 2 3) #1#)
==> (#1=(2 3) #1#)
==> (#1=(nil) #1#)
==> (#1=(7 8) #1#)
==> (#1=(8) #1#)
==> (#1=(9) #1#)
This is a breadth first search. I think it has the advantages over
the other proposed solutions of being cleaner (simplier) and of having
only one terminal recursive call, which allow us to derecursive it
easily.
Now, here comes the help:
- divide and conquer.
- since we work on trees, it's natural to process it recursively,
but you don't have always to work at the level of the node a do
a node-per-node depth first tree walking.
- basically, to get the depth of a tree, you take it by the root,
you shake it, and the leaf that is the bottomest is the one you
want (yes, it helps to think with images, the alternative is
easier, it's formal maths).
So if you draw a tree, and take a rule, starting from the root you can
keep the rule horizontal and move it downward. Then the last node you
see below the rule is the deepest. That's basically what does my
function. Instead of translating the rule, you could rotate it around
the root, in effect walking thru all the node in a deep first search,
and memorizing the last deepest node you've seen thru the rule. When
you've swiped the whole tree, the last deepest node is the deepest
one.
So, I take the argument as a list of trees. First I divide the atoms
from the subtrees. (If there's only atoms, no subtrees, I return the
given list). If all the subtrees are flat lists, I return the
first. Then I conquer the next level: I recursively or iteratively
call deepest on all the subtrees.
Note that most of the complexity of the function comes from the
asymetrical specifications:
(mapcar (lambda (trees)
(show (deepest-rec trees)))
'( (1 2 3)
((1) (2) (3))
(1 (2 3))))
==> (1 2 3)
==> (1)
==> (2 3)
Why should we return the argument with it's :
*
/ | \
1 2 3
but we should return the first child when it's:
*
/ | \
* * *
| | |
1 2 3
?
--
__Pascal_Bourguignon__ http://www.informatimago.com/
----------------------------------------------------------------------
There is a fault in reality. Do not adjust your minds. -- Salman Rushdie
david nathan katcher <········@students.uiuc.edu> writes:
>
> returns a list which is nested deepest in a given input list.
(defun deepest (object)
(let ((max-cons object) (max-level 0) (level 0))
(labels ((traverse (cons)
(when (> (incf level) max-level)
(setq max-level level) (setq max-cons cons))
(dolist (item cons (decf level))
(when (consp item) (traverse item)))))
(when (consp object) (traverse object))
(values max-cons max-level))))
Yet another version of deepest. Hope it's recursive enough.
--
"Hurry if you still want to see something. Everything is vanishing."
-- Paul C�zanne (1839-1906)