Coding Challenge - Morris Sequence
-
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 -
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
-
- 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 KreskowiakThe length of row n won't exceed twice the length of row n-1 , yes? The result is computable, therefore a Turing Machine can compute it, and, because Turing Machines have virtually unlimited storage, simply use one.
-
The length of row n won't exceed twice the length of row n-1 , yes? The result is computable, therefore a Turing Machine can compute it, and, because Turing Machines have virtually unlimited storage, simply use one.
You build the machine and I'll go make the infinite paper tape.
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 KreskowiakThe spec isn't clear! Send it back! :wtf: As this is, in essence, a compression algorithm, at line 8->9 (according to the OEIS) I would do:
1113213211
11 132132 11 <== three subsequences
21 2132 21 <== three outputs, eight digits
Which is shorter than their naive result of:
1113213211
111 3 2 1 3 2 11 <== seven subsequences
31 13 12 11 13 12 21 <== seven outputs, fourteen digits
A 40% saving. The complexity of the algorithm increases due to seeking how to split the input into the fewest subsequences of some repetition length (1 in the naive implementation).
-
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 Kreskowiak340472211484 approx (via log extrapolation)
-
The spec isn't clear! Send it back! :wtf: As this is, in essence, a compression algorithm, at line 8->9 (according to the OEIS) I would do:
1113213211
11 132132 11 <== three subsequences
21 2132 21 <== three outputs, eight digits
Which is shorter than their naive result of:
1113213211
111 3 2 1 3 2 11 <== seven subsequences
31 13 12 11 13 12 21 <== seven outputs, fourteen digits
A 40% saving. The complexity of the algorithm increases due to seeking how to split the input into the fewest subsequences of some repetition length (1 in the naive implementation).
When in the :elephant: is the spec Everclear[^] ? Project Euler specs aren't clear either. We always have to do the best we can with what we've got. :-D
1113213211
11 132132 11 <== 13?
21 132132 21 <== three outputs, eight digits
What happened to the 13? The output looks like it should be 10 digits, not 8.
1113213211
111 32132 11
31 32132 21 <== if I understand what you're trying to do
There seems to a problem with representation. How do you tell the difference between single values and a run length value?
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
340472211484 approx (via log extrapolation)
Nope, not even close.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
When in the :elephant: is the spec Everclear[^] ? Project Euler specs aren't clear either. We always have to do the best we can with what we've got. :-D
1113213211
11 132132 11 <== 13?
21 132132 21 <== three outputs, eight digits
What happened to the 13? The output looks like it should be 10 digits, not 8.
1113213211
111 32132 11
31 32132 21 <== if I understand what you're trying to do
There seems to a problem with representation. How do you tell the difference between single values and a run length value?
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakDave Kreskowiak wrote:
What happened to the 13?
There are 2 132s , hence
2132.Dave Kreskowiak wrote:
How do you tell the difference between single values and a run length value?
Doesn't matter, but internally (if I write it) it would be in the data structure. It just wouldn't be apparent in the output unless you want it.
(1,1)
(2,1)
...
(2,1),(2,132),(2,1)
...The question is about only the number of digits.
-
340472211484 approx (via log extrapolation)
What base? The length is
10-- in some base I haven't determined yet. -
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 KreskowiakSo I stored booleans in a file:
string Morris(int S, int N)
{
string projectPath = System.IO.Path.GetFullPath(@"..\..\..\");
using (BinaryWriter writer = new BinaryWriter(File.Open(projectPath + "input.txt", FileMode.Create)))
{
writer.Write(S > 2);
writer.Write(S == 2);
}for (int i = 1; i < N; i++) { Debug.WriteLine(i+1); using (BinaryReader reader = new BinaryReader(File.Open(projectPath + "input.txt", FileMode.Open))) { int count = 1; bool currMSB = reader.ReadBoolean(); bool currLSB = reader.ReadBoolean(); bool nextMSB, nextLSB; using (BinaryWriter writer = new BinaryWriter(File.Open(projectPath + "output.txt", FileMode.Create))) { while (reader.BaseStream.Position != reader.BaseStream.Length) { nextMSB = reader.ReadBoolean(); nextLSB = reader.ReadBoolean(); if ((currMSB == nextMSB) && (currLSB == nextLSB)) { count++; } else { writer.Write(count > 2); writer.Write(count == 2); writer.Write(currMSB); writer.Write(currLSB); currMSB = nextMSB; currLSB = nextLSB; count = 1; } } writer.Write(count > 2); writer.Write(count == 2); writer.Write(currMSB); writer.Write(currLSB); } } File.Delete(projectPath + "input.txt"); System.IO.File.Copy(projectPath + "output.txt", projectPath + "input.txt"); System.IO.File.WriteAllText(projectPath + "output.txt", string.Empty); } StringBuilder output = new StringBuilder(); using (BinaryReader reader = new BinaryReader(File.Open(projectPath + "input.txt", FileMode.Ope -
Dave Kreskowiak wrote:
What happened to the 13?
There are 2 132s , hence
2132.Dave Kreskowiak wrote:
How do you tell the difference between single values and a run length value?
Doesn't matter, but internally (if I write it) it would be in the data structure. It just wouldn't be apparent in the output unless you want it.
(1,1)
(2,1)
...
(2,1),(2,132),(2,1)
...The question is about only the number of digits.
Ah, OK. I missed that. Hmmm. In my implementation, I wrote up a reader/writer that takes care of the "on the fly". This would make an interesting, and challenging, implementation to write. I'll have to look into trying this next weekend. My current implementation writes all the data but there is an option to convert the data to a human-readable format. Not that you'd want to see thousands of pages of 1's, 2's, and 3's, but it did come in handy for analysis when experimenting with implementations.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
So I stored booleans in a file:
string Morris(int S, int N)
{
string projectPath = System.IO.Path.GetFullPath(@"..\..\..\");
using (BinaryWriter writer = new BinaryWriter(File.Open(projectPath + "input.txt", FileMode.Create)))
{
writer.Write(S > 2);
writer.Write(S == 2);
}for (int i = 1; i < N; i++) { Debug.WriteLine(i+1); using (BinaryReader reader = new BinaryReader(File.Open(projectPath + "input.txt", FileMode.Open))) { int count = 1; bool currMSB = reader.ReadBoolean(); bool currLSB = reader.ReadBoolean(); bool nextMSB, nextLSB; using (BinaryWriter writer = new BinaryWriter(File.Open(projectPath + "output.txt", FileMode.Create))) { while (reader.BaseStream.Position != reader.BaseStream.Length) { nextMSB = reader.ReadBoolean(); nextLSB = reader.ReadBoolean(); if ((currMSB == nextMSB) && (currLSB == nextLSB)) { count++; } else { writer.Write(count > 2); writer.Write(count == 2); writer.Write(currMSB); writer.Write(currLSB); currMSB = nextMSB; currLSB = nextLSB; count = 1; } } writer.Write(count > 2); writer.Write(count == 2); writer.Write(currMSB); writer.Write(currLSB); } } File.Delete(projectPath + "input.txt"); System.IO.File.Copy(projectPath + "output.txt", projectPath + "input.txt"); System.IO.File.WriteAllText(projectPath + "output.txt", string.Empty); } StringBuilder output = new StringBuilder(); using (BinaryReader reader = new BinaryReader(File.Open(projectPath + "input.txt", FileMode.OpeInteresting but I question if this is actually writing one byte per value? Don't have time to test right now.
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 KreskowiakMy instant impression of it is that there has to be a better way than brute force: there's something very Fibonacci-sequence-like about the output... in my head, I can almost predict the pattern from one iteration to the next, without trying to describe anything... if only I had better coffee... if only Dijkstra were still alive... damn it: now you've got me interested.
-
Interesting but I question if this is actually writing one byte per value? Don't have time to test right now.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakI suspect that it is using a byte for each boolean value. As per the usual answers: Why is a boolean 4 bytes in .NET? - Stack Overflow[^] I could store them in a BitVector32 or a BitArray and write that to the file, but I don't have the time to implement it now.
-
I suspect that it is using a byte for each boolean value. As per the usual answers: Why is a boolean 4 bytes in .NET? - Stack Overflow[^] I could store them in a BitVector32 or a BitArray and write that to the file, but I don't have the time to implement it now.
I tried doing this in a BitArray, but found it to be limited in flexibility and performance. This was about 10 years that I originally worked on this problem. I was doing some cleaning around the drive to get rid of old stuff and ran into the project. Then, of course, I just had to run it again and maybe update the code a little bit. :)
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
My instant impression of it is that there has to be a better way than brute force: there's something very Fibonacci-sequence-like about the output... in my head, I can almost predict the pattern from one iteration to the next, without trying to describe anything... if only I had better coffee... if only Dijkstra were still alive... damn it: now you've got me interested.
I know there has to be a better way to do it because I did find a list that gave the lengths for the first 3000 numbers in the sequence. Let's just say there are more digits in the 3000th number than there are atoms in the observable universe. I'll post the answer and the length of #3000 Monday morning. It does make for any interesting problem!
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak