Algorithm help

ruby-talk
1

I guess no one cares, but there is an even shorter version
(and it should still be O(log n)):

···

-------------------------------------------------------------
data = [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790, 9998, 9999]
p1, p2, ranges = 0, (data.size - 1) * 2, [data[0]..data[0]]

until p1 == data.size
    if (d2 = data[p2 = (p1 + p2) / 2]) - (d1 = data[p1]) == p2 - p1
        ranges << ((ranges.last.end+1 >= d1 ? ranges.pop.first :
d1)..d2)
        p1, p2 = p2+1, data.size - 1
    end
end

puts ranges
-------------------------------------------------------------

I get some odd satisfaction from shrinking stuff, call me stupid...

Simon

2

This looks cute. What makes you sure it's O(log n)?

Btw, here's another funny idea:

···

Kroeger Simon (ext) <simon.kroeger.ext@siemens.com> wrote:

I guess no one cares, but there is an even shorter version
(and it should still be O(log n)):

-------------------------------------------------------------
data = [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790, 9998,
9999] p1, p2, ranges = 0, (data.size - 1) * 2, [data[0]..data[0]]

until p1 == data.size
    if (d2 = data[p2 = (p1 + p2) / 2]) - (d1 = data[p1]) == p2 - p1
        ranges << ((ranges.last.end+1 >= d1 ? ranges.pop.first :
d1)..d2)
        p1, p2 = p2+1, data.size - 1
    end
end

puts ranges
-------------------------------------------------------------

I get some odd satisfaction from shrinking stuff, call me stupid...

-----------------
data = [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790, 9998, 9999]
ranges =

data.inject(0) {|s,x| s | (1 << x)}.to_s(2).reverse!.scan(/1+/) do |m|
  s = $`.length
  ranges << (s .. (s + m.length - 1))
end

puts ranges
-----------------

Kind regards

    robert

3

I know this is a little off-topic, but the Rails Wiki
(http://wiki.rubyonrails.com/rails/recently_revised/) has been getting
vandalized something fierce of late. Does anyone here know who
administers it, or if there is any coordinated effort to do something
about it (like adding logins or various filters)? So far as I can tell
there's just a bunch of us deleting it as fast as we spot it, and trying
to restore pages that get obliterated in the process.

It gets old.

--MarkusQ

4

Nice :slight_smile:

martin

···

Robert Klemme <bob.news@gmx.net> wrote:

Btw, here's another funny idea:

-----------------
data = [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790, 9998, 9999]
ranges =

data.inject(0) {|s,x| s | (1 << x)}.to_s(2).reverse!.scan(/1+/) do |m|
  s = $`.length
  ranges << (s .. (s + m.length - 1))
end

puts ranges

5

not bad (and *so* short), but failing for descending ranges and ones with
negative values:

     harp:~ > ruby a.rb
      =>
     [0] => [0..0]
     [0, 1] => [0..1]
     [1, 0] => [0..1]
     [0, 1, 2] => [0..2]
     [2, 1, 0] => [0..2]
     [0, 1, 2, 3] => [0..3]
     [3, 2, 1, 0] => [0..3]
     [0, 3] => [0..0, 3..3]
     [3, 0] => [0..0, 3..3]
     [0, 3, 5] => [0..0, 3..3, 5..5]
     [5, 3, 0] => [0..0, 3..3, 5..5]
     [0, 3, 5, 7] => [0..0, 3..3, 5..5, 7..7]
     [7, 5, 3, 0] => [0..0, 3..3, 5..5, 7..7]
     [0, 1, 3, 4] => [0..1, 3..4]
     [4, 3, 1, 0] => [0..1, 3..4]
     [0, 1, 3, 4, 6, 7] => [0..1, 3..4, 6..7]
     [7, 6, 4, 3, 1, 0] => [0..1, 3..4, 6..7]
     [0, 1, 3, 4, 6, 7, 9, 10] => [0..1, 3..4, 6..7, 9..10]
     [10, 9, 7, 6, 4, 3, 1, 0] => [0..1, 3..4, 6..7, 9..10]
     [0, 1, 3, 4, 6, 7, 10] => [0..1, 3..4, 6..7, 10..10]
     [10, 7, 6, 4, 3, 1, 0] => [0..1, 3..4, 6..7, 10..10]
     [0, 3, 4, 6, 7, 9, 10] => [0..0, 3..4, 6..7, 9..10]
     [10, 9, 7, 6, 4, 3, 0] => [0..0, 3..4, 6..7, 9..10]
     [0, 1, 3] => [0..1, 3..3]
     [3, 1, 0] => [0..1, 3..3]
     [0, 3, 4] => [0..0, 3..4]
     [4, 3, 0] => [0..0, 3..4]
     [0, -1] => [0..0]
     [-1, 0] => [0..0]
     [0, -1, -2] => [0..0]
     [-2, -1, 0] => [0..0]
     [0, -1, -3, -4] => [0..0]
     [-4, -3, -1, 0] => [0..0]
     [0, -1, -3, -4, -6] => [0..0]
     [-6, -4, -3, -1, 0] => [0..0]
     [0, -1, -3, -4, -6, -7] => [0..0]
     [-7, -6, -4, -3, -1, 0] => [0..0]
     [-1, -3, -4, -6, -7] =>
     [-7, -6, -4, -3, -1] =>
     [-3, -4] =>
     [-4, -3] =>
     [-3, -4, -6, -8, -9, -10, -11, -12, - =>
     [-42, -41, -40, -39, -38, -37, -36, - =>

     harp:~ > cat a.rb
     tests = [
       ,
       [0],
       [0,1],
       [0,1,2],
       [0,1,2,3],
       [0,3],
       [0,3,5],
       [0,3,5,7],
       [0,1,3,4],
       [0,1,3,4,6,7],
       [0,1,3,4,6,7,9,10],
       [0,1,3,4,6,7,10],
       [0,3,4,6,7,9,10],
       [0,1,3],
       [0,3,4],
       [0,-1],
       [0,-1,-2],
       [0,-1,-3,-4],
       [0,-1,-3,-4,-6],
       [0,-1,-3,-4,-6,-7],
       [-1,-3,-4,-6,-7],
       [-3,-4],
       [-3,-4,-6, *(-42 .. -8).to_a.reverse],
     ]

     def sequences d
       seqs =
       d.inject(0) {|s,x| s | (1 << x)}.to_s(2).reverse!.scan(/1+/) do |m|
         s = $`.length
         seqs << (s .. (s + m.length - 1))
       end
       seqs
     end

     tests.each do |a|
       begin
         printf "%-37.37s => %37.37s\n", a.inspect, sequences(a).inspect
         a.reverse!
         printf "%-37.37s => %37.37s\n", a.inspect, sequences(a).inspect
       rescue => e
         printf "%-37.37s => %s\n", a.inspect, "#{ e } (#{ e.message })"
       end
     end

i never thought i'd get any help at all on this and ended up with so many
viable ideas... what a great list!

regards.

-a

···

On Fri, 5 Aug 2005, Robert Klemme wrote:

Btw, here's another funny idea:

-----------------
data = [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790, 9998, 9999]
ranges =

data.inject(0) {|s,x| s | (1 << x)}.to_s(2).reverse!.scan(/1+/) do |m|
s = $`.length
ranges << (s .. (s + m.length - 1))
end

puts ranges

--

email :: ara [dot] t [dot] howard [at] noaa [dot] gov
phone :: 303.497.6469
My religion is very simple. My religion is kindness.
--Tenzin Gyatso

===============================================================================

6

Ara.T.Howard wrote:

> Btw, here's another funny idea:
> [snip code]

not bad (and *so* short), but failing for descending ranges [...]

Descending ranges don't have much method support in Ruby, though.

rg = (43..41)

p rg.include?(42) #-> false
p rg.max #-> nil
p rg.to_a #->

.... and others.

daz

···

On Fri, 5 Aug 2005, Robert Klemme wrote:

7

but

   harp:~ > irb -r narray
   irb(main):001:0> na = NArray::to_na [1,2,3,4]

   => NArray.int(4):
   [ 1, 2, 3, 4 ]

   irb(main):002:0> na[ -3 .. -1 ]
   => NArray.int(3):
   [ 2, 3, 4 ]

   irb(main):003:0> na[ -1 .. -3 ]
   => NArray.int(3):
   [ 4, 3, 2 ]

which is precisely what i'm doing.

cheers.

-a

···

On Sat, 6 Aug 2005, daz wrote:

Ara.T.Howard wrote:

On Fri, 5 Aug 2005, Robert Klemme wrote:

Btw, here's another funny idea:
[snip code]

not bad (and *so* short), but failing for descending ranges [...]

Descending ranges don't have much method support in Ruby, though.

rg = (43..41)

p rg.include?(42) #-> false
p rg.max #-> nil
p rg.to_a #->

.... and others.

--

email :: ara [dot] t [dot] howard [at] noaa [dot] gov
phone :: 303.497.6469
My religion is very simple. My religion is kindness.
--Tenzin Gyatso

===============================================================================

8

Ara.T.Howard wrote:

but

   harp:~ > irb -r narray
[...]

which is precisely what i'm doing.

cheers.

-a

Fair enough.
Didn't want any more weather balloons landing in my garden, that's all :slight_smile:

daz

9

lol. i've moved onto satelites - you __really__ don't want any of those
landing in your garden!

-a

···

On Sat, 6 Aug 2005, daz wrote:

Fair enough.
Didn't want any more weather balloons landing in my garden, that's all :slight_smile:

--

email :: ara [dot] t [dot] howard [at] noaa [dot] gov
phone :: 303.497.6469
My religion is very simple. My religion is kindness.
--Tenzin Gyatso

===============================================================================