Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re: Challenge: Another Infinite Lazy List

by Roy Johnson (Monsignor)
on Mar 18, 2005 at 13:27 UTC ( #440692=note: print w/ replies, xml ) Need Help??


in reply to Challenge: Another Infinite Lazy List

This is actually a simpler problem, because the output for each iteration comes directly off of one of the input streams. One interesting property of that is that you can easily advance yourself in the output stream without generating the whole sequence.

use strict; use warnings; { my @streams = map [$_, 0], (2,3,5); sub limbic_sequence { my $first_after = shift; if (defined $first_after) { $_->[1] = int($first_after/$_->[0]) for @streams; } my ($lowest) = sort {$a <=> $b} map {($_->[1]+1) * $_->[0]} @s +treams; $_->[1]++ for grep {($_->[1]+1) * $_->[0] == $lowest} @streams +; $lowest; } } print join ', ', map limbic_sequence, 1..50; print "\n"; printf "First after 100000 is: %d\n", limbic_sequence(100000); print join ', ', map limbic_sequence, 1..50; print "\n"; __END__ #Output 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 2 +7, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 50, 51 +, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68 First after 100000 is: 100002 100004, 100005, 100006, 100008, 100010, 100011, 100012, 100014, 100015 +, 100016, 100017, 100018, 100020, 100022, 100023, 100024, 100025, 100 +026, 100028, 100029, 100030, 100032, 100034, 100035, 100036, 100038, +100040, 100041, 100042, 100044, 100045, 100046, 100047, 100048, 10005 +0, 100052, 100053, 100054, 100055, 100056, 100058, 100059, 100060, 10 +0062, 100064, 100065, 100066, 100068, 100070, 100071

Caution: Contents may have been coded under pressure.


Comment on Re: Challenge: Another Infinite Lazy List
Download Code
Re^2: Challenge: Another Infinite Lazy List
by demerphq (Chancellor) on Mar 18, 2005 at 16:14 UTC

    Am I right in thinking you are basically doing the same thing as my make_sub2() implementation but rotating the data (Ie, i have two array of N elements, you have N arrays of 2 elements)?

    ---
    demerphq

      It looks like we're working with the same data, though I don't think we're doing the same thing with it to get our results. Here's mine explained: Each stream stores its base (2, 3, or 5) and the multiplier last used with that base to generate an output element. To generate the next element of the sequence, I check what the next output would be from each stream (multiply the base by the last multiplier + 1) and choose the lowest of those, incrementing the multiplier of each stream that would give me that lowest number. That's it.

      Caution: Contents may have been coded under pressure.

        Hmm. My variation uses the @v array to store the next value that would come from a given stream, and the @f array to store what value a given stream is incremented by when a value is "popped" from it. When it comes time to return the next value in the sequence the lowest value available is "popped" from the streams. If it could have also come from a stream with a smaller factor it is ignored and the process repeats otherwise the popped value is returned.

        As far as I can tell this is basically the same thing as yours, except you multiply and I increment, and the way we handle dupes is slighlty different but the principle is the same. Its just interesting to me, I find the way identical algorithms can look so different at first glance to be fascinating.

        ---
        demerphq

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://440692]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (5)
As of 2014-09-20 14:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (159 votes), past polls