Beefy Boxes and Bandwidth Generously Provided by pair Networks
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 ( #718134=note: print w/replies, xml ) Need Help??

in reply to Re: Challenge: Simple algorithm for continuing series of integers
in thread Challenge: Simple algorithm for continuing series of integers

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:

$s[1]= $a + $b*$s[0] $s[2]= $a + $b*$s[1]

Or just:

$b= ($s[2]-$s[1]) / ($s[1]-$s[0]); $a= $s[1] - $b*$s[0];

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

- tye        

Replies are listed 'Best First'.
Re^3: Challenge: Simple algorithm for continuing series of integers (confidence)
by blokhead (Monsignor) on Oct 20, 2008 at 14:10 UTC
    I agree, the magic-star should generally only identify a sequence that is nicely overspecified. But in the interest of Huffman coding the language I think that if anything warrants an exception, it should be arithmetic sequences (including constant sequences), since these would be the most common use cases (including 1,2,3,4...). Many times I've wanted to iterate over the multiples of N. I think "1,1,..*" or "2,4,6,..*" is just fine, and overspecifying the sequences by one more seems overkill because the rule is so simple/common.


      If I meant to write 1,2,4 but typo'd the "4" and wrote 1,2,3, then I would like to know about the typo. Having 1,2,4...* not work will help with that, but my experience is that people will expect 1,2,4...* to work because it will seem obvious while they are writing it (and I just typed "1,2,3" and had to delete the 3 and type 4).

      I figured there would be an exception for simple counting lists so that just "2 ... *" would be sufficient for "2,3,4,5 ... *". So 1,1...* vs 1.1...* would be another ugly typo that I would like detected. 100,101...* vs 100_101...*?

      So I respectfully disagree. But I figured it would be an up-hill fight against the common Perl mindset of making things rediculously terse.

      - tye        

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (2)
As of 2021-04-21 03:14 GMT
Find Nodes?
    Voting Booth?

    No recent polls found