Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Comment on

( #3333=superdoc: 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.";

In reply to Re: Shortest string containing all from 0000 to 9999 challenge. by sauoq
in thread Shortest string containing all from 0000 to 9999 challenge. by EvdB

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others meditating upon the Monastery: (5)
    As of 2017-11-19 00:31 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      In order to be able to say "I know Perl", you must have:













      Results (278 votes). Check out past polls.

      Notices?