From: David Brynjar Franzson
Subject: a sublist problem
Date: 
Message-ID: <pd-8E0DC7.15555202052004@news.stanford.edu>
Hi, I have a problem that I seem to be completely unable to wrap my head 
around, except by using way to many subfunctions.

Here is the problem

I have a list, in the form '(2 (2 (4 5)) 3), where (2 2 3) are 
considered to be of the same "level". For this to be usable in the 
application I am using, the (2 (4 5)) must be converted to (10 (4 5)) 
(i.e. (+ 4 5) = 9 and I need the number in front of this to be higher 
then that number. As (2 2 3) are on the same level, I now need to go in 
and multiply it into being '(10 (10 (4 5)) 15). 

I know that I am probably not framing the problem well, and I apologize 
for that. A second problem is that this can happen on much more complex 
and deeper nested lists of this type. Any help in how to approach this 
problem would be greatly appreciated.

Sincerely,
david brynjar franzson

From: Paul Wallich
Subject: Re: a sublist problem
Date: 
Message-ID: <c73vsl$7en$1@reader2.panix.com>
David Brynjar Franzson wrote:

> Hi, I have a problem that I seem to be completely unable to wrap my head 
> around, except by using way to many subfunctions.
> 
> Here is the problem
> 
> I have a list, in the form '(2 (2 (4 5)) 3), where (2 2 3) are 
> considered to be of the same "level". For this to be usable in the 
> application I am using, the (2 (4 5)) must be converted to (10 (4 5)) 
> (i.e. (+ 4 5) = 9 and I need the number in front of this to be higher 
> then that number. As (2 2 3) are on the same level, I now need to go in 
> and multiply it into being '(10 (10 (4 5)) 15). 
> 
> I know that I am probably not framing the problem well, and I apologize 
> for that. A second problem is that this can happen on much more complex 
> and deeper nested lists of this type. Any help in how to approach this 
> problem would be greatly appreciated.

I'm still not exactly sure what your rules are, but it seems to me that 
a recursive solution should work fairly nicely if you remember that not 
all recursion is tail or tail-like, and that you can return more than 
one thing when you come back up from your recursive descent (for example 
here not only list fragments but also a possibly cumulative 
multiplication factor).

Then again I could be completely wrong

paul
From: Matthew Danish
Subject: Re: a sublist problem
Date: 
Message-ID: <20040503020501.GA25328@mapcar.org>
On Sun, May 02, 2004 at 03:55:53PM -0700, David Brynjar Franzson wrote:
> Hi, I have a problem that I seem to be completely unable to wrap my head 
> around, except by using way to many subfunctions.
> 
> Here is the problem
> 
> I have a list, in the form '(2 (2 (4 5)) 3), where (2 2 3) are 
> considered to be of the same "level". For this to be usable in the 
> application I am using, the (2 (4 5)) must be converted to (10 (4 5)) 
> (i.e. (+ 4 5) = 9 and I need the number in front of this to be higher 
> then that number. As (2 2 3) are on the same level, I now need to go in 
> and multiply it into being '(10 (10 (4 5)) 15). 
> 
> I know that I am probably not framing the problem well, and I apologize 
> for that. A second problem is that this can happen on much more complex 
> and deeper nested lists of this type. Any help in how to approach this 
> problem would be greatly appreciated.

You might find this easier if you introduce more structure into it,
because right now you are confusing yourself and other people.

Consider a possible framing of the problem, which I am not sure is
correct:

(defstruct level
  (num 0 :type integer)
  (args nil :type list))  ;; args is a list of levels

(defparameter *example*
  (make-level :num 2
	      :args (list (make-level 
			    :num 2
			    :args (list (make-level
					  :num 4
					  :args (list (make-level :num
								  5)))))
			  (make-level :num 3))))

  
*example* ;; ==>

#||

#S(LEVEL :NUM 2
   :ARGS
   (#S(LEVEL :NUM 2 :ARGS (#S(LEVEL :NUM 4 :ARGS (#S(LEVEL :NUM 5 :ARGS NIL)))))
    #S(LEVEL :NUM 3 :ARGS NIL)))

||#

(defun level->sexpr (lev)
  (cond ((null (level-args lev))
	 (level-num lev))
	(t
	 (cons (level-num lev)
	       (mapcar #'level->sexpr (level-args lev))))))

(level->sexpr *example*) ;; ==> (2 (2 (4 5)) 3)


With this model of your problem, consider a recursive solution.  The
first step is to think of how to handle a single, arbitrary node in the
tree.  Then, handle your base case.  After that, the recursive solution
should just fall into place.

(defun convert-level (lev)
  (cond ((null (level-args lev))
         ;; BASE CASE -- no conversion needed
         (values lev 1))
        (t
         ;; INDUCTIVE HYPOTHESIS:
         ;;   CONVERT-LEVEL will return a level structure and the
         ;;   multiplier it was converted by.
         ;; ...
         ;; at this point I become very unsure of the semantics of your
         ;; problem... what happens when there are multiple arguments
         ;; that need conversion?  Take the largest multiplier and apply
         ;; it to all?  Messy sketch of solution follows:
         (let* ((values
                 (sort (loop for arg in (level-args lev)
                             collect
                             (multiple-value-list (convert-level arg)))
                       #'>
                       :key #'second))
                (mult (or (second (first values)) 1))
                (sublevels
                 (loop for (sublev m) in values
                       collect
                       (make-level :num (* (/ (level-num sublev) m)
                                                    mult)
                            :args (level-args sublev))))
                (sum (reduce #'+ sublevels
                             :key #'level-num))
                (mult2 (if (< (* mult (level-num lev))
                              sum)
                           (ceiling sum (level-num lev))
                           mult)))
           (values
            (make-level
             :num (* (level-num lev) mult2)
             :args sublevels)
            mult2)))))

(level->sexpr (convert-level *example*)) ;; ==> (20 (8 (8 5)) 12)


Anyway, all I know is that your description is flawed, because 4 and 5
cannot be on the same level, otherwise the 2 preceeding them must also
be on the same level to be consistent.  Maybe you meant (2 4 5).  And if
the number in front must be higher than the arguments to it, then why is
10 acceptable in front of 15?

-- 
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
From: Kenny Tilton
Subject: Re: a sublist problem
Date: 
Message-ID: <lPglc.80205$WA4.3692@twister.nyc.rr.com>
David Brynjar Franzson wrote:

> Hi, I have a problem that I seem to be completely unable to wrap my head 
> around, except by using way to many subfunctions.
> 
> Here is the problem
> 
> I have a list, in the form '(2 (2 (4 5)) 3), where (2 2 3) are 
> considered to be of the same "level".

How is the second two at the same level as the first? Are you saying a 
list can consist of numbers N in which an element Ni appears either as 
an atom or as the first element of a list?

  For this to be usable in the
> application I am using, the (2 (4 5)) must be converted to (10 (4 5)) 
> (i.e. (+ 4 5) = 9 and I need the number in front of this to be higher 
> then that number. As (2 2 3) are on the same level, I now need to go in 
> and multiply it into being '(10 (10 (4 5)) 15). 

Why did the three and the other two also get multiplied by five? Is the 
rule that any increment be applied to all Ns at the same level or above?

> 
> I know that I am probably not framing the problem well, and I apologize 
> for that. A second problem is that this can happen on much more complex 
> and deeper nested lists of this type.

If you cannot frame the problem better, at least generate a second, more 
deeply nested example so we can figure out the pattern.

kenny

-- 
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
From: Thomas Schilling
Subject: Re: a sublist problem
Date: 
Message-ID: <c740qq$h2jps$1@uni-berlin.de>
David Brynjar Franzson wrote:

> I have a list, in the form '(2 (2 (4 5)) 3), where (2 2 3) are
> considered to be of the same "level". For this to be usable in the
> application I am using, the (2 (4 5)) must be converted to (10 (4 5))
> (i.e. (+ 4 5) = 9 and I need the number in front of this to be higher
> then that number. As (2 2 3) are on the same level, I now need to go in
> and multiply it into being '(10 (10 (4 5)) 15).

Hm, I assume the top-level list is assumed to be special, i.e. there's a
link of the two "2"s and the '(4 5) is kind of a condition for the "2",
right? But what would your conversion-function be supposed to do for
  '(2 (2 (4 5 (6 7))) 3) ?
how must the '(6 7) be treated? (+ 6 7) ?

If that assumption applies you might try to find the min-values for each of
the top-level list's elements and then calculate the needed factor.