Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

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 ( #260184=note: print w/replies, xml ) Need Help??


in reply to Re^2: Shortest string containing all from 0000 to 9999 challenge. (how many?)
in thread Shortest string containing all from 0000 to 9999 challenge.

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";
-sauoq
"My two cents aren't worth a dime.";
  • Comment on Re: Re^2: Shortest string containing all from 0000 to 9999 challenge. (how many?)
  • Download Code

Replies are listed 'Best First'.
Re^4: Shortest string containing all from 0000 to 9999 challenge. (how many?)
by tye (Sage) on May 22, 2003 at 19:49 UTC

    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

      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.";
      

        Oops. I misread that you were starting with '9' as well as starting with '9999'. (Did I mention I'm busy today?)

        BTW, trim '9000' off the end of the first and '9999' off the front of the second, and you get the same substring.

                        - tye

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://260184]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (3)
As of 2017-11-21 05:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    In order to be able to say "I know Perl", you must have:













    Results (295 votes). Check out past polls.

    Notices?