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.
On Jan 16, 2:02 pm, Kenneth Tilton <kentil...@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)))
* Kenneth Tilton <49708557$0$20284$607ed...@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
* Kenneth Tilton <49708557$0$20284$607ed...@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
Willem Broekema wrote: > On Jan 16, 2:02 pm, Kenneth Tilton <kentil...@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)
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.
Kenneth Tilton <kentil...@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 (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)
> 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.
> ;; 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))
>> * Kenneth Tilton <49708557$0$20284$607ed...@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))
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.
On Jan 17, 3:13 am, Ariel Badichi <a...@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.
> 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.
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.
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
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.
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.
> 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.
> 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.
Ron Garret wrote: > In article <49708557$0$20284$607ed...@cv.net>, > Kenneth Tilton <kentil...@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.
> 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.
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.
> Ron Garret wrote: > > In article <49708557$0$20284$607ed...@cv.net>, > > Kenneth Tilton <kentil...@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) > > (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.
> 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 wrote: > On Jan 17, 2:42 am, Ariel Badichi <a...@tidexsystems.com> wrote: >> On Jan 17, 3:13 am, Ariel Badichi <a...@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.
> > 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)))))
Ron Garret wrote: > In article <49719f28$0$4870$607ed...@cv.net>, > Kenneth Tilton <kentil...@gmail.com> wrote:
>> Ron Garret wrote: >>> In article <49708557$0$20284$607ed...@cv.net>, >>> Kenneth Tilton <kentil...@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.
>>>> 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?
> Adde wrote: > > On Jan 17, 2:42 am, Ariel Badichi <a...@tidexsystems.com> wrote: > >> On Jan 17, 3:13 am, Ariel Badichi <a...@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...).
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)
|
