A little algorithmic help requested...

H

Hal Fulton

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
 
H

H.Yamamoto

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?
Click to expand...

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)
case j - i
when 0
when 1
b << a
when 2
b << a << a[i+1]
else
b << (a..a[j-1])
end
i = j
end
end

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

Jeffrey Dik

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?
Click to expand...

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
ranges[-1] = ranges.last.first..a
else
ranges.push(a..a)
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
 
C

CT

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

Gavin Sinclair

Here's a problem my tired brain is having trouble with.
Click to expand...
Given a sorted array of integers, convert them into as many
ranges as possible (ranges of three or more).
Click to expand...
Example:
[1,2,3,4,6,7,8,11,12,15,16,17] ==> [1..4,6..8,11,12,15..17]
Click to expand...
How would *you* do this?
Click to expand...

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
 
G

George Ogata

Hal Fulton said:
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]
Click to expand...

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..a[j])}[/i]
 
R

Robert Klemme

George Ogata said:
Hal Fulton said:
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]
Click to expand...

Interesting one to golf with:

a.each_index{|i|a[i..j=i+2]==[x=a[i],x+1,x+2]and(0while[/i]
Click to expand...

a[j]+1==a[j+=1];a[i..j-=1]=a..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
 
M

Mauricio Fernández

Example:
[1,2,3,4,6,7,8,11,12,15,16,17] ==> [1..4,6..8,11,12,15..17]
Click to expand...

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..a[j])}[/i]
Click to expand...


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.

--
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

You will not censor me through bug terrorism.
-- James Troup
 
J

Jim Haungs

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

Jim Haungs

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

Jim Haungs

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

Michael Neumann

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?
Click to expand...

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
 
J

Jason Creighton

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?
Click to expand...

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
 
H

Hal Fulton

George said:
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]
Click to expand...


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..a[j])}[/i]
Click to expand...


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

Thanks to all who replied.


Hal
 
G

George Ogata

Mauricio Fernández said:
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..a[j])}[/i]
Click to expand...


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.
Click to expand...


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<3&&(j+=1while a[j+1]==1+x=a[j];a[i..j]=a..x);i+=1}

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

Martin DeMello

Hal Fulton said:
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?
Click to expand...

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

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

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


martin
 
R

Robert Klemme

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?
Click to expand...

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
Click to expand...

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
 
D

David A. Black

Hi --

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?
Click to expand...

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
Click to expand...

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.
Click to expand...

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Help with an algorythm 5
C program: memory leak/ segmentation fault/ memory limit exceeded 0
Little Things 137
I need help in understanding these files on my phone, Could someone help me understand these files? Urgent help needed. Please help. 4
Needing a little help with a ruby program 1
Unofficial quiz: Here's an algorithmic question for you 3
Review requested: Binding.call_stack(), Binding.of_caller()-style 3
A little diversion (probability fun in Ruby) 1

Members online

No members online now.
Total: 1,993 (members: 0, guests: 1,993)
Robots: 205

Forum statistics

Threads
474,148
Messages
2,570,838
Members
47,385
Latest member
Joneswilliam01

Latest Threads

Top