Wrong.

By the way it's not that sure that you can start with every 4 digit number. I think you can - but you need to prove it.

Update: Or is it right? Let's have two differend 4 digit strings - if they are different then at least on one of the 4 position they have different digits - the permutation will change those digits to different digits as well. It means the permutation induces a 1-1 function on the 10000 4 digit strings. There can't be any more of them so in the whole resulting string there will be exactly 10000 different 4 digit strings. QED

That was long time since I proved a theorem.

By the way it's not that sure that you can start with every 4 digit number. I think you can - but you need to prove it.

You can.

First, it is sufficient to prove that you can do it with every possible pattern of same/differing numbers. Permutations take care of the rest. (Your thinking on that was fine, by the way.) There are only twelve such patterns: AAAA AAAB AABA ABAA BAAA AABC ABAC ABCA BAAC BACA BCAA ABCD. All you have to do is choose A, B, C, and D as four different digits and find a solution for each one. I chose A=0, B=1, C=2, and D=3 and then, using the same code in my original solution, found that there was indeed a solution for each of the 12 patterns.

So, for a lower bound, we have at least 12 * 10! (or the number of starting patterns multiplied by the permutations.)

Some other interesting facts (proofs left as an exercise):

• The reverse of a valid solution is a valid solution.
• No valid solutions are palindromic.

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

I meant unique in the 'these two string compare differently' sense, rather that the set theory sense.

---

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller

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... ):

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

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

update:i fixed a typo in the name of the sequences, when BrowserUK alerted me of my misspelling

.-enlil