|
That's cheating!
Oh, and what you linked to starts the sequence with a 2, not a 1.
System.ItDidntWorkException: Something didn't work as expected.
C# - How to debug code[ ^].
Seriously, go read these articles.
Dave Kreskowiak
|
|
|
|
|
I have been running the code (which I posted here somewhere) in the background as I'm reading for the exam. The text file that just holds the current number is 1.6 GB, and I guess that's one way of measuring the length. So I'll definitely post the end number on the Lounge forum Then it will at last contain something worthwhile
|
|
|
|
|
PS. Do you want the text file?
...
...
...
|
|
|
|
|
Good luck posting it!
System.ItDidntWorkException: Something didn't work as expected.
C# - How to debug code[ ^].
Seriously, go read these articles.
Dave Kreskowiak
|
|
|
|
|
I have a day off, so I thought I would make use of this challenge to try TDD(test-driven development).
It's actually a rather good example for TDD and I am finding that writing the tests first is making this challenge a lot faster and even more enjoyable to develop a solution to.
Thanks for the challenge
[edit]I started off using stacks to do the calculations and soon ran out of memory.
I am now using a less processor intensive method(a secret...) and the application got to line 77 and the length of the line is 1,149,440,192 digits long - flippin' heck!
No stack overflow either, as the way I have written the application means that all that will happen is that my disk space will run out - I am not sure if I want to find that out...
“That which can be asserted without evidence, can be dismissed without evidence.”
― Christopher Hitchens
modified 1-Dec-17 10:10am.
|
|
|
|
|
Strings? Why not use a List of Tuple<short,short> ?
After more thought and before reading Richard's response...
Tuple<nybble,nybble>
Using a byte to implement such a Tuple.
Having read Richard's response...
Huh, yeah, use a byte to implement a
Tuple<Tuple<nyblet,nyblet>,Tuple<nyblet,nyblet>> ...
I would also try to use many threads.
modified 2-Dec-17 1:07am.
|
|
|
|
|
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 , 2 and 3 .
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 are 1 , 2 and 3 , 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.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
Here we go - breaking the no code in the lounge rule here...
internal void Stream(int upTo)
{
using (StreamWriter writer = new StreamWriter("E:\\temp\\MorrisSequence\\" + "line1.txt"))
{
writer.Write("1");
}
for (int i = 1; i <= upTo; i++)
{
Console.WriteLine(i);
using (StreamReader reader = new StreamReader("E:\\temp\\MorrisSequence\\" + "line" + i + ".txt"))
{
int count = 1;
char currChar = (char)reader.Read();
char lastChar = currChar;
char nextChar;
string writeNum = (i + 1).ToString();
using (StreamWriter writer = new StreamWriter("E:\\temp\\MorrisSequence\\" + "line" + writeNum + ".txt"))
{
while (reader.Peek() >= 0)
{
nextChar = (char)reader.Peek();
if (nextChar != lastChar)
{
writer.Write(count.ToString() + currChar.ToString());
count = 0;
}
currChar= (char)reader.Read();
lastChar = currChar;
count++;
}
writer.Write(count.ToString() + currChar.ToString());
}
}
}
}
[edit] small tidy up, giving filenames proper names that relate to what they contain.
“That which can be asserted without evidence, can be dismissed without evidence.”
― Christopher Hitchens
modified 1-Dec-17 10:15am.
|
|
|
|
|
That's one way around it. But I hope you've got a large SSD!
Is there a reason you're writing strings instead of bytes?
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
I was tempted to leave it running this evening but as you mention I think it will fill up the disk space - file 77 is just over 1 gig in size and it's only a text file.
What I may do is compress then delete files prior to the one I am currently reading(the 1 gig file compresses to 80mb largely because it is composed of 1s,2s and 3s).
Richard Deeming wrote: Is there a reason you're writing strings instead of bytes? Um er yes, um err, um er because... that idea never occurred to me - thanks for the tip
“That which can be asserted without evidence, can be dismissed without evidence.”
― Christopher Hitchens
|
|
|
|
|
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 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
|
|
|
|
|
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.
|
|
|
|
|
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
|
|
|
|
|
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
|
|
|
|
|
Yep - that's the count I get too
“That which can be asserted without evidence, can be dismissed without evidence.”
― Christopher Hitchens
|
|
|
|
|
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
|
|
|
|
|
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 n you get 41 , then that means iteration n-1 must have had ...x1111... . But given the rules of the sequence, that would have to be written as either (x+1)1 or 21 .
"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.
|
|
|
|
|
|
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
modified 1-Dec-17 10:27am.
|
|
|
|
|
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
|
|
|
|
|
Cant be far off
|
|
|
|