Beefy Boxes and Bandwidth Generously Provided by pair Networks
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??


in reply to Shortest string containing all from 0000 to 9999 challenge.

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

Log In?
Username:
Password:

What's my password?
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?