# 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:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![HAL\_9000](https://avatars.discourse-cdn.com/v4/letter/h/90ced4/32.png) [@HAL\_9000](https://rubytalk.org/u/HAL_9000)\
**Post date:** [11 July 2004 07:10 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/1 "2004-07-11T07:10:34Z")

</div>

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?

Thanks,  
Hal

---

<div class="post-metadata">

**Author:** ![H.Yamamoto](https://avatars.discourse-cdn.com/v4/letter/h/eb9ed0/32.png) [@H.Yamamoto](https://rubytalk.org/u/H.Yamamoto)\
**Post date:** [11 July 2004 08:21 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/2 "2004-07-11T08:21:29Z")

</div>

Hello.

> [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?

How about this? It seems working.

a = [1,2,3,4,6,7,8,11,12,15,16,17]  
b =

i = 0  
(0..a.size).each do |j|  
&nbsp;&nbsp;if (j == a.size) || (j - i != a[j] - a[i])  
&nbsp;&nbsp;&nbsp;&nbsp;case j - i  
&nbsp;&nbsp;&nbsp;&nbsp;when 0  
&nbsp;&nbsp;&nbsp;&nbsp;when 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b \<\< a[i]  
&nbsp;&nbsp;&nbsp;&nbsp;when 2  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b \<\< a[i] \<\< a[i+1]  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b \<\< (a[i]..a[j-1])  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;i = j  
&nbsp;&nbsp;end  
end

p b # [1..4, 6..8, 11, 12, 15..17]

---

<div class="post-metadata">

**Author:** ![Jeffrey\_Dik](https://avatars.discourse-cdn.com/v4/letter/j/a87d85/32.png) [@Jeffrey\_Dik](https://rubytalk.org/u/Jeffrey_Dik)\
**Post date:** [11 July 2004 08:22 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/3 "2004-07-11T08:22:50Z")

</div>

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

At 4:20am, I'd do it like this

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a = [1,2,3,4,6,7,8,11,12,15,16,17]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;def to\_ranges(a)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges = [a[0]..a[0]]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a.shift  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a.each\_index { |i|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if ranges.last.last + 1 == a[i]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges[-1] = ranges.last.first..a[i]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges.push(a[i]..a[i])  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges.map! { |r|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case r.last-r.first  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when 0  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r = r.first  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r = [r.first, r.last]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges.flatten  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;puts to\_ranges(a)

I'm guessing I'd do it differently at a some other time in the day 🙂

Sleepy time,  
Jeff

> **···**
>
> On Sun, Jul 11, 2004 at 04:10:34PM +0900, Hal Fulton wrote:
> 
> > Thanks,  
> > Hal

---

<div class="post-metadata">

**Author:** ![CT1](https://avatars.discourse-cdn.com/v4/letter/c/f6c823/32.png) [@CT1](https://rubytalk.org/u/CT1)\
**Post date:** [11 July 2004 08:22 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/4 "2004-07-11T08:22:53Z")

</div>

Hiya,

I may not have read you correctly, but does this do what you seek?

> **···**
>
> --  
> require 'pp'  
> a = [1,2,3,4,6,7,8,11,12,15,16,17]  
> pp a.inject([[a.shift]]) {|arr,i|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp = arr.last  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(temp.last.next == i)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp \<\< i  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arr \<\< [i]  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arr  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}.inject() {|arr,i|  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(i.length \>= 3)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arr\<\<(i.first..i.last)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;arr = arr + i  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
> --  
> Gives me: [1,2,3,4,6,7,8,11,12,15,16,17]  
> First inject collects all consecutive ranges into sub-arrays, second  
> one converts these to ranges/flattened arrays.  
> corrections/improvements are welcome.  
> HTH  
> - CT
> 
> 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?
> > 
> > Thanks,  
> > Hal

---

<div class="post-metadata">

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

</div>

def ranges(list, min\_range\_size=3)  
&nbsp;&nbsp;&nbsp;&nbsp;curr = # The current group as we traverse the input list.  
&nbsp;&nbsp;&nbsp;&nbsp;groups = [curr] # e.g. [[1,2,3,4], [6,7,8], [11], ...]  
&nbsp;&nbsp;&nbsp;&nbsp;list.each do |n|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# Either N fits into the current group (curr), or it begins a  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# new one.  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if curr.empty?  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curr \<\< n  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elsif curr.last == n - 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curr \<\< n  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curr = [n]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;groups \<\< curr  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# Now we turn the groups into ranges.  
&nbsp;&nbsp;&nbsp;&nbsp;result =   
&nbsp;&nbsp;&nbsp;&nbsp;groups.each do |g|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if g.size \< min\_range\_size  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result.concat g  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result \<\< (g.first .. g.last)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;result.compact  
&nbsp;&nbsp;end

&nbsp;&nbsp;require 'test/unit'  
&nbsp;&nbsp;class RangeTest \< Test::Unit::TestCase  
&nbsp;&nbsp;&nbsp;&nbsp;def test\_range  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal([1], ranges([1]))  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal([1,2], ranges([1,2]))  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal([1..3], ranges([1,2,3]))  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal([1..4,6], ranges([1,2,3,4,6]))  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal([1,2,3,4,6], ranges([1,2,3,4,6], 10))  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal([1..4,6..8,11,12,15..17], ranges([1,2,3,4,6,7,8,11,12,15,16,17]))  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal([1..4,6..8,11..12,15..17], ranges([1,2,3,4,6,7,8,11,12,15,16,17], 2))  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal([1..1,3..3,5..5,7..7], ranges([1,3,5,7], 1))  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;assert\_equal([1..4,6..6,8..9], ranges([1,2,3,4,6,8,9], 0))  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end

Cheers,  
Gavin

> **···**
>
> On Sunday, July 11, 2004, 5:10:34 PM, Hal 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?

---

<div class="post-metadata">

**Author:** ![George\_Ogata1](https://avatars.discourse-cdn.com/v4/letter/g/d9b06d/32.png) [@George\_Ogata1](https://rubytalk.org/u/George_Ogata1)\
**Post date:** [11 July 2004 10:37 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/6 "2004-07-11T10:37:27Z")

</div>

Hal Fulton \<hal9000@hypermetrics.com\> writes:

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

Interesting one to golf with:

a.each\_index{|i|a[i..j=i+2]==[x=a[i],x+1,x+2]and(0while a[j]+1==a[j+=1];a[i..j-=1]=a[i]..a[j])}

---

<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:** [11 July 2004 12:31 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/7 "2004-07-11T12:31:37Z")

</div>

Hi --

> **···**
>
> On Sun, 11 Jul 2004, Hal Fulton 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?
> 
> Haven't tried yet -- but see also:
> 
> > **[WebMD - Better information. Better health.](https://www.webmd.com/?CodingChallenge0001)**
> >
> > The leading source for trustworthy and timely health and medical news and information. Providing credible health information, supportive community, and educational services by blending award-winning expertise in content, community services, expert...
> 
> David
> 
> --  
> David A. Black  
> dblack@wobblini.net

---

<div class="post-metadata">

**Author:** ![Jim\_Haungs](https://avatars.discourse-cdn.com/v4/letter/j/ce7236/32.png) [@Jim\_Haungs](https://rubytalk.org/u/Jim_Haungs)\
**Post date:** [11 July 2004 16:12 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/8 "2004-07-11T16:12:26Z")

</div>

Here's an iterator approach.

The maximum group size and the splitting criterion can be  
parameterized.

def groups(anArray, split)  
&nbsp;&nbsp;list =   
&nbsp;&nbsp;anArray.each do | n |  
&nbsp;&nbsp;&nbsp;&nbsp;if list.empty? or split[list.last, n]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list \<\< n  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;yield list  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list = [n]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;yield list  
end

def ranges(anArray, maxGroupSize, split)  
&nbsp;&nbsp;groups(anArray, split) do | group |  
&nbsp;&nbsp;&nbsp;&nbsp;if group.size \> maxGroupSize then  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;yield group  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group.each {|g| yield [g]}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
end

test = [1,2,3,4,6,7,8,11,12,15,16,17,18]

maxGroupSize = 2  
criterion = proc{|x,y| x.succ == y}  
ranges(test, maxGroupSize, criterion) { | range | p range }  
&nbsp;&nbsp;  
[1, 2, 3, 4]  
[6, 7, 8]  
[11]  
[12]  
[15, 16, 17, 18]

> **···**
>
> 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?
> > 
> > Thanks,  
> > Hal

---

<div class="post-metadata">

**Author:** ![Jim\_Haungs](https://avatars.discourse-cdn.com/v4/letter/j/ce7236/32.png) [@Jim\_Haungs](https://rubytalk.org/u/Jim_Haungs)\
**Post date:** [11 July 2004 16:17 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/9 "2004-07-11T16:17:26Z")

</div>

Here's an iterator approach.

The maximum group size and the splitting criterion can be  
parameterized.

def groups(anArray, split)  
&nbsp;&nbsp;list =   
&nbsp;&nbsp;anArray.each do | n |  
&nbsp;&nbsp;&nbsp;&nbsp;if list.empty? or split[list.last, n]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list \<\< n  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;yield list  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list = [n]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;yield list  
end

def ranges(anArray, maxGroupSize, split)  
&nbsp;&nbsp;groups(anArray, split) do | group |  
&nbsp;&nbsp;&nbsp;&nbsp;if group.size \> maxGroupSize then  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;yield group  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group.each {|g| yield [g]}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
end

test = [1,2,3,4,6,7,8,11,12,15,16,17,18]

maxGroupSize = 2  
criterion = proc{|x,y| x.succ == y}  
ranges(test, maxGroupSize, criterion) { | range | p range }  
&nbsp;&nbsp;  
[1, 2, 3, 4]  
[6, 7, 8]  
[11]  
[12]  
[15, 16, 17, 18]

> **···**
>
> 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?
> > 
> > Thanks,  
> > Hal

---

<div class="post-metadata">

**Author:** ![Jim\_Haungs](https://avatars.discourse-cdn.com/v4/letter/j/ce7236/32.png) [@Jim\_Haungs](https://rubytalk.org/u/Jim_Haungs)\
**Post date:** [11 July 2004 16:17 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/10 "2004-07-11T16:17:26Z")

</div>

Here's an iterator approach.

The maximum group size and the splitting criterion can be  
parameterized.

def groups(anArray, split)  
&nbsp;&nbsp;list =   
&nbsp;&nbsp;anArray.each do | n |  
&nbsp;&nbsp;&nbsp;&nbsp;if list.empty? or split[list.last, n]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list \<\< n  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;yield list  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;list = [n]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;yield list  
end

def ranges(anArray, maxGroupSize, split)  
&nbsp;&nbsp;groups(anArray, split) do | group |  
&nbsp;&nbsp;&nbsp;&nbsp;if group.size \> maxGroupSize then  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;yield group  
&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;group.each {|g| yield [g]}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;end  
end

test = [1,2,3,4,6,7,8,11,12,15,16,17,18]

maxGroupSize = 2  
criterion = proc{|x,y| x.succ == y}  
ranges(test, maxGroupSize, criterion) { | range | p range }  
&nbsp;&nbsp;  
[1, 2, 3, 4]  
[6, 7, 8]  
[11]  
[12]  
[15, 16, 17, 18]

> **···**
>
> 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?
> > 
> > Thanks,  
> > Hal

---

<div class="post-metadata">

**Author:** ![George5](https://avatars.discourse-cdn.com/v4/letter/g/7c8e57/32.png) [@George5](https://rubytalk.org/u/George5)\
**Post date:** [11 July 2004 17:09 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/11 "2004-07-11T17:09:47Z")

</div>

require 'enumerator'

&nbsp;&nbsp;def to\_range(arr)  
&nbsp;&nbsp;&nbsp;&nbsp;ranges = [r=]  
&nbsp;&nbsp;&nbsp;&nbsp;arr.each\_cons(2) {|a,b|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r \<\< a  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges \<\< (r = ) if (b-a) != 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r \<\< b  
&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;ranges.map {|r|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r.uniq!  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r.size \> 2 ? (r.first..r.last) : r  
&nbsp;&nbsp;&nbsp;&nbsp;}.flatten  
&nbsp;&nbsp;end

&nbsp;&nbsp;a = [1,2,3,4,6,7,8,11,12,15,16,17]  
&nbsp;&nbsp;p to\_range(a)

But no, I wouldn't do it this way.

Regards,

&nbsp;&nbsp;Michael

> **···**
>
> On Sun, Jul 11, 2004 at 04:10:34PM +0900, Hal Fulton 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?

---

<div class="post-metadata">

**Author:** ![Martin\_DeMello1](https://avatars.discourse-cdn.com/v4/letter/m/3be4f8/32.png) [@Martin\_DeMello1](https://rubytalk.org/u/Martin_DeMello1)\
**Post date:** [12 July 2004 11:32 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/12 "2004-07-12T11:32:24Z")

</div>

a = [1,2,3,4,6,7,8,11,12,15,16,17]

i = 0; b =   
while (a[i]) do  
&nbsp;&nbsp;j = i  
&nbsp;&nbsp;while (a[j] && (a[j] - a[i]) == (j-i)) do  
&nbsp;&nbsp;&nbsp;&nbsp;j += 1  
&nbsp;&nbsp;end  
&nbsp;&nbsp;j = j-1  
&nbsp;&nbsp;b += ((j-i \< 2) ? a[i..j] : [a[i]..a[j]])  
&nbsp;&nbsp;i = j+1  
end

p b #=\> [1..4, 6..8, 11, 12, 15..17]

martin

> **···**
>
> 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?

---

<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:** [12 July 2004 12:27 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/13 "2004-07-12T12:27:24Z")

</div>

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  
&nbsp;&nbsp;def to\_ranges  
&nbsp;&nbsp;&nbsp;&nbsp;ranges = Array.new  
&nbsp;&nbsp;&nbsp;&nbsp;self.sort.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;&nbsp;&nbsp;next  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges[-1] = Range.new(ranges[-1].begin, e)  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;return ranges  
&nbsp;&nbsp;end  
end

Jason Creighton

> **···**
>
> 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?

---

<div class="post-metadata">

**Author:** ![Rob\_Partington1](https://avatars.discourse-cdn.com/v4/letter/r/e480ec/32.png) [@Rob\_Partington1](https://rubytalk.org/u/Rob_Partington1)\
**Post date:** [14 July 2004 13:42 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/14 "2004-07-14T13:42:20Z")

</div>

[http://rjp.frottage.org/create\_runs.txt](http://rjp.frottage.org/create_runs.txt)

(uses only bash, not ruby, doesn't do any sorting at all,  
copes with numbers from -1B to +1B)

Probably not ideal for your ruby program, though.

> **···**
>
> On Sun, 11 Jul 2004 16:10:34 +0900, Hal Fulton \<hal9000@hypermetrics.com\> wrote:
> 
> > 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?

---

<div class="post-metadata">

**Author:** ![H.Yamamoto](https://avatars.discourse-cdn.com/v4/letter/h/eb9ed0/32.png) [@H.Yamamoto](https://rubytalk.org/u/H.Yamamoto)\
**Post date:** [11 July 2004 14:08 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/15 "2004-07-11T14:08:14Z")

</div>

(2004/07/11 19:37)

> a.each\_index{|i|a[i..j=i+2]==[x=a[i],x+1,x+2]and(0while a[j]+1==a[j+=1];a[i..j-=1]=a[i]..a[j])}

Amazing.

> **···**
>
> George Ogata \<g\_ogata@optushome.com.au\> 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:** [11 July 2004 14:27 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/16 "2004-07-11T14:27:26Z")

</div>

"George Ogata" \<g\_ogata@optushome.com.au\> schrieb im Newsbeitrag  
news:877jtaltuz.fsf@optushome.com.au...

> Hal Fulton \<hal9000@hypermetrics.com\> writes:
> 
> \> 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]
> 
> Interesting one to golf with:
> 
> a.each\_index{|i|a[i..j=i+2]==[x=a[i],x+1,x+2]and(0while

a[j]+1==a[j+=1];a[i..j-=1]=a[i]..a[j])}

Great! I was going to suggest the more conventional

aa = [1,2,3,4,6,7,8,11,12,15,16,17]

a = aa.dup

ranges =   
first = last = a.shift

a.each do |i|  
&nbsp;&nbsp;if i - last == 1  
&nbsp;&nbsp;&nbsp;&nbsp;last = i  
&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;ranges \<\< (first..last)  
&nbsp;&nbsp;&nbsp;&nbsp;first = last = i  
&nbsp;&nbsp;end  
end

ranges \<\< (first..last)

p ranges

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

---

<div class="post-metadata">

**Author:** ![Mauricio\_Fernndez](https://avatars.discourse-cdn.com/v4/letter/m/e495f1/32.png) [@Mauricio\_Fernndez](https://rubytalk.org/u/Mauricio_Fernndez)\
**Post date:** [11 July 2004 15:15 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/17 "2004-07-11T15:15:37Z")

</div>

Golfing a bit on #ruby-lang, exoticorn & I got

s=;a.map{|x|(l=s[-1])&&x-l[-1]\<2?l\<\<x:s\<\<};s.map{|f|f[2]?f[0]..f[-1]:f}.flatten

Note that whereas your solution is in-place, this one creates a new  
array. It is easier to specify the minimum range size, too.

> **···**
>
> On Sun, Jul 11, 2004 at 07:37:27PM +0900, George Ogata wrote:
> 
> > \> Example:  
> > \> [1,2,3,4,6,7,8,11,12,15,16,17] ==\> [1..4,6..8,11,12,15..17]
> > 
> > Interesting one to golf with:
> > 
> > a.each\_index{|i|a[i..j=i+2]==[x=a[i],x+1,x+2]and(0while a[j]+1==a[j+=1];a[i..j-=1]=a[i]..a[j])}
> 
> --  
> Running Debian GNU/Linux Sid (unstable)  
> batsman dot geo at yahoo dot com
> 
> You will not censor me through bug terrorism.  
> &nbsp;&nbsp;-- James Troup

---

<div class="post-metadata">

**Author:** ![HAL\_9000](https://avatars.discourse-cdn.com/v4/letter/h/90ced4/32.png) [@HAL\_9000](https://rubytalk.org/u/HAL_9000)\
**Post date:** [11 July 2004 23:49 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/18 "2004-07-11T23:49:13Z")

</div>

George Ogata wrote:

> Hal Fulton \<hal9000@hypermetrics.com\> writes:
> 
> > 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]
> 
> Interesting one to golf with:
> 
> a.each\_index{|i|a[i..j=i+2]==[x=a[i],x+1,x+2]and(0while a[j]+1==a[j+=1];a[i..j-=1]=a[i]..a[j])}

Ha, interesting indeed, but I don't do golf. 🙂

Thanks to all who replied.

Hal

---

<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:** [12 July 2004 13:52 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/19 "2004-07-12T13:52:23Z")

</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  
> &nbsp;&nbsp;def to\_ranges  
> &nbsp;&nbsp;&nbsp;&nbsp;ranges = Array.new  
> &nbsp;&nbsp;&nbsp;&nbsp;self.sort.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;&nbsp;&nbsp;next  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ranges[-1] = Range.new(ranges[-1].begin, e)  
> &nbsp;&nbsp;&nbsp;&nbsp;end  
> &nbsp;&nbsp;&nbsp;&nbsp;return ranges  
> &nbsp;&nbsp;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.

Regards

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

> **···**
>
> > On Sun, 11 Jul 2004 16:10:34 +0900, \> Hal Fulton \<hal9000@hypermetrics.com\> wrote:

---

<div class="post-metadata">

**Author:** ![George\_Ogata1](https://avatars.discourse-cdn.com/v4/letter/g/d9b06d/32.png) [@George\_Ogata1](https://rubytalk.org/u/George_Ogata1)\
**Post date:** [12 July 2004 10:32 UTC](https://rubytalk.org/t/a-little-algorithmic-help-requested/12508/20 "2004-07-12T10:32:29Z")

</div>

Mauricio Fernández \<batsman.geo@yahoo.com\> writes:

> > a.each\_index{|i|a[i..j=i+2]==[x=a[i],x+1,x+2]and(0while a[j]+1==a[j+=1];a[i..j-=1]=a[i]..a[j])}
> 
> Golfing a bit on #ruby-lang, exoticorn & I got
> 
> s=;a.map{|x|(l=s[-1])&&x-l[-1]\<2?l\<\<x:s\<\<};s.map{|f|f[2]?f[0]..f[-1]:f}.flatten
> 
> Note that whereas your solution is in-place, this one creates a new  
> array. It is easier to specify the minimum range size, too.

Nice! The "(l=s[-1])&&x-l[-1]\<2" bit is quite clever. Using it (and  
a few other tweaks) I can get mine down to:

i=0;a.map{a[j=i+2]&&a[j]-a[i]\<3&&(j+=1while a[j+1]==1+x=a[j];a[i..j]=a[i]..x);i+=1}

But yeah, in-place isn't how I'd normally do it.

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