Coding Challenge - Morris Sequence
-
Interesting. When I originally did the research into this thing I saw the pattern developing in the brute force results but I was never able to get any code to work that looked for and tracked the pattern. I'll have to dig into this later to see exactly how it works and where I made my mistakes. I still have a couple of the broken projects from way back then. Thanks for sharing!
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakI wish I could say that this is exploiting some underlying pattern, but it's really just a more efficient brute force implementation. It's more like a depth-first tree traversal - you never have to compute and store the entire string at one level before working on the next.
-
I wish I could say that this is exploiting some underlying pattern, but it's really just a more efficient brute force implementation. It's more like a depth-first tree traversal - you never have to compute and store the entire string at one level before working on the next.
That's what I thought. When I originally started looking at this, I found the storage requirements for a single iteration were going to jump exponentially. I was looking for a method to do this, something like what you've done, but couldn't get it to work.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
I wish I could say that this is exploiting some underlying pattern, but it's really just a more efficient brute force implementation. It's more like a depth-first tree traversal - you never have to compute and store the entire string at one level before working on the next.
Wow, I see where my previous mistakes were compared to yours. I got a couple of hints from your code that got my old code working, and what I was misinterpreting. Your code, on my machine, does the 100 numbers in an hour and ten minutes. FAR faster than my brute force runs that store every iteration on disk in a byte-compressed format and takes just under 6 hours to run. Thanks for the help!
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
The answer for the length of the 100th number is 511,247,092,564 digits. The length escalates frighteningly quickly. The LENGTH of the 3000th number in the chain is, get this, 4029857719515768641307384677908679928310793769651641917926155107836565892187598804862177357001771122238068645667821323998368650130801806344030981271295995422208436642014734696538407619447946889047668430308242548524802874469136450965097114152481264391293269162985708430576259447637028591596189605329702198409448541645531801518246316682171504624370 digits long. That's not the number. That's how long it is in digits! That's more digits than there are the estimated number of atoms in the observable universe, by many orders of magnitude!
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakI've left my totally brute-force string-based solution running for 4 days and it's only on the 64th iteration having got up to 50 within an hour - so, yeah, that rather underlines how it can never really be achieved in reasonable time without an awful lot more finesse. I really enjoyed this as a coding challenge even though I didn't get remotely close to cracking it. A simple looking task on the surface but one that soon reveals itself to be monumentally problematic.
98.4% of statistics are made up on the spot.
-
Wow, I see where my previous mistakes were compared to yours. I got a couple of hints from your code that got my old code working, and what I was misinterpreting. Your code, on my machine, does the 100 numbers in an hour and ten minutes. FAR faster than my brute force runs that store every iteration on disk in a byte-compressed format and takes just under 6 hours to run. Thanks for the help!
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakNo problem. It was an interesting challenge! FWIW, I was looking further at the code and at how to optimize it. One interesting thing I found is that if the order of ProcessLevel() calls is reversed we get the same sequences but reversed! This means that the initial prefix for each level is always 1 and can be initialized as such, which then means the check for currentOccurrence != 0 in ProcessLevel() can be removed. Doesn't seem like much, but when that function is executed trillions of times it makes a noticeable difference. You must have a fast machine, 100 takes quite a bit longer for me.
-
No problem. It was an interesting challenge! FWIW, I was looking further at the code and at how to optimize it. One interesting thing I found is that if the order of ProcessLevel() calls is reversed we get the same sequences but reversed! This means that the initial prefix for each level is always 1 and can be initialized as such, which then means the check for currentOccurrence != 0 in ProcessLevel() can be removed. Doesn't seem like much, but when that function is executed trillions of times it makes a noticeable difference. You must have a fast machine, 100 takes quite a bit longer for me.
Interesting. I'll have to play around with that some more. I'm wondering how long it would take to get to 200, let alone 3,000. And how to hang onto numbers that big. It seems a BigInt class would be needed but performance may suffer greatly. I just built a new machine about 9 months ago, overclocked and water cooled of course. :-D
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
Interesting. I'll have to play around with that some more. I'm wondering how long it would take to get to 200, let alone 3,000. And how to hang onto numbers that big. It seems a BigInt class would be needed but performance may suffer greatly. I just built a new machine about 9 months ago, overclocked and water cooled of course. :-D
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakMy runtimes are about 3500 sec at l=100 and about 50000 sec at l=110 for an increase of about 14.3x. So from l=100 to l=200 is 14.3 ^ 10 x the time, or 347,636,939,799 hours. ~39 million years, give or take :) l=3000? heh. I think that's a pretty good definition of "forever".
-
It's also known as the Conway Sequence, Look and Say Sequence, and probably some others. It's rather simple. Start with a 1 and then describe what you see for the next iteration. So, starting at 1, the next number is one 1 (11), the next is two 1 (21), then one 2 one 1 (1211), and so on:
1
11
21
1211
111221
312211The question to answer is what's the length in digits of the 100th number in the chain, starting with "1" as the first? The first six numbers have been given above. You could write it out by hand, but I wouldn't recommend it, and as developers, that's not what we do. The seemingly simple challenge is to write the code to come up with the answer. The only hint you get is the 50th number is 894,810 digits long. Oh, and don't bother Googling for code. Those examples will only get you so far and definitely won't get you to the answer.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakThat's quite a number. Got me spending electricity for almost 21h ;)
Paulo Gomes Measuring programming progress by lines of code is like measuring aircraft building progress by weight. —Bill Gates Everything should be made as simple as possible, but not simpler. —Albert Einstein
-
The answer for the length of the 100th number is 511,247,092,564 digits. The length escalates frighteningly quickly. The LENGTH of the 3000th number in the chain is, get this, 4029857719515768641307384677908679928310793769651641917926155107836565892187598804862177357001771122238068645667821323998368650130801806344030981271295995422208436642014734696538407619447946889047668430308242548524802874469136450965097114152481264391293269162985708430576259447637028591596189605329702198409448541645531801518246316682171504624370 digits long. That's not the number. That's how long it is in digits! That's more digits than there are the estimated number of atoms in the observable universe, by many orders of magnitude!
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakI got the same value for the 100th but it took me almost 21h with iterators. Did you actually calculate the 3000th????
Paulo Gomes Measuring programming progress by lines of code is like measuring aircraft building progress by weight. —Bill Gates Everything should be made as simple as possible, but not simpler. —Albert Einstein
-
I got the same value for the 100th but it took me almost 21h with iterators. Did you actually calculate the 3000th????
Paulo Gomes Measuring programming progress by lines of code is like measuring aircraft building progress by weight. —Bill Gates Everything should be made as simple as possible, but not simpler. —Albert Einstein
No, I didn't. I don't have an algorithm to go that high in my lifetime. At least not yet. I'm still working on the problem in some spare time. There is only a single place on the entire 'net where that number is listed, here[^]. Seems to be down right now though.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
Wrong again!
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakDave Kreskowiak wrote:Wrong again! 100 : 511247092564 Exactly this time ! Regards, R
-
Dave Kreskowiak wrote:Wrong again! 100 : 511247092564 Exactly this time ! Regards, R
Great!
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
It's also known as the Conway Sequence, Look and Say Sequence, and probably some others. It's rather simple. Start with a 1 and then describe what you see for the next iteration. So, starting at 1, the next number is one 1 (11), the next is two 1 (21), then one 2 one 1 (1211), and so on:
1
11
21
1211
111221
312211The question to answer is what's the length in digits of the 100th number in the chain, starting with "1" as the first? The first six numbers have been given above. You could write it out by hand, but I wouldn't recommend it, and as developers, that's not what we do. The seemingly simple challenge is to write the code to come up with the answer. The only hint you get is the 50th number is 894,810 digits long. Oh, and don't bother Googling for code. Those examples will only get you so far and definitely won't get you to the answer.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakI don't know if anyone is looking at this anymore due to it being an old topic, but there is a way to calculate the length of these sequences in linear time. For example, it's possible to calculate the length of sequences 1..5000 in < 1 sec.
-
I don't know if anyone is looking at this anymore due to it being an old topic, but there is a way to calculate the length of these sequences in linear time. For example, it's possible to calculate the length of sequences 1..5000 in < 1 sec.
OK, care to share?
Asking questions is a skill CodeProject Forum Guidelines Google: C# How to debug code Seriously, go read these articles.
Dave Kreskowiak -
OK, care to share?
Asking questions is a skill CodeProject Forum Guidelines Google: C# How to debug code Seriously, go read these articles.
Dave KreskowiakJohn Conway did extensive research a while back on this sequence. He discovered that after a certain point (level 8), each level can be written as a series of 92 subsequences that in turn evolve into one or several of the 92 subsequences. So it's possible to write a program that just keeps track of the number of times a particular subsequence has been seen, and then "evolve" it for the next level, which is iterating over a 92 element array for each level and creating a new 92 element array for the next. Since the size of each subsequence is known, calculating the length of a particular level is as simple as multiplying the count of each subsequence by the length, and adding them all together. I can post the source here if that's kosher. It's not pretty but it works :)
-
John Conway did extensive research a while back on this sequence. He discovered that after a certain point (level 8), each level can be written as a series of 92 subsequences that in turn evolve into one or several of the 92 subsequences. So it's possible to write a program that just keeps track of the number of times a particular subsequence has been seen, and then "evolve" it for the next level, which is iterating over a 92 element array for each level and creating a new 92 element array for the next. Since the size of each subsequence is known, calculating the length of a particular level is as simple as multiplying the count of each subsequence by the length, and adding them all together. I can post the source here if that's kosher. It's not pretty but it works :)
Here's the code, it allows a param to specify the level, default is 100. uint16384_t allows computation to slightly above level 40000. #include #include #include // g++ xxx.cpp -std=c++11 -march=corei7 using namespace std; using namespace boost::multiprecision; typedef number > uint16384_t; uint32_t maxLevel = 100; static chrono::time_point start, timeFinished; const uint32_t levelSize[] = { 4, 7, 12, 12, 4, 5, 12, 6, 8, 10, // 1-10 10, 14, 12, 14, 18, 42, 42, 26, 14, 28, // 11-20 14, 24, 24, 5, 7, 10, 10, 8, 2, 9, // 21-30 9, 23, 2, 6, 32, 32, 8, 3, 5, 6, // 31-40 10, 18, 18, 6, 10, 8, 7, 8, 12, 20, // 41-50 34, 34, 20, 10, 7, 7, 11, 13, 21, 17, // 51-60 2, 1, 4, 7, 14, 14, 7, 4, 6, 8, // 61-70 10, 16, 28, 28, 9, 12, 12, 16, 18, 24, // 71-80 23, 16, 6, 5, 15, 6, 10, 10, 3, 27, // 81-90 27, 5 }; // 91-92 vector levelEvolution[] = { {63}, {64, 62}, {65}, {66}, {68}, // 1-5 {69}, {84, 55}, {70}, {71}, {76}, // 6-10 {77}, {82}, {78}, {79}, {80}, // 11-15 {81, 29, 91}, {81, 29, 90}, {81, 30}, {75, 29, 92}, {75, 32}, // 16-20 {72}, {73}, {74}, {83}, {86}, // 21-25 {87}, {88},
-
John Conway did extensive research a while back on this sequence. He discovered that after a certain point (level 8), each level can be written as a series of 92 subsequences that in turn evolve into one or several of the 92 subsequences. So it's possible to write a program that just keeps track of the number of times a particular subsequence has been seen, and then "evolve" it for the next level, which is iterating over a 92 element array for each level and creating a new 92 element array for the next. Since the size of each subsequence is known, calculating the length of a particular level is as simple as multiplying the count of each subsequence by the length, and adding them all together. I can post the source here if that's kosher. It's not pretty but it works :)
Interesting. I'll have to dig into this when I have time. I never ran into Conways work on this sequence, probably because when I originally looked at the problem, it was before the Internet. :)
Asking questions is a skill CodeProject Forum Guidelines Google: C# How to debug code Seriously, go read these articles.
Dave Kreskowiak -
Interesting. I'll have to dig into this when I have time. I never ran into Conways work on this sequence, probably because when I originally looked at the problem, it was before the Internet. :)
Asking questions is a skill CodeProject Forum Guidelines Google: C# How to debug code Seriously, go read these articles.
Dave KreskowiakJust for grins, here's the count for level 40,000: 40000 4635633985186214870877877413722713070723692264232360834980754675669021402160038877796951548157965850907625470807504140268863386308875922216544076356172070784955086897189222123714604381634573888057338465221572146218079925997157606608320534279579971679678414013902819102532727448009605874593053705947677930158618663548395090114530007994024079764737450688935431742180956428699222647161605621043699723423613570660324777824381361753910640661567335726933418272004634589081395330061896758750022408276981442051636945663402270144291630216473454855520871537959913299122383546459911689173268242490107968480175270623804963957320188660754924681073968253619370268833880109615584479405584443268144156251179419394524532362671756733405339000925068258354920200165111897846616026560433502452131359961828965630741183144628861792280419299623490456434975101922619363730362392023785772196827723773921632625319247872576089818908216385290805985618447917234009410618193480820781463383161153391902256393618750950402112735155551469757923382451004135020903973016464396136542447221369089499771980454964375458365136995788788108390457745822089660593406532693516268047071714808760623570745688594081443375768418530002836352635026431633153477215522895063891000374608804519992545524523190118693890160554750997514533194788627189651125394551375551853272720730531013551025773362890692709302331864484539046665214284995027344662082977556718920678195336245605490255788719657859536271362824614323254256596797206506249218942817336815141378516946856299200067189686780275509827982732169801024311606965773426916151467275538759223775063671730434004444335603416998422129464458377125908577420849890694631643276173103386393934680725227579651924660230543132154958737330979429650745764251462549568470308878793325240566584074063817540455270668276854534974651331477347465734116702589482800704181144591053591566962442788598394698511355728474953413805501219544575750189315792631606042852424172650135394963236390116230679676413952056531632106191368985914234916492623807380681749381864725966760375534820526237529806450230956355225089537725462474865303489276127464994796211570349764722715507300535680039569710676252073248657414114718048170519300814251352749914617964701127634521183668122589456024548405264324766933842446243154060023313380969128238572821640145539472079456705550288724321539513470936977058965691756961402998828245114620059035184841363848024178403547933904732650768823278406334997012123599939571360410812744961293200142617752823619141084620201788
-
Interesting. I'll have to dig into this when I have time. I never ran into Conways work on this sequence, probably because when I originally looked at the problem, it was before the Internet. :)
Asking questions is a skill CodeProject Forum Guidelines Google: C# How to debug code Seriously, go read these articles.
Dave Kreskowiakjust for grins, here's level 40,000: 46356339851862148708778774137227130707236922642323608349807546756690214021600388 77796951548157965850907625470807504140268863386308875922216544076356172070784955 08689718922212371460438163457388805733846522157214621807992599715760660832053427 95799716796784140139028191025327274480096058745930537059476779301586186635483950 90114530007994024079764737450688935431742180956428699222647161605621043699723423 61357066032477782438136175391064066156733572693341827200463458908139533006189675 87500224082769814420516369456634022701442916302164734548555208715379599132991223 83546459911689173268242490107968480175270623804963957320188660754924681073968253 61937026883388010961558447940558444326814415625117941939452453236267175673340533 90009250682583549202001651118978466160265604335024521313599618289656307411831446 28861792280419299623490456434975101922619363730362392023785772196827723773921632 62531924787257608981890821638529080598561844791723400941061819348082078146338316 11533919022563936187509504021127351555514697579233824510041350209039730164643961 36542447221369089499771980454964375458365136995788788108390457745822089660593406 53269351626804707171480876062357074568859408144337576841853000283635263502643163 31534772155228950638910003746088045199925455245231901186938901605547509975145331 94788627189651125394551375551853272720730531013551025773362890692709302331864484 53904666521428499502734466208297755671892067819533624560549025578871965785953627 13628246143232542565967972065062492189428173368151413785169468562992000671896867 80275509827982732169801024311606965773426916151467275538759223775063671730434004 44433560341699842212946445837712590857742084989069463164327617310338639393468072 52275796519246602305431321549587373309794296507457642514625495684703088787933252 40566584074063817540455270668276854534974651331477347465734116702589482800704181 14459105359156696244278859839469851135572847495341380550121954457575018931579263 16060428524241726501353949632363901162306796764139520565316321061913689859142349 16492623807380681749381864725966760375534820526237529806450230956355225089537725 46247486530348927612746499479621157034976472271550730053568003956971067625207324 86574141147180481705193008142513527499146179647011276345211836681225894560245484 05264324766933842446243154060023313380969128238572821640145539472079456705550288 72432153951347093697705896569175696140299882824511462005903518484136384802417840 354793390473265076882327840633499701212359993957136041081274