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

Okay, I accidentally left a debugging output line in the original post. 
The correct definition is:

---
def search (num_array)
    data = num_array.to_s
    (0..num_array.size).each {|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
---

Executes the same, but won't fill your screen with "m = 1; m = 2; ..." 
messages for larger search patterns :)


Lennon Day-Reynolds wrote:

> 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:
>
> ---
> [...]
> ---
>
> 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
>>
>>
>>  
>>
>
>
>
>