From: Lennon Day-Reynolds <lennon@...>
Date: 2003-03-12T22:47:00+09:00
Subject: Re: Coding challenge: Recurring stream

It's nasty (as in geometric-scaling as string size increases) *and* 
hackish (since the source array gets converted into a string and 
regexp-searched for matches), but it works:

---
def search (num_array)
    data = num_array.to_s
    (0..num_array.size).each {|m|
        puts "m = #{m}"
        (1..((num_array.size - m) / 2).to_i).each {|k|
            pat_str = data[m..(m + k)]
            if data =~ /(?:#{pat_str}){2,}/
                return num_array[m..(m + k)]
            end
        }
    }
    return nil
end
---

As a bonus, the actual matching subarray is returned, rather than just 
its offset and length. Change the 'return ...' line to read 'return [k, 
m]' or similar if you want something closer to the original request. It 
can also be simplified by removing the outermost loop if you really 
don't need the initial prefix search, but since it terminates as soon as 
a match is found, the simple case of patterns like '1, 2, 3, 1, 2, 3, 
...' will avoid the extra cost, anyway.

My apologies to anyone offended by the code; it's late, I'm tired, and I 
can't find my copy of 'Algorithms and Data Structures in Perl', which is 
my standard crib for search algorithms.

Lennon Day-Reynolds
lennon@day-reynolds.com

Martin DeMello 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.
>
>martin
>
>
>  
>