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?

My algorithm was to seek as each next digit one that will complete a previously unused 4-digit number.  If no digit could do that, then choose the digit that would be the 3rd digit in as many still-unsent 4-digit numbers as possible.  If none such existed then choose the digit that would be the 2nd digit in as many still unsent 4-digit numbers as possible.  If none such existed then choose the digit that would be the 1st digit in as many still unsent 4-digit numbers as possible.

I arbitrarily started with "1234".

A string of 10063 digits was found:

1234000010002000300040011001200130014002100220023002400310032003300340
1010201030104011101120113011401210122012301240131013201330134020203020
4021102120213021402210222022302240231023202330234100410141024103110321
0331034110411112111311141122112311241132113311341203120412121312141222
1223122412321233123500050015002500350105011501250135020502150225023510
0510151025103511051115112511351205121512251236000600160026003601060116
0126013602060216022602361006101610261036110611161126113612061216122612
3700070017002700370107011701270137020702170227023710071017102710371107
1117112711371207121712271238000800180028003801080118012801380208021802
2802381008101810281038110811181128113812081218122812390009001900290039
0109011901290139020902190229023910091019102910391109111911291139120912
1912291232203221322223230303130323131323240304031403241304131413242004
2014202421042114212422042214222423042314232503050315032513051315132520
0520152025210521152125220522152225230523152326030603160326130613161326
2006201620262106211621262206221622262306231623270307031703271307131713
2720072017202721072117212722072217222723072317232803080318032813081318
1328200820182028210821182128220822182228230823182329030903190329130913
1913292009201920292109211921292209221922292309231923203320430043104320
5300531053206300631063207300731073208300831083209300931093203420352036
2037203820392033303340335033603370338033903321332233233313332430143024
3114312432143224330433143325301530253115312532153225330533153326301630
2631163126321632263306331633273017302731173127321732273307331733283018
3028311831283218322833083318332930193029311931293219322933093319332342
1342234303431343235213522353035313532362136223630363136323721372237303
7313732382138223830383138323921392239303931393233413342335133523361336
2337133723381338233913392333343335333633373338333933344004401440244034
4104411441244134420442144224423443044314432443345004501450245034510451
1451245134520452145224523453045314532453346004601460246034610461146124
6134620462146224623463046314632463347004701470247034710471147124713472
0472147224723473047314732473348004801480248034810481148124813482048214
8224823483048314832483349004901490249034910491149124913492049214922492
3493049314932493340404140424043405040514052405340604061406240634070407
1407240734080408140824083409040914092409340444045400540154025403540464
0064016402640364047400740174027403740484008401840284038404940094019402
9403940415041604170418041904141424143414441454105411541254135414641064
1164126413641474107411741274137414841084118412841384149410941194129413
9414151416141714181419141524153415420542154305431544054415500550155105
5115520552155305531554055415600560156105611562056215630563156405641570
0570157105711572057215730573157405741580058015810581158205821583058315
8405841590059015910591159205921593059315940594150505150605061507050715
0805081509050915042504350445045502550355046500650165026503650475007501
7502750375048500850185028503850495009501950295039504260427042804290425
1425242425342434254225432544244425512552255325542354245425602561256225
6325642064216422642364246425702571257225732574207421742274237424742580
2581258225832584208421842284238424842590259125922593259420942194229423
9424942505250625072508250925053505450555056505750585059505160517051805
1905151525153514351545144515551355145515651065116512651365146515751075
1175127513751475158510851185128513851485159510951195129513951495151615
1715181519151624162516341635063516430643164406441645064516520652165306
5316540654165506551660066016610661166206621663066316640664166506651670
0670167106711672067216730673167406741675067516800680168106811682068216
8306831684068416850685169006901691069116920692169306931694069416950695
1606061607060716080608160906091605260536043605460446055603560456056602
6603660466057600760176027603760476058600860186028603860486059600960196
0296039604960527052805290526142615262426252526342635243525352643264426
4524452545265226532654265523552455255526612662266326642665236524652565
2670267126722673267426752075217522752375247525752680268126822683268426
8520852185228523852485258526902691269226932694269520952195229523952495
2595260626072608260926063606460656066606760686069606170618061906161626
1636143615361646144615461656135614561556166613661466156616761076117612
7613761476157616861086118612861386148615861696109611961296139614961596
1617161816191617241725172617341735073517360736174307431744074417450745
1746074617530753175407541755075517560756176207621763076317640764176507
6517660766177007701771077117720772177307731774077417750775177607761780
0780178107811782078217830783178407841785078517860786179007901791079117
9207921793079317940794179507951796079617070717080708170907091706270637
0437053706470447054706570357045705570667036704670567067702770377047705
7706870087018702870387048705870697009701970297039704970597062806290627
1427152716272427252726262734273527362436253626362743274427452746244625
4626462753275427552756235624562556265627622763276427652766236624662566
2666277127722773277427752776237624762576267627802781278227832784278527
8620862186228623862486258626862790279127922793279427952796209621962296
2396249625962696270727082709270737074707570767077707870797071807190717
1727173714371537163717471447154716471757135714571557165717671367146715
6716671777137714771577167717871087118712871387148715871687179710971197
1297139714971597169717181719171824182518261827183418350835183608361837
0837184308431844084418450845184608461847084718530853185408541855085518
5608561857085718630863186408641865086518660866186708671872087218730873
1874087418750875187608761877087718800880188108811882088218830883188408
8418850885188608861887088718900890189108911892089218930893189408941895
0895189608961897089718080818090809180728073804380538063807480448054806
4807580358045805580658076803680468056806680778037804780578067807880288
0388048805880688079800980198029803980498059806980729072814281528162817
2824282528262827272834283528362837243725372637273728432844284528462847
2447254726472747285328542855285628572357245725572657275728632864286528
6628672367246725672667276728722873287428752876287723772477257726772777
2881288228832884288528862887238724872587268727872890289128922893289428
9528962897209721972297239724972597269727972808280928083808480858086808
7808880898081908181828183814381538163817381848144815481648174818581358
1458155816581758186813681468156816681768187813781478157816781778188813
8814881588168817881898109811981298139814981598169817981819181924192519
2619271928193419350935193609361937093719380938194309431944094419450945
1946094619470947194809481953095319540954195509551956095619570957195809
5819630963196409641965096519660966196709671968096819730973197409741975
0975197609761977097719780978198209821983098319840984198509851986098619
8709871988098819900990199109911992099219930993199409941995099519960996
1997099719980998190909190829083904390539063907390849044905490649074908
5903590459055906590759086903690469056906690769087903790479057906790779
0889038904890589068907890899029903990499059906990799089912991359136913
7913891399142914391449145914691479148914991529153915491559156915791589
1599162916391649165916691679168916991729173917491759176917791789179918
2918391849185918691879188918992298229923582359236823692378237923882389
2398239924292438243924482449245824592468246924782479248824892498249925
2925382539254825492558255925682569257825792588258925982599262926382639
2648264926582659266826692678267926882689269826992729273827392748274927
5827592768276927782779278827892798279928282928382839284828492858285928
6828692878287928882889289828993294329532963297329832993354335533563357
3358335933643365336633673368336933743375337633773378337933843385338633
8733883389339433953396339733983399342934343534363437343834393444344534
4634473448344934543455345634573458345934643465346634673468346934743475
3476347734783479348434853486348734883489349434953496349734983499352935
3536353735383539354435453546354735483549355435553556355735583559356435
6535663567356835693574357535763577357835793584358535863587358835893594
3595359635973598359936293636373638363936443645364636473648364936543655
3656365736583659366436653666366736683669367436753676367736783679368436
8536863687368836893694369536963697369836993729373738373937443745374637
4737483749375437553756375737583759376437653766376737683769377437753776
3777377837793784378537863787378837893794379537963797379837993829383839
3844384538463847384838493854385538563857385838593864386538663867386838
6938743875387638773878387938843885388638873888388938943895389638973898
3899429442954296429742984299439443954396439743984399444454446444744484
4494455445644574458445944654466446744684469447544764477447844794485448
6448744884489449544964497449844994529453945454645474548454945554556455
7455845594565456645674568456945754576457745784579458545864587458845894
5954596459745984599462946394646474648464946554656465746584659466546664
6674668466946754676467746784679468546864687468846894695469646974698469
9472947394747484749475547564757475847594765476647674768476947754776477
7477847794785478647874788478947954796479747984799482948394848494855485
6485748584859486548664867486848694875487648774878487948854886488748884
8894895489648974898489952955296529752985299539553965397539853995495549
6549754985499555565557555855595566556755685569557655775578557955865587
5588558955965597559855995629563956495656575658565956665667566856695676
5677567856795686568756885689569656975698569957295739574957575857595766
5767576857695776577757785779578657875788578957965797579857995829583958
4958585958665867586858695876587758785879588658875888588958965897589858
9962966297629862996396639763986399649664976498649965966597659865996666
7666866696677667866796687668866896697669866996729673967496759676768676
9677767786779678767886789679767986799682968396849685968686968776878687
9688768886889689768986899729772987299739773987399749774987499759775987
5997697769876997777877797788778977987799782978397849785978697878797888
7889789878998298829983988399849884998598859986988699879887998888988999
0929093909490959096909790989099919192919391949195919691979198919992929
3929492959296929792989299939394939593969397939893999494959496949794989
49995959695979598959996969796989699979798979998989999
 10063 

The program:

DEFINT A-Z
DIM nums(10000)
seq$ = "1234"
nums(1234) = 1
numCt = 1

DO
 pref = 10 * VAL(RIGHT$(seq$, 3))
 dig = -1
 FOR add = 0 TO 9
  IF nums(pref + add) = 0 THEN dig = add: EXIT FOR
 NEXT
 IF dig < 0 THEN
   pref = 100 * VAL(RIGHT$(seq$, 2))
   bestCt = 0
   REDIM digCt(10)
   FOR add = 0 TO 99
    IF nums(pref + add) = 0 THEN
      dig1 = add \ 10
      digCt(dig1) = digCt(dig1) + 1
      IF digCt(dig1) > bestCt THEN bestCt = digCt(dig1): bestDig = dig1
    END IF
   NEXT
   IF bestCt > 0 THEN dig = bestDig
 END IF
 IF dig < 0 THEN
   pref = 1000 * VAL(RIGHT$(seq$, 1))
   bestCt = 0
   REDIM digCt(10)
   FOR add = 0 TO 999
    IF nums(pref + add) = 0 THEN
      dig1 = add \ 100
      digCt(dig1) = digCt(dig1) + 1
      IF digCt(dig1) > bestCt THEN bestCt = digCt(dig1): bestDig = dig1
    END IF
   NEXT
   IF bestCt > 0 THEN dig = bestDig
 END IF
 IF dig < 0 THEN
   pref = 0
   bestCt = 0
   REDIM digCt(10)
   FOR add = 0 TO 9999
    IF nums(pref + add) = 0 THEN
      dig1 = add \ 1000
      digCt(dig1) = digCt(dig1) + 1
      IF digCt(dig1) > bestCt THEN bestCt = digCt(dig1): bestDig = dig1
    END IF
   NEXT
   IF bestCt > 0 THEN dig = bestDig
 END IF
 IF dig >= 0 THEN
   currNum = VAL(RIGHT$(seq$, 3)) * 10 + dig
   IF nums(currNum) = 0 THEN
     nums(currNum) = 1
     numCt = numCt + 1
   END IF
   seq$ = seq$ + LTRIM$(STR$(dig))
 END IF
LOOP UNTIL numCt = 10000
OPEN "phonansh.txt" FOR OUTPUT AS #2
 FOR block = 1 TO 10063 STEP 70
  PRINT #2, MID$(seq$, block, 70)
 NEXT
 PRINT #2, LEN(seq$)
CLOSE
PRINT seq$, LEN(seq$)

Posted by Charlie on 2004-05-24 14:34:13