The stupid question is the question not asked 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??

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?)

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

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 exploiting the Monastery: (8)
As of 2018-07-16 07:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
It has been suggested to rename Perl 6 in order to boost its marketing potential. Which name would you prefer?

Results (333 votes). Check out past polls.

Notices?