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

[sauoq]

What is the shortest string that contains all the numbers from 0000 to 9999.

Assuming the numbers must all have 4 digits, the shortest theoretical length is 10003 digits if you can get them to overlap perfectly (10000 unique numbers and 3 digits of overhead.) As it happens, you can do it perfectly. Here's one example (be careful of newlines if you copy and paste it):

0000100020003000400050006000700080009001100120013001400150016001700180
+0190021002
2002300240025002600270028002900310032003300340035003600370038003900410
+0420043004
4004500460047004800490051005200530054005500560057005800590061006200630
+0640065006
6006700680069007100720073007400750076007700780079008100820083008400850
+0860087008
8008900910092009300940095009600970098009901010201030104010501060107010
[phone]
1120113011401150116011701180119012101220123012401250126012701280129013
[phone]
1340135013601370138013901410142014301440145014601470148014901510152015
[phone]
1560157015801590161016201630164016501660167016801690171017201730174017
[phone]
1780179018101820183018401850186018701880189019101920193019401950196019
[phone]
2020302040205020602070208020902110212021302140215021602170218021902210
[phone]
4022502260227022802290231023202330234023502360237023802390241024202430
[phone]
6024702480249025102520253025402550256025702580259026102620263026402650
[phone]
8026902710272027302740275027602770278027902810282028302840285028602870
[phone]
1029202930294029502960297029802990303040305030603070308030903110312031
[phone]
3160317031803190321032203230324032503260327032803290331033203330334033
[phone]
3380339034103420343034403450346034703480349035103520353035403550356035
[phone]
3610362036303640365036603670368036903710372037303740375037603770378037
[phone]
3830384038503860387038803890391039203930394039503960397039803990404050
[phone]
8040904110412041304140415041604170418041904210422042304240425042604270
[phone]
1043204330434043504360437043804390441044204430444044504460447044804490
[phone]
3045404550456045704580459046104620463046404650466046704680469047104720
[phone]
5047604770478047904810482048304840485048604870488048904910492049304940
[phone]
7049804990505060507050805090511051205130514051505160517051805190521052
[phone]
5250526052705280529053105320533053405350536053705380539054105420543054
[phone]
5470548054905510552055305540555055605570558055905610562056305640565056
[phone]
5690571057205730574057505760577057805790581058205830584058505860587058
[phone]
5920593059405950596059705980599060607060806090611061206130614061506160
[phone]
9062106220623062406250626062706280629063106320633063406350636063706380
[phone]
2064306440645064606470648064906510652065306540655065606570658065906610
[phone]
4066506660667066806690671067206730674067506760677067806790681068206830
[phone]
6068706880689069106920693069406950696069706980699070708070907110712071
[phone]
7160717071807190721072207230724072507260727072807290731073207330734073
[phone]
7380739074107420743074407450746074707480749075107520753075407550756075
[phone]
7610762076307640765076607670768076907710772077307740775077607770778077
[phone]
7830784078507860787078807890791079207930794079507960797079807990808090
[phone]
3081408150816081708180819082108220823082408250826082708280829083108320
[phone]
5083608370838083908410842084308440845084608470848084908510852085308540
[phone]
7085808590861086208630864086508660867086808690871087208730874087508760
[phone]
9088108820883088408850886088708880889089108920893089408950896089708980
[phone]
9120913091409150916091709180919092109220923092409250926092709280929093
[phone]
9340935093609370938093909410942094309440945094609470948094909510952095
[phone]
9560957095809590961096209630964096509660967096809690971097209730974097
[phone]
9780979098109820983098409850986098709880989099109920993099409950996099
[phone]
1112111311141115111611171118111911221123112411251126112711281129113211
[phone]
1136113711381139114211431144114511461147114811491152115311541155115611
[phone]
1162116311641165116611671168116911721173117411751176117711781179118211
[phone]
1186118711881189119211931194119511961197119811991212131214121512161217
[phone]
2212231224122512261227122812291232123312341235123612371238123912421243
[phone]
4612471248124912521253125412551256125712581259126212631264126512661267
[phone]
7212731274127512761277127812791282128312841285128612871288128912921293
[phone]
9612971298129913131413151316131713181319132213231324132513261327132813
[phone]
1334133513361337133813391342134313441345134613471348134913521353135413
[phone]
1358135913621363136413651366136713681369137213731374137513761377137813
[phone]
1384138513861387138813891392139313941395139613971398139914141514161417
[phone]
2214231424142514261427142814291432143314341435143614371438143914421443
[phone]
4614471448144914521453145414551456145714581459146214631464146514661467
[phone]
7214731474147514761477147814791482148314841485148614871488148914921493
[phone]
9614971498149915151615171518151915221523152415251526152715281529153215
[phone]
1536153715381539154215431544154515461547154815491552155315541555155615
[phone]
1562156315641565156615671568156915721573157415751576157715781579158215
[phone]
1586158715881589159215931594159515961597159815991616171618161916221623
[phone]
2616271628162916321633163416351636163716381639164216431644164516461647
[phone]
5216531654165516561657165816591662166316641665166616671668166916721673
[phone]
7616771678167916821683168416851686168716881689169216931694169516961697
[phone]
1718171917221723172417251726172717281729173217331734173517361737173817
[phone]
1744174517461747174817491752175317541755175617571758175917621763176417
[phone]
1768176917721773177417751776177717781779178217831784178517861787178817
[phone]
1794179517961797179817991818191822182318241825182618271828182918321833
[phone]
3618371838183918421843184418451846184718481849185218531854185518561857
[phone]
6218631864186518661867186818691872187318741875187618771878187918821883
[phone]
8618871888188918921893189418951896189718981899191922192319241925192619
[phone]
1932193319341935193619371938193919421943194419451946194719481949195219
[phone]
1956195719581959196219631964196519661967196819691972197319741975197619
[phone]
1982198319841985198619871988198919921993199419951996199719981999222232
[phone]
6222722282229223322342235223622372238223922432244224522462247224822492
[phone]
5225622572258225922632264226522662267226822692273227422752276227722782
[phone]
4228522862287228822892293229422952296229722982299232324232523262327232
[phone]
3342335233623372338233923432344234523462347234823492353235423552356235
[phone]
3632364236523662367236823692373237423752376237723782379238323842385238
[phone]
3892393239423952396239723982399242425242624272428242924332434243524362
[phone]
9244324442445244624472448244924532454245524562457245824592463246424652
[phone]
8246924732474247524762477247824792483248424852486248724882489249324942
[phone]
7249824992525262527252825292533253425352536253725382539254325442545254
[phone]
5492553255425552556255725582559256325642565256625672568256925732574257
[phone]
5782579258325842585258625872588258925932594259525962597259825992626272
[phone]
3263426352636263726382639264326442645264626472648264926532654265526562
[phone]
9266326642665266626672668266926732674267526762677267826792683268426852
[phone]
8268926932694269526962697269826992727282729273327342735273627372738273
[phone]
7452746274727482749275327542755275627572758275927632764276527662767276
[phone]
7742775277627772778277927832784278527862787278827892793279427952796279
[phone]
8282928332834283528362837283828392843284428452846284728482849285328542
[phone]
7285828592863286428652866286728682869287328742875287628772878287928832
[phone]
6288728882889289328942895289628972898289929293329342935293629372938293
[phone]
9452946294729482949295329542955295629572958295929632964296529662967296
[phone]
9742975297629772978297929832984298529862987298829892993299429952996299
[phone]
3334333533363337333833393344334533463347334833493354335533563357335833
[phone]
3366336733683369337433753376337733783379338433853386338733883389339433
[phone]
3398339934343534363437343834393444344534463447344834493454345534563457
[phone]
6434653466346734683469347434753476347734783479348434853486348734883489
[phone]
9634973498349935353635373538353935443545354635473548354935543555355635
[phone]
3564356535663567356835693574357535763577357835793584358535863587358835
[phone]
3596359735983599363637363836393644364536463647364836493654365536563657
[phone]
6436653666366736683669367436753676367736783679368436853686368736883689
[phone]
9636973698369937373837393744374537463747374837493754375537563757375837
[phone]
3766376737683769377437753776377737783779378437853786378737883789379437
[phone]
3798379938383938443845384638473848384938543855385638573858385938643865
[phone]
6838693874387538763877387838793884388538863887388838893894389538963897
[phone]
3944394539463947394839493954395539563957395839593964396539663967396839
[phone]
3976397739783979398439853986398739883989399439953996399739983999444454
[phone]
8444944554456445744584459446544664467446844694475447644774478447944854
[phone]
8448944954496449744984499454546454745484549455545564557455845594565456
[phone]
5694575457645774578457945854586458745884589459545964597459845994646474
[phone]
5465646574658465946654666466746684669467546764677467846794685468646874
[phone]
5469646974698469947474847494755475647574758475947654766476747684769477
[phone]
7784779478547864787478847894795479647974798479948484948554856485748584
[phone]
6486748684869487548764877487848794885488648874888488948954896489748984
[phone]
9564957495849594965496649674968496949754976497749784979498549864987498
[phone]
9964997499849995555655575558555955665567556855695576557755785579558655
[phone]
5596559755985599565657565856595666566756685669567656775678567956865687
[phone]
9656975698569957575857595766576757685769577657775778577957865787578857
[phone]
5798579958585958665867586858695876587758785879588658875888588958965897
[phone]
5966596759685969597659775978597959865987598859895996599759985999666676
[phone]
7667866796687668866896697669866996767686769677767786779678767886789679
[phone]
8686968776878687968876888688968976898689969697769786979698769886989699
[phone]
7778777977887789779877997878797888788978987899797988798979987999888898
[phone]
000

The (admittedly lousy) script I used follows. It's a bit c-ish...

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

my $string = '0000';  # Might as well start somewhere.
my %seen = ( $string => 1 );
my $seen = 1;

sub see {
    my $n = shift;
    $seen{$n}++;
    $seen++ if $seen{$n} == 1;
    return $seen{$n} == 1;
}

sub unsee {
    $seen{substr($string, -4)}--;
    $seen--;
    return substr($string, -1, 1, '');
}



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

    if (! $sawnew) {
        do {
            $last = unsee();
        } until ($last != 9);
        $last += 1;
        next;
    }

    print "seen: $seen\n", "len : ", length $string, "\n";
}

print $string, "\n";

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

[EvdB]

Very nicely done - although I wish you had waited until after the weekend to show me up...

--tidiness is the memory loss of environmental mnemonics