Number of levels in a tree

Discussion of Common Lisp
methusala
Posts: 35
Joined: Fri Oct 03, 2008 6:35 pm

Re: Number of levels in a tree

Post by methusala » Tue Nov 10, 2009 12:50 pm

Congratulations on a valiant attempt that is almost there. Here are some observations:

CL-USER> (nivel '((a) b c) 0)
; Evaluation aborted.
CL-USER>
-returned 'b is not of type list'

CL-USER> (nivel '((a) (b) (c)) 0)
1
CL-USER>
-function requires all root level leaves to be lists.

CL-USER> (nivel '((a) (b (d)) (c)) 0)
2
-works for this particular tree

CL-USER> (nivel '((a) ((b) d) (c)) 0)
; Evaluation aborted.
'd is not of type list'

CL-USER> (nivel '((a (d)) (b) (c)) 0)
1
CL-USER>
-mises d sub-branch of first root leaf a


Here is the code I wrote, which is made a little different by using if, progn and listp instead of cond and atom; is also messy and probably has more code than needed, but it works:

Code: Select all

(defun levelnum(x)
       (+ 0
       (if (atom x) 0
       (progn
       (+
(if                   
       (>
 (if (not (null (cdr x))) (+ 0 (levelnum (cdr x)))0)
(if (listp (car x))  (+ 1 (levelnum (car x )))0))
 (if (not (null (cdr x))) (+ 0 (levelnum (cdr x)))0)
(if (listp (car x))  (+ 1 (levelnum (car x ))) 0)))))))     

CL-USER> (levelnum '((a) b c) )
1

CL-USER> (levelnum '((a) (b) (c)))
1

CL-USER> (levelnum '((a) (b (d)) (c)) 0)
2

CL-USER> (levelnum '((a) ((b) d) (c)) )
2

CL-USER> (levelnum '((a (d)) (b) (c)) )
2
CL-USER>

Also, look at these comparisons:

CL-USER> (levelnum '((a) (b) (c) (d (e))))
2
CL-USER> (nivel '((a) (b) (c) (d (e))) 0)
1



CL-USER> (levelnum '((a) ((k (o (r))) (d) ) (c (n))) )
4
CL-USER> (nivel '((a) ((k (o (r))) (d) ) (c (n))) 0)
2

Do you see the differences in the code that caused these result differences?

Minato
Posts: 8
Joined: Mon Nov 09, 2009 7:06 am

Re: Number of levels in a tree

Post by Minato » Wed Nov 11, 2009 1:28 am

yep,understood,thx

Minato
Posts: 8
Joined: Mon Nov 09, 2009 7:06 am

Re: Number of levels in a tree

Post by Minato » Wed Nov 11, 2009 4:59 am

what about a function to return the maximum value of all the numerical atoms of a list, at any level,without using set functions,could anyone give me some hints?

methusala
Posts: 35
Joined: Fri Oct 03, 2008 6:35 pm

Re: Number of levels in a tree

Post by methusala » Wed Nov 11, 2009 7:17 am

Look at the levelnum code and think about how to change it.

Minato
Posts: 8
Joined: Mon Nov 09, 2009 7:06 am

Re: Number of levels in a tree

Post by Minato » Thu Nov 12, 2009 8:46 am

never mind,i did it,thanks again

Harleqin
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Re: Number of levels in a tree

Post by Harleqin » Thu Nov 19, 2009 3:44 am

Minato wrote:this is my code:

Code: Select all

(defun nivel (l k)
  (cond
    ((null (cdr l)) k)
    ((> (nivel (cadr l) (+ k 1))
        (nivel (caddr l) (+ k 1)))
     (nivel (cadr l) (+ k 1)))
    (t (nivel (caddr l) (+ k 1)))))
Formatted. You can use

Code: Select all

 tags for that.
"Just throw more hardware at it" is the root of all evil.
Svante

Post Reply