Author Topic: Find the nest level of a list  (Read 6887 times)

0 Members and 1 Guest are viewing this topic.

Grrr1337

  • Swamp Rat
  • Posts: 812
Find the nest level of a list
« on: October 18, 2017, 01:31:53 PM »
Hey guys,
Anyone wanna play?  :idea:

The task is to find the "deepest" nesting level of a list:

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

I hope the above example is clear enough.  :rolleyes2:

Heres my attempt with this:
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. (defun NestedListLevel ( L / rec )
  10.   (defun rec ( L i )
  11.     (or i (setq i 0))
  12.     (cond
  13.       ( (not L) (list i))
  14.       ( (and (listp L) (listp (car L))) (append (rec (car L) (1+ i)) (rec (cdr L) i)) )
  15.       ( (listp L) (rec (cdr L) i) )
  16.     )
  17.   )
  18.   (if (and L (listp L)) (apply 'max (rec L nil)) )
  19. ); defun NestedListLevel
IMO my code is a bit sloppy (sorry about that  - haven't done much recursions recently).
(apply ''((a b c)(a b c))
  '(
    (( f L ) (apply 'strcat (f L)))
    (( L ) (if L (cons (chr (car L)) (f (cdr L)))))
    (72 101 108 108 111 32 87 111 114 108 100)
  )
)
vevo.bg

Lee Mac

  • Seagull
  • Posts: 12905
  • London, England
Re: Find the nest level of a list
« Reply #1 on: October 18, 2017, 02:01:47 PM »
Quick one:
Code - Auto/Visual Lisp: [Select]
  1. (defun foo ( lst )
  2.     (apply 'max (mapcar '(lambda ( x ) (if (listp x) (if (< 0 (vl-list-length x)) (+ 1 (foo x)) 1) 0)) lst))
  3. )

ronjonp

  • Needs a day job
  • Posts: 7526
Re: Find the nest level of a list
« Reply #2 on: October 18, 2017, 02:37:52 PM »
Here's mine:
Code - Auto/Visual Lisp: [Select]
  1.  
  2. (defun nestedlistlevel_rjp (l)
  3.   (if (listp l)
  4.     (apply 'max
  5.            (mapcar (function (lambda (x)
  6.                                (if (listp x)
  7.                                  (length (vl-remove-if-not
  8.                                            (function (lambda (y) (= 40 y)))
  9.                                            (vl-string->list (vl-princ-to-string x))
  10.                                          )
  11.                                  )
  12.                                  0
  13.                                )
  14.                              )
  15.                    )
  16.                    l
  17.            )
  18.     )
  19.   ))
« Last Edit: October 19, 2017, 09:25:06 AM by ronjonp »

Windows 11 x64 - AutoCAD /C3D 2023

Custom Build PC

Lee Mac

  • Seagull
  • Posts: 12905
  • London, England
Re: Find the nest level of a list
« Reply #3 on: October 18, 2017, 03:18:17 PM »
Code - Auto/Visual Lisp: [Select]
  1. (nestedlistlevel_rjp '(("(1") "2" "3"))

Code - Auto/Visual Lisp: [Select]
  1. (nestedlistlevel_rjp '(((1) (2) (3))))

:wink:

Grrr1337

  • Swamp Rat
  • Posts: 812
Re: Find the nest level of a list
« Reply #4 on: October 18, 2017, 03:22:04 PM »
Wow Lee, you always keep up with this super-advanced lisp level!
Guess I still have to figure out the mapcar with a recursive function combo.

Ron, interesting technique, but here are some bad news:

Code - Auto/Visual Lisp: [Select]
  1. _$ (NestedListLevel '(((((("A")))((((((((((((((((((((((("B" ("C"))))))))))))))))))))))))("C")))) )
  2. 26
  3. _$ (NESTEDLISTLEVEL_RJP '(((((("A")))((((((((((((((((((((((("B" ("C"))))))))))))))))))))))))("C")))) )
  4. 30
  5. _$ (foo '(((((("A")))((((((((((((((((((((((("B" ("C"))))))))))))))))))))))))("C")))) )
  6. 26
(apply ''((a b c)(a b c))
  '(
    (( f L ) (apply 'strcat (f L)))
    (( L ) (if L (cons (chr (car L)) (f (cdr L)))))
    (72 101 108 108 111 32 87 111 114 108 100)
  )
)
vevo.bg

Lee Mac

  • Seagull
  • Posts: 12905
  • London, England
Re: Find the nest level of a list
« Reply #5 on: October 18, 2017, 03:28:03 PM »
Thanks Grrr1337  :-)

Here's another:
Code - Auto/Visual Lisp: [Select]
  1. (defun foo ( l )
  2.     (cond
  3.         (   (/= 'list (type l)) 0)
  4.         (   (listp (car l)) (max (+ 1 (foo (car l))) (foo (cdr l))))
  5.         (   (foo (cdr l)))
  6.     )
  7. )

Lee Mac

  • Seagull
  • Posts: 12905
  • London, England
Re: Find the nest level of a list
« Reply #6 on: October 18, 2017, 03:47:26 PM »
Another, RJP-style :-)

Code - Auto/Visual Lisp: [Select]
  1. (defun foo ( l / n r x )
  2.     (setq l (vl-string->list (vl-prin1-to-string l)) r 0 n -1)
  3.     (while (setq x (car l))
  4.         (cond
  5.             (   (= 34 x) (setq l (member 34 (cdr l))))
  6.             (   (= 40 x) (setq n (1+ n)))
  7.             (   (= 41 x) (setq r (max n r) n (1- n)))
  8.         )
  9.         (setq l (cdr l))
  10.     )
  11.     r
  12. )

Grrr1337

  • Swamp Rat
  • Posts: 812
Re: Find the nest level of a list
« Reply #7 on: October 18, 2017, 03:49:37 PM »
Lee, the second one is outstanding! :-o
As I understood,
First you dig into the levels and then the recursion 'exits out'
by comparing each pair of lists (where the more nested has a higher priority for the max function [due the sum of the increasing 1+ increment]).

Even if I had the thought just for the idea I would be unable to write it correctly.
Actually now I see that in your both codes you are able to avoid to pass an index variable.
(BTW such complex subfunctions hint themselves about their author, even if its not mentioned)
(apply ''((a b c)(a b c))
  '(
    (( f L ) (apply 'strcat (f L)))
    (( L ) (if L (cons (chr (car L)) (f (cdr L)))))
    (72 101 108 108 111 32 87 111 114 108 100)
  )
)
vevo.bg

Lee Mac

  • Seagull
  • Posts: 12905
  • London, England
Re: Find the nest level of a list
« Reply #8 on: October 18, 2017, 04:12:22 PM »
Lee, the second one is outstanding! :-o
As I understood,
First you dig into the levels and then the recursion 'exits out'
by comparing each pair of lists (where the more nested has a higher priority for the max function [due the sum of the increasing 1+ increment]).

Thank you Grrr1337 - the recursion is perhaps best demonstrated by a trace call:
Code - Auto/Visual Lisp: [Select]
  1. _$ (foo '(("A")((((("B")))))("C")))
  2. 5
Code - Auto/Visual Lisp: [Select]
  1. Entering (FOO (("A") ((((("B"))))) ("C")))
  2.   Entering (FOO ("A"))
  3.     Entering (FOO nil)
  4.     Result:  0
  5.   Result:  0
  6.   Entering (FOO (((((("B"))))) ("C")))
  7.     Entering (FOO ((((("B"))))))
  8.       Entering (FOO (((("B")))))
  9.         Entering (FOO ((("B"))))
  10.           Entering (FOO (("B")))
  11.             Entering (FOO ("B"))
  12.               Entering (FOO nil)
  13.               Result:  0
  14.             Result:  0
  15.             Entering (FOO nil)
  16.             Result:  0
  17.           Result:  1
  18.           Entering (FOO nil)
  19.           Result:  0
  20.         Result:  2
  21.         Entering (FOO nil)
  22.         Result:  0
  23.       Result:  3
  24.       Entering (FOO nil)
  25.       Result:  0
  26.     Result:  4
  27.     Entering (FOO (("C")))
  28.       Entering (FOO ("C"))
  29.         Entering (FOO nil)
  30.         Result:  0
  31.       Result:  0
  32.       Entering (FOO nil)
  33.       Result:  0
  34.     Result:  1
  35.   Result:  5
  36. Result:  5

Even if I had the thought just for the idea I would be unable to write it correctly.
Actually now I see that in your both codes you are able to avoid to pass an index variable.
(BTW such complex subfunctions hint themselves about their author, even if its not mentioned)

That's very kind of you to say, but don't be so down on yourself - your programming abilities have already improved significantly over the last few months since you started participating on the forums, and so with continued study & practice, there's no reason why you can't continue to progress. :-)

ronjonp

  • Needs a day job
  • Posts: 7526
Re: Find the nest level of a list
« Reply #9 on: October 18, 2017, 04:15:03 PM »
Code - Auto/Visual Lisp: [Select]
  1. (nestedlistlevel_rjp '(("(1") "2" "3"))

Code - Auto/Visual Lisp: [Select]
  1. (nestedlistlevel_rjp '(((1) (2) (3))))

 ;)
I figured it was a bust :) .. just a quick one for the data set provided.

Windows 11 x64 - AutoCAD /C3D 2023

Custom Build PC

Grrr1337

  • Swamp Rat
  • Posts: 812
Re: Find the nest level of a list
« Reply #10 on: October 18, 2017, 05:32:52 PM »
That's very kind of you to say, but don't be so down on yourself

I'm more like impressed on what you guys can do in this forum (so I'm trying to learn whatever I possibly can).

your programming abilities have already improved significantly over the last few months since you started participating on the forums

I guess that once you get to know any programming language + doing alot of experiments and practice (which are results of high interest) the results are shown...
And then you can get a brief idea of what this language is capable of, so one could give inputs with his ideas about helpful functions (obviously you've been through all of this).

But ofcourse the learning process is not everything.. the tutoring part is (or the good explaining guys are) very important.
Just imagine if in every different programming language there was a Lee Mac guy helping you out with C++/VBA/Ruby/Python...
Its no secret about your huge impact over LISP.

In other words when I attempt to write any decend code in private and I get stuck somewhere in an unknown area,
ofcourse at first I google for a solution... what do I find? - similar question/issue by user X which years ago is solved by Lee Mac.
Then I spend some time to investigate Lee's code to understand or learn something new - so I end up with aside experiment codes where I learned more than I've expected.
Although for some this might sound like a annoying painful process with too much effort, I know that most of you guys here know what is to be driven by your own interest to explore even more in this LISP world.

and so with continued study & practice, there's no reason why you can't continue to progress. :-)

Well with that  trace call  you just revealed how such complex iterations/recursions can be visualised, so that shall be my small step of another adventure. :)
Like I previously mentioned, a I'm a NP++ user, that visualises in his head how the code runs (evaluation by evaluation)
and if stuck - just check the doubtful evaluations in VLIDE's console. So you know that didn't used any other advantages from VLIDE.

I always thought can I impress one of the best LISPers with any code(s) and ended up with progress.  :-D
atleast this idea boosted some motivation
(apply ''((a b c)(a b c))
  '(
    (( f L ) (apply 'strcat (f L)))
    (( L ) (if L (cons (chr (car L)) (f (cdr L)))))
    (72 101 108 108 111 32 87 111 114 108 100)
  )
)
vevo.bg

ronjonp

  • Needs a day job
  • Posts: 7526
Re: Find the nest level of a list
« Reply #11 on: October 19, 2017, 09:16:03 AM »

For $h!+$ :)
Quote
_$


NESTEDLISTLEVEL
LEEFOO1
LEEFOO2
LEEFOORJPSTYLE
(((("A"))) ((((((((((((((((((((((("B" ("C")))))))))))))))))))))))) ("C")) Benchmarking .................Elapsed milliseconds / relative speed for 16384 iteration(s):


    (LEEFOO2 L).............1329 / 1.99 <fastest>
    (LEEFOORJPSTYLE L)......1375 / 1.92
    (NESTEDLISTLEVEL L).....1547 / 1.71
    (LEEFOO1 L).............2641 / 1 <slowest>


 
; 6 forms loaded from #<editor "<Untitled-1> loading...">
_$

Windows 11 x64 - AutoCAD /C3D 2023

Custom Build PC

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: Find the nest level of a list
« Reply #12 on: October 19, 2017, 11:23:44 AM »
My humble different approach only with strings, slower   :oops: , maybe good for lists with many numbers... >:D
Code: [Select]
(defun ALE_List_NestedLevel (l / r s e c i o)
  (setq i (vl-princ-to-string l) s 2 c 0 o 0)
  (while (setq e (vl-string-position 41 i s))
    (cond
      ( (= "(" (setq r (substr i s 1))) (setq c (1+ c) s (1+ s)) )
      ( (= ")" r)           (setq o (max c o) c (1- c) s (1+ s)) )
      ( (> (vl-string-position 40 i s) e)        (setq s (1+ e)) )
      ( T                                        (setq s (1+ s)) )
    )
  )
  o
)

Grrr1337

  • Swamp Rat
  • Posts: 812
Re: Find the nest level of a list
« Reply #13 on: October 19, 2017, 12:15:16 PM »
The only easy iterative approach that comes to my mind is this:

Code - Auto/Visual Lisp: [Select]
  1. (defun NestLvl ( L / i )
  2.   (and L (listp L) (setq i 0)
  3.     (while (and L (vl-some (function vl-consp) L))
  4.       (setq L (apply (function append) (mapcar (function (lambda (x) (cond ( (listp x) x) ( (list x) )))) L)))
  5.       (setq i (1+ i))
  6.     )
  7.   )
  8.   i
  9. )

Code - Auto/Visual Lisp: [Select]
  1. _$ (NestLvl "string") -> nil
  2. _$ (NestLvl nil ) -> nil
  3. _$ (NestLvl '("A" "B" "C") ) -> 0
  4. _$ (NestLvl '(("A")("B")("C")) ) -> 1
  5. _$ (NestLvl '(("A")(("B"))("C")) ) -> 2
  6. _$ (NestLvl '(("A")((((("B")))))("C")) ) -> 5
  7. _$ (NestLvl '(((("A")))((((((("B")))))))("C")) ) -> 7
  8. _$ (NestLvl '(((("A")))((((((((((((((((((((((("B" ("C"))))))))))))))))))))))))("C")) ) -> 24
  9. _$ (NestLvl '(((((("A")))((((((((((((((((((((((("B" ("C"))))))))))))))))))))))))("C")))) ) -> 26

IMO converting the whole list to a string and then processing is more frustrating. :)

Thanks for the benchmark Ron - I suspected that Lee's second suggestion would be the fastest.
(apply ''((a b c)(a b c))
  '(
    (( f L ) (apply 'strcat (f L)))
    (( L ) (if L (cons (chr (car L)) (f (cdr L)))))
    (72 101 108 108 111 32 87 111 114 108 100)
  )
)
vevo.bg

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1451
  • Marco
Re: Find the nest level of a list
« Reply #14 on: October 19, 2017, 01:09:50 PM »
maybe it needs some tweaking ...
Code: [Select]
(defun ALE_List_NestedLevel2 (l / r s e c i o m)
  (setq i (vl-princ-to-string l) s 2 c 0 o 0)
  (while (setq e (vl-string-position 41 i s))
    (cond
      ( (= "(" (setq r (substr i s 1))) (setq c (1+ c) s (1+ s)) )
      ( (= ")" r)           (setq o (max c o) c (1- c) s (1+ s)) )
      ( (or
          (not (setq m (vl-string-position 40 i s)))
          (> m e)
        )
        (setq s (1+ e))
      )
      ( T (setq s (1+ s)) )
    )
  )
  o
)