in reply to Re: Shortest string containing all from 0000 to 9999 challenge.
in thread Shortest string containing all from 0000 to 9999 challenge.

Based on a naive statistical analysis, we might expect about 2.8e5659 unique shortest strings. I got this number by computing the odds of a string of 10003 digits being a solution and multiplying that by the number of 10003-digit strings. Of course, floating point won't handle that. I got around this by reducing the formula a bit and computing the log() of the value instead and dividing by log(10) to get about 5659.45 ( all from the "perl -de 0" prompt, just in case anyone thought this was off-topic q-: ).

The odds of me having made a mistake in this calculation are rather large (it was a quick hack with no double checking -- both the math and the arithmatic). I'll try to find time later to post my analysis and code used to do the calculations.

I'm also not convinced (having not spent much time thinking about it) that a naive statistical analysis would be very valid. My qualms here appear to be diminishing the more I think about it (in part because the answer is so *huge*), but I still think the worry is worth mentioning.

It certainly was an interesting problem. (:

Also note that sauoq has shown us the lexicographically first of the shortest strings.

I also have an inkling that we can eliminate the backtracking in sauoq's program (or maybe not...). But I've got real work™ to do... ):

                - tye
  • Comment on Re^2: Shortest string containing all from 0000 to 9999 challenge. (how many?)

Replies are listed 'Best First'.
Re: Re^2: Shortest string containing all from 0000 to 9999 challenge. (how many?)
by sauoq (Abbot) on May 22, 2003 at 19:33 UTC
    I also have an inkling that we can eliminate the backtracking in sauoq's program (or maybe not...).

    Your intuition is right. My (much nicer) second try below generates a valid solution string without backtracking. Notice it isn't the same string as my original answer though. (Nor is it a permutation.)

    #!/usr/bin/perl -w
use strict; 

my $string = '9999';  # Starting with nines simplifies the loop
my %seen = ( $string => 1 ); 
my $seen = 1;

while ($seen < 10000) {
    for (0 .. 9) {
        my $candidate = substr($string, -3) . $_; 
        next if $seen{$candidate}; 
        $string .= $_;
        $seen{$candidate} ++; 
        $seen++; 
        last;
    }
}

print $string, "\n";

    [download]
    -sauoq
"My two cents aren't worth a dime.";
[reply]
[d/l]

      It isn't a permutation, but I suspect you can swap between them with y/0-9/9876543210/ and that it is the lexicographically last shortest solution. (:

                      - tye
[reply]
[d/l]

        Nope. This one starts with "9999", so the translation would start with "0000" which would sort before this one (hence, it couldn't be last.)

        I think you will get the lexicographically last shortest if you perform that translation on the lexicographically first shortest though. :-)

        -sauoq
"My two cents aren't worth a dime.";
[reply]

In Section Meditations