Coding Challenge - Morris Sequence
-
Congratulations! You're the first to post the correct answer. Extra credit: how did you do it in 2 hours?
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakSince we only need to compute the length, storing the entire string isn't necessary. Furthermore, the computation can be done recursively and requires very little code/storage for each level of recursion. The memory footprint while running was about 16k IIRC. I removed some extraneous code and got the runtime at l=100 to about 1.5 hours. Probably could optimize it even more, but I don't see the point. I'd post code here but it seems to be discouraged.
-
Since we only need to compute the length, storing the entire string isn't necessary. Furthermore, the computation can be done recursively and requires very little code/storage for each level of recursion. The memory footprint while running was about 16k IIRC. I removed some extraneous code and got the runtime at l=100 to about 1.5 hours. Probably could optimize it even more, but I don't see the point. I'd post code here but it seems to be discouraged.
It would be interesting to see. Code has been an exception in the past for challenges like this.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
It would be interesting to see. Code has been an exception in the past for challenges like this.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakOK, here it is... #include #include #include using namespace std; #define maxLevel 100 static uint32_t currentLevel = 0; static chrono::time_point start, timeFinished; class LevelProcessor { public: LevelProcessor() : currentOccurrence(0), currentPrefix(0), myLevel(currentLevel++), totalSize(0) { } void ProcessLevel(uint32_t prefix); void FinishLevel(); uint32_t currentOccurrence; uint32_t currentPrefix; const uint32_t myLevel; uint64_t totalSize; }; static LevelProcessor processors[maxLevel]; void LevelProcessor::ProcessLevel(uint32_t prefix) { if (prefix == currentPrefix) { ++currentOccurrence; return; } if (currentOccurrence != 0) { if (myLevel < maxLevel - 1) { processors[myLevel + 1].ProcessLevel(currentOccurrence); processors[myLevel + 1].ProcessLevel(currentPrefix); } ++totalSize; } currentPrefix = prefix; currentOccurrence = 1; } void LevelProcessor::FinishLevel() { ++totalSize; if (myLevel < maxLevel - 1) { processors[myLevel + 1].ProcessLevel(currentOccurrence); processors[myLevel + 1].ProcessLevel(currentPrefix); } chrono::time_point timeFinished = chrono::system_clock::now(); chrono::duration elapsed_seconds = timeFinished - start; time_t end_time = chrono::system_clock::to_time_t(timeFinished); cout << "level " << myLevel + 1 << " is done, size = " << totalSize * 2 << " at " << "elapsed time: " << elapsed_seconds.count() << "secs" << endl; if (myLevel < maxLevel - 1) processors[myLevel + 1].FinishLevel(); } int main() { start = chrono::system_clock::now(); processors[1].ProcessLevel(1); processors[1].FinishLevel(); timeFinished = chrono::system_clock::now(); chrono::duration elapsed_seconds = timeFinished - start; time_t end_time = chrono::system_clock::to_time_t(timeFinished); cout << "finished computation at " << ctime(&end_time) << "elapsed time: " << elapsed_seconds.count() << "secs" << endl; } So much for my indenting, oh well.
-
OK, here it is... #include #include #include using namespace std; #define maxLevel 100 static uint32_t currentLevel = 0; static chrono::time_point start, timeFinished; class LevelProcessor { public: LevelProcessor() : currentOccurrence(0), currentPrefix(0), myLevel(currentLevel++), totalSize(0) { } void ProcessLevel(uint32_t prefix); void FinishLevel(); uint32_t currentOccurrence; uint32_t currentPrefix; const uint32_t myLevel; uint64_t totalSize; }; static LevelProcessor processors[maxLevel]; void LevelProcessor::ProcessLevel(uint32_t prefix) { if (prefix == currentPrefix) { ++currentOccurrence; return; } if (currentOccurrence != 0) { if (myLevel < maxLevel - 1) { processors[myLevel + 1].ProcessLevel(currentOccurrence); processors[myLevel + 1].ProcessLevel(currentPrefix); } ++totalSize; } currentPrefix = prefix; currentOccurrence = 1; } void LevelProcessor::FinishLevel() { ++totalSize; if (myLevel < maxLevel - 1) { processors[myLevel + 1].ProcessLevel(currentOccurrence); processors[myLevel + 1].ProcessLevel(currentPrefix); } chrono::time_point timeFinished = chrono::system_clock::now(); chrono::duration elapsed_seconds = timeFinished - start; time_t end_time = chrono::system_clock::to_time_t(timeFinished); cout << "level " << myLevel + 1 << " is done, size = " << totalSize * 2 << " at " << "elapsed time: " << elapsed_seconds.count() << "secs" << endl; if (myLevel < maxLevel - 1) processors[myLevel + 1].FinishLevel(); } int main() { start = chrono::system_clock::now(); processors[1].ProcessLevel(1); processors[1].FinishLevel(); timeFinished = chrono::system_clock::now(); chrono::duration elapsed_seconds = timeFinished - start; time_t end_time = chrono::system_clock::to_time_t(timeFinished); cout << "finished computation at " << ctime(&end_time) << "elapsed time: " << elapsed_seconds.count() << "secs" << endl; } So much for my indenting, oh well.
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 Kreskowiak -
I didn't follow that.
The quick and dirty code I wrote was
#include
#includeclass s {
private:
char indx;
char ondx;
char v[10];
public:
bool done;
unsigned long long count;
s(void) {
indx = '\0';
ondx = '\0';
done = false;
count= 0UL;
}
void put (char c) {
v[indx++] = c;
indx = indx % 10;
}
char get (void) {
char c = v[ondx++];
ondx = ondx %10;
return c;
}
char peek (void) {
return v[ondx];
}
bool isEmpty (void) {
return indx == ondx;
}
};s context[100];
// the two functions "nextItem" and "doCount" call each other recursively.
bool nextItem (char& c, int level);
// count number of consecutive instances of v from level below
// return count as a character in 'c'; save v with msb set. and
// character which terminated count in context.
void doCount (char& c, char v, int level) {
bool r = false;
s& x = context[level];
c = '1';
x.put (v + 0X80);
while (!x.done) {
char t;
x.done = nextItem (t, level - 1);
if (t == v) {
c++;
}
else {
// count is complete so we need to put the terminating value
// in the buffer, value we are counting is already there
x.put (t);
break;
}
}
}// return in 'c' the next character from the specified level
// signal done if that character is the last.
// there are two special cases:
// 1) level = 0, the single character '1' is returned and done is signalled
// 2) There are no characters held in the context (this must be the first entry)
// Otherwise there are one or two characters in the context. If the next character
// held in the context ha the msb set, the count has already been returned so the
// character should be returned. Otherwise the character is the terminating character
// from the last count and more repetitions (if any) must be counted, after which the
// count is returned. When the lower level has signalled done, then when the last
// character is returned also signal done.
// Count the number of characters returned and when the last character is returned and
// done s signalled, report the level and the total.bool nextItem (char& c, int level) {
s& x = context[level];
bool r = false;
if (!x.isEmpty()) {
// more ready to output
char v = x.get();
c = v & 0X7F;
if (v & 0X80) {
r = x.isEmpty();
}
else {
// this is the next value and we need to count any more
doCount (c, v, level);
}
}
else if (level == 0) {
// at the lowest level the seed is a single '1'
c -
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 :)