Keep It Simple, Stupid PerlMonks

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

by sauoq (Abbot)
 on May 22, 2003 at 09:51 UTC ( #260016=note: print w/replies, xml ) Need Help??

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
+8010901110
1120113011401150116011701180119012101220123012401250126012701280129013
+1013201330
1340135013601370138013901410142014301440145014601470148014901510152015
+3015401550
1560157015801590161016201630164016501660167016801690171017201730174017
+5017601770
1780179018101820183018401850186018701880189019101920193019401950196019
+7019801990
2020302040205020602070208020902110212021302140215021602170218021902210
+2220223022
4022502260227022802290231023202330234023502360237023802390241024202430
+2440245024
6024702480249025102520253025402550256025702580259026102620263026402650
+2660267026
8026902710272027302740275027602770278027902810282028302840285028602870
+2880289029
1029202930294029502960297029802990303040305030603070308030903110312031
+3031403150
3160317031803190321032203230324032503260327032803290331033203330334033
+5033603370
3380339034103420343034403450346034703480349035103520353035403550356035
+7035803590
3610362036303640365036603670368036903710372037303740375037603770378037
+9038103820
3830384038503860387038803890391039203930394039503960397039803990404050
+4060407040
8040904110412041304140415041604170418041904210422042304240425042604270
+4280429043
1043204330434043504360437043804390441044204430444044504460447044804490
+4510452045
3045404550456045704580459046104620463046404650466046704680469047104720
+4730474047
5047604770478047904810482048304840485048604870488048904910492049304940
+4950496049
7049804990505060507050805090511051205130514051505160517051805190521052
+2052305240
5250526052705280529053105320533053405350536053705380539054105420543054
+4054505460
5470548054905510552055305540555055605570558055905610562056305640565056
+6056705680
5690571057205730574057505760577057805790581058205830584058505860587058
+8058905910
5920593059405950596059705980599060607060806090611061206130614061506160
+6170618061
9062106220623062406250626062706280629063106320633063406350636063706380
+6390641064
2064306440645064606470648064906510652065306540655065606570658065906610
+6620663066
4066506660667066806690671067206730674067506760677067806790681068206830
+6840685068
6068706880689069106920693069406950696069706980699070708070907110712071
+3071407150
7160717071807190721072207230724072507260727072807290731073207330734073
+5073607370
7380739074107420743074407450746074707480749075107520753075407550756075
+7075807590
7610762076307640765076607670768076907710772077307740775077607770778077
+9078107820
7830784078507860787078807890791079207930794079507960797079807990808090
+8110812081
3081408150816081708180819082108220823082408250826082708280829083108320
+8330834083
5083608370838083908410842084308440845084608470848084908510852085308540
+8550856085
7085808590861086208630864086508660867086808690871087208730874087508760
+8770878087
9088108820883088408850886088708880889089108920893089408950896089708980
+8990909110
9120913091409150916091709180919092109220923092409250926092709280929093
+1093209330
9340935093609370938093909410942094309440945094609470948094909510952095
+3095409550
9560957095809590961096209630964096509660967096809690971097209730974097
+5097609770
9780979098109820983098409850986098709880989099109920993099409950996099
+7099809991
1112111311141115111611171118111911221123112411251126112711281129113211
+3311341135
1136113711381139114211431144114511461147114811491152115311541155115611
+5711581159
1162116311641165116611671168116911721173117411751176117711781179118211
+8311841185
1186118711881189119211931194119511961197119811991212131214121512161217
+1218121912
2212231224122512261227122812291232123312341235123612371238123912421243
+1244124512
4612471248124912521253125412551256125712581259126212631264126512661267
+1268126912
7212731274127512761277127812791282128312841285128612871288128912921293
+1294129512
9612971298129913131413151316131713181319132213231324132513261327132813
+2913321333
1334133513361337133813391342134313441345134613471348134913521353135413
+5513561357
1358135913621363136413651366136713681369137213731374137513761377137813
+7913821383
1384138513861387138813891392139313941395139613971398139914141514161417
+1418141914
2214231424142514261427142814291432143314341435143614371438143914421443
+1444144514
4614471448144914521453145414551456145714581459146214631464146514661467
+1468146914
7214731474147514761477147814791482148314841485148614871488148914921493
+1494149514
9614971498149915151615171518151915221523152415251526152715281529153215
+3315341535
1536153715381539154215431544154515461547154815491552155315541555155615
+5715581559
1562156315641565156615671568156915721573157415751576157715781579158215
+8315841585
1586158715881589159215931594159515961597159815991616171618161916221623
+1624162516
2616271628162916321633163416351636163716381639164216431644164516461647
+1648164916
5216531654165516561657165816591662166316641665166616671668166916721673
+1674167516
7616771678167916821683168416851686168716881689169216931694169516961697
+1698169917
1718171917221723172417251726172717281729173217331734173517361737173817
+3917421743
1744174517461747174817491752175317541755175617571758175917621763176417
+6517661767
1768176917721773177417751776177717781779178217831784178517861787178817
+8917921793
1794179517961797179817991818191822182318241825182618271828182918321833
+1834183518
3618371838183918421843184418451846184718481849185218531854185518561857
+1858185918
6218631864186518661867186818691872187318741875187618771878187918821883
+1884188518
8618871888188918921893189418951896189718981899191922192319241925192619
+2719281929
1932193319341935193619371938193919421943194419451946194719481949195219
+5319541955
1956195719581959196219631964196519661967196819691972197319741975197619
+7719781979
1982198319841985198619871988198919921993199419951996199719981999222232
+2242225222
6222722282229223322342235223622372238223922432244224522462247224822492
+2532254225
5225622572258225922632264226522662267226822692273227422752276227722782
+2792283228
4228522862287228822892293229422952296229722982299232324232523262327232
+8232923332
3342335233623372338233923432344234523462347234823492353235423552356235
+7235823592
3632364236523662367236823692373237423752376237723782379238323842385238
+6238723882
3892393239423952396239723982399242425242624272428242924332434243524362
+4372438243
9244324442445244624472448244924532454245524562457245824592463246424652
+4662467246
8246924732474247524762477247824792483248424852486248724882489249324942
+4952496249
7249824992525262527252825292533253425352536253725382539254325442545254
+6254725482
5492553255425552556255725582559256325642565256625672568256925732574257
+5257625772
5782579258325842585258625872588258925932594259525962597259825992626272
+6282629263
3263426352636263726382639264326442645264626472648264926532654265526562
+6572658265
9266326642665266626672668266926732674267526762677267826792683268426852
+6862687268
8268926932694269526962697269826992727282729273327342735273627372738273
+9274327442
7452746274727482749275327542755275627572758275927632764276527662767276
+8276927732
7742775277627772778277927832784278527862787278827892793279427952796279
+7279827992
8282928332834283528362837283828392843284428452846284728482849285328542
+8552856285
7285828592863286428652866286728682869287328742875287628772878287928832
+8842885288
6288728882889289328942895289628972898289929293329342935293629372938293
+9294329442
9452946294729482949295329542955295629572958295929632964296529662967296
+8296929732
9742975297629772978297929832984298529862987298829892993299429952996299
+7299829993
3334333533363337333833393344334533463347334833493354335533563357335833
+5933643365
3366336733683369337433753376337733783379338433853386338733883389339433
+9533963397
3398339934343534363437343834393444344534463447344834493454345534563457
+3458345934
6434653466346734683469347434753476347734783479348434853486348734883489
+3494349534
9634973498349935353635373538353935443545354635473548354935543555355635
+5735583559
3564356535663567356835693574357535763577357835793584358535863587358835
+8935943595
3596359735983599363637363836393644364536463647364836493654365536563657
+3658365936
6436653666366736683669367436753676367736783679368436853686368736883689
+3694369536
9636973698369937373837393744374537463747374837493754375537563757375837
+5937643765
3766376737683769377437753776377737783779378437853786378737883789379437
+9537963797
3798379938383938443845384638473848384938543855385638573858385938643865
+3866386738
6838693874387538763877387838793884388538863887388838893894389538963897
+3898389939
3944394539463947394839493954395539563957395839593964396539663967396839
+6939743975
3976397739783979398439853986398739883989399439953996399739983999444454
+4464447444
8444944554456445744584459446544664467446844694475447644774478447944854
+4864487448
8448944954496449744984499454546454745484549455545564557455845594565456
+6456745684
5694575457645774578457945854586458745884589459545964597459845994646474
+6484649465
5465646574658465946654666466746684669467546764677467846794685468646874
+6884689469
5469646974698469947474847494755475647574758475947654766476747684769477
+5477647774
7784779478547864787478847894795479647974798479948484948554856485748584
+8594865486
6486748684869487548764877487848794885488648874888488948954896489748984
+8994949554
9564957495849594965496649674968496949754976497749784979498549864987498
+8498949954
9964997499849995555655575558555955665567556855695576557755785579558655
+8755885589
5596559755985599565657565856595666566756685669567656775678567956865687
+5688568956
9656975698569957575857595766576757685769577657775778577957865787578857
+8957965797
5798579958585958665867586858695876587758785879588658875888588958965897
+5898589959
5966596759685969597659775978597959865987598859895996599759985999666676
+6686669667
7667866796687668866896697669866996767686769677767786779678767886789679
+7679867996
8686968776878687968876888688968976898689969697769786979698769886989699
+7699869997
7778777977887789779877997878797888788978987899797988798979987999888898
+8998989999
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.";
```

Replies are listed 'Best First'.
Re: Re: Shortest string containing all from 0000 to 9999 challenge.
by EvdB (Deacon) on May 22, 2003 at 11:33 UTC
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

Create A New User
Node Status?
node history
Node Type: note [id://260016]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (9)
As of 2018-07-18 14:50 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 (393 votes). Check out past polls.

Notices?