Hi!
I'm doing a school work. And i need to calculate the cost of a route.
But I have a list with all the points that i'm passing... And i need
to remove a part of a list.
I have this list '((8 2) (8 3) (8 4) (7 4) (6 4) (5 4) (4 4) (4 5) (3
5) (3 6) (4 6) (4 5) (4 4) (5 4) (6 4) (7 4) (8 4) (8 5) (9 5) (10 5))
And i want to remove the part os list that begin in '(8 4) to the '(8
4)..
The result sould be this: '((8 2) (8 3) (8 4) (8 5) (9 5) (10 5))
Can anyone help me?
Regards,
Alexandre
On Jun 10, 5:19 pm, Alexandre Almeida <·········@gmail.com> wrote:
> Hi!
>
> I'm doing a school work. And i need to calculate the cost of a route.
> But I have a list with all the points that i'm passing... And i need
> to remove a part of a list.
>
> I have this list '((8 2) (8 3) (8 4) (7 4) (6 4) (5 4) (4 4) (4 5) (3
> 5) (3 6) (4 6) (4 5) (4 4) (5 4) (6 4) (7 4) (8 4) (8 5) (9 5) (10 5))
>
> And i want to remove the part os list that begin in '(8 4) to the '(8
> 4)..
>
> The result sould be this: '((8 2) (8 3) (8 4) (8 5) (9 5) (10 5))
>
> Can anyone help me?
>
> Regards,
> Alexandre
(REMOVE-IF PREDICATE SEQUENCE &REST ....
On Jun 10, 10:19 am, Alexandre Almeida <·········@gmail.com> wrote:
> i need to calculate the cost of a route.
> i need to remove a part of a list.
This should be fairly close to optimal:
(defun rem-loops (orig &key (test #'eql))
(let* ((list (copy-list orig))
(cell list))
(loop
(unless cell (return list))
(let ((dupe-cell (member (car cell) (cdr cell) :test test)))
(if dupe-cell
(setf (cdr cell) (cdr dupe-cell))
(setf cell (cdr cell)))))))
--Dan
------------------------------------------------
http://www.prairienet.org/~dsb/
cl-match: expressive pattern matching in Lisp
http://common-lisp.net/project/cl-match/
danb <·········@gmail.com> writes:
> On Jun 10, 10:19 am, Alexandre Almeida <·········@gmail.com> wrote:
>> i need to calculate the cost of a route.
>> i need to remove a part of a list.
>
> This should be fairly close to optimal:
>
> (defun rem-loops (orig &key (test #'eql))
> (let* ((list (copy-list orig))
> (cell list))
> (loop
> (unless cell (return list))
> (let ((dupe-cell (member (car cell) (cdr cell) :test test)))
> (if dupe-cell
> (setf (cdr cell) (cdr dupe-cell))
> (setf cell (cdr cell)))))))
Far from it, IMO:
(rem-loops '(1 2 a 4 b 2 h i j k 4 7))
(1 2 H I J K 4 7)
(1 2 a 4 7) would be a better answer. But to what question, already?
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we. -- Georges W. Bush
On Jun 10, 2:08 pm, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> danb <·········@gmail.com> writes:
> > On Jun 10, 10:19 am, Alexandre Almeida <·········@gmail.com> wrote:
> >> i need to calculate the cost of a route.
> >> i need to remove a part of a list.
>
> > This should be fairly close to optimal:
>
> > (defun rem-loops (orig &key (test #'eql))
> > (let* ((list (copy-list orig))
> > (cell list))
> > (loop
> > (unless cell (return list))
> > (let ((dupe-cell (member (car cell) (cdr cell) :test test)))
> > (if dupe-cell
> > (setf (cdr cell) (cdr dupe-cell))
> > (setf cell (cdr cell)))))))
>
> Far from it, IMO:
>
> (rem-loops '(1 2 a 4 b 2 h i j k 4 7))
> (1 2 H I J K 4 7)
>
> (1 2 a 4 7) would be a better answer.
> But to what question, already?
Good point. I'll weasel out of that by restricting
my claim to minimizing some combination of run time,
space used, and code size in eliminating loops, rather
than optimizing the result. Path minimization would
be more work, and the OP didn't exactly say whether
it's part of the spec, but of course it could very
well be important.
--Dan
------------------------------------------------
http://www.prairienet.org/~dsb/
cl-match: expressive pattern matching in Lisp
http://common-lisp.net/project/cl-match/
Alexandre Almeida wrote:
> Hi!
>
> I'm doing a school work. And i need to calculate the cost of a route.
> But I have a list with all the points that i'm passing... And i need
> to remove a part of a list.
>
> I have this list '((8 2) (8 3) (8 4) (7 4) (6 4) (5 4) (4 4) (4 5) (3
> 5) (3 6) (4 6) (4 5) (4 4) (5 4) (6 4) (7 4) (8 4) (8 5) (9 5) (10 5))
>
> And i want to remove the part os list that begin in '(8 4) to the '(8
> 4)..
>
> The result sould be this: '((8 2) (8 3) (8 4) (8 5) (9 5) (10 5))
>
> Can anyone help me?
See http://www.lispworks.com/documentation/HyperSpec/Body/c_conses.htm
and http://www.lispworks.com/documentation/HyperSpec/Body/c_sequen.htm
(People typically forget that the sequence functions can be used on
lists as well.)
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Jun 10, 5:29 pm, Pascal Costanza <····@p-cos.net> wrote:
> Alexandre Almeida wrote:
> > Hi!
>
> > I'm doing a school work. And i need to calculate the cost of a route.
> > But I have a list with all the points that i'm passing... And i need
> > to remove a part of a list.
>
> > I have this list '((8 2) (8 3) (8 4) (7 4) (6 4) (5 4) (4 4) (4 5) (3
> > 5) (3 6) (4 6) (4 5) (4 4) (5 4) (6 4) (7 4) (8 4) (8 5) (9 5) (10 5))
>
> > And i want to remove the part os list that begin in '(8 4) to the '(8
> > 4)..
>
> > The result sould be this: '((8 2) (8 3) (8 4) (8 5) (9 5) (10 5))
>
> > Can anyone help me?
>
> Seehttp://www.lispworks.com/documentation/HyperSpec/Body/c_conses.htm
> andhttp://www.lispworks.com/documentation/HyperSpec/Body/c_sequen.htm
>
> (People typically forget that the sequence functions can be used on
> lists as well.)
>
> Pascal
>
> --
> My website:http://p-cos.net
> Common Lisp Document Repository:http://cdr.eurolisp.org
> Closer to MOP & ContextL:http://common-lisp.net/project/closer/
Tanks for the reply!!
Finally i have a solution not the best one, but works:
(defun inverter (L A)
(if (null L)
A
(inverter (rest L) (cons (first L) A))))
(defun DevPerc_aux (lx lrec lista)
(if (null lx)
lista
(if (iguais (car lx) lrec)
lista
(DevPerc_aux (cdr lx) lrec (cons (car lx) lista))
)
)
)
;devolve a lista sem recuos
(defun DevPercurso(lx lrec)
(append (inverter(DevPerc_aux lx lrec nil) nil) (append (list
lrec) (DevPerc_aux (inverter lx nil) lrec nil))))
regards,
Alexandre
Alexandre Almeida <·········@gmail.com> writes:
> On Jun 10, 5:29 pm, Pascal Costanza <····@p-cos.net> wrote:
>> Alexandre Almeida wrote:
>> > Hi!
>>
>> > I'm doing a school work. And i need to calculate the cost of a route.
>> > But I have a list with all the points that i'm passing... And i need
>> > to remove a part of a list.
>>
>> > I have this list '((8 2) (8 3) (8 4) (7 4) (6 4) (5 4) (4 4) (4 5) (3
>> > 5) (3 6) (4 6) (4 5) (4 4) (5 4) (6 4) (7 4) (8 4) (8 5) (9 5) (10 5))
>>
>> > And i want to remove the part os list that begin in '(8 4) to the '(8
>> > 4)..
>>
>> > The result sould be this: '((8 2) (8 3) (8 4) (8 5) (9 5) (10 5))
>>
>> > Can anyone help me?
>>
>> Seehttp://www.lispworks.com/documentation/HyperSpec/Body/c_conses.htm
>> andhttp://www.lispworks.com/documentation/HyperSpec/Body/c_sequen.htm
>>
>> (People typically forget that the sequence functions can be used on
>> lists as well.)
>>
>> Pascal
>>
>> --
>> My website:http://p-cos.net
>> Common Lisp Document Repository:http://cdr.eurolisp.org
>> Closer to MOP & ContextL:http://common-lisp.net/project/closer/
>
> Tanks for the reply!!
>
> Finally i have a solution not the best one, but works:
>
> (defun inverter (L A)
> (if (null L)
> A
> (inverter (rest L) (cons (first L) A))))
>
>
> (defun DevPerc_aux (lx lrec lista)
> (if (null lx)
> lista
> (if (iguais (car lx) lrec)
> lista
> (DevPerc_aux (cdr lx) lrec (cons (car lx) lista))
> )
>
> )
> )
>
> ;devolve a lista sem recuos
> (defun DevPercurso(lx lrec)
> (append (inverter(DevPerc_aux lx lrec nil) nil) (append (list
> lrec) (DevPerc_aux (inverter lx nil) lrec nil))))
>
> regards,
> Alexandre
Only lightly tested:
(defun remove-loops (list)
(if (null list)
nil
(let ((last-occurrence (position (first list) (rest list)
:test #'equal :from-end t)))
(cons (first list)
(remove-loops
(if last-occurrence
(subseq (rest list) (1+ last-occurrence))
(rest list)))))))
Den Tue, 10 Jun 2008 10:04:57 -0700 skrev Alexandre Almeida:
> (defun DevPerc_aux (lx lrec lista)
This is a purely aesthetical remark, but: it's very much against CL
conventions to use either CamelCase or underscores in names, doing both
is just ewww :). You have dashes available, use that. Also, it's
customary to give full and meaningful names to variables, especially
those that are a part of a function's public interface (ie. its
parameters). And the last thing is that you're recursing here to process
list; whilst it's by no means incorrect, you have to take into account
that CL implementations are not required to do tail-call optimisation, so
unless you never expect the input lists to be large, you should be rather
careful about not running out of stack. Iteration is preferred in CL
(unlike in Scheme).
Cheers,
Maciej
Alexandre Almeida <·········@gmail.com> writes:
> Finally i have a solution not the best one, but works:
>
> (defun inverter (L A)
> (if (null L)
> A
> (inverter (rest L) (cons (first L) A))))
There's (REVERSE sequence)
> (defun DevPerc_aux (lx lrec lista)
> (if (null lx)
> lista
> (if (iguais (car lx) lrec)
> lista
> (DevPerc_aux (cdr lx) lrec (cons (car lx) lista)))))
>
> ;devolve a lista sem recuos
> (defun DevPercurso(lx lrec)
> (append (inverter(DevPerc_aux lx lrec nil) nil)
> (append (list lrec)
> (DevPerc_aux (inverter lx nil) lrec nil))))
CL:APPEND takes a variable number of argument:
(append (reverse (DevPerc_aux lx lrec nil))
(list lrec)
(DevPerc_aux (reverse lx) lrec nil))
--
__Pascal Bourguignon__ http://www.informatimago.com/
IMPORTANT NOTICE TO PURCHASERS: The entire physical universe,
including this product, may one day collapse back into an
infinitesimally small space. Should another universe subsequently
re-emerge, the existence of this product in that universe cannot be
guaranteed.
Alexandre Almeida <·········@gmail.com> writes:
> Hi!
>
> I'm doing a school work. And i need to calculate the cost of a route.
> But I have a list with all the points that i'm passing...
>
> And i need
> to remove a part of a list.
>
> I have this list '((8 2) (8 3) (8 4) (7 4) (6 4) (5 4) (4 4) (4 5) (3
> 5) (3 6) (4 6) (4 5) (4 4) (5 4) (6 4) (7 4) (8 4) (8 5) (9 5) (10 5))
>
> And i want to remove the part os list that begin in '(8 4) to the '(8
> 4)..
>
> The result sould be this: '((8 2) (8 3) (8 4) (8 5) (9 5) (10 5))
>
> Can anyone help me?
So, if you try to formalize up things a little, what would that give?
You see, there's a gigantic ambiguity in what you say here. You write
(8 4) twice, with a different meaning each time. Try to express
yourself, what is the first (8 4) and what is the other one?
--
__Pascal Bourguignon__ http://www.informatimago.com/
IMPORTANT NOTICE TO PURCHASERS: The entire physical universe,
including this product, may one day collapse back into an
infinitesimally small space. Should another universe subsequently
re-emerge, the existence of this product in that universe cannot be
guaranteed.
On Jun 10, 8:19 am, Alexandre Almeida <·········@gmail.com> wrote:
> Hi!
>
> I'm doing a school work. And i need to calculate the cost of a route.
> But I have a list with all the points that i'm passing... And i need
> to remove a part of a list.
>
> I have this list '((8 2) (8 3) (8 4) (7 4) (6 4) (5 4) (4 4) (4 5) (3
> 5) (3 6) (4 6) (4 5) (4 4) (5 4) (6 4) (7 4) (8 4) (8 5) (9 5) (10 5))
>
> And i want to remove the part os list that begin in '(8 4) to the '(8
> 4)..
>
> The result sould be this: '((8 2) (8 3) (8 4) (8 5) (9 5) (10 5))
It looks as if the resulting sequence is the longest subsequence of
the original sequence, in which the sums of the value pairs are
strictly increasing.
> Can anyone help me?
Maybe this?
(defun strictly-increasing (input-pair-list)
(loop with max = nil
for pair in input-pair-list
for pair-value = (apply #'+ pair)
when (or (null max) (> pair-value max))
collect pair and
do (setf max pair-value))))
This could be generalized to an arbitrarily shaped list, not just
pairs of numbers. The function which reduces the elements of the list
to a sum can be passed in as an argument: (lambda (item) (apply #'+
item)). The default function should be IDENTITY, so that the function
works with simple list of items by default. The comparison function
can also be parametrized, defaulting to the > function so the function
works with numbers by default.
(defun strictly-increasing (input-list &key (greater #'>)
(value #'identity))
(loop with max = nil
for item in input-list
for item-value = (funcall value item)
when (or (null max) (funcall greater item-value max))
collect item and
do (setf max item-value))))
Now you can call it like this:
(strictly-increasing '((8 2) (8 3) (8 4) (7 4) (6 4) (5 4)
(4 4) (4 5) (3 5) (3 6) (4 6) (4 5)
(4 4) (5 4) (6 4) (7 4) (8 4) (8 5)
(9 5) (10 5))
:value #'(lambda (item) (apply #'+ item)))
-> ((8 2) (8 3) (8 4) (8 5) (9 5) (10 5))