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

```