|Perl Monk, Perl Meditation|
Re^2: Challenge: Simple algorithm for continuing series of integers (confidence)by tye (Sage)
|on Oct 20, 2008 at 04:54 UTC||Need Help??|
Your reply is pretty similar to the reply I had in mind and started to write and then quickly abandoned. Thanks. :)
Some minor differences: I planned to strictly limit the complexity of generator that would be considered, nothing beyond $s[$n]= $a + $b*$s[$n-1] + $c*$s[$n-2];. I find that the next order of generator is too opaque for the reader of the code and so isn't something I'd have automated (the expense also climbs). So I had no intention of using PDL.
But I also wanted to request that guessing be made much safer than proposed. I don't find "1,1" compellingly unique nor "1,3,5". I'd want at least "1,1,1" and "1,3,5,7" to be required.
Actually, I'd take the last two items off the end of the presented start of the sequence and use that to compute the simplest matching sequence generator from some simple class(es) of generators. Then I'd only use it if the next two numbers matched the guessed-at sequence. If the numbers don't match, then I'd reject the code, not try to guess again.
For something this magical, it is good to have a couple of "check digits" so that it stays DWIM not DoSomethingSurprising. Making a single typo in one number should very much not just happily pick a sequence that I didn't intend to describe. And people are very prone to expect other people to see things as they themselves currently see things and so will type "1,2,4,7" and fully expect that the next item is "obvious" (and then will come back a few weeks later and have no idea what they had in mind when they wrote that). For this type of magic, it is incumbent upon Perl to require the author to be more explicit than they naturally will think that they need to be.
So, if you have three numbers in your example, you have to predict the sequence from the first number alone. The simplest prediction is a constant list, so that is the only type of list that can be generalized from just three items. So fewer than 3 items or a sequence of 3 items not all the same would always refuse to be generalized.
If you have 4 items, then you must predict based on only the first two. The simplest prediction would be a linear progression. So "1,2,3,4 ... *" would work as would "1,3,5,7 ... *".
If you have 5 items, then you can use the first three to predict. So we'd solve the following two simultaneous equations:
(If the first two items are the same, then set $b to 0 which gives us a constant sequence again and generalizing fails unless the third item is also the same.)
So for 1,2,4,$x,$y ... * Perl guesses $b= 2 so $a= 0 and fails unless $x is 8 and $y is 16.
When we get to 1,4,9,16,$x,$y ... *, the human thinks "$n**2" and Perl 6 computes $a= 2, $b= 2, $c= -1, that is $s[$n]= 2 + 2*$s[$n-1] - $s[$n-2]; since (9) == 2 + 2*(4) - (1) and (16) == 2 + 2*(9) - (4). Did Perl DWIM? I leave that as an exercise for the reader.