in reply to Pattern enumeration.

I guess there must be a way to calculate this precisely in a reasonable time, but if you only want an approximate answer, that's much easier. Just use sampling.

I made the computer fill the board with random letters 10_000_000 times, and 896_728 out of those were correct (no three adjacent letters in a row or column). As there are 6.33e49 possible boards, this means there are approximately 5.68e48 correct boards.

Replies are listed 'Best First'.
Re^2: Pattern enumeration.
by BrowserUk (Patriarch) on Jul 29, 2010 at 16:33 UTC

    Beat ya to it! :)

    The problem is, it converges very slowly. After 1 billion trials, it has still only rendered (at most) 5 significant digits. And plus or minus 1 place in that 5th digit is still a stunningly large margin of error:

    [0] Perl> $t = 6**64;; [0] Perl> $a = $t * 0.08972;; [0] Perl> $b = $t * 0.08973;; [0] Perl> print $b - $a;; 6.33402866630814e+044

    Another problem is that 1 billion (or even 1 trillion) trials is such a minuscule sample that I'm not at all convinced that even those 5 digits are accurate. That figure is produced using Perl's built-in rand, which on my platform equates to MSC's hopelessly inadequate 15-bit linear congruential generator, with its known cyclic flaws.

    I substituted Math::Random::MT and got substantially different results, but the MT, whilst a vastly better PRNG, is really very slow by comparison. Generating and testing an adaquate sample, say a quadrillion, would take a very long time also.

    Luckily, salva came to the rescue with a very clever piece of C code that with luck will render an exact answer within the next 10 or so hours.

    I'm also convinced that it can be done (very quickly) using purely numerical methods. Though it is considerably more complicated than I first thought. I just found a ridiculous typo(*) that had been hanging me up for two days. Maybe I'll make some progress now.

    (*)I have variables $x_1, $x_2, $y_1, $y_2 to represent the values 1 and 2 to the left; and 1 & 2 above the current position. I thought they were vaguely mnemonic for X-1 etc.

    Trouble is, in one place I typed $x-1 instead of $x_1 by accident, and whilst nothing appeared broken, the results were rubbish. I must have looked right past that typo a hundred times without spotting it!


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

      Sure. It's a binomial distribution with probability of an individual board being good around 0.09, so the divergence of the ratio of good boards you get from n samples is around 0.3/sqrt(n), which is about 9e-6 for n=1e9, so you should expect only four correct significant digits.