moritz has asked for the wisdom of the Perl Monks concerning the following question:
Background
Perl 6 introduces the series operator, infix:<...>. Its normal behavior is to acccept a closure on the right side, and executes that closure to get next value, so you could write
my @even = 0, 2, 4 ... { $_ + 2}; my @powers = 1, 2, 4 ... { $_ * 2 }; my @fib = 1, 1, 2 ... { $^a + $^b};
Now there's a special, "magic" behavior if the right side isn't a closure but rather the Whatever star *:
my @ints = 1, 2, 3, 4 ... *; my @even = 0, 2, 4, 6 ... *; my @powers = 1, 2, 4, 8 ... *;
The spec says about that operator
If the right operand is * (Whatever) and the sequence is obviously arithmetic or geometric, the appropriate function is deduced:
1, 3, 5 ... * # odd numbers 1, 2, 4 ... * # powers of 2Conjecture: other such patterns may be recognized in the future, depending on which unrealistic benchmarks we want to run faster. :)
The Challenge
It's not hard to detect arithmetic or geometric sequences and to continue them. My interest is more in an elegant, general algorithm for continuing such series. If you can provide such an algorithm, it might even make its way into the Perl 6 specs.
The criteria are
- Principle of least surprise: If there's no obvious solution, bail out (or return undef) rather than making up a solution.
- Simplicity: You should neither need a degree in computer science nor in mathematics to understand what's going on.
- Generality: The more sequences it can detect and continue, the better. When a sequence is detected, it should be able to return arbitrary many items of that sequence.
- Speed: Before you spend too much time in that operator rather give up (that implies no support for the sequence of prime numbers, since you can't easily find the next prime number).
- Integers only, for now. Don't care about floating points and rounding errors for now.
(Using a dump of the OEIS database doesn't meet these criteria).
My thoughts
My thoughts in spoiler tags below. Please try to find your solution prior to reading that, I don't want to bias you into a particular direction.
I've also written a small test script, but that should more serve as a starting point than as an authorotative test.
#!/usr/bin/perl use strict; use warnings; use Test::More qw(no_plan); sub series { # your code here. } my @tests = ( [[1], undef], [[1, 1], 1], [[0, 0], 0], [[1, 2], undef], [[0, 1, 2], 3], [[1, 0, -1], -2], [[1, 2, 3], 4], [[1, 2, 4], 8], # powers [[2, 4, 8], 16], [[1, 3, 9], 27], [[1, -1, 1, -1], 1], # alternations [[-1, 1, -1, 1], -1], [[1, 0, 1, 0], 1], [[0, 1, 0, 1], 0], [[1, 1, 2, 3, 5], 8], # fibonacci [[0, 1, 1, 2, 3], 8], [[1, 2, 3, 5, 8], 13], [[1, 2, 6, 24, 120], 720], # factorials [[1, 0, 0, 1], undef], [[1, 2, 3, 1], undef], ); for my $t (@tests) { my $expected = defined $t->[1] ? $t->[1] : 'undef'; my $result = series(@{$t->[0]}); $result = 'undef' unless defined $result; is $result, $expected, "seq " . join(', ', @{$t->[0]}); }
Update: Thanks for all the replies. I have to mull it over in my head, there are certainly good ideas and valid concern in the replies.
|
---|