Topic: Find the nest level of a list

[Marc'Antonio Alessi]

The only easy iterative approach that comes to my mind is this:
...
IMO converting the whole list to a string and then processing is more frustrating.

Yes but it is not so bad:

Code: [Select]

(setq alist '(((((("A")))((((((((((((((((((((((("B" ("C"))))))))))))))))))))))))("C")))) )
Benchmark.lsp | © 2005 Michael Puckett | All Rights Reserved
Elapsed milliseconds / relative speed for 32768 iteration(s):
    (LEEFOO2 ALIST)...................1375 / 3.89 <fastest>
    (ALE_LIST_NESTEDLEVEL2 ALIST).....2391 / 2.23
    (NESTLVL ALIST)...................5343 / 1 <slowest>

Thanks for the benchmark Ron - I suspected that Lee's second suggestion would be the fastest.

The recursion to Lee's levels is not in my reach, it's really on another planet for me  (and for many others too) 

[Grrr1337]

Yeah Alessi - iterating a string makes sence to be faster.

This is my attempt with it - which ended up a bit more understandable version of Lee's 3rd code (the RJP-Style) :

Code - Auto/Visual Lisp: [Select]

1. (defun nlvls ( L / sL n x isStr nL r )
2.   (and L (listp L) (setq sL (mapcar 'chr (vl-string->list (vl-prin1-to-string L))))
3.     (progn (setq n -1)
4.       (while sL (setq x (car sL)) (setq sL (cdr sL))
5.         (cond
6.           ( (and (= "(" x) (not isStr) )
7.             (setq n (1+ n))
8.           )
9.           ( (and (= ")" x) (not isStr) )
10.             (setq n (1- n))
11.           )
12.           ( (= "\"" x) (setq isStr (if isStr nil T)) ) ; shift the string state
13.         ); cond
14.         (setq nL (cons n nL))
15.       ); while
16.       (setq r (apply 'max nL))
17.     ); progn
18.   ); and
19.   r
20. ); defun nlvls

Code - Auto/Visual Lisp: [Select]

1. _$ (nlvls "string") -> nil
2. _$ (nlvls nil ) -> nil
3. _$ (nlvls '("A" "B" "C") ) -> 0
4. _$ (nlvls '(("A")("B")("C")) ) -> 1
5. _$ (nlvls '(("A")(("B"))("C")) ) -> 2
6. _$ (nlvls '(("A")((((("B")))))("C")) ) -> 5
7. _$ (nlvls '(((("A")))((((((("B")))))))("C")) ) -> 7
8. _$ (nlvls '(((("A")))((((((((((((((((((((((("B" ("C"))))))))))))))))))))))))("C")) ) -> 24
9. _$ (nlvls '(((((("A")))((((((((((((((((((((((("B" ("C"))))))))))))))))))))))))("C")))) ) -> 26
10. _$ (nlvls '(("(1") "2" "3")) -> 1
11. _$ (nlvls '(((1) (2) (3)))) -> 2

And sorry I'm not that good string manipulator.

[Marc'Antonio Alessi]

Yeah Alessi - iterating a string makes sence to be faster.
This is my attempt with it - which ended up a bit more understandable version of Lee's 3rd code (the RJP-Style) :
...
And sorry I'm not that good string manipulator.

(setq alist '(((((("A")))((((((((((((((((((((((("B" ("C"))))))))))))))))))))))))("C")))) ); -> 26
My version works only on one long string:
Comando: (vl-princ-to-string alist)
"((((((A))) (((((((((((((((((((((((B (C)))))))))))))))))))))))) (C))))"


Not with a list of strings:
Comando: (mapcar 'chr (vl-string->list (vl-prin1-to-string alist)))

("(" "(" "(" "(" "(" "(" "\"" "A" "\"" ")" ")" ")" " " "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "(" "\"" "B" "\"" " " "(" "\"" "C" "\"" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" ")" " " "(" "\"" "C" "\"" ")" ")" ")" ")")

Code: [Select]

Benchmark.lsp | © 2005 Michael Puckett | All Rights Reserved

Elapsed milliseconds / relative speed for 32768 iteration(s):
    (LEEFOORJPSTYLE ALIST)............1547 / 1.88 <fastest>
    (ALE_LIST_NESTEDLEVEL2 ALIST).....2406 / 1.21
    (NLVLS ALIST).....................2907 / 1 <slowest>I think that a good solution (not recursive) is to modifiy Lee's LEEFOORJPSTYLE

Code: [Select]

(defun LEEFOORJPSTYLE ( l / n r x )
    (setq l (vl-string->list (vl-prin1-to-string l)) r 0 n -1)
    (while (setq x (car l))
        (cond
            (   (= 34 x) (setq l (member 34 (cdr l))))
            (   (= 40 x) (setq n (1+ n)))
            (   (= 41 x) (setq r (max n r) n (1- n)))
        )
        (setq l (cdr l))
    )
    r
)to skip numbers as it skip strings...

[Marc'Antonio Alessi]

This is a test with Strings and Numbers;
(setq alist '((((((1212121212 12121212 12121212 1 233333333)))((((((((((((((((((((((("BBBBBBBB" (121233333 211212 121212 12121212 12121212 12121212 1233333312))))))))))))))))))))))))("CBBBBBBB")))))

Code: [Select]

Elapsed milliseconds / relative speed for 16384 iteration(s):
    (ALE_LIST_NESTEDLEVEL2 ALIST).....1391 / 2.34 <fastest>
    (LEEFOORJPSTYLE ALIST)............1515 / 2.15
    (NLVLS ALIST).....................3250 / 1 <slowest>

[VovKa]

Code: [Select]

'("a\"(((())))")

[Grrr1337]

Yeah Alessi - iterating a string makes sence to be faster.
This is my attempt with it - which ended up a bit more understandable version of Lee's 3rd code (the RJP-Style) :
...
And sorry I'm not that good string manipulator.

(setq alist '(((((("A")))((((((((((((((((((((((("B" ("C"))))))))))))))))))))))))("C")))) ); -> 26
My version works only on one long string:
Comando: (vl-princ-to-string alist)
"((((((A))) (((((((((((((((((((((((B (C)))))))))))))))))))))))) (C))))"

Yeah, I noticed that.. thats why I apologise.

Code: [Select]

'("a\"(((())))")

Blew my head. 
I guess this shows that processing the whole list as a string would be even more complex.

[Marc'Antonio Alessi]

Code: [Select]

'("a\"(((())))")

Comando: (ALE_List_NestedLevel2  '("a\"(((())))"))
4
Comando: (LEEFOORJPSTYLE  '("a\"(((())))"))
4
Comando: (nlvls  '("a\"(((())))"))
4
Comando: (foo  '("a\"(((())))"))
0
Yes... Lee's Foo is the best, 

[Grrr1337]

Alessi,
The codes on replies #1 #5 #13 aswell the first one in my post should work on this (since they don't process the list as a string).

This mod of the code in my main post should be slightly faster:

Code - Auto/Visual Lisp: [Select]

1. ; _$ (NestedListLevel "string") -> nil
2. ; _$ (NestedListLevel nil ) -> nil
3. ; _$ (NestedListLevel '("A" "B" "C") ) -> 0
4. ; _$ (NestedListLevel '(("A")("B")("C")) ) -> 1
5. ; _$ (NestedListLevel '(("A")(("B"))("C")) ) -> 2
6. ; _$ (NestedListLevel '(("A")((((("B")))))("C")) ) -> 5
7. ; _$ (NestedListLevel '(((("A")))((((((("B")))))))("C")) ) -> 7
8. ; _$ (NestedListLevel '(((("A")))((((((((((((((((((((((("B" ("C"))))))))))))))))))))))))("C")) ) -> 24
9. ; _$ (NestedListLevel '(((((("A")))((((((((((((((((((((((("B" ("C"))))))))))))))))))))))))("C")))) ) -> 26
10. ; _$ (NestedListLevel '(("(1") "2" "3")) -> 1
11. ; _$ (NestedListLevel '(((1) (2) (3)))) -> 2
12. ; _$ (NestedListLevel '("a\"(((())))")) -> 0
13. (defun NestedListLevel ( L / rec )
14.   (defun rec ( L i )
15.     (cond
16.       ( (not L) (list i))
17.       ( (eq 'LIST (type L))
18.         (cond
19.           ( (eq 'LIST (type (car L))) (append (rec (car L) (1+ i)) (rec (cdr L) i)) )
20.           ( (rec (cdr L) i) )
21.         )
22.       )
23.     )
24.   )
25.   (if (and L (listp L)) (apply 'max (rec L 0)) )
26. ); defun NestedListLevel

I assume that Lee's code in Reply #5 is the fastest, but I'm not sure how it compares to the one in Reply #13.
Theoretically the strategy you mentioned would be the fastest, until Vovka pointed out the nested strings problem.

(Sorry not sure how to address you [Mark/Antonio/Alessi])

[VovKa]

I assume that Lee's code in Reply #5 is the fastest, but I'm not sure how it compares to the one in Reply #13.

as to the code in Reply #13

Code: [Select]

(NestLvl '((1 . 2)))

[Grrr1337]

I assume that Lee's code in Reply #5 is the fastest, but I'm not sure how it compares to the one in Reply #13.

as to the code in Reply #13

Code: [Select]

(NestLvl '((1 . 2)))

Unexpected! <duh>

[Marc'Antonio Alessi]

Alessi,
The codes on replies #1 #5 #13 aswell the first one in my post should work on this (since they don't process the list as a string).

This mod of the code in my main post should be slightly faster:
...
I assume that Lee's code in Reply #5 is the fastest, but I'm not sure how it compares to the one in Reply #13.
Theoretically the strategy you mentioned would be the fastest, until Vovka pointed out the nested strings problem.

(Sorry not sure how to address you [Mark/Antonio/Alessi])

For #13 see #23...

Code: [Select]

(setq alist '((((((1212121212 12121212 12121212 1 233333333)((1 . 2)))("a\"(((())))")))((((((((((((((((((((((("BBBBBBBB" (121233333 211212 121212 12121212 12121212 12121212 1233333312))))))))))))))))))))))))("CBBBBBBB"))))
Elapsed milliseconds / relative speed for 32768 iteration(s):
    (FOO#5 ALIST)..................1750 / 1.76 <fastest>
    (FOO#1 ALIST)..................1891 / 1.63
    (NESTEDLISTLEVEL#22 ALIST).....3078 / 1 <slowest>>>> Marco

[Grrr1337]

I thought that #22 would be close to #5, but it seems that append and maybe (apply 'max ...) slows down the process.
Thanks Marco!

[VovKa]

found one in a book https://issuu.com/enelf/docs/lisp1/382
section 3.3 number 2
it's a bit different but looks good

[Grrr1337]

found one in a book https://issuu.com/enelf/docs/lisp1/382
section 3.3 number 2
it's a bit different but looks good

Cool book!
However the function you pointed doesn't work:

Code: [Select]

; глубина = depth
(defun depth (х)
  (cond
    ( (atom x) 1)
    (t (max_ (+ 1 (depth (car x))) (depth (cdr x))) )
  )
)

(defun max_ (х у) ; встроенная функция MAX
  (if (> x y) x y)
)
Returns a value of 1 for all of our performed tests.

[Marc'Antonio Alessi]

Code: [Select]

(defun depth (x)
  (cond
    ( (atom x) 1)
    (t (max_ (+ 1 (depth (car x))) (depth (cdr x))) )
  )
)
(defun max_ (x y)
  (if (> x y) x y)
)

Code: [Select]

Comando: (setq alist '((((((1212121212 12121212 12121212 1 233333333)((1 . 2)))("a\"(((())))")))((((((((((((((((((((((("BBBBBBBB" (121233333 211212 121212 12121212 12121212 12121212 1233333312))))))))))))))))))))))))("CBBBBBBB"))))
((((((1212121212 12121212 12121212 1 233333333) ((1 . 2))) ("a\"(((())))"))) ((((((((((((((((((((((("BBBBBBBB" (121233333 211212 121212 12121212 12121212 12121212 1233333312)))))))))))))))))))))))) ("CBBBBBBB")))
Comando: (FOO#5 ALIST)
25
Comando: (depth AList)
27
Comando: (setq alist '(((((("A")))((((((((((((((((((((((("B" ("C"))))))))))))))))))))))))("C")))) )
(((((("A"))) ((((((((((((((((((((((("B" ("C")))))))))))))))))))))))) ("C"))))
Comando: (FOO#5 ALIST)
26
Comando: (depth AList)
28