Martin DeMello <martindemello / yahoo.com> wrote:

> Given a stream of numbers that, at some point, recurs with period k,
> find k.
> 
> Harder: as before, but with a prefix of m nonrepeating digits before the
> cycle sets in.

Sounds like repeating decimals.  If by 'stream' you mean an infinite
list, let's start with a simple generator:

  class Repeat
    def initialize str
      @prefix, @repeat = str.split(/_/)
      @prefix = @prefix.scan(/\d/).map {|x| x.to_i}
      @repeat = @repeat.scan(/\d/).map {|x| x.to_i}
    end
    def [] i
      if i < @prefix.size
        @prefix[i]
      else
        @repeat[(i - @prefix.size) % @repeat.size]
      end
    end
    def each
      i = -1
      yield self[i] while i+=1
    end
  end

Repeat.new takes a single string formatted as non-repeating digits,
followed by an underscore, followed by repeating digits:

                                 #    __
  stream = Repeat.new "100_45"   # 10045

To find the period k at which a stream of digits repeats, create a
string one digit at a time and try to use a regular expression to pick
out a repeating pattern:

  # stream:  Any collection responding to the #each method.
  # times:   Number of times a pattern must be repeated.
  # max:     Maximum number of digits to check before giving up.

  def find_k(stream, times=2, max=nil)
    re  = /^(.+?)\1{#{times - 1}}/
    str = ""
    stream.each { |num|
      str[0,0] = num.to_s
      return $1.size if str =~ re
      return if max && str.size > max
    }
    nil
  end

  puts find_k(stream)     # 1, saw '0'  2 times in '100'
  puts find_k(stream, 3)  # 2, saw '45' 3 times in '100454545'

Because find_k only requires stream#each, a finite list can also
be used:

  list = [1, 2, 3, 4, 5, 3, 4, 5, 3, 4, 5]
  puts find_k(list)  # 3

Or, since stringifying a finite list won't take forever, this should
be reasonably fast:

  def find_k_finite(list, times=2)
    list.reverse * '' =~ /^(\d+?)\1{#{times - 1}}/ and $1.size
  end

  puts find_k_finite(list)  # 3

-- 
Tabby