From: Kenneth Tilton
Subject: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <49708557$0$20284$607ed4bc@cv.net>
You are given a simple-vector and a list of malformed ranges, malformed
in that the second value is the last one to /keep/ vs. what subseq wants
as the end parameter: the first one to omit. But all ranges are pairs
(even if only one value is thus delimited) and the pairs are guarnteed
to be ordered and well-formed and not to go out of bounds, so there is that.
Your mission is to return a simple-vector with those values excised.
(defun excise-ranges (seq ranges)
....)
such that:
(excise-ranges #(0 1 2 3) '((0 0)))
-> #(1 2 3)
(excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
-> #(0 30)
And do it better than I, which should not be too hard from the looks of
the mess below (if you scroll down far enough).
hth,kt
(bk-defun excise-ranges (seq ranges)
(loop with length = (length seq)
and s1 = (when (plusp (caar ranges))
(subseq seq 0 (caar ranges)))
for (r1 r2) on ranges
collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
into ss
finally (return (apply 'concatenate 'simple-vector s1 ss))))
On Jan 16, 2:02 pm, Kenneth Tilton <·········@gmail.com> wrote:
> (bk-defun excise-ranges (seq ranges)
> (loop with length = (length seq)
> and s1 = (when (plusp (caar ranges))
> (subseq seq 0 (caar ranges)))
> for (r1 r2) on ranges
> collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
> into ss
> finally (return (apply 'concatenate 'simple-vector s1 ss))))
This version is a bit longer, but more efficient due to REPLACE:
(defun ex (seq ranges)
(loop with new-length = (- (length seq)
(loop for (start end) in ranges sum (1+
(- end start))))
with dest = (subseq seq 0 new-length)
for ((s1 e1) (s2 nil)) on ranges ;; s, e inclusive
for gap-start-ix = (1+ e1)
for gap-end-ix = (or s2 (length seq)) ;; end-ix exclusive
for gap-length = (- gap-end-ix gap-start-ix)
for dest-ix = s1 then dest-ix
when (plusp gap-length)
do (replace dest seq :start1 dest-ix :start2 gap-start-ix :end2
gap-end-ix)
(incf dest-ix gap-length)
finally (return dest)))
- Willem
From: Kenneth Tilton
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <4970b4be$0$4908$607ed4bc@cv.net>
Willem Broekema wrote:
> On Jan 16, 2:02 pm, Kenneth Tilton <·········@gmail.com> wrote:
>> (bk-defun excise-ranges (seq ranges)
>> (loop with length = (length seq)
>> and s1 = (when (plusp (caar ranges))
>> (subseq seq 0 (caar ranges)))
>> for (r1 r2) on ranges
>> collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
>> into ss
>> finally (return (apply 'concatenate 'simple-vector s1 ss))))
>
> This version is a bit longer, but more efficient due to REPLACE:
>
> (defun ex (seq ranges)
> (loop with new-length = (- (length seq)
> (loop for (start end) in ranges sum (1+
> (- end start))))
> with dest = (subseq seq 0 new-length)
> for ((s1 e1) (s2 nil)) on ranges ;; s, e inclusive
> for gap-start-ix = (1+ e1)
> for gap-end-ix = (or s2 (length seq)) ;; end-ix exclusive
> for gap-length = (- gap-end-ix gap-start-ix)
> for dest-ix = s1 then dest-ix
> when (plusp gap-length)
> do (replace dest seq :start1 dest-ix :start2 gap-start-ix :end2
> gap-end-ix)
> (incf dest-ix gap-length)
> finally (return dest)))
Whoa, extra credit for the replace!
An email entry gave me an idea, I might be entering my own contest with
a five-liner.
I was looking for short and elegant, but we can have a category for
effiency. I'd let it be nexcise-ranges but we'll need to support undo.
cheers,kth
From: Kenneth Tilton
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <4970b99c$0$29326$607ed4bc@cv.net>
Willem Broekema wrote:
> On Jan 16, 2:02 pm, Kenneth Tilton <·········@gmail.com> wrote:
>> (bk-defun excise-ranges (seq ranges)
>> (loop with length = (length seq)
>> and s1 = (when (plusp (caar ranges))
>> (subseq seq 0 (caar ranges)))
>> for (r1 r2) on ranges
>> collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
>> into ss
>> finally (return (apply 'concatenate 'simple-vector s1 ss))))
>
> This version is a bit longer, but more efficient due to REPLACE:
>
> (defun ex (seq ranges)
> (loop with new-length = (- (length seq)
> (loop for (start end) in ranges sum (1+
> (- end start))))
> with dest = (subseq seq 0 new-length)
> for ((s1 e1) (s2 nil)) on ranges ;; s, e inclusive
> for gap-start-ix = (1+ e1)
> for gap-end-ix = (or s2 (length seq)) ;; end-ix exclusive
> for gap-length = (- gap-end-ix gap-start-ix)
> for dest-ix = s1 then dest-ix
> when (plusp gap-length)
> do (replace dest seq :start1 dest-ix :start2 gap-start-ix :end2
> gap-end-ix)
> (incf dest-ix gap-length)
> finally (return dest)))
>
>
> - Willem
well, it /feels/ like three lines :(
(defun excise-ranges (seq ranges)
(coerce
(loop with bounds = (loop for (min max) in ranges
collect min
collect (1+ max))
and collecting = t
for elt across seq
for n upfrom 0
when (and bounds (= n (car bounds)))
do (setf collecting (not collecting))
(pop bounds)
when collecting collect elt)
'simple-vector)
lightly tested.
kt
On Jan 16, 7:02 am, Kenneth Tilton <·········@gmail.com> wrote:
> You are given a simple-vector and a list of malformed ranges, malformed
> in that the second value is the last one to /keep/ vs. what subseq wants
> as the end parameter: the first one to omit. But all ranges are pairs
> (even if only one value is thus delimited) and the pairs are guarnteed
> to be ordered and well-formed and not to go out of bounds, so there is that.
>
> Your mission is to return a simple-vector with those values excised.
>
> (defun excise-ranges (seq ranges)
> ....)
>
> such that:
>
> (excise-ranges #(0 1 2 3) '((0 0)))
> -> #(1 2 3)
>
> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
> -> #(0 30)
>
> And do it better than I, which should not be too hard from the looks of
> the mess below (if you scroll down far enough).
>
> hth,kt
>
> (bk-defun excise-ranges (seq ranges)
> (loop with length = (length seq)
> and s1 = (when (plusp (caar ranges))
> (subseq seq 0 (caar ranges)))
> for (r1 r2) on ranges
> collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
> into ss
> finally (return (apply 'concatenate 'simple-vector s1 ss))))
Ruby:
def delete_ranges seq, ranges
indices = (0 ... seq.size).to_a
ranges.each{|r| indices -= Range.new( *r ).to_a }
seq.values_at *indices
end
p delete_ranges( [2,3,4,5,6,7,8], [[1,1], [4,5]] )
p delete_ranges( [0,1,2,3], [[0, 0]] )
p delete_ranges( [0,10,20,30,40], [[1,2],[4,4]] )
--- output ---
[2, 4, 5, 8]
[1, 2, 3]
[0, 30]
From: André Thieme
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <gktbrg$2k4$1@news.motzarella.org>
·········@yahoo.com schrieb:
> Ruby:
>
> def delete_ranges seq, ranges
> indices = (0 ... seq.size).to_a
> ranges.each{|r| indices -= Range.new( *r ).to_a }
> seq.values_at *indices
> end
>
>
> p delete_ranges( [2,3,4,5,6,7,8], [[1,1], [4,5]] )
> p delete_ranges( [0,1,2,3], [[0, 0]] )
> p delete_ranges( [0,10,20,30,40], [[1,2],[4,4]] )
>
> --- output ---
> [2, 4, 5, 8]
> [1, 2, 3]
> [0, 30]
OMG, is there *anything* that your Comal like language Ruby can do
easily? I don�t think so.
When I see your code I feel teleported back into the past, to the mid
70ies, where Comal programs had to be so complicated and long.
In Clojure:
(defn delete-ranges [col ranges]
(map #(col %) (filter #(not-any? (fn [[f s]] (<= f % s)) ranges)
(range (count col)))))
I put (range (count seq)) on the last line because some newsreaders
might have problems displaying it otherwise.
Lisp style saved us here over 10% of keystrokes, 10% of strange symbols
(non-english, non-whitespace and non-digits) and the Ruby program has
250% of the LOC of the lisp version.
user> (delete-ranges [2 3 4 5 6 7 8] [[1 1] [4 5]])
(2 4 5 8)
user> (delete-ranges [0 1 2 3], [[0 0]])
(1 2 3)
user> (delete-ranges [0 10 20 30 40] [[1 2] [4 4]])
(0 30)
But please don�t give up William. Keep posting to the wrong newsgroup.
It�s so much fun to beat you every single time *giggle*
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
From: Patrick May
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <m2ljtbqbx8.fsf@spe.com>
Kenneth Tilton <·········@gmail.com> writes:
> You are given a simple-vector and a list of malformed ranges,
> malformed in that the second value is the last one to /keep/ vs. what
> subseq wants as the end parameter: the first one to omit. But all
> ranges are pairs (even if only one value is thus delimited) and the
> pairs are guarnteed to be ordered and well-formed and not to go out of
> bounds, so there is that.
>
> Your mission is to return a simple-vector with those values excised.
>
> (defun excise-ranges (seq ranges)
> ....)
>
> such that:
>
> (excise-ranges #(0 1 2 3) '((0 0)))
> -> #(1 2 3)
>
> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
> -> #(0 30)
I'll be different and not use loop:
(defun excise-ranges (sequence ranges)
"Return a sequence that consists of the elements in SEQUENCE not in
the inclusive ranges of RANGES."
(flet ((expand-range (range)
(let ((result nil))
(dotimes (i (1+ (- (second range) (first range))) result)
(push (+ i (first range)) result)))))
(let ((expanded-ranges (reduce #'append (mapcar #'expand-range ranges)))
(result nil))
(dotimes (i (length sequence)
(make-array (length result)
:initial-contents (nreverse result)))
(unless (find i expanded-ranges)
(push (aref sequence i) result))))))
Oh, wait, you wanted it to be _efficient_, too?
Regards,
Patrick
------------------------------------------------------------------------
S P Engineering, Inc. | Large scale, mission-critical, distributed OO
| systems design and implementation.
http://www.spe.com/pjm | (C++, Java, Common Lisp, Jini, middleware, SOA)
From: Pascal Costanza
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <6tbtgmFa8ucoU1@mid.individual.net>
Kenneth Tilton wrote:
> You are given a simple-vector and a list of malformed ranges, malformed
> in that the second value is the last one to /keep/ vs. what subseq wants
> as the end parameter: the first one to omit. But all ranges are pairs
> (even if only one value is thus delimited) and the pairs are guarnteed
> to be ordered and well-formed and not to go out of bounds, so there is
> that.
>
> Your mission is to return a simple-vector with those values excised.
>
> (defun excise-ranges (seq ranges)
> ....)
>
> such that:
>
> (excise-ranges #(0 1 2 3) '((0 0)))
> -> #(1 2 3)
>
> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
> -> #(0 30)
>
(defun excise-ranges-helper (vector ranges)
(declare (vector vector))
(loop with nada = vector ;; ;)
for (lower upper) in ranges
do (fill vector nada :start lower :end (1+ upper))
finally (return (loop for entry across vector
unless (eq entry nada)
collect entry))))
(defgeneric excise-ranges (sequence ranges)
(:method ((sequence vector) ranges)
(coerce (excise-ranges-helper (copy-seq sequence) ranges) 'vector))
(:method ((sequence list) ranges)
(excise-ranges-helper (coerce sequence 'vector) ranges)))
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 Jan 16, 7:12 pm, Pascal Costanza <····@p-cos.net> wrote:
>
> (defun excise-ranges-helper (vector ranges)
> (declare (vector vector))
> (loop with nada = vector ;; ;)
> for (lower upper) in ranges
> do (fill vector nada :start lower :end (1+ upper))
> finally (return (loop for entry across vector
> unless (eq entry nada)
> collect entry))))
>
> (defgeneric excise-ranges (sequence ranges)
> (:method ((sequence vector) ranges)
> (coerce (excise-ranges-helper (copy-seq sequence) ranges) 'vector))
> (:method ((sequence list) ranges)
> (excise-ranges-helper (coerce sequence 'vector) ranges)))
>
That's a good approach, but there are some unnecessary complications
here. I would write the following:
(defun excise-ranges (sequence ranges)
(loop with nada = (load-time-value (cons nil nil))
for (lower upper) in ranges
do (fill sequence nada :start lower :end (1+ upper))
finally (return (remove nada sequence :test #'eq))))
Note that I use a "private" cons, which is guaranteed not to be an
element
of the sequence at function entry or exit. Note that the sequence is
passed
just to FILL and REMOVE, which are generic sequence operators - no
need
to coerce anything.
Ariel
On Jan 17, 3:13 am, Ariel Badichi <····@tidexsystems.com> wrote:
>
> (defun excise-ranges (sequence ranges)
> (loop with nada = (load-time-value (cons nil nil))
> for (lower upper) in ranges
> do (fill sequence nada :start lower :end (1+ upper))
> finally (return (remove nada sequence :test #'eq))))
>
I should have used DELETE rather than REMOVE here, since the function
is clearly destructive. Also, I apologize for the formatting errors
in that post.
Ariel
On Jan 17, 2:42 am, Ariel Badichi <····@tidexsystems.com> wrote:
> On Jan 17, 3:13 am, Ariel Badichi <····@tidexsystems.com> wrote:
>
>
>
> > (defun excise-ranges (sequence ranges)
> > (loop with nada = (load-time-value (cons nil nil))
> > for (lower upper) in ranges
> > do (fill sequence nada :start lower :end (1+ upper))
> > finally (return (remove nada sequence :test #'eq))))
>
> I should have used DELETE rather than REMOVE here, since the function
> is clearly destructive. Also, I apologize for the formatting errors
> in that post.
>
> Ariel
Since the original problem didn't mention anything about the list
containing junk (or maybe I missed something?), I don't see why we
couldn't just use nil. Also the upper bound was not to be removed
according to the description (or maybe...).
(defun excise-ranges (sequence ranges)
(loop for (lower upper) in ranges
do (fill sequence nil :start lower :end upper)
finally (return (delete-if #'null sequence)))))
Adde
On Jan 17, 7:21 pm, Adde <····@trialcode.com> wrote:
> On Jan 17, 2:42 am, Ariel Badichi <····@tidexsystems.com> wrote:
>
> > On Jan 17, 3:13 am, Ariel Badichi <····@tidexsystems.com> wrote:
>
> > > (defun excise-ranges (sequence ranges)
> > > (loop with nada = (load-time-value (cons nil nil))
> > > for (lower upper) in ranges
> > > do (fill sequence nada :start lower :end (1+ upper))
> > > finally (return (remove nada sequence :test #'eq))))
>
> > I should have used DELETE rather than REMOVE here, since the function
> > is clearly destructive. Also, I apologize for the formatting errors
> > in that post.
>
> > Ariel
>
> Since the original problem didn't mention anything about the list
> containing junk (or maybe I missed something?), I don't see why we
> couldn't just use nil. Also the upper bound was not to be removed
> according to the description (or maybe...).
>
> (defun excise-ranges (sequence ranges)
> (loop for (lower upper) in ranges
> do (fill sequence nil :start lower :end upper)
> finally (return (delete-if #'null sequence)))))
>
> Adde
I should definitely learn to read more carefully, the description
explicitly state that the upper bound should be removed. Sorry about
that.
(defun excise-ranges (sequence ranges)
(loop for (lower upper) in ranges
do (fill sequence nil :start lower :end (1+ upper))
finally (return (delete-if #'null sequence)))))
From: Pascal Costanza
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <6tem3fFagas5U1@mid.individual.net>
Adde wrote:
> On Jan 17, 2:42 am, Ariel Badichi <····@tidexsystems.com> wrote:
>> On Jan 17, 3:13 am, Ariel Badichi <····@tidexsystems.com> wrote:
>>
>>
>>
>>> (defun excise-ranges (sequence ranges)
>>> (loop with nada = (load-time-value (cons nil nil))
>>> for (lower upper) in ranges
>>> do (fill sequence nada :start lower :end (1+ upper))
>>> finally (return (remove nada sequence :test #'eq))))
>> I should have used DELETE rather than REMOVE here, since the function
>> is clearly destructive. Also, I apologize for the formatting errors
>> in that post.
>>
>> Ariel
>
> Since the original problem didn't mention anything about the list
> containing junk (or maybe I missed something?), I don't see why we
> couldn't just use nil. Also the upper bound was not to be removed
> according to the description (or maybe...).
>
> (defun excise-ranges (sequence ranges)
> (loop for (lower upper) in ranges
> do (fill sequence nil :start lower :end upper)
> finally (return (delete-if #'null sequence)))))
The OP didn't give a full specification. ;)
However, it was stated that the upper was to be removed. Also, it wasn't
stated that the sequence wouldn't contain nil.
Finally, (delete-if #'null ...) is a bit verbose, (delete nil ...) would
be sufficient.
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 Jan 17, 7:24 pm, Pascal Costanza <····@p-cos.net> wrote:
> Adde wrote:
> > On Jan 17, 2:42 am, Ariel Badichi <····@tidexsystems.com> wrote:
> >> On Jan 17, 3:13 am, Ariel Badichi <····@tidexsystems.com> wrote:
>
> >>> (defun excise-ranges (sequence ranges)
> >>> (loop with nada = (load-time-value (cons nil nil))
> >>> for (lower upper) in ranges
> >>> do (fill sequence nada :start lower :end (1+ upper))
> >>> finally (return (remove nada sequence :test #'eq))))
> >> I should have used DELETE rather than REMOVE here, since the function
> >> is clearly destructive. Also, I apologize for the formatting errors
> >> in that post.
>
> >> Ariel
>
> > Since the original problem didn't mention anything about the list
> > containing junk (or maybe I missed something?), I don't see why we
> > couldn't just use nil. Also the upper bound was not to be removed
> > according to the description (or maybe...).
>
> > (defun excise-ranges (sequence ranges)
> > (loop for (lower upper) in ranges
> > do (fill sequence nil :start lower :end upper)
> > finally (return (delete-if #'null sequence)))))
>
> The OP didn't give a full specification. ;)
>
> However, it was stated that the upper was to be removed. Also, it wasn't
> stated that the sequence wouldn't contain nil.
>
> Finally, (delete-if #'null ...) is a bit verbose, (delete nil ...) would
> be sufficient.
>
> 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/
Sloppy reading on my part, thanks ;)
Nitpicking here but isn't the default test for (delete) #'eql?
Changing the test to match the runtime complexity of #'null would make
it just as verbose as (delete-if).
(delete nil sequence :test #'eq)
Adde
From: Pascal Costanza
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <6teperFai6lsU1@mid.individual.net>
Adde wrote:
> On Jan 17, 7:24 pm, Pascal Costanza <····@p-cos.net> wrote:
>> Adde wrote:
>>> On Jan 17, 2:42 am, Ariel Badichi <····@tidexsystems.com> wrote:
>>>> On Jan 17, 3:13 am, Ariel Badichi <····@tidexsystems.com> wrote:
>>>>> (defun excise-ranges (sequence ranges)
>>>>> (loop with nada = (load-time-value (cons nil nil))
>>>>> for (lower upper) in ranges
>>>>> do (fill sequence nada :start lower :end (1+ upper))
>>>>> finally (return (remove nada sequence :test #'eq))))
>>>> I should have used DELETE rather than REMOVE here, since the function
>>>> is clearly destructive. Also, I apologize for the formatting errors
>>>> in that post.
>>>> Ariel
>>> Since the original problem didn't mention anything about the list
>>> containing junk (or maybe I missed something?), I don't see why we
>>> couldn't just use nil. Also the upper bound was not to be removed
>>> according to the description (or maybe...).
>>> (defun excise-ranges (sequence ranges)
>>> (loop for (lower upper) in ranges
>>> do (fill sequence nil :start lower :end upper)
>>> finally (return (delete-if #'null sequence)))))
>> The OP didn't give a full specification. ;)
>>
>> However, it was stated that the upper was to be removed. Also, it wasn't
>> stated that the sequence wouldn't contain nil.
>>
>> Finally, (delete-if #'null ...) is a bit verbose, (delete nil ...) would
>> be sufficient.
>>
>> 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/
>
> Sloppy reading on my part, thanks ;)
> Nitpicking here but isn't the default test for (delete) #'eql?
> Changing the test to match the runtime complexity of #'null would make
> it just as verbose as (delete-if).
> (delete nil sequence :test #'eq)
I trust that a good compiler knows how to test efficiently against 'nil.
Furthermore, this is not the part where I expect a bottleneck. ;)
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/
From: Pascal Costanza
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <6te4i9FagaccU1@mid.individual.net>
Ariel Badichi wrote:
> On Jan 16, 7:12 pm, Pascal Costanza <····@p-cos.net> wrote:
>> (defun excise-ranges-helper (vector ranges)
>> (declare (vector vector))
>> (loop with nada = vector ;; ;)
>> for (lower upper) in ranges
>> do (fill vector nada :start lower :end (1+ upper))
>> finally (return (loop for entry across vector
>> unless (eq entry nada)
>> collect entry))))
>>
>> (defgeneric excise-ranges (sequence ranges)
>> (:method ((sequence vector) ranges)
>> (coerce (excise-ranges-helper (copy-seq sequence) ranges) 'vector))
>> (:method ((sequence list) ranges)
>> (excise-ranges-helper (coerce sequence 'vector) ranges)))
>>
>
> That's a good approach, but there are some unnecessary complications
> here. I would write the following:
>
> (defun excise-ranges (sequence ranges)
> (loop with nada = (load-time-value (cons nil nil))
> for (lower upper) in ranges
> do (fill sequence nada :start lower :end (1+ upper))
> finally (return (remove nada sequence :test #'eq))))
>
> Note that I use a "private" cons, which is guaranteed not to be an
> element
> of the sequence at function entry or exit.
That's also true for the value I use in my code, because the vector that
I use as a marker is a freshly created vector. But, indeed, I meant that
as a joke. ;)
> Note that the sequence is
> passed
> just to FILL and REMOVE, which are generic sequence operators - no
> need
> to coerce anything.
Nice, also wrt to using DELETE, as you state in your own follow-up.
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/
From: Kenneth Tilton
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <49712ff6$0$4888$607ed4bc@cv.net>
Kenneth Tilton wrote:
> Madhu wrote:
>> * Kenneth Tilton <·························@cv.net> :
>> Wrote on Fri, 16 Jan 2009 08:02:22 -0500:
>>
>> [snip]
>>
>> | (bk-defun excise-ranges (seq ranges)
>> | (loop with length = (length seq)
>> | and s1 = (when (plusp (caar ranges))
>> | (subseq seq 0 (caar ranges)))
>> | for (r1 r2) on ranges
>> | collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
>> | into ss
>> | finally (return (apply 'concatenate 'simple-vector s1 ss))))
>>
>>
>> ;; same algorithm as gnus-list-range-difference in gnus/gnus-range.el
>>
>> (defun excise-ranges (vector ranges)
>> "Return a list of elements in VECTOR whose indices are not members of
>> RANGES."
>> (loop for number from 0 for elem across vector
>> do (loop while (and ranges (< (cadar ranges) number))
>> do (setq ranges (cdr ranges)))
>> when (or (not ranges) (< number (caar ranges)))
>> collect elem))
>
> Nice! Is the nested loop necessary better than?:
>
> (defun excise-ranges (vector ranges)
> (loop for n from 0
> for elem across vector
> for rr = (member n ranges :key 'cadr :test '<=)
> when (or (not ranges) (< n (caar rr)))
> collect elem))
Silly optimization but only because I failed to say the average number
of ranges would be 1.0001 and we would almost never see more than 2 so
since others are taking care to truncate the range list:
(defun excise-ranges (vector ranges)
(loop for n upfrom 0
for elem across vector
for rrc = ranges then rr
for rr = (member n rrc :key 'cadr :test '<=)
when (or (not rr) (< n (caar rr)))
collect elem))
I still like my "three-liner". :(
kt
From: Madhu
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <m3eiz3xm2q.fsf@moon.robolove.meer.net>
* Kenneth Tilton <·························@cv.net> :
Wrote on Fri, 16 Jan 2009 08:02:22 -0500:
[snip]
| (bk-defun excise-ranges (seq ranges)
| (loop with length = (length seq)
| and s1 = (when (plusp (caar ranges))
| (subseq seq 0 (caar ranges)))
| for (r1 r2) on ranges
| collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
| into ss
| finally (return (apply 'concatenate 'simple-vector s1 ss))))
;; same algorithm as gnus-list-range-difference in gnus/gnus-range.el
(defun excise-ranges (vector ranges)
"Return a list of elements in VECTOR whose indices are not members of
RANGES."
(loop for number from 0 for elem across list
do (loop while (and ranges (< (cadar ranges) number))
do (setq ranges (cdr ranges)))
when (or (not ranges) (< number (caar ranges)))
collect elem))
--
Madhu
From: Madhu
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <m3bpu7xlr3.fsf@moon.robolove.meer.net>
* Kenneth Tilton <·························@cv.net> :
Wrote on Fri, 16 Jan 2009 08:02:22 -0500:
[snip]
| (bk-defun excise-ranges (seq ranges)
| (loop with length = (length seq)
| and s1 = (when (plusp (caar ranges))
| (subseq seq 0 (caar ranges)))
| for (r1 r2) on ranges
| collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
| into ss
| finally (return (apply 'concatenate 'simple-vector s1 ss))))
;; same algorithm as gnus-list-range-difference in gnus/gnus-range.el
(defun excise-ranges (vector ranges)
"Return a list of elements in VECTOR whose indices are not members of
RANGES."
(loop for number from 0 for elem across vector
do (loop while (and ranges (< (cadar ranges) number))
do (setq ranges (cdr ranges)))
when (or (not ranges) (< number (caar ranges)))
collect elem))
--
Madhu
From: Kenneth Tilton
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <49712cf1$0$4908$607ed4bc@cv.net>
Madhu wrote:
> * Kenneth Tilton <·························@cv.net> :
> Wrote on Fri, 16 Jan 2009 08:02:22 -0500:
>
> [snip]
>
> | (bk-defun excise-ranges (seq ranges)
> | (loop with length = (length seq)
> | and s1 = (when (plusp (caar ranges))
> | (subseq seq 0 (caar ranges)))
> | for (r1 r2) on ranges
> | collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
> | into ss
> | finally (return (apply 'concatenate 'simple-vector s1 ss))))
>
>
> ;; same algorithm as gnus-list-range-difference in gnus/gnus-range.el
>
> (defun excise-ranges (vector ranges)
> "Return a list of elements in VECTOR whose indices are not members of
> RANGES."
> (loop for number from 0 for elem across vector
> do (loop while (and ranges (< (cadar ranges) number))
> do (setq ranges (cdr ranges)))
> when (or (not ranges) (< number (caar ranges)))
> collect elem))
Nice! Is the nested loop necessary better than?:
(defun excise-ranges (vector ranges)
(loop for n from 0
for elem across vector
for rr = (member n ranges :key 'cadr :test '<=)
when (or (not ranges) (< n (caar rr)))
collect elem))
kth
In article <·························@cv.net>,
Kenneth Tilton <·········@gmail.com> wrote:
> You are given a simple-vector and a list of malformed ranges, malformed
> in that the second value is the last one to /keep/ vs. what subseq wants
> as the end parameter: the first one to omit. But all ranges are pairs
> (even if only one value is thus delimited) and the pairs are guarnteed
> to be ordered and well-formed and not to go out of bounds, so there is that.
>
> Your mission is to return a simple-vector with those values excised.
>
> (defun excise-ranges (seq ranges)
> ....)
>
> such that:
>
> (excise-ranges #(0 1 2 3) '((0 0)))
> -> #(1 2 3)
>
> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
> -> #(0 30)
>
>
> And do it better than I, which should not be too hard from the looks of
> the mess below (if you scroll down far enough).
>
> hth,kt
>
>
> (bk-defun excise-ranges (seq ranges)
> (loop with length = (length seq)
> and s1 = (when (plusp (caar ranges))
> (subseq seq 0 (caar ranges)))
> for (r1 r2) on ranges
> collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
> into ss
> finally (return (apply 'concatenate 'simple-vector s1 ss))))
(defun excise-ranges (seq ranges)
(loop for (a b) in ranges do
(loop for i from a to b do (setf (elt seq i) '#1=#:zap)))
(remove '#1# seq))
rg
From: Kenneth Tilton
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <49719f28$0$4870$607ed4bc@cv.net>
Ron Garret wrote:
> In article <·························@cv.net>,
> Kenneth Tilton <·········@gmail.com> wrote:
>
>> You are given a simple-vector and a list of malformed ranges, malformed
>> in that the second value is the last one to /keep/ vs. what subseq wants
>> as the end parameter: the first one to omit. But all ranges are pairs
>> (even if only one value is thus delimited) and the pairs are guarnteed
>> to be ordered and well-formed and not to go out of bounds, so there is that.
>>
>> Your mission is to return a simple-vector with those values excised.
>>
>> (defun excise-ranges (seq ranges)
>> ....)
>>
>> such that:
>>
>> (excise-ranges #(0 1 2 3) '((0 0)))
>> -> #(1 2 3)
>>
>> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
>> -> #(0 30)
>>
>>
>> And do it better than I, which should not be too hard from the looks of
>> the mess below (if you scroll down far enough).
>>
>> hth,kt
>>
>>
>> (bk-defun excise-ranges (seq ranges)
>> (loop with length = (length seq)
>> and s1 = (when (plusp (caar ranges))
>> (subseq seq 0 (caar ranges)))
>> for (r1 r2) on ranges
>> collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
>> into ss
>> finally (return (apply 'concatenate 'simple-vector s1 ss))))
>
> (defun excise-ranges (seq ranges)
> (loop for (a b) in ranges do
> (loop for i from a to b do (setf (elt seq i) '#1=#:zap)))
> (remove '#1# seq))
The teacher said we cannot use setf.
Nice, tho. I learned something there about how to use uninterned symbols.
kt
In article <························@cv.net>,
Kenneth Tilton <·········@gmail.com> wrote:
> Ron Garret wrote:
> > In article <·························@cv.net>,
> > Kenneth Tilton <·········@gmail.com> wrote:
> >
> >> You are given a simple-vector and a list of malformed ranges, malformed
> >> in that the second value is the last one to /keep/ vs. what subseq wants
> >> as the end parameter: the first one to omit. But all ranges are pairs
> >> (even if only one value is thus delimited) and the pairs are guarnteed
> >> to be ordered and well-formed and not to go out of bounds, so there is
> >> that.
> >>
> >> Your mission is to return a simple-vector with those values excised.
> >>
> >> (defun excise-ranges (seq ranges)
> >> ....)
> >>
> >> such that:
> >>
> >> (excise-ranges #(0 1 2 3) '((0 0)))
> >> -> #(1 2 3)
> >>
> >> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
> >> -> #(0 30)
> >>
> >>
> >> And do it better than I, which should not be too hard from the looks of
> >> the mess below (if you scroll down far enough).
> >>
> >> hth,kt
> >>
> >>
> >> (bk-defun excise-ranges (seq ranges)
> >> (loop with length = (length seq)
> >> and s1 = (when (plusp (caar ranges))
> >> (subseq seq 0 (caar ranges)))
> >> for (r1 r2) on ranges
> >> collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
> >> into ss
> >> finally (return (apply 'concatenate 'simple-vector s1 ss))))
> >
> > (defun excise-ranges (seq ranges)
> > (loop for (a b) in ranges do
> > (loop for i from a to b do (setf (elt seq i) '#1=#:zap)))
> > (remove '#1# seq))
>
> The teacher said we cannot use setf.
Changing the rules after the game has started? OK, here's a setf-free
version:
(defun excise-ranges (seq ranges)
(coerce
(loop for (a b) on (cons -1 (apply 'append ranges)) by 'cddr
append (coerce (subseq seq (1+ a) b) 'list)) 'simple-vector))
I note in passing that the first version did not depend on the ranges
being in order. This one does.
rg
From: Kenneth Tilton
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <49722517$0$5817$607ed4bc@cv.net>
Ron Garret wrote:
> In article <························@cv.net>,
> Kenneth Tilton <·········@gmail.com> wrote:
>
>> Ron Garret wrote:
>>> In article <·························@cv.net>,
>>> Kenneth Tilton <·········@gmail.com> wrote:
>>>
>>>> You are given a simple-vector and a list of malformed ranges, malformed
>>>> in that the second value is the last one to /keep/ vs. what subseq wants
>>>> as the end parameter: the first one to omit. But all ranges are pairs
>>>> (even if only one value is thus delimited) and the pairs are guarnteed
>>>> to be ordered and well-formed and not to go out of bounds, so there is
>>>> that.
>>>>
>>>> Your mission is to return a simple-vector with those values excised.
>>>>
>>>> (defun excise-ranges (seq ranges)
>>>> ....)
>>>>
>>>> such that:
>>>>
>>>> (excise-ranges #(0 1 2 3) '((0 0)))
>>>> -> #(1 2 3)
>>>>
>>>> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
>>>> -> #(0 30)
>>>>
>>>>
>>>> And do it better than I, which should not be too hard from the looks of
>>>> the mess below (if you scroll down far enough).
>>>>
>>>> hth,kt
>>>>
>>>>
>>>> (bk-defun excise-ranges (seq ranges)
>>>> (loop with length = (length seq)
>>>> and s1 = (when (plusp (caar ranges))
>>>> (subseq seq 0 (caar ranges)))
>>>> for (r1 r2) on ranges
>>>> collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
>>>> into ss
>>>> finally (return (apply 'concatenate 'simple-vector s1 ss))))
>>> (defun excise-ranges (seq ranges)
>>> (loop for (a b) in ranges do
>>> (loop for i from a to b do (setf (elt seq i) '#1=#:zap)))
>>> (remove '#1# seq))
>> The teacher said we cannot use setf.
>
> Changing the rules after the game has started?
Only for certain players.
> OK, here's a setf-free
> version:
>
>
> (defun excise-ranges (seq ranges)
> (coerce
> (loop for (a b) on (cons -1 (apply 'append ranges)) by 'cddr
> append (coerce (subseq seq (1+ a) b) 'list)) 'simple-vector))
Nice. Why not use concatenate and stay as a vector?
kt
>
>
> I note in passing that the first version did not depend on the ranges
> being in order. This one does.
>
> rg
In article <························@cv.net>,
Kenneth Tilton <·········@gmail.com> wrote:
> Ron Garret wrote:
> > In article <························@cv.net>,
> > Kenneth Tilton <·········@gmail.com> wrote:
> >
> >> Ron Garret wrote:
> >>> In article <·························@cv.net>,
> >>> Kenneth Tilton <·········@gmail.com> wrote:
> >>>
> >>>> You are given a simple-vector and a list of malformed ranges, malformed
> >>>> in that the second value is the last one to /keep/ vs. what subseq wants
> >>>> as the end parameter: the first one to omit. But all ranges are pairs
> >>>> (even if only one value is thus delimited) and the pairs are guarnteed
> >>>> to be ordered and well-formed and not to go out of bounds, so there is
> >>>> that.
> >>>>
> >>>> Your mission is to return a simple-vector with those values excised.
> >>>>
> >>>> (defun excise-ranges (seq ranges)
> >>>> ....)
> >>>>
> >>>> such that:
> >>>>
> >>>> (excise-ranges #(0 1 2 3) '((0 0)))
> >>>> -> #(1 2 3)
> >>>>
> >>>> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
> >>>> -> #(0 30)
> >>>>
> >>>>
> >>>> And do it better than I, which should not be too hard from the looks of
> >>>> the mess below (if you scroll down far enough).
> >>>>
> >>>> hth,kt
> >>>>
> >>>>
> >>>> (bk-defun excise-ranges (seq ranges)
> >>>> (loop with length = (length seq)
> >>>> and s1 = (when (plusp (caar ranges))
> >>>> (subseq seq 0 (caar ranges)))
> >>>> for (r1 r2) on ranges
> >>>> collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
> >>>> into ss
> >>>> finally (return (apply 'concatenate 'simple-vector s1 ss))))
> >>> (defun excise-ranges (seq ranges)
> >>> (loop for (a b) in ranges do
> >>> (loop for i from a to b do (setf (elt seq i) '#1=#:zap)))
> >>> (remove '#1# seq))
> >> The teacher said we cannot use setf.
> >
> > Changing the rules after the game has started?
>
> Only for certain players.
>
>
> > OK, here's a setf-free
> > version:
> >
> >
> > (defun excise-ranges (seq ranges)
> > (coerce
> > (loop for (a b) on (cons -1 (apply 'append ranges)) by 'cddr
> > append (coerce (subseq seq (1+ a) b) 'list)) 'simple-vector))
>
> Nice. Why not use concatenate and stay as a vector?
Because I was feeling loopy. But since you brought it up:
(defun excise-ranges (seq rngs &optional (r (cons -1 (apply 'append
rngs))))
(and r (concatenate 'simple-vector (subseq seq (1+ (car r)) (cadr r))
(excise-ranges seq nil (cddr r)))))
rg
From: Kenneth Tilton
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <49725dac$0$20307$607ed4bc@cv.net>
Ron Garret wrote:
> In article <························@cv.net>,
> Kenneth Tilton <·········@gmail.com> wrote:
>
>> Ron Garret wrote:
>>> In article <························@cv.net>,
>>> Kenneth Tilton <·········@gmail.com> wrote:
>>>
>>>> Ron Garret wrote:
>>>>> In article <·························@cv.net>,
>>>>> Kenneth Tilton <·········@gmail.com> wrote:
>>>>>
>>>>>> You are given a simple-vector and a list of malformed ranges, malformed
>>>>>> in that the second value is the last one to /keep/ vs. what subseq wants
>>>>>> as the end parameter: the first one to omit. But all ranges are pairs
>>>>>> (even if only one value is thus delimited) and the pairs are guarnteed
>>>>>> to be ordered and well-formed and not to go out of bounds, so there is
>>>>>> that.
>>>>>>
>>>>>> Your mission is to return a simple-vector with those values excised.
>>>>>>
>>>>>> (defun excise-ranges (seq ranges)
>>>>>> ....)
>>>>>>
>>>>>> such that:
>>>>>>
>>>>>> (excise-ranges #(0 1 2 3) '((0 0)))
>>>>>> -> #(1 2 3)
>>>>>>
>>>>>> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
>>>>>> -> #(0 30)
>>>>>>
>>>>>>
>>>>>> And do it better than I, which should not be too hard from the looks of
>>>>>> the mess below (if you scroll down far enough).
>>>>>>
>>>>>> hth,kt
>>>>>>
>>>>>>
>>>>>> (bk-defun excise-ranges (seq ranges)
>>>>>> (loop with length = (length seq)
>>>>>> and s1 = (when (plusp (caar ranges))
>>>>>> (subseq seq 0 (caar ranges)))
>>>>>> for (r1 r2) on ranges
>>>>>> collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
>>>>>> into ss
>>>>>> finally (return (apply 'concatenate 'simple-vector s1 ss))))
>>>>> (defun excise-ranges (seq ranges)
>>>>> (loop for (a b) in ranges do
>>>>> (loop for i from a to b do (setf (elt seq i) '#1=#:zap)))
>>>>> (remove '#1# seq))
>>>> The teacher said we cannot use setf.
>>> Changing the rules after the game has started?
>> Only for certain players.
>>
>>
>>> OK, here's a setf-free
>>> version:
>>>
>>>
>>> (defun excise-ranges (seq ranges)
>>> (coerce
>>> (loop for (a b) on (cons -1 (apply 'append ranges)) by 'cddr
>>> append (coerce (subseq seq (1+ a) b) 'list)) 'simple-vector))
>> Nice. Why not use concatenate and stay as a vector?
>
> Because I was feeling loopy. But since you brought it up:
>
> (defun excise-ranges (seq rngs &optional (r (cons -1 (apply 'append
> rngs))))
> (and r (concatenate 'simple-vector (subseq seq (1+ (car r)) (cadr r))
> (excise-ranges seq nil (cddr r)))))
Cool! Our first recursive entry! But the teacher said...
kth
From: Kenneth Tilton
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <497b7b63$0$25448$607ed4bc@cv.net>
Kenneth Tilton wrote:
> Ron Garret wrote:
>> In article <························@cv.net>,
>> Kenneth Tilton <·········@gmail.com> wrote:
>>
>>> Ron Garret wrote:
>>>> In article <························@cv.net>,
>>>> Kenneth Tilton <·········@gmail.com> wrote:
>>>>
>>>>> Ron Garret wrote:
>>>>>> In article <·························@cv.net>,
>>>>>> Kenneth Tilton <·········@gmail.com> wrote:
>>>>>>
>>>>>>> You are given a simple-vector and a list of malformed ranges,
>>>>>>> malformed in that the second value is the last one to /keep/ vs.
>>>>>>> what subseq wants as the end parameter: the first one to omit.
>>>>>>> But all ranges are pairs (even if only one value is thus
>>>>>>> delimited) and the pairs are guarnteed to be ordered and
>>>>>>> well-formed and not to go out of bounds, so there is that.
>>>>>>>
>>>>>>> Your mission is to return a simple-vector with those values excised.
>>>>>>>
>>>>>>> (defun excise-ranges (seq ranges)
>>>>>>> ....)
>>>>>>>
>>>>>>> such that:
>>>>>>>
>>>>>>> (excise-ranges #(0 1 2 3) '((0 0)))
>>>>>>> -> #(1 2 3)
>>>>>>>
>>>>>>> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
>>>>>>> -> #(0 30)
>>>>>>>
>>>>>>>
>>>>>>> And do it better than I, which should not be too hard from the
>>>>>>> looks of the mess below (if you scroll down far enough).
>>>>>>>
>>>>>>> hth,kt
>>>>>>>
>>>>>>>
>>>>>>> (bk-defun excise-ranges (seq ranges)
>>>>>>> (loop with length = (length seq)
>>>>>>> and s1 = (when (plusp (caar ranges))
>>>>>>> (subseq seq 0 (caar ranges)))
>>>>>>> for (r1 r2) on ranges
>>>>>>> collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
>>>>>>> into ss
>>>>>>> finally (return (apply 'concatenate 'simple-vector s1 ss))))
>>>>>> (defun excise-ranges (seq ranges)
>>>>>> (loop for (a b) in ranges do
>>>>>> (loop for i from a to b do (setf (elt seq i) '#1=#:zap)))
>>>>>> (remove '#1# seq))
>>>>> The teacher said we cannot use setf.
>>>> Changing the rules after the game has started?
>>> Only for certain players.
>>>
>>>
>>>> OK, here's a setf-free version:
>>>>
>>>>
>>>> (defun excise-ranges (seq ranges)
>>>> (coerce
>>>> (loop for (a b) on (cons -1 (apply 'append ranges)) by 'cddr
>>>> append (coerce (subseq seq (1+ a) b) 'list)) 'simple-vector))
>>> Nice. Why not use concatenate and stay as a vector?
>>
>> Because I was feeling loopy. But since you brought it up:
>>
>> (defun excise-ranges (seq rngs &optional (r (cons -1 (apply 'append
>> rngs))))
>> (and r (concatenate 'simple-vector (subseq seq (1+ (car r)) (cadr r))
>> (excise-ranges seq nil (cddr r)))))
>
> Cool! Our first recursive entry! But the teacher said...
>
uh-oh. A better recursive solution occurred to me:
(defun excise-ranges (seq cuts &optional (start 0))
(if (null cuts)
(subseq seq start)
(concatenate 'simple-vector
(subseq seq start (caar cuts))
(excise-ranges seq (cdr cuts) (1+ (cadar cuts))))))
And indeed I recall from my Logo experience: recursion can be a much
simpler way to iterate. Tho the above copies too much, so:
(defun excise-ranges (seq cuts)
(labels ((keepers (seq cuts &optional (start 0))
(if (null cuts)
(list (subseq seq start))
(cons (subseq seq start (caar cuts))
(keepers seq (cdr cuts) (1+ (cadar cuts)))))))
(apply 'concatenate 'simple-vector (keepers seq cuts))))
Still better than:
(defun excise-ranges (seq ranges)
(coerce
(loop with bounds = (loop for (min max) in ranges
collect min
collect (1+ max))
and collecting = t
for elt across seq
for n upfrom 0
when (and bounds (= n (car bounds)))
do (setf collecting (not collecting))
(pop bounds)
when collecting collect elt)
'simple-vector))
hmm....
From: Bakul Shah
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <49719756.3030802@bitblocks.com>
Kenneth Tilton wrote:
> You are given a simple-vector and a list of malformed ranges, malformed
> in that the second value is the last one to /keep/ vs. what subseq wants
> as the end parameter: the first one to omit. But all ranges are pairs
> (even if only one value is thus delimited) and the pairs are guarnteed
> to be ordered and well-formed and not to go out of bounds, so there is
> that.
>
> Your mission is to return a simple-vector with those values excised.
>
> (defun excise-ranges (seq ranges)
> ....)
>
> such that:
>
> (excise-ranges #(0 1 2 3) '((0 0)))
> -> #(1 2 3)
>
> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
> -> #(0 30)
If closed intervals for elements to be excluded as in your problem
are converted to half open intervals for elements to be *included*,
things might get simpler. As an example, your [1 2] [4 4] becomes
[0 1) [3 4) [5...). Now you can do something like
(defun squeeze (seq ranges)
(reduce #'append
(mapcar
(lambda (r) (apply #'subseq seq (if (consp r) r (list r (length seq)))))
ranges)))
(squeeze '(0 10 20 30 40) '((0 1) (3 4))) => (0 30)
Since append is not generalized for sequences other than lists,
actual solution will be messier.
I'd actually prefer to represent the same range as (0 1 3 4 5)
instead of ((0 1) (3 4) (5 ...)) as one can think of alternating
numbers starting inclusion/exclusion of sequential elements. This
seems like a generally useful idiom. Ideally I should be able to
do e.g.
(squeeze "abcdef" '(0)) => "abcdef"
(squeeze "abcdef" '(0 1) => "a"
(squeeze "abcdef" '(0 1 3) => "adef"
(squeeze "abcdef" '(0 1 3 4) => "ad"
(squeeze "abcdef" '(0 1 3 4 5) => "adf"
From: Kenneth Tilton
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <49719e77$0$4901$607ed4bc@cv.net>
Bakul Shah wrote:
> Kenneth Tilton wrote:
>> You are given a simple-vector and a list of malformed ranges,
>> malformed in that the second value is the last one to /keep/ vs. what
>> subseq wants as the end parameter: the first one to omit. But all
>> ranges are pairs (even if only one value is thus delimited) and the
>> pairs are guarnteed to be ordered and well-formed and not to go out of
>> bounds, so there is that.
>>
>> Your mission is to return a simple-vector with those values excised.
>>
>> (defun excise-ranges (seq ranges)
>> ....)
>>
>> such that:
>>
>> (excise-ranges #(0 1 2 3) '((0 0)))
>> -> #(1 2 3)
>>
>> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
>> -> #(0 30)
>
> If closed intervals for elements to be excluded as in your problem
> are converted to half open intervals for elements to be *included*,
> things might get simpler.
I thought that might be a fun way to do it, albeit excessive by some
measure that did not appear clearly to me in my usual mist.
As an example, your [1 2] [4 4] becomes
> [0 1) [3 4) [5...). Now you can do something like
>
> (defun squeeze (seq ranges)
> (reduce #'append
> (mapcar
> (lambda (r) (apply #'subseq seq (if (consp r) r (list r (length
> seq)))))
> ranges)))
>
> (squeeze '(0 10 20 30 40) '((0 1) (3 4))) => (0 30)
>
> Since append is not generalized for sequences other than lists,
> actual solution will be messier.
>
> I'd actually prefer to represent the same range as (0 1 3 4 5)
> instead of ((0 1) (3 4) (5 ...)) as one can think of alternating
> numbers starting inclusion/exclusion of sequential elements. This
> seems like a generally useful idiom.
Did you see my "three line" solution that came out to ten? I also took
the second "max" value and incremented it to be an "end" value.
kt
>... Ideally I should be able to
> do e.g.
>
> (squeeze "abcdef" '(0)) => "abcdef"
> (squeeze "abcdef" '(0 1) => "a"
> (squeeze "abcdef" '(0 1 3) => "adef"
> (squeeze "abcdef" '(0 1 3 4) => "ad"
> (squeeze "abcdef" '(0 1 3 4 5) => "adf"
(defun excise-ranges (seq ranges)
(flet ((in-range (i)
(some (lambda (range) (<= (car range) i (cadr range)))
ranges)))
(coerce
(loop for i from 0
for e across seq
unless (in-range i) collect e)
'simple-vector)))
Wade
On Jan 18, 12:34 pm, Wade <·············@gmail.com> wrote:
> On Jan 17, 5:11 pm, Wade <·············@gmail.com> wrote:
>
> > (defun excise-ranges (seq ranges)
> > (flet ((in-range (i)
> > (some (lambda (range) (<= (car range) i (cadr range)))
> > ranges)))
> > (coerce
> > (loop for i from 0
> > for e across seq
> > unless (in-range i) collect e)
> > 'simple-vector)))
>
> > Wade
>
> Based on Kevin's insight I would change my version to,
>
> (defun excise-ranges (seq ranges &aux (i 0))
> (flet ((in-ranges (e) (declare (ignore e))
> (prog1
> (some (lambda (r) (<= (car r) i (cadr r))) ranges)
> (incf i))))
> (remove-if #'in-ranges seq)))
>
> Wade
I've never really liked using the &aux parameter like that, if it's
only purpose here is to make the code one line shorter, by removing a
let.
Also, you'd stick a prog1 inside an implict progn just to avoid
initializing i to -1 and doing the incf first? I mean if you are
trying to cut lines ;)
Kevin
From: Kenneth Tilton
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <4973a771$0$20294$607ed4bc@cv.net>
K Livingston wrote:
> On Jan 18, 12:34 pm, Wade <·············@gmail.com> wrote:
>> On Jan 17, 5:11 pm, Wade <·············@gmail.com> wrote:
>>
>>> (defun excise-ranges (seq ranges)
>>> (flet ((in-range (i)
>>> (some (lambda (range) (<= (car range) i (cadr range)))
>>> ranges)))
>>> (coerce
>>> (loop for i from 0
>>> for e across seq
>>> unless (in-range i) collect e)
>>> 'simple-vector)))
>>> Wade
>> Based on Kevin's insight I would change my version to,
>>
>> (defun excise-ranges (seq ranges &aux (i 0))
>> (flet ((in-ranges (e) (declare (ignore e))
>> (prog1
>> (some (lambda (r) (<= (car r) i (cadr r))) ranges)
>> (incf i))))
>> (remove-if #'in-ranges seq)))
>>
>> Wade
>
>
> I've never really liked using the &aux parameter like that, if it's
> only purpose here is to make the code one line shorter, by removing a
> let.
Interesting. I resent giving up a level of indentation just to get one
lousy local variable.
>
> Also, you'd stick a prog1 inside an implict progn just to avoid
> initializing i to -1 and doing the incf first? I mean if you are
> trying to cut lines ;)
Puh-leaze! Initialization to -1 screams obfuscation, while using a
variable initialized to a sensible variable and then incrementing it...
well, hang on, I do not want to say a word in favor of any nonsense in
which a predicate has a side effect. Clearly we have reached the point
of diminishing return, the horse is rightly dead and fully beaten, the
fat lady has sung... this, in a word, is an ex-challenge.
kth
>
> Kevin
>
From: Pascal Costanza
Subject: Re: Straight From the Trenches Nooby Stumper Dunk the Kenny Gotta Be A Shorter Cleaner Way #26
Date:
Message-ID: <6teelcFa9ktcU1@mid.individual.net>
Kenneth Tilton wrote:
> You are given a simple-vector and a list of malformed ranges, malformed
> in that the second value is the last one to /keep/ vs. what subseq wants
> as the end parameter: the first one to omit. But all ranges are pairs
> (even if only one value is thus delimited) and the pairs are guarnteed
> to be ordered and well-formed and not to go out of bounds, so there is
> that.
>
> Your mission is to return a simple-vector with those values excised.
>
> (defun excise-ranges (seq ranges)
> ....)
>
> such that:
>
> (excise-ranges #(0 1 2 3) '((0 0)))
> -> #(1 2 3)
>
> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
> -> #(0 30)
Using the LispWorks multiprocessing API:
(defconstant +nof-cores+ 4)
(defstruct (rep (:constructor make-rep (target source length)))
target source length)
(defun extract-ranges (target source reps)
(declare (vector source target reps))
(loop with reps-per-core = (ceiling (length reps) +nof-cores+)
with mailbox = (mp:make-mailbox :size +nof-cores+)
for index from 0 to (length reps) by reps-per-core
for count from 0 do
(let ((index index))
(mp:process-run-function
"extract ranges" '()
(lambda ()
(loop for i from index below (min (+ index reps-per-core)
(length reps))
for rep = (aref reps i) do
(replace target source
:start1 (rep-target rep)
:end1 (+ (rep-target rep) (rep-length rep))
:start2 (rep-source rep)
:end2 (+ (rep-source rep) (rep-length rep)))
finally (mp:mailbox-send mailbox 'done)))))
finally (loop repeat count do
(assert (eq (mp:mailbox-read mailbox) 'done))
finally (return-from extract-ranges target))))
(defun excise-ranges (sequence ranges)
(loop with reps = (make-array (ceiling (length sequence) 2)
:adjustable t :fill-pointer 0)
for target = 0 then (+ target length)
for source = 0 then (1+ upper)
for (lower upper) in ranges
for length = (- lower source)
unless (zerop length)
do (vector-push-extend (make-rep target source length) reps)
finally
(let ((length (- (length sequence) upper 1)))
(unless (zerop length)
(vector-push-extend (make-rep target source length) reps))
(return (extract-ranges
(make-array (+ target length))
sequence
reps)))))
Only lightly tested, without any guarantees that this is actually
efficient. (It's probably not, so consider this more as an exercise.)
What would a Clojure version look like?
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 Jan 16, 7:02 am, Kenneth Tilton <·········@gmail.com> wrote:
> You are given a simple-vector and a list of malformed ranges, malformed
> in that the second value is the last one to /keep/ vs. what subseq wants
> as the end parameter: the first one to omit. But all ranges are pairs
> (even if only one value is thus delimited) and the pairs are guarnteed
> to be ordered and well-formed and not to go out of bounds, so there is that.
>
> Your mission is to return a simple-vector with those values excised.
>
> (defun excise-ranges (seq ranges)
> ....)
>
> such that:
>
> (excise-ranges #(0 1 2 3) '((0 0)))
> -> #(1 2 3)
>
> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
> -> #(0 30)
>
> And do it better than I, which should not be too hard from the looks of
> the mess below (if you scroll down far enough).
>
> hth,kt
>
> (bk-defun excise-ranges (seq ranges)
> (loop with length = (length seq)
> and s1 = (when (plusp (caar ranges))
> (subseq seq 0 (caar ranges)))
> for (r1 r2) on ranges
> collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
> into ss
> finally (return (apply 'concatenate 'simple-vector s1 ss))))
Ok, because it's cute, here's one just using REMOVE-IF (and a little
(disgusting) side effecting inside of the remove call).
(defun excise-ranges (v ranges)
(let ((i -1))
(remove-if #'(lambda (x)
(in-range x ranges))
v
:key #'(lambda (x)
(declare (ignore x))
(incf i)))))
I guess actually, the test could also be #'identity and key could call
in-range. For this to be fast I'm assuming remove (and a single pass
only) is more efficient than the setf needed for incf?
Since you said there would be few ranges, I stole Wade's in-range
function...
(defun in-range (i ranges)
(some #'(lambda (range)
(<= (car range) i (cadr range)))
ranges))
If the range list is ordered, and if you wanted to be a little more
sick with the side effecting inside of remove,... only check the first
interval, once you have exceeded it remove it from the ranges list.
If there are many intervals that would save you a lot of traversing of
the ranges list.
I know I wrote it, but I'm not sure if it's too weird to use. It
works, though.
Kevin
On Jan 16, 5:02 am, Kenneth Tilton <·········@gmail.com> wrote:
> You are given a simple-vector and a list of malformed ranges, malformed
> in that the second value is the last one to /keep/ vs. what subseq wants
> as the end parameter: the first one to omit. But all ranges are pairs
> (even if only one value is thus delimited) and the pairs are guarnteed
> to be ordered and well-formed and not to go out of bounds, so there is that.
>
> Your mission is to return a simple-vector with those values excised.
>
> (defun excise-ranges (seq ranges)
> ....)
>
> such that:
>
> (excise-ranges #(0 1 2 3) '((0 0)))
> -> #(1 2 3)
>
> (excise-ranges #(0 10 20 30 40) '((1 2)(4 4)))
> -> #(0 30)
>
> And do it better than I, which should not be too hard from the looks of
> the mess below (if you scroll down far enough).
>
> hth,kt
>
> (bk-defun excise-ranges (seq ranges)
> (loop with length = (length seq)
> and s1 = (when (plusp (caar ranges))
> (subseq seq 0 (caar ranges)))
> for (r1 r2) on ranges
> collect (subseq seq (1+ (cadr r1)) (if r2 (car r2) length))
> into ss
> finally (return (apply 'concatenate 'simple-vector s1 ss))))
(defun er (vector ranges)
(let ((vec (make-array (length vector) :fill-pointer 0))
(idx 0))
(dolist (r ranges vec)
(dotimes (n (- (car r) idx))
(vector-push (aref vector (+ idx n)) vec))
(setf idx (1+ (cadr r))))))
(print (er #(0 1 2 3 4 5 6 7 8 9) '((1 2) (4 4) (8 50))))
Well I do not return a real vector, but close, vectorp still returns
that it's a vector, but in fact it's (array t (*)) - all because I'm
using :fill-pointer
And coerce won't help it... but I think it's fine...