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

Hmm...yeah, it's *very* late. The original version can show false 
positives on data sets that don't actually contain a repeating pattern, 
and after changing it to match the proper number of occurances of the 
regexp group, (i.e., not just two) it stops working quickly enough to 
handle data sets over a few hundred numbers before I get impatient and 
^C the process.

For those who care, to eliminate the false positives, replace line 6 
(the regexp match) with the following:
 >>>
if data =~ /(?:#{pat_str)){#{data.size/k},}/
<<<

I've tested it so far on each digit of the first thousand powers of two, 
and it correctly finds the 5-element repeating pattern for the 'ones' 
digit, the 20-element pattern for the 'tens', and the 100-element 
pattern for the 'hundreds'. If I had a faster machine and/or more RAM, I 
might let it do its thing on the thousands place, just to check, but the 
whole exponential-growth issue probably means it just isn't worth it.

I'm sure there are other problems, but I don't think I'll find them 
without sleep, and since several "real" solutions seem to be coming up 
now, I'll probably just let the pros handle it.

G'night,

Lennon


Lennon Day-Reynolds wrote:

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