Finding deepest sublist
Finding deepest sublist
Hi, I must say that LISP is a new programming language to me and quite difficult one. Unfortunately I'm stuck right at the start, while trying to solve some exercises, so I'm thinking perhaps you could give me some pointers. The problem sounds simple - as I've already mentioned in the title, I want to find the deepest sublist (for example, the 1st element there) in the received list. I'm struggling with determining the right technique, hope you could help with some directions.
-
gugamilare
- Posts: 406
- Joined: Sat Mar 07, 2009 6:17 pm
- Location: Brazil
- Contact:
Re: Finding deepest sublist
I think the simpler way to do this is using two functions.
One, called "depth-of-list", will determine the depth of a list.
The other, called "find-deepest-sublist", will determine which sublist is the deepest one.
What is the definition of depth of a list? That is simple: the empty list (i.e., NIL) have depth 0. For a non-empty list, it is the depth of the deepest sublist plus one.
Therefore, the function "depth-of-list" will check if the list is NIL. If it is, return zero. Otherwise, it calls "find-deepest-sublist" and recursively calls "depth-of-list" in that list.
The function "find-deepest-sublist" now is easy to do. It has to iterate over all elements of a list (using dolist or loop), calculate the depth of that element (using "depth-of-list") and return whichever elements have the highest depth.
Good luck! In case you are stuck with the concepts of Common Lisp, try Practical Common Lisp.
One, called "depth-of-list", will determine the depth of a list.
The other, called "find-deepest-sublist", will determine which sublist is the deepest one.
What is the definition of depth of a list? That is simple: the empty list (i.e., NIL) have depth 0. For a non-empty list, it is the depth of the deepest sublist plus one.
Therefore, the function "depth-of-list" will check if the list is NIL. If it is, return zero. Otherwise, it calls "find-deepest-sublist" and recursively calls "depth-of-list" in that list.
The function "find-deepest-sublist" now is easy to do. It has to iterate over all elements of a list (using dolist or loop), calculate the depth of that element (using "depth-of-list") and return whichever elements have the highest depth.
Good luck! In case you are stuck with the concepts of Common Lisp, try Practical Common Lisp.
Re: Finding deepest sublist
Thanks for the reply, however I've already solved the problem in another way. I wrote a function that flattens a list by 1 level - based on this, I was able to determine the deepest sublist (until list flattening returns an empty list) and print the 1st element out. Anyway, thanks for the help, will try to do it like you suggested.