From: Joseph McDonald <joe@...>
Date: 2002-09-19T05:11:59+09:00
Subject: Re: How to Efficiently Calculate the Pattern of Zeros and Ones?


WDT> I am dealing with this algorithmic problem.  I have an array of arbitrary
WDT> integers.  I have to count the occurences of 1's with the pattern

WDT>     "0 0 ... 0 1 0 .. 0 0"

WDT> in the array.  The minimum number of zeros on each side of the 1 is a
WDT> parameter, say m = 2.  Also at the beginning and at the end of the array,
WDT> the boundary condition does not require the minimum number of zeros, as
WDT> long as they are zeros (or non-existent).

WDT> For example, with m = 2:

WDT>     [1 0 0 1 0 0 5 1]   --> 2
WDT>     [0 0 1 0 0 1 0 2]   --> 1
WDT>     [1 0 1 0 1 0 1 0]   --> 0
WDT>     [1 0 0 0 0 0 1 0]   --> 2

WDT> Typical array length will be around 24.  The problem is I will have
WDT> thousands, if not hundreds of thousands, of such arrays.  What is a good
WDT> way to do it in Ruby?  (Even coverting the array first to, for example,
WDT> string and then use regexp, is also fine as long as it is efficient.)

Well, I don't have a test case for it, so there could be a bug
lurking, but this does over 10,000 per second on my box:

I'm sure someone can make it faster.

#!/usr/local/bin/ruby

def count_pattern(num,arrays) # pass in a zillion arrays

  arrays.each do |arr|
    hits = 0
    onehit = false
    numzeros = num  # cheater

    arr.each do |x|
      if x == 1 and numzeros >= num
        onehit = true
        numzeros = 0
        next
      end
      if x == 0
        numzeros += 1
        if onehit == true and numzeros >= num # HIT!
          hits += 1
          onehit = false
        end
      else
        numzeros = 0
        onehit = false
      end
    end
    hits += 1 if onehit == true # trailing one
    puts "[#{arr.join(' ')}] -> #{hits}"
  end
end

arrs = [
[1, 0, 0, 1, 0, 0, 5, 1],
[0, 0, 1, 0, 0, 1, 0, 2],
[1, 0, 1, 0, 1, 0, 1, 0],
[1, 0, 0, 0, 0, 0, 1, 0]
]

count_pattern(2,arrs)

regards,
-joe