# A little algorithmic help requested

**URL:** <https://rubytalk.org/t/a-little-algorithmic-help-requested/12508>\
**Category:** ruby-talk\
**Created:** [11 July 2004 07:10 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508 "2004-07-11T07:10:34Z")\
**Posts on this page:** 3\
**Page:** 2

<div class="post-metadata">

**Author:** ![David\_A\_Black3](https://avatars.discourse-cdn.com/v4/letter/d/6a8cbe/32.png) [@David\_A\_Black3](https://rubytalk.org/u/David_A_Black3)\
**Post date:** [12 July 2004 14:40 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/21 "2004-07-12T14:40:03Z")

</div>

Hi --

> "Jason Creighton" \<androflux@softhome.net.remove.to.reply\> schrieb im  
> Newsbeitrag  
> news:20040711153514.4b895d41.androflux@softhome.net.remove.to.reply...  
> \>  
> \> \> 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 🙂

&nbsp;&nbsp;def to\_ranges  
&nbsp;&nbsp;&nbsp;&nbsp;values\_at(\*(0...size).find\_all {|i|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;at(i) != at(i-1) + 1 }).zip(  
&nbsp;&nbsp;&nbsp;&nbsp;values\_at(\*(0...size).find\_all {|i|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;at(i) != at(i+1) - 1 rescue true })).  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;map {|a,b| Range.new(a,b) }  
&nbsp;&nbsp;end

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

David

> **···**
>
> On Mon, 12 Jul 2004, Robert Klemme wrote:
> 
> > \> On Sun, 11 Jul 2004 16:10:34 +0900, \> \> Hal Fulton \<hal9000@hypermetrics.com\> wrote:
> 
> --  
> David A. Black  
> dblack@wobblini.net

---

<div class="post-metadata">

**Author:** ![Jason\_Creighton3](https://avatars.discourse-cdn.com/v4/letter/j/e19adc/32.png) [@Jason\_Creighton3](https://rubytalk.org/u/Jason_Creighton3)\
**Post date:** [13 July 2004 04:07 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/22 "2004-07-13T04:07:22Z")

</div>

> "Jason Creighton" \<androflux@softhome.net.remove.to.reply\> schrieb im  
> Newsbeitrag  
> news:20040711153514.4b895d41.androflux@softhome.net.remove.to.reply...  
> \>  
> \> \> 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"! 🙂

Oh, right, that would be easier. 🙂

> 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.

I realized I was doing this, but I didn't think the performance hit  
would be that much. But doing it a nicer was is much faster:

~/prog/rb$ ruby range-problem.rb  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;user system total real  
to\_ranges 2.340000 0.000000 2.340000 ( 2.338682)  
to\_ranges2 0.410000 0.000000 0.410000 ( 0.400007)

range-problem.rb:  
#! /usr/bin/ruby -w

# NOTE: to\_ranges assumes sorted object.

module Enumerable  
&nbsp;&nbsp;def to\_ranges  
&nbsp;&nbsp;&nbsp;&nbsp;ranges = Array.new  
&nbsp;&nbsp;&nbsp;&nbsp;self.each do |e|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if ranges[-1] == nil or ranges[-1].end.succ != e  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges \<\< Range.new(e,e)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges[-1] = Range.new(ranges[-1].begin, e)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;return ranges  
&nbsp;&nbsp;end

&nbsp;&nbsp;def to\_ranges2  
&nbsp;&nbsp;&nbsp;&nbsp;ranges = Array.new  
&nbsp;&nbsp;&nbsp;&nbsp;low, high = nil, nil  
&nbsp;&nbsp;&nbsp;&nbsp;self.each do |e|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if low == nil  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# First item in collection  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;low, high = e,e  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elsif high.succ != e  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# We hit something out of sequence  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges \<\< Range.new(low,high)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;low, high = e, e  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;high = e  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;ranges \<\< Range.new(low,high)  
&nbsp;&nbsp;&nbsp;&nbsp;return ranges  
&nbsp;&nbsp;end  
end

if \_\_FILE\_\_ == $0  
&nbsp;&nbsp;require 'benchmark'  
&nbsp;&nbsp;Benchmark.bm(10) do |b|  
&nbsp;&nbsp;&nbsp;&nbsp;b.report("to\_ranges") { (1..2\*\*16).to\_ranges }  
&nbsp;&nbsp;&nbsp;&nbsp;b.report("to\_ranges2") { (1..2\*\*16).to\_ranges2 }  
&nbsp;&nbsp;end  
end

Jason Creighton

> **···**
>
> On Mon, 12 Jul 2004 15:47:41 +0200, "Robert Klemme" \<bob.news@gmx.net\> wrote:
> 
> > \> On Sun, 11 Jul 2004 16:10:34 +0900, \> \> Hal Fulton \<hal9000@hypermetrics.com\> wrote:

---

<div class="post-metadata">

**Author:** ![Robert](https://avatars.discourse-cdn.com/v4/letter/r/e95f7d/32.png) [@Robert](https://rubytalk.org/u/Robert)\
**Post date:** [13 July 2004 08:22 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/23 "2004-07-13T08:22:23Z")

</div>

"Jason Creighton" \<androflux@softhome.net.remove.to.reply\> schrieb im  
Newsbeitrag  
news:20040712105553.44b0cf99.androflux@softhome.net.remove.to.reply...

> \>  
> \> "Jason Creighton" \<androflux@softhome.net.remove.to.reply\> schrieb im  
> \> Newsbeitrag  
> \> news:20040711153514.4b895d41.androflux@softhome.net.remove.to.reply...  
> \> \>  
> \> \> \> 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"! 🙂
> 
> Oh, right, that would be easier. 🙂
> 
> \> 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.
> 
> I realized I was doing this, but I didn't think the performance hit  
> would be that much. But doing it a nicer was is much faster:

See? 🙂

> ~/prog/rb$ ruby range-problem.rb  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;user system total real  
> to\_ranges 2.340000 0.000000 2.340000 ( 2.338682)  
> to\_ranges2 0.410000 0.000000 0.410000 ( 0.400007)

That's quite some difference. Wow!

> range-problem.rb:  
> #! /usr/bin/ruby -w
> 
> # NOTE: to\_ranges assumes sorted object.
> 
> module Enumerable  
> &nbsp;&nbsp;def to\_ranges  
> &nbsp;&nbsp;&nbsp;&nbsp;ranges = Array.new  
> &nbsp;&nbsp;&nbsp;&nbsp;self.each do |e|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if ranges[-1] == nil or ranges[-1].end.succ != e  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges \<\< Range.new(e,e)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges[-1] = Range.new(ranges[-1].begin, e)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;return ranges  
> &nbsp;&nbsp;end
> 
> &nbsp;&nbsp;def to\_ranges2  
> &nbsp;&nbsp;&nbsp;&nbsp;ranges = Array.new  
> &nbsp;&nbsp;&nbsp;&nbsp;low, high = nil, nil  
> &nbsp;&nbsp;&nbsp;&nbsp;self.each do |e|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if low == nil  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# First item in collection  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;low, high = e,e  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elsif high.succ != e  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# We hit something out of sequence  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges \<\< Range.new(low,high)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;low, high = e, e  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;high = e  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;ranges \<\< Range.new(low,high)  
> &nbsp;&nbsp;&nbsp;&nbsp;return ranges  
> &nbsp;&nbsp;end  
> end

Now you've implemented it basically the same way I did (as far as I  
remember). 🙂 Thanks for the measuremets!

Regards

&nbsp;&nbsp;&nbsp;&nbsp;robert

> **···**
>
> > On Mon, 12 Jul 2004 15:47:41 +0200, \> "Robert Klemme" \<bob.news@gmx.net\> wrote:  
> > \> \> On Sun, 11 Jul 2004 16:10:34 +0900, \> \> \> Hal Fulton \<hal9000@hypermetrics.com\> wrote:

[Previous page](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508.md?page=1)