A Very Long Alarm Code

NullRoot · 2007-11-20 03:29:52

My first real post and hopefully one that will get a varied approach with some interesting answers.

There exists an alarm system that requires a 4-digit code. The alarm doesn't mind how many digits you type in, so long as the string of digits contains the correct code. For instance:
If the access code is 1234 then the alarm would turn off if the following sequence was input:
347212345860.

The question is, what is the shortest string of numbers we could input that would cover every possible combination of 4-digit access codes using the standard keys 0 to 9?

My thoughts so far on this have been that we could use log10 to deduce the length of the number, so I'm more concerned about how we might go about constructing it.
The absolute worse case scenario would be 40,000 digits; every possible 4 digit code of which there are 10,000 - 0000 to 9999.
This wouldn't necessarily be required, however, since if we used that method we would have:
00000001000200030004...
which we could happily 'truncate' to:
00001000200030004...
and still fulfill the need for the combination '0000'. I also notice that 1000, 2000, 3000, etc. are in these first few numbers, too, along with the 00X0 and 0X00 combinations.

So is there an approach of choice to this type of problem? If so, please point me in the right direction. If not, let's hear some thoughts on where we can begin!

Ricky · 2007-11-20 11:30:53

10003:

0000100020003000400050006000700080009001100120013001400150016001700180019002100220023002400250026002700280029003100320033003400350036003700380039004100420043004400450046004700480049005100520053005400550056005700580059006100620063006400650066006700680069007100720073007400750076007700780079008100820083008400850086008700880089009100920093009400950096009700980099010102010301040105010601070108010901110112011301140115011601170118011901210122012301240125012601270128012901310132013301340135013601370138013901410142014301440145014601470148014901510152015301540155015601570158015901610162016301640165016601670168016901710172017301740175017601770178017901810182018301840185018601870188018901910192019301940195019601970198019902020302040205020602070208020902110212021302140215021602170218021902210222022302240225022602270228022902310232023302340235023602370238023902410242024302440245024602470248024902510252025302540255025602570258025902610262026302640265026602670268026902710272027302740275027602770278027902810282028302840285028602870288028902910292029302940295029602970298029903030403050306030703080309031103120313031403150316031703180319032103220323032403250326032703280329033103320333033403350336033703380339034103420343034403450346034703480349035103520353035403550356035703580359036103620363036403650366036703680369037103720373037403750376037703780379038103820383038403850386038703880389039103920393039403950396039703980399040405040604070408040904110412041304140415041604170418041904210422042304240425042604270428042904310432043304340435043604370438043904410442044304440445044604470448044904510452045304540455045604570458045904610462046304640465046604670468046904710472047304740475047604770478047904810482048304840485048604870488048904910492049304940495049604970498049905050605070508050905110512051305140515051605170518051905210522052305240525052605270528052905310532053305340535053605370538053905410542054305440545054605470548054905510552055305540555055605570558055905610562056305640565056605670568056905710572057305740575057605770578057905810582058305840585058605870588058905910592059305940595059605970598059906060706080609061106120613061406150616061706180619062106220623062406250626062706280629063106320633063406350636063706380639064106420643064406450646064706480649065106520653065406550656065706580659066106620663066406650666066706680669067106720673067406750676067706780679068106820683068406850686068706880689069106920693069406950696069706980699070708070907110712071307140715071607170718071907210722072307240725072607270728072907310732073307340735073607370738073907410742074307440745074607470748074907510752075307540755075607570758075907610762076307640765076607670768076907710772077307740775077607770778077907810782078307840785078607870788078907910792079307940795079607970798079908080908110812081308140815081608170818081908210822082308240825082608270828082908310832083308340835083608370838083908410842084308440845084608470848084908510852085308540855085608570858085908610862086308640865086608670868086908710872087308740875087608770878087908810882088308840885088608870888088908910892089308940895089608970898089909091109120913091409150916091709180919092109220923092409250926092709280929093109320933093409350936093709380939094109420943094409450946094709480949095109520953095409550956095709580959096109620963096409650966096709680969097109720973097409750976097709780979098109820983098409850986098709880989099109920993099409950996099709980999111121113111411151116111711181119112211231124112511261127112811291132113311341135113611371138113911421143114411451146114711481149115211531154115511561157115811591162116311641165116611671168116911721173117411751176117711781179118211831184118511861187118811891192119311941195119611971198119912121312141215121612171218121912221223122412251226122712281229123212331234123512361237123812391242124312441245124612471248124912521253125412551256125712581259126212631264126512661267126812691272127312741275127612771278127912821283128412851286128712881289129212931294129512961297129812991313141315131613171318131913221323132413251326132713281329133213331334133513361337133813391342134313441345134613471348134913521353135413551356135713581359136213631364136513661367136813691372137313741375137613771378137913821383138413851386138713881389139213931394139513961397139813991414151416141714181419142214231424142514261427142814291432143314341435143614371438143914421443144414451446144714481449145214531454145514561457145814591462146314641465146614671468146914721473147414751476147714781479148214831484148514861487148814891492149314941495149614971498149915151615171518151915221523152415251526152715281529153215331534153515361537153815391542154315441545154615471548154915521553155415551556155715581559156215631564156515661567156815691572157315741575157615771578157915821583158415851586158715881589159215931594159515961597159815991616171618161916221623162416251626162716281629163216331634163516361637163816391642164316441645164616471648164916521653165416551656165716581659166216631664166516661667166816691672167316741675167616771678167916821683168416851686168716881689169216931694169516961697169816991717181719172217231724172517261727172817291732173317341735173617371738173917421743174417451746174717481749175217531754175517561757175817591762176317641765176617671768176917721773177417751776177717781779178217831784178517861787178817891792179317941795179617971798179918181918221823182418251826182718281829183218331834183518361837183818391842184318441845184618471848184918521853185418551856185718581859186218631864186518661867186818691872187318741875187618771878187918821883188418851886188718881889189218931894189518961897189818991919221923192419251926192719281929193219331934193519361937193819391942194319441945194619471948194919521953195419551956195719581959196219631964196519661967196819691972197319741975197619771978197919821983198419851986198719881989199219931994199519961997199819992222322242225222622272228222922332234223522362237223822392243224422452246224722482249225322542255225622572258225922632264226522662267226822692273227422752276227722782279228322842285228622872288228922932294229522962297229822992323242325232623272328232923332334233523362337233823392343234423452346234723482349235323542355235623572358235923632364236523662367236823692373237423752376237723782379238323842385238623872388238923932394239523962397239823992424252426242724282429243324342435243624372438243924432444244524462447244824492453245424552456245724582459246324642465246624672468246924732474247524762477247824792483248424852486248724882489249324942495249624972498249925252625272528252925332534253525362537253825392543254425452546254725482549255325542555255625572558255925632564256525662567256825692573257425752576257725782579258325842585258625872588258925932594259525962597259825992626272628262926332634263526362637263826392643264426452646264726482649265326542655265626572658265926632664266526662667266826692673267426752676267726782679268326842685268626872688268926932694269526962697269826992727282729273327342735273627372738273927432744274527462747274827492753275427552756275727582759276327642765276627672768276927732774277527762777277827792783278427852786278727882789279327942795279627972798279928282928332834283528362837283828392843284428452846284728482849285328542855285628572858285928632864286528662867286828692873287428752876287728782879288328842885288628872888288928932894289528962897289828992929332934293529362937293829392943294429452946294729482949295329542955295629572958295929632964296529662967296829692973297429752976297729782979298329842985298629872988298929932994299529962997299829993333433353336333733383339334433453346334733483349335433553356335733583359336433653366336733683369337433753376337733783379338433853386338733883389339433953396339733983399343435343634373438343934443445344634473448344934543455345634573458345934643465346634673468346934743475347634773478347934843485348634873488348934943495349634973498349935353635373538353935443545354635473548354935543555355635573558355935643565356635673568356935743575357635773578357935843585358635873588358935943595359635973598359936363736383639364436453646364736483649365436553656365736583659366436653666366736683669367436753676367736783679368436853686368736883689369436953696369736983699373738373937443745374637473748374937543755375637573758375937643765376637673768376937743775377637773778377937843785378637873788378937943795379637973798379938383938443845384638473848384938543855385638573858385938643865386638673868386938743875387638773878387938843885388638873888388938943895389638973898389939394439453946394739483949395439553956395739583959396439653966396739683969397439753976397739783979398439853986398739883989399439953996399739983999444454446444744484449445544564457445844594465446644674468446944754476447744784479448544864487448844894495449644974498449945454645474548454945554556455745584559456545664567456845694575457645774578457945854586458745884589459545964597459845994646474648464946554656465746584659466546664667466846694675467646774678467946854686468746884689469546964697469846994747484749475547564757475847594765476647674768476947754776477747784779478547864787478847894795479647974798479948484948554856485748584859486548664867486848694875487648774878487948854886488748884889489548964897489848994949554956495749584959496549664967496849694975497649774978497949854986498749884989499549964997499849995555655575558555955665567556855695576557755785579558655875588558955965597559855995656575658565956665667566856695676567756785679568656875688568956965697569856995757585759576657675768576957765777577857795786578757885789579657975798579958585958665867586858695876587758785879588658875888588958965897589858995959665967596859695976597759785979598659875988598959965997599859996666766686669667766786679668766886689669766986699676768676967776778677967876788678967976798679968686968776878687968876888688968976898689969697769786979698769886989699769986999777787779778877897798779978787978887889789878997979887989799879998888988998989999000

Code:

#include <iostream>
#include <string>

using namespace std;

string addchar(string s) {
  //cout << "String: " << s << endl;
  int i;
  if (s.size() == 10003) {
    cout << s.c_str() << endl;
    cin >> i;
    return s.substr(0, s.size()-1);
  }
  string last_three;
  if (s.size() >= 3) last_three = s.substr(s.size()-3, s.size());

  for (i = '0'; i <= '9'; i++) {
    string search_str = last_three + (char)i;
    if (s.size() < 3 || s.find(search_str) == string::npos) {
      addchar(s + (char)i);
    }
  }
  return s.substr(0, s.size()-1);
}

int main() {
  addchar("");
  return 0;
}

So now we know that a solution exists, prove that my simple construction algorithm will allow you to create a list of all possible combinations.

NullRoot · 2007-11-20 22:28:41

10,003. Amusing considering there's 10,000 combinations.

I was hoping for something more formulaic, but I did say I wanted varied approaches, too.
I must admit ignorance, Ricky; I don't know C++. Any way you could comment that for me? Just to make sure I understand what it's doing.
I'd like to hear your thoughts on how you approached this problem, too.

I like how if it took you half a second to type in each digit then this particular string would have you poking buttons for about 84 minutes

TheDude · 2007-11-21 04:45:27

In a nutshell, he created a function and calls it once with an empty string as the argument.

Inside the function, ignoring the fluff, takes the last 3 numbers of the string passed to it and stores them in another string.
It then loops through every digit 0 through 9 and appends it to the end of the temporary string. It then checks to see if this
new, 4 digit number exists elsewhere inside the string. If it does the function moves onto the next digit. If the 4 digit string
does not already exist in the master string it adds it, and then calls itself recursively with the new string as the argument.
Once the loop continues all the way through it finally ends.

Unfortunately, it's written recursively, which makes it easy to write and understand but difficult to follow, and therefore to prove
correct. If you're into programming you might try using the same approach but with an iterative function instead.

Note that 10,003 characters is the absolute minimum number of characters needed to answer your problem. There are, as you
said, 10,000 different combinations, each having at least 1 different number or different order from every other combo, which
implies a minimum of 10,000 characters. Coupled with the fact that each combo is 4 characters long, and 10,003 is the minimum
possible. Kudos to Ricky for finding the ideal answer.

Ricky · 2007-11-21 06:04:06

Dude, good explanation, but it seems like your explanation was intended for a coder. You can explain the algorithm in a mathy way instead.

So my construction starts with an empty string. Then we attempt to append a 0, 1, 2, 3, ..., 9 to it, and check to see if it's a valid string. That is, we check to see if the last 4 digits appear only once in the string. If it is, great, we move on to append more. If it isn't, then we throw it out. Continue this process until we reach a string of size 10003. Once we have a string of this size, every possible 4 digit combination can occur at most once. Since there are only 10000 such combinations, and every digit after the first three represent a single combination (ending with that digit), every combination must appear exactly once.

If this hadn't worked, I would have no idea what to do. The ideal solution was the easiest to check, so I went for that.

NullRoot · 2007-11-21 22:59:52

Thanks very much guys.

I do code, but I use Visual Basic (esp. within Excel) since Excel is pretty heavily used where I work and it's a pretty widely available program given the
proliferation of Microsoft. I'm glad that method worked, Ricky, as I had thought of trying that, but wasn't sure if it would be the ideal. I can follow the
logic involved with 10,003 being optimal, but you know how it is; sometimes you think of something that sounds so simple you can't help but self-doubt!

Ricky · 2007-11-22 13:31:11

For every difficult and complex problem exists a solution that is simple, elegant, and completely wrong.

Math Is Fun Forum

#1 2007-11-20 03:29:52

A Very Long Alarm Code

#2 2007-11-20 11:30:53

Re: A Very Long Alarm Code

#3 2007-11-20 22:28:41

Re: A Very Long Alarm Code

#4 2007-11-21 04:45:27

Re: A Very Long Alarm Code

#5 2007-11-21 06:04:06

Re: A Very Long Alarm Code

#6 2007-11-21 22:59:52

Re: A Very Long Alarm Code

#7 2007-11-22 13:31:11

Re: A Very Long Alarm Code

Board footer