From the Math Forum problem of the week 1020:

Let p(n) be the probability that a random n-digit integer has all 10 digits occurring (where for simplicity we do include leading 0s; that is, we consider 0000012345 as being a 10-digit number). So p(9) is 0 and p(10) = 10!/1010.

What is the smallest n for which p(n) > 1/2?

Suggested by Danny Lichtblau, Wolfram Research, Inc.

I was trying to solve it analytically, but then I got tired and decided to "cheat". I figured that a very simple Perl script could give me an approximate value for p(n), by generating $N random $n-digit numbers and testing how many of them have every digit. The following code does that while remaining reasonably readable: 

#!/usr/bin/perl -l
($n,$N) = @ARGV;
for (1 .. $N) {
    @a = map { int(rand(10)) } 1 .. $n;
    my %h;
    @h{@a} = ();
    $g++ if keys %h == 10;
}
print $g/$N;

[download]

The question now is how short you can make a program that does the same. The only requirements are: 1) take two command-line arguments, $n and $N; and 2) print out the probability followed by a newline (the probability must be computed by the random method).

Generic rules for Perl Golf may be found at http://www.xs4all.nl/~thospel/golf/rules.html

Replies are listed 'Best First'.
Re: Golf: Pandigital puzzle
by revdiablo (Prior) on Nov 18, 2004 at 22:41 UTC

    Just to get it started, he's a minor improvement:

    #!/usr/bin/perl -l
($n,$N) = @ARGV;
for (1 .. $N) {
    my %h;
    $h{int rand 10}++ for 1 .. $n;
    $g++ if keys %h > 9;
}
print $g/$N;

    [download]

    Update: here's another minor improvement on that:

    #!/usr/bin/perl -l
($n,$N) = @ARGV;
for (1 .. $N) {
    %h = map { int rand 10, "" } 1 .. $n;
    $g++ if keys %h > 9;
}
print $g/$N;

    [download]

    Cheap update: removing the whitespace:

    #!/usr/bin/perl -l
($n,$N)=@ARGV;
for(1..$N){
%h=map{int rand 10,""}1..$n;
keys%h>9&&$g++
}
print$g/$N;

    [download]

    Yet another (and hopefully final) update: here are the counts, as reported by the golfcount program:

    145: itub
121: revd1
117: revd2
 87: revd3

    [download]
[reply]
[d/l]
[select]
      By the rules, my count is 76: 
      #!/usr/bin/perl -l
$N=pop;print 1/$N*grep{%h=map{int
rand(10),1}1..$ARGV[0];10==keys%h}1..$N

      [download]
      Incidentally this program, as amusing as it may be, won't give you the exact answer to the puzzle. The following brief program will. (Don't look if you want to figure out the real puzzle for yourself!) 
      #! /usr/bin/perl
use strict;
# $stats[$i][$j] will be the number of ways to have used $j different
# digits in a $i digit number.
my @stats = [1, map 0, 1..10];
my $i = 0;
while ($stats[$i][10]*2 < 10**$i) {
  my $last_stats = $stats[$i];
  $i++;
  my $next_stats = $stats[$i] = [map 0, 0..10];
  for my $j (0..10) {
    $next_stats->[$j] += $j*$last_stats->[$j];
    $next_stats->[$j+1] += (10 - $j)*$last_stats->[$j];
  }
}
print $i, "\n";

      [download]
[reply]
[d/l]
[select]
        You can still squeeze three more characters:
        (I played with the option of wasting half the random numbers, but it seems it's not really useful...) 

        #!/usr/bin/perl -l
$N=pop;print 1/$N*grep{%h=map{int rand 10}1..$ARGV[0]*2;9<keys%h}1..$N

        [download]
[reply]
[d/l]
        Look, no hashes! But 77 chars long... 
        #!/usr/bin/perl -l
$N=pop;print 1/$N*grep{my@a;$a[rand 10]++for 1..$ARGV[0];9<grep$_,@a}1
+..$N

        [download]
[reply]
[d/l]
Re: Golf: Pandigital puzzle
by Jenda (Abbot) on Nov 19, 2004 at 01:45 UTC

    Looks like I'm on 74 :-)

    $N=pop;for(1..$N){%h=map{int rand 10,0}1..$ARGV[0];$g+=keys%h>9}print$
+g/$N

    [download]

    I must admit though that I stole the pop() trick from tilly.

    Update: Actually not. The -l switch. 77.

    Update 2: 76:

    #!perl -l
$N=pop;for(1..$N){$g+=keys%{{map{int rand 10,0}1..$ARGV[0]}}>9}print$g
+/$N

    [download]

    Jenda
    We'd like to help you learn to help yourself
    Look around you, all you see are sympathetic eyes
    Stroll around the grounds until you feel at home
       -- P. Simon in Mrs. Robinson

[reply]
[d/l]
[select]
      Let's tweak that down to 72: 
      #!perl -l
$N=pop;print 1/$N*grep{keys%{{map{int
rand 10}1..$ARGV[0]*2}}>9}1..$N

      [download]
[reply]
[d/l]
        Further tweaking to 71 
        print 1/($N=pop)*grep{keys%{{map{int
rand 10}1..$ARGV[0]*2}}>9}1..$N

        [download]

        Update: If I can change the order of the parameters, I can get to 70. 
        $#a=2*pop;print 1/($N=pop)*grep{keys%{{map{int
rand 10}@a}}>9}1..$N

        [download]

        Being right, does not endow the right to be rude; politeness costs nothing.
        Being unknowing, is not the same as being stupid.
        Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
        Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

[reply]
[d/l]
[select]

Back to Meditations