Coding Challenge - Morris Sequence
-
I have already text files over 2.2 GB so I think you'll have to delete them as you gom at least that's what I do. And I think using bytes is cheating :laugh: also I didn't know that 3 would be the highest number. I don't think is enough not if you start at 3,4,5 or any other number, at least I got some 5 then. Or my code was wrong.
My comment about 1,2,3 was based on looking at file 50 very briefly. I could run an analysis as I go through them. I have re-written it so that it zips and deletes files that are not being read - let's see how quickly my computer or hard drive goes up in a puff of smoke... My guess is that it may be one of those tasks where it is not possible to calculate up to 100 within the lifetime of the universe.
“That which can be asserted without evidence, can be dismissed without evidence.”
― Christopher Hitchens
-
My comment about 1,2,3 was based on looking at file 50 very briefly. I could run an analysis as I go through them. I have re-written it so that it zips and deletes files that are not being read - let's see how quickly my computer or hard drive goes up in a puff of smoke... My guess is that it may be one of those tasks where it is not possible to calculate up to 100 within the lifetime of the universe.
“That which can be asserted without evidence, can be dismissed without evidence.”
― Christopher Hitchens
GuyThiebaut wrote:
My guess is that it may be one of those tasks where it is not possible to calculate up to 100 within the lifetime of the universe.
Nah, I don't think so, I was able to run up to 77 before VS threw an out of memory exception. And as I told Richard, I think I found a formula, but It looked kind of complicated.
-
This one's a real bugger for memory. String-based approaches are obviously out - 16 bits to store each character is overkill when the only symbols you need to store are
1,2and3.List<byte>is obviously not going to work, because it would need to allocate an array big enough to hold the entire sequence.LinkedList<byte>has to create an object for every byte in the list, so the overhead far outweighs the payload. I settled on a custom singly-linked list of byte arrays, re-using two instances (previous and current) to reduce memory churn. But even that was eating huge amounts of memory. Finally, realising that the only numbers in the sequence are1,2and3, I decided to stuff four numbers into each byte, which brings the memory usage under control. However, it still takes a damn long time to run, and I haven't left it for long enough to get to the 100th iteration yet. Morris Sequence · GitHub[^] Having spent far too long thinking about this, now's the time for you to tell me there's some secret trick to calculate the sequence without having to store the whole thing. :-D
"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer
Well, he did only ask about the length of the 100 th number. So according to Look-and-say sequence - Wikipedia[^]. Dave told us that the 50th number had length:
L50 = 894810
And the wikipedia article said:
L_n+1/L_n= lambda = 1.303577269034
so....
L50*lambda^(50)= 511175198256
if my math is right enough. Very hard programming challange :D
-
My comment about 1,2,3 was based on looking at file 50 very briefly. I could run an analysis as I go through them. I have re-written it so that it zips and deletes files that are not being read - let's see how quickly my computer or hard drive goes up in a puff of smoke... My guess is that it may be one of those tasks where it is not possible to calculate up to 100 within the lifetime of the universe.
“That which can be asserted without evidence, can be dismissed without evidence.”
― Christopher Hitchens
Oh, it's possible. My machine is sitting here listing the iteration, length, and time to calculate for each of the 100 numbers.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
Well, he did only ask about the length of the 100 th number. So according to Look-and-say sequence - Wikipedia[^]. Dave told us that the 50th number had length:
L50 = 894810
And the wikipedia article said:
L_n+1/L_n= lambda = 1.303577269034
so....
L50*lambda^(50)= 511175198256
if my math is right enough. Very hard programming challange :D
Exact length is required and that's not the answer.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
PS. Do you want the text file? ... ... ... :laugh: :laugh: :laugh:
Good luck posting it! :laugh:
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
Oh, it's possible. My machine is sitting here listing the iteration, length, and time to calculate for each of the 100 numbers.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakGood to know! Currently at line 82 and the file size for line 82 alone is over 4 Gigabytes.
“That which can be asserted without evidence, can be dismissed without evidence.”
― Christopher Hitchens
-
Good to know! Currently at line 82 and the file size for line 82 alone is over 4 Gigabytes.
“That which can be asserted without evidence, can be dismissed without evidence.”
― Christopher Hitchens
4,326,816,254 to be exact.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
Exact length is required and that's not the answer.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakCant be far off :)
-
Cant be far off :)
:-D
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
I have already text files over 2.2 GB so I think you'll have to delete them as you gom at least that's what I do. And I think using bytes is cheating :laugh: also I didn't know that 3 would be the highest number. I don't think is enough not if you start at 3,4,5 or any other number, at least I got some 5 then. Or my code was wrong.
Kenneth Haugland wrote:
I don't think is enough not if you start at 3,4,5 or any other number, at least I got some 5 then.
Whatever digit you start with will always be in the last position. No other digit will exceed 3, no matter how many iterations you try. For example, if in iteration
nyou get41, then that means iterationn-1must have had...x1111.... But given the rules of the sequence, that would have to be written as either(x+1)1or21.
"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer
-
Kenneth Haugland wrote:
I don't think is enough not if you start at 3,4,5 or any other number, at least I got some 5 then.
Whatever digit you start with will always be in the last position. No other digit will exceed 3, no matter how many iterations you try. For example, if in iteration
nyou get41, then that means iterationn-1must have had...x1111.... But given the rules of the sequence, that would have to be written as either(x+1)1or21.
"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer
Ah, yes that makes sense. Also seems to be that the higher the number of iterations the higher of LSB seems to be equal? if you can find that formula you might shorten the calculations by quite a bit.
-
Oh, it's possible. My machine is sitting here listing the iteration, length, and time to calculate for each of the 100 numbers.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakSo how long did it take? Did you do something in parallell or?
-
So how long did it take? Did you do something in parallell or?
I'll say 82 took my machine 59 seconds.
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 Kreskowiak -
85 MINUTES?! You'll be running this for about a week to get to 100. It can be done a lot quicker than that. The 76th number took 12 seconds on my machine and it's a "nothing special" machine.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
85 MINUTES?! You'll be running this for about a week to get to 100. It can be done a lot quicker than that. The 76th number took 12 seconds on my machine and it's a "nothing special" machine.
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 Kreskowiak- Strings and string methods are not going to do it. They're too slow and take up too much memory. 2) The only digits you see in any of these numbers are 1, 2, and 3. It seems like a waste to use an entire byte to store each digit. 3) If you graph the math on the progression of the length of these numbers, you'll see that on a LOGARITHMIC SCALE, the graph is about a 40 degree line. What would that look like on a normal X/Y scale? 4) You cannot do this "in memory", without going to the extremes of cleverness, and even then, you'd still need a gargantuan amount of RAM.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
4,326,816,254 to be exact.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakYep - that's the count I get too :thumbsup:
“That which can be asserted without evidence, can be dismissed without evidence.”
― Christopher Hitchens
-
- Strings and string methods are not going to do it. They're too slow and take up too much memory. 2) The only digits you see in any of these numbers are 1, 2, and 3. It seems like a waste to use an entire byte to store each digit. 3) If you graph the math on the progression of the length of these numbers, you'll see that on a LOGARITHMIC SCALE, the graph is about a 40 degree line. What would that look like on a normal X/Y scale? 4) You cannot do this "in memory", without going to the extremes of cleverness, and even then, you'd still need a gargantuan amount of RAM.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak
