# A little algorithmic help requested

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

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?

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

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

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

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

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

def to_ranges(a)
ranges = [a[0]..a[0]]
a.shift
a.each_index { |i|
if ranges.last.last + 1 == a[i]
ranges[-1] = ranges.last.first..a[i]
else
ranges.push(a[i]..a[i])
end
}
ranges.map! { |r|
case r.last-r.first
when 0
r = r.first
when 1
r = [r.first, r.last]
end

r
}
ranges.flatten
end

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

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|
temp = arr.last
if(temp.last.next == i)
temp << i
else
arr << [i]
end
arr
}.inject([]) {|arr,i|
if(i.length >= 3)
arr<<(i.first..i.last)
else
arr = arr + i
end
}
--
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

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

require 'test/unit'
class RangeTest < Test::Unit::TestCase
def test_range
assert_equal([1], ranges([1]))
assert_equal([1,2], ranges([1,2]))
assert_equal([1..3], ranges([1,2,3]))
assert_equal([1..4,6], ranges([1,2,3,4,6]))
assert_equal([1,2,3,4,6], ranges([1,2,3,4,6], 10))
assert_equal([1..4,6..8,11,12,15..17], ranges([1,2,3,4,6,7,8,11,12,15,16,17]))
assert_equal([1..4,6..8,11..12,15..17], ranges([1,2,3,4,6,7,8,11,12,15,16,17], 2))
assert_equal([1..1,3..3,5..5,7..7], ranges([1,3,5,7], 1))
assert_equal([1..4,6..6,8..9], ranges([1,2,3,4,6,8,9], 0))
end
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?

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

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:

http://www.rubygarden.org/ruby?CodingChallenge0001

David

--
David A. Black
dblack@wobblini.net

Here's an iterator approach.

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

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

def ranges(anArray, maxGroupSize, split)
groups(anArray, split) do | group |
if group.size > maxGroupSize then
yield group
else
group.each {|g| yield [g]}
end
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 }

[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

Here's an iterator approach.

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

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

def ranges(anArray, maxGroupSize, split)
groups(anArray, split) do | group |
if group.size > maxGroupSize then
yield group
else
group.each {|g| yield [g]}
end
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 }

[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

Here's an iterator approach.

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

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

def ranges(anArray, maxGroupSize, split)
groups(anArray, split) do | group |
if group.size > maxGroupSize then
yield group
else
group.each {|g| yield [g]}
end
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 }

[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

require 'enumerator'

def to_range(arr)
ranges = [r=[]]
arr.each_cons(2) {|a,b|
r << a
ranges << (r = []) if (b-a) != 1
r << b
}
ranges.map {|r|
r.uniq!
r.size > 2 ? (r.first..r.last) : r
}.flatten
end

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

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

Regards,

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?

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

i = 0; b = []
while (a[i]) do
j = i
while (a[j] && (a[j] - a[i]) == (j-i)) do
j += 1
end
j = j-1
b += ((j-i < 2) ? a[i..j] : [a[i]..a[j]])
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?

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

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?

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?

(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:

"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|
if i - last == 1
last = i
else
ranges << (first..last)
first = last = i
end
end

ranges << (first..last)

p ranges

robert

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

s=[];a.map{|x|(l=s[-1])&&x-l[-1]<2?l<<x:s<<[x]};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.
-- James Troup

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

"Jason Creighton" <androflux@softhome.net.remove.to.reply> schrieb im
Newsbeitrag

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

Regards

robert

···

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

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<<[x]};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.