Instantly share code, notes, and snippets.

# bifurcation/seq.py Secret

Created July 1, 2018 20:29
Show Gist options
• Save bifurcation/8f425d02fc020f5a52edd58fdca092b1 to your computer and use it in GitHub Desktop.
Solution to Jun 29 Riddler
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 import random def expand(x): return [x // 1000, (x // 100) % 10, (x // 10) % 10, x % 10] def tail(s): return 1000*s[-4] + 100*s[-3] + 10*s[-2] + s[-1] digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] def trial(): known = {} unseen = range(10000) seqs = [] while len(unseen) > 0: seq = expand(random.choice(unseen)) known[tail(seq)] = True del unseen[unseen.index(tail(seq))] while True: found = False random.shuffle(digits) for d in digits: seq.append(d) t = tail(seq) if t in known: seq.pop() continue found = True known[t] = True del unseen[unseen.index(t)] break if not found: break seqs.append(seq) return seqs minn = 11000 prevmin = minn absmin = 10003 while True: seqs = trial() l = map(len, seqs) n = sum(l) minn = min(n, minn) print "{} (<= {})".format(n, minn) if minn < prevmin: print " ".join(map(str, l)) print " : ".join(map(lambda x: "".join(map(str, x)), seqs)) prevmin = minn if minn == absmin: break
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 seq_str = "6503243022979499445496081341386044103411676421216956335398337764846850521051391331590022607275717945579421401474931926576625103322637555024831807554381576091682560125964987794061884648081880876501127748169078159946887166595278658032888373527452010145230838711383461367625582661911864337904874285530078219839201431557334881686011038688432670016258820167144797985474543281372884426050533429949830164008722779638586135384065563869489578612626131521865078783586837216853725643597994079747401638377453745878063195018431316146950432052975584820461635424284131793809783833965400345939751295196586551185512865928520567589119952472141513182642621029884048801825435358924013647964292915742568342325926341018327902053510256502242677322955148412172749953768567699959832848985644204824185180964496778079960547018065056073197329425275529983562684152384529826065323024765726995805745091435608701778596369271380123032732040851903553486329938649136313996133690459846305121270113244647510124224508533160965797888947376978944335287825765207171887728039427308243142331294386765301937220334011941842581739415332024417302870646029317029492243995669147117968494790793623010881556150232116438847009453566372444146190090404716745996533310102097461037616151896986893220629812797673013405640343962834163075338253494100673103658797245127314377709909713620025311170385756559423736427253559325240399744696756903967392860325571409682341945850705720611910199044378270826857213257918102300315309191246347980771691390210397933727671154996955653973863827988882514590724105684606223593675966338873978799277343114651168968652921284552520061603749050643224877740029194372678802204910926656859477417116024275371397409586336611114182772615588909104554159235673426458692035119545146009318715873657856045898918684732751611332896339343574928175509245654190252869160077367722383517344050172662816508274181840928449333810170082829632542112096340905734141454161775243740276228812696248887931588488758401278834972702229860941274072635084857684344453373240530457696352175758582920010534601480628728499939121974558367127121550503055010424071538766153759162270911395360603569825263335405880954174459577828833846233210410778166654918019875617538190942686820289992610575401960310935710846606839051791715592417281104818086392226647100494699750027103023476707929629784579063689803694907383043172125876755385691596040745724860285667332585925295209125725522194006679836388185705989729419562254734985777898827541327193831546201951473375305370445261717587177126792887218817724626698836157820687203403085215071148671746802681072504035806728796618955352496565895659676776288214833575065225079038209208223206513309026447051074080243278244786609806490361927350617658344861490297439593750953136558998001210962067991059518120322160430789237151710606689120416585404427921394955277733193012218589454521173811654675224424570286104352280039389592063972821188634958104064059178687984935203061971463731565665126838186356345399488585267539326311829049612396116683260951582461873594617204475990552424989260859827268803791227919533052481714556667260279652891963011106279486624219154088741247413035004129834078642518529090663223094655595554971723150662221296101591493235703485037886443421874809293200321361255459625755707768707854122466623948705436343893395477187618693110217168061457398898149502836545465847935456610979600811291261804330021536883976434828311968083242098151412345223762653443009594847889529480473950593880684023133585520604687635961839444429710284031205406882470947526408405576497951742005537989626477719059439828713392471824897399881157756797118158388231162854423991310861841759595822577473056196459452805492506863645642346835058162747802088070477046041889146706342559742287749829459290586684215471994351572965975930998205042312137340218025115813014689500583006300438380236053826380580155316348371781052274821337833600527336833376557701206911094970156148784379249567829393611233049295969721525087143030008031348901297258496699075922738509076646215110558129254147920587431856886906455965532646360364826124591872305901429805625977901375689752727217353364614247850893990062695392398428106826293821207577351932927249018549526569981893008588317335618141350483899667131499023886538967900353203813298931232482387700444779584411122995132253730448938142079152261156271707497563067406241260485651980996431655001740499327757442291748623100917742106573848308620395872513686775591085025003723939817970240638178903148921159863140428935887084583986574358379417803874498486861936690531516499161821820774382423549494835479933862673546428805599781439456398734513079525488429340869602586414052027711985246716083595325124480502734724343390985931623662997005761524450545802123530272853806658153470730702706801444889976323797702022590426599376344717613493849041190899470417705259491290748830299060866402901669464367411426917366819462866174712408123703208654851448438750810317507641342214259542386692199733985049574795383968897159414362846154287494045033651783993501408314622676661699197209522908309334308472799017372013387373793480100709609950777293632452539402555134775940823371949349164222473568699369370879234992806958966263207846912367849591280895443107517767947872714217779371817252209432914588851701381252135999791071925748791416836253888139307475722111512380489496407071054412838299214385598788555521672343684810839516294673636212256749156930265540770761289460762377130989534155575329007502134548347154553672076743346680051494516881966827808845681704547292671979753544404674278776928370582598510030927932835233890464921891651696831667470391729778307695463286738084366771013287694054254531276387817681214661211080982409971962138983128222898216454271853400532278581929840015038948258936500882842435075450295350991272385976170903391933021476635378990855062502639466571101653183780498042166272987689056527150864873171981385138414277036374858330158439331449769801607969022336260344920425306216591145175628029282697346310664953089135137998666631570923174148599170658862114986273907791387049772571957000566205186678183323816366535906818285165610089062351822414416603370071488221782306547560936851228590819890246084106715647025466952830368245845009757967851563218467224040984540918235291898698386514007289000130259355682268920746240201287590921078017122239019481288531050805234415795574192029648152933272007982202397189403622059954936092582158009229689434781248530311722827362789511743739639924495484225804524136015153578004220842660898416474324973613969967489601862563514346296070060712319446331152795403262348447483231694472549069005073487647264375788497495125163787521450677758146411805391551664886652668751509670261657598160176406783104794401035268217456038471475564676106358113702339775319987003317603989413927525832093417693591585361732857836418034731304051510589070371079431982322839167095098645191661388385236430179872902809387946395232667549886811187021922862249179957286473822930814066047891500741543122369748480307326878738726518835528506942064244364483931478411713446791163911788109151977149782284338539558561275867576763903738854295613779999457152886164836641939436521243604270400983752395680516737472262213005410816444355587030486979220722271641202163303469268046676807370988760204750360756607434504567240048491481352566855461189930669616874510641046384306097730692215736992264179560699411501693649430509374413344213126308789707529672599209998445154189084981183058511130579259130886080600036732144575704807180086852847765934646829575183196710994248027564968145629223427683064460901090040189289278345553960633296602210115390825012649303925624402693351605515548724257061299622947135657760493784871208755104909925562090956924840739142833135434060135542037514223186077511407580948557233474761958573096650976670420556026004627597809134659030388925194227504708174969321567746780597055449985841992307235020316466393733080131136669342080026630957986114706614102674603018131914432323404158629061027840873334962778440897853282895885713711193564507205772193475831382804137672913265245365600245517678637646947426367016845327072958357357717316813691901575281931022812265439708859503548646544069392161321907132362468624773188527651082100235846536396645781192179270357621763712935120084485255039043492328076866365377208154827645307165251724791632746643929735578423041969666056363020666440970698719192469011751952195590274241505192365944250349001875343250555697097312492648917668856316793957162454481472832937754461201544736082976088964782650632694501928732392692944875731124191752045112666864043706021131378197546938546057870932464094015208929233503190659802818167513587737855671834819996873001918500648656232950605921597303306370701496379623823614772737787104403807429409304698987959722551878695109550744822761403701076317847464527002820007656416219617909390675057125094490874635504657019786003836957636108771571861787629106130689929990329704391844494418790528249977776655231419843541107086727763341253399915314534581877887852222017857930548991835342801161073380069758239103233307723741692536600685807832532475433261446621492743097262825533558080721197654226981001184763047232769080449112569599899554783743616208343760526909614321626249396415664202627053640175426199345694160676061568775013980820366389102494282378628976243844625445508376601904760788298535362954304290342465237588148291116984753698558605113434186795732561176276001411357278133394720200993132011442863037739353177981959054681560584274476888418384201882672108942916976828680908832225235519963184845184924296910000656708360237299115526252578934458281440002070620436964644197031897410987477867050009694331819137423687184597128587548114336357997236337465637708961947644561663467797375476207358208548007368035927669716167874033598804022722924333241121836816198678965159336185919914028893795088800047444684439008334574057080856218117738979086064769188867440760106969238922515260161220045386159564854371417085746977611005968545779262025737163125402416770670333367961589774438033832170569650414919885015321265827112815044650" def shiftadd(x, d): return (10*x + d) % 10000 seq = [int(x) for x in seq_str] seen = {} val = 0 val = shiftadd(val, seq[0]) val = shiftadd(val, seq[1]) val = shiftadd(val, seq[2]) val = shiftadd(val, seq[3]) seen[val] = True for d in seq[4:]: val = shiftadd(val, d) seen[val] = True if len(seen) == 10000: print "PASS" else: print "FAIL"