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