Consider an answering machine with remote inquiry facility, where you can call the answering machine and enter a 4 digit passcode into your telephone keypad, so you can listen to the messages from anywhere you like. Many of these machines will let you in if you enter the correct consecutive sequence of digits, regardless of what preceded that sequence.

Example: Passcode is 1234.

if you feed the machine 1234, you're in.
if you feed the machine 01234, you're in.
if you feed the machine 0121234, you're in.
if you feed the machine 94129838701234, you're in.

To brute-force hack the machine, you could try all numbers from 0000 to 9999, sending 40000 sounds across the wire. But since you are a smart hacker, you see that there's room for optimization. What is the shortest series of digits you have to send to the answering machine in order to break the code in any case?

By starting with 9999 instead of 1234, using otherwise the same program, I got the theoretic minimum: 10003:

9999000010002000300040005000600070008000900110012001300140015001600170
0180019002100220023002400250026002700280029003100320033003400350036003
7003800390041004200430044004500460047004800490051005200530054005500560
0570058005900610062006300640065006600670068006900710072007300740075007
6007700780079008100820083008400850086008700880089009100920093009400950
0960097009800990101020103010401050106010701080109011101120113011401150
1160117011801190121012201230124012501260127012801290131013201330134013
5013601370138013901410142014301440145014601470148014901510152015301540
1550156015701580159016101620163016401650166016701680169017101720173017
4017501760177017801790181018201830184018501860187018801890191019201930
1940195019601970198019902020302040205020602070208020902110212021302140
2150216021702180219022102220223022402250226022702280229023102320233023
4023502360237023802390241024202430244024502460247024802490251025202530
2540255025602570258025902610262026302640265026602670268026902710272027
3027402750276027702780279028102820283028402850286028702880289029102920
2930294029502960297029802990303040305030603070308030903110312031303140
3150316031703180319032103220323032403250326032703280329033103320333033
4033503360337033803390341034203430344034503460347034803490351035203530
3540355035603570358035903610362036303640365036603670368036903710372037
3037403750376037703780379038103820383038403850386038703880389039103920
3930394039503960397039803990404050406040704080409041104120413041404150
4160417041804190421042204230424042504260427042804290431043204330434043
5043604370438043904410442044304440445044604470448044904510452045304540
4550456045704580459046104620463046404650466046704680469047104720473047
4047504760477047804790481048204830484048504860487048804890491049204930
4940495049604970498049905050605070508050905110512051305140515051605170
5180519052105220523052405250526052705280529053105320533053405350536053
7053805390541054205430544054505460547054805490551055205530554055505560
5570558055905610562056305640565056605670568056905710572057305740575057
6057705780579058105820583058405850586058705880589059105920593059405950
5960597059805990606070608060906110612061306140615061606170618061906210
6220623062406250626062706280629063106320633063406350636063706380639064
1064206430644064506460647064806490651065206530654065506560657065806590
6610662066306640665066606670668066906710672067306740675067606770678067
9068106820683068406850686068706880689069106920693069406950696069706980
6990707080709071107120713071407150716071707180719072107220723072407250
7260727072807290731073207330734073507360737073807390741074207430744074
5074607470748074907510752075307540755075607570758075907610762076307640
7650766076707680769077107720773077407750776077707780779078107820783078
4078507860787078807890791079207930794079507960797079807990808090811081
2081308140815081608170818081908210822082308240825082608270828082908310
8320833083408350836083708380839084108420843084408450846084708480849085
1085208530854085508560857085808590861086208630864086508660867086808690
8710872087308740875087608770878087908810882088308840885088608870888088
9089108920893089408950896089708980899090911091209130914091509160917091
8091909210922092309240925092609270928092909310932093309340935093609370
9380939094109420943094409450946094709480949095109520953095409550956095
7095809590961096209630964096509660967096809690971097209730974097509760
9770978097909810982098309840985098609870988098909910992099309940995099
6099709980999111121113111411151116111711181119112211231124112511261127
1128112911321133113411351136113711381139114211431144114511461147114811
4911521153115411551156115711581159116211631164116511661167116811691172
1173117411751176117711781179118211831184118511861187118811891192119311
9411951196119711981199121213121412151216121712181219122212231224122512
2612271228122912321233123412351236123712381239124212431244124512461247
1248124912521253125412551256125712581259126212631264126512661267126812
6912721273127412751276127712781279128212831284128512861287128812891292
1293129412951296129712981299131314131513161317131813191322132313241325
1326132713281329133213331334133513361337133813391342134313441345134613
4713481349135213531354135513561357135813591362136313641365136613671368
1369137213731374137513761377137813791382138313841385138613871388138913
9213931394139513961397139813991414151416141714181419142214231424142514
2614271428142914321433143414351436143714381439144214431444144514461447
1448144914521453145414551456145714581459146214631464146514661467146814
6914721473147414751476147714781479148214831484148514861487148814891492
1493149414951496149714981499151516151715181519152215231524152515261527
1528152915321533153415351536153715381539154215431544154515461547154815
4915521553155415551556155715581559156215631564156515661567156815691572
1573157415751576157715781579158215831584158515861587158815891592159315
9415951596159715981599161617161816191622162316241625162616271628162916
3216331634163516361637163816391642164316441645164616471648164916521653
1654165516561657165816591662166316641665166616671668166916721673167416
7516761677167816791682168316841685168616871688168916921693169416951696
1697169816991717181719172217231724172517261727172817291732173317341735
1736173717381739174217431744174517461747174817491752175317541755175617
5717581759176217631764176517661767176817691772177317741775177617771778
1779178217831784178517861787178817891792179317941795179617971798179918
1819182218231824182518261827182818291832183318341835183618371838183918
4218431844184518461847184818491852185318541855185618571858185918621863
1864186518661867186818691872187318741875187618771878187918821883188418
8518861887188818891892189318941895189618971898189919192219231924192519
2619271928192919321933193419351936193719381939194219431944194519461947
1948194919521953195419551956195719581959196219631964196519661967196819
6919721973197419751976197719781979198219831984198519861987198819891992
1993199419951996199719981999222232224222522262227222822292233223422352
2362237223822392243224422452246224722482249225322542255225622572258225
9226322642265226622672268226922732274227522762277227822792283228422852
2862287228822892293229422952296229722982299232324232523262327232823292
3332334233523362337233823392343234423452346234723482349235323542355235
6235723582359236323642365236623672368236923732374237523762377237823792
3832384238523862387238823892393239423952396239723982399242425242624272
4282429243324342435243624372438243924432444244524462447244824492453245
4245524562457245824592463246424652466246724682469247324742475247624772
4782479248324842485248624872488248924932494249524962497249824992525262
5272528252925332534253525362537253825392543254425452546254725482549255
3255425552556255725582559256325642565256625672568256925732574257525762
5772578257925832584258525862587258825892593259425952596259725982599262
6272628262926332634263526362637263826392643264426452646264726482649265
3265426552656265726582659266326642665266626672668266926732674267526762
6772678267926832684268526862687268826892693269426952696269726982699272
7282729273327342735273627372738273927432744274527462747274827492753275
4275527562757275827592763276427652766276727682769277327742775277627772
7782779278327842785278627872788278927932794279527962797279827992828292
8332834283528362837283828392843284428452846284728482849285328542855285
6285728582859286328642865286628672868286928732874287528762877287828792
8832884288528862887288828892893289428952896289728982899292933293429352
9362937293829392943294429452946294729482949295329542955295629572958295
9296329642965296629672968296929732974297529762977297829792983298429852
9862987298829892993299429952996299729982999333343335333633373338333933
4433453346334733483349335433553356335733583359336433653366336733683369
3374337533763377337833793384338533863387338833893394339533963397339833
9934343534363437343834393444344534463447344834493454345534563457345834
5934643465346634673468346934743475347634773478347934843485348634873488
3489349434953496349734983499353536353735383539354435453546354735483549
3554355535563557355835593564356535663567356835693574357535763577357835
7935843585358635873588358935943595359635973598359936363736383639364436
4536463647364836493654365536563657365836593664366536663667366836693674
3675367636773678367936843685368636873688368936943695369636973698369937
3738373937443745374637473748374937543755375637573758375937643765376637
6737683769377437753776377737783779378437853786378737883789379437953796
3797379837993838393844384538463847384838493854385538563857385838593864
3865386638673868386938743875387638773878387938843885388638873888388938
9438953896389738983899393944394539463947394839493954395539563957395839
5939643965396639673968396939743975397639773978397939843985398639873988
3989399439953996399739983999444454446444744484449445544564457445844594
4654466446744684469447544764477447844794485448644874488448944954496449
7449844994545464547454845494555455645574558455945654566456745684569457
5457645774578457945854586458745884589459545964597459845994646474648464
9465546564657465846594665466646674668466946754676467746784679468546864
6874688468946954696469746984699474748474947554756475747584759476547664
7674768476947754776477747784779478547864787478847894795479647974798479
9484849485548564857485848594865486648674868486948754876487748784879488
5488648874888488948954896489748984899494955495649574958495949654966496
7496849694975497649774978497949854986498749884989499549964997499849995
5556555755585559556655675568556955765577557855795586558755885589559655
9755985599565657565856595666566756685669567656775678567956865687568856
8956965697569856995757585759576657675768576957765777577857795786578757
8857895796579757985799585859586658675868586958765877587858795886588758
8858895896589758985899595966596759685969597659775978597959865987598859
8959965997599859996666766686669667766786679668766886689669766986699676
7686769677767786779678767886789679767986799686869687768786879688768886
8896897689868996969776978697969876988698969976998699977778777977887789
779877997878797888788978987899797988798979987999888898899898999

 10003

Posted by Charlie on 2004-05-24 14:49:11