From: "David A. Black" <dblack@...>
Date: 2004-07-12T23:40:03+09:00
Subject: Re: A little algorithmic help requested...

Hi --

On Mon, 12 Jul 2004, Robert Klemme wrote:

> 
> "Jason Creighton" <androflux@softhome.net.remove.to.reply> schrieb im
> Newsbeitrag
> news:20040711153514.4b895d41.androflux@softhome.net.remove.to.reply...
> > On Sun, 11 Jul 2004 16:10:34 +0900,
> > Hal Fulton <hal9000@hypermetrics.com> wrote:
> >
> > > Here's a problem my tired brain is having trouble with.
> > >
> > > Given a sorted array of integers, convert them into as many
> > > ranges as possible (ranges of three or more).
> > >
> > > Example:
> > > [1,2,3,4,6,7,8,11,12,15,16,17] ==> [1..4,6..8,11,12,15..17]
> > >
> > > How would *you* do this?
> >
> > Here's one that doesn't follow that "need at least three of more"
> > limitation, but it's how *I* would do it, because it returns an array of
> > *only* ranges, which seems like it would be more fun to deal with that a
> > mix of ranges and numbers.
> >
> > module Enumerable
> >   def to_ranges
> >     ranges = Array.new
> >     self.sort.each do |e|
> >       if ranges[-1] == nil or ranges[-1].end.succ != e
> >         ranges << Range.new(e,e)
> >         next
> >       end
> >       ranges[-1] = Range.new(ranges[-1].begin, e)
> >     end
> >     return ranges
> >   end
> > end
> 
> Nice and short, although I'd use "else" instead of "next"! :-)
> 
> However, there is a performance drawback: you recreate ranges all over
> again.  In the worst case of an array that contains all numbers from 1 to
> 1000 you create 999 Range instances and keep only one of them.  That's not
> efficient.  IMHO a solution in module Enumerable (i.e. a general solution)
> should do better with respect to time and space.

Just for fun, here's a "purely functional" version, though not
suitable for Enumerable because it uses size, and not very robust
because it doesn't sort... but, like I said, just for fun :-)

  def to_ranges
    values_at(*(0...size).find_all {|i|
                at(i) != at(i-1) + 1 }).zip(
    values_at(*(0...size).find_all {|i|
                at(i) != at(i+1) - 1 rescue true })).
      map {|a,b| Range.new(a,b) }
  end

(Annoyingly repetitve as to code... could of course be split out.)


David

-- 
David A. Black
dblack@wobblini.net