Algorithm help

ruby-talk
1

sorry it took me so long to respond pit and martin... got sidetracked. your
binary search idea was perfect! for the actual data i'll be working with this
should be either O(1) or O(log(n)) - thought it can obviously degrade in the
general case. i used your idea in essentially the reverse pit, here's what i
ended up with:

     harp:~ > cat a.rb

     def sequences list
       distance = lambda do |a,b|
         (b - a).abs
       end

       continuous = lambda do |range, list|
         first, last = range.first, range.last
         a, b = list[first], list[last]
         (list.empty? or (distance[a,b] == distance[first,last])) ? (a .. b) : nil
       end

       discrete = lambda do |range, list|
         first, last = range.first, range.last
         edge = last + 1
         edge >= list.length or distance[list[last], list[edge]] > 1
       end

       sequence = lambda do |range, list|
         first, last = range.first, range.last
         list[first] .. list[last]
       end

       last = list.length - 1
       a, b = 0, last

       accum =

       while a <= b and a < list.length and b < list.length
         range = a .. b

         if continuous[ range, list ]
           if discrete[ range, list ]
             accum << sequence[ range, list ]
             a, b = b + 1, last # move a and b up
           else
             b = b + distance[b, last] / 2 # move b up
           end
         else
           b = a + distance[a, b] / 2 # move b down
         end
       end

       accum
     end

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

     tests.each do |a|
       printf "%-37.37s => %37.37s\n", a.inspect, sequences(a).inspect
       a.reverse!
       printf "%-37.37s => %37.37s\n", a.inspect, sequences(a).inspect
     end

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

your ideas were essential to getting the peice of code i'm working on now
running in a reasonable amount of time - thanks to all the contributors!

-a

···

On Tue, 2 Aug 2005, Pit Capitain wrote:

This might work better: binary search for {x | (x - min) == (i_x - i_min)},
set i_min to i_x+1 and repeat. For an added optimisation, run two loops
in parallel, searching from each end.

Just in case you haven't implemented Martin's binary search idea yet:

def gap?( data, min, max )
   data[ max ] - data[ min ] > max - min
end

def find_gaps( data, min, max, acc )
   if gap?( data, min, max )
     if max - min == 1
       acc << max
     else
       mid = ( max + min ) / 2
       find_gaps( data, min, mid, acc )
       find_gaps( data, mid, max, acc )
     end
   end
end

def gaps( data )
   acc = [ 0 ]
   find_gaps( data, 0, data.size - 1, acc )
   acc << data.size
end

def ranges( *data )
   gaps = gaps( data )
   ( 1 ... gaps.size ).map { |idx|
     data[ gaps[ idx - 1 ] ] .. data[ gaps[ idx ] - 1 ]
   }
end

p ranges( 1, 2, 3, 6789, 6790, 6791 )
# => [1..3, 6789..6791]

--

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

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

2

Ara.T.Howard wrote:

<snip>

your ideas were essential to getting the peice of code i'm working on now
running in a reasonable amount of time - thanks to all the contributors!

-a

No applause please. Just throw money (at RubyCentral).

:slight_smile:

Regards,

Dan

3

how? i bought the new book...

-a

···

On Thu, 4 Aug 2005, Daniel Berger wrote:

Ara.T.Howard wrote:

<snip>

your ideas were essential to getting the peice of code i'm working on now
running in a reasonable amount of time - thanks to all the contributors!

-a

No applause please. Just throw money (at RubyCentral).

--

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

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