Coding Challenge - Morris Sequence
-
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 -
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 Kreskowiaklevel 1 size = 1
level 2 size = 2
level 3 size = 2
level 4 size = 4
level 5 size = 6
level 6 size = 6
level 7 size = 8
level 8 size = 10
level 9 size = 14
level 10 size = 20
level 11 size = 26
level 12 size = 34
level 13 size = 46
level 14 size = 62
level 15 size = 78
level 16 size = 102
level 17 size = 134
level 18 size = 176
level 19 size = 226
level 20 size = 302
level 21 size = 408
level 22 size = 528
level 23 size = 678
level 24 size = 904
level 25 size = 1182
level 26 size = 1540
level 27 size = 2012
level 28 size = 2606
level 29 size = 3410
level 30 size = 4462
level 31 size = 5808
level 32 size = 7586
level 33 size = 9898
level 34 size = 12884
level 35 size = 16774
level 36 size = 21890
level 37 size = 28528
level 38 size = 37158
level 39 size = 48410
level 40 size = 63138
level 41 size = 82350
level 42 size = 107312
level 43 size = 139984
level 44 size = 182376
level 45 size = 237746
level 46 size = 310036
level 47 size = 403966
level 48 size = 526646
level 49 size = 686646
level 50 size = 894810
level 51 size = 1166642
level 52 size = 1520986
level 53 size = 1982710
level 54 size = 2584304
level 55 size = 3369156
level 56 size = 4391702
level 57 size = 5724486
level 58 size = 7462860
level 59 size = 9727930
level 60 size = 12680852
level 61 size = 16530884
level 62 size = 21549544
level 63 size = 28091184
level 64 size = 36619162
level 65 size = 47736936
level 66 size = 62226614
level 67 size = 81117366
level 68 size = 105745224
level 69 size = 137842560
level 70 size = 179691598
level 71 size = 234241786
level 72 size = 305351794
level 73 size = 398049970
level 74 size = 518891358
level 75 size = 676414798
level 76 size = 881752750
level 77 size = 1149440192
level 78 size = 1498380104
level 79 size = 1953245418
level 80 size = 2546222700
level 81 size = 3319186080
level 82 size = 4326816254
level 83 size = 5640348764
level 84 size = 7352630884
level 85 size = 9584715106
level 86 size = 12494412020
level 87 size = 16287462624
level 88 size = 21231903676
level 89 size = 27677468012
level 90 size = 36079732206
level 91 size = 47032657188
level 92 size = 61310766500
level 93 size = 79923316046
level 94 size = 104186199146
level 95 size = 135814773100
level 96 size = 177045063068
level 97 size = 230791944956
level 98 size = 300854953626
level 99 size = 392187941864
level 100 size = 511247092564
finished computation at Fri Dec 1 16:48:41 2017
elapsed time: 7205.75secs -
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:elephant: OK, I'll see how far I get doing it "my way" -- but I'll address the more general problem, allowing the starting input to be more than one symbol and not limited to the symbols
1,2, and3. Also, allowing the caller to specify the maximum subsequence length -- that'll be the hard part. I think the only alcohol in the place is one shot of tequila; it will have to be enough. Sunday morning update: By midnight I had the basic functionality (subsequence lengths 0 and 1) working and tested -- but using a List<T> which means that there are allocation issues. This morning's immediate goal -- implement a SegmentedList<T> class. Sunday afternoon update: The SegmentedList<T> is working well, and it allows for multiple threads for improved speed. -
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 KreskowiakThey definitely store the booleans as bytes. I ran this:
string MorrisBitVector32(int S, int N)
{
//Need the mask for accessing the individual bits
int[] _masks = new int[32];
{
_masks[0] = BitVector32.CreateMask();
}
for (int i = 1; i < 32; i++)
{
_masks[i] = BitVector32.CreateMask(_masks[i - 1]);
}//Hopefully setes the path to the project folder string projectPath = System.IO.Path.GetFullPath(@"..\\..\\..\\"); using (BinaryWriter writer = new BinaryWriter(File.Open(projectPath + "input.txt", FileMode.Create))) { BitVector32 v = new BitVector32(); // Standard 3 = 11, 2=10,1=01 and // 00 is not more numbers in this BitVector32 v\[\_masks\[0\]\] = S >= 2; v\[\_masks\[1\]\] = S != 2; //Writes a 32bit integer to the file writer.Write(v.Data); } for (int i = 1; i < N; i++) { Debug.WriteLine(i + 1); using (BinaryReader reader = new BinaryReader(File.Open(projectPath + "input.txt", FileMode.Open))) { // Initiates variables for each N run bool currMSB, currLSB, firstRun; firstRun = true; currMSB = false; currLSB = false; int count = 0; int k = 0; BitVector32 outputBits = new BitVector32(); using (BinaryWriter writer = new BinaryWriter(File.Open(projectPath + "output.txt", FileMode.Create))) { while (reader.BaseStream.Position != reader.BaseStream.Length) { BitVector32 inputBits = new BitVector32(reader.ReadInt32()); if (firstRun) { count = 1; currMSB = inputBits\[\_masks\[0\]\]; currLSB = inputBits\[\_masks\[1\]\]; } bool nextMSB, nextLSB; for (int j = (firstRun ? 2 : 0); j < 32; j += 2) { nextMSB = inputBits\[\_ma -
Nope, not even close.
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave KreskowiakAfter a bit more fiddling:
Test length 48 th : 526646 526,646
Test length 49 th : 686646 686,646
Test length 50 th : 894810 894,810
51st length : 1,166,642
52nd length : 1,521,070
53rd length : 1,983,164
54th length : 2,585,639
55th length : 3,371,142
56th length : 4,395,278
57th length : 5,730,540
58th length : 7,471,449
59th length : 9,741,236
60th length : 12,700,573
61st length : 16,558,941
62nd length : 21,589,461
63rd length : 28,148,228
64th length : 36,699,513
65th length : 47,848,635
66th length : 62,384,802
67th length : 81,336,981
68th length : 106,046,733
69th length : 138,263,181
70th length : 180,266,818
71st length : 235,030,941
72nd length : 306,432,122
73rd length : 399,524,610
74th length : 520,898,113
75th length : 679,144,257
76th length : 885,464,758
77th length : 1,154,464,356
78th length : 1,505,184,637
79th length : 1,962,451,918
80th length : 2,558,634,627
81st length : 3,335,934,550
82nd length : 4,349,374,155
83rd length : 5,670,691,453
84th length : 7,393,418,089
85th length : 9,639,500,137
86th length : 12,567,930,256
87th length : 16,386,002,249
88th length : 21,363,984,700
89th length : 27,854,252,387
90th length : 36,316,229,718
91st length : 47,348,911,849
92nd length : 61,733,265,560
93rd length : 80,487,511,283
94th length : 104,939,199,534
95th length : 136,819,183,789
96th length : 178,384,141,824
97th length : 232,576,318,416
98th length : 303,231,797,036
99th length : 395,352,043,407
100th length : 515,457,942,582Regards , R
-
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 KreskowiakSince the only requirement was to determine the length, it is not necessary to store the full string. A simple 100 level recursion that, at each level, returns the next digit in sequence suffices - it takes a long time to run, but does not need huge amounts of space. At each level above the first it is only necessary to store at most two digits - the digit of which you have just counted the repetitions, and the digit that broke the sequence. Each invocation at any level alternates between returning the count and returning the counted digit.
-
After a bit more fiddling:
Test length 48 th : 526646 526,646
Test length 49 th : 686646 686,646
Test length 50 th : 894810 894,810
51st length : 1,166,642
52nd length : 1,521,070
53rd length : 1,983,164
54th length : 2,585,639
55th length : 3,371,142
56th length : 4,395,278
57th length : 5,730,540
58th length : 7,471,449
59th length : 9,741,236
60th length : 12,700,573
61st length : 16,558,941
62nd length : 21,589,461
63rd length : 28,148,228
64th length : 36,699,513
65th length : 47,848,635
66th length : 62,384,802
67th length : 81,336,981
68th length : 106,046,733
69th length : 138,263,181
70th length : 180,266,818
71st length : 235,030,941
72nd length : 306,432,122
73rd length : 399,524,610
74th length : 520,898,113
75th length : 679,144,257
76th length : 885,464,758
77th length : 1,154,464,356
78th length : 1,505,184,637
79th length : 1,962,451,918
80th length : 2,558,634,627
81st length : 3,335,934,550
82nd length : 4,349,374,155
83rd length : 5,670,691,453
84th length : 7,393,418,089
85th length : 9,639,500,137
86th length : 12,567,930,256
87th length : 16,386,002,249
88th length : 21,363,984,700
89th length : 27,854,252,387
90th length : 36,316,229,718
91st length : 47,348,911,849
92nd length : 61,733,265,560
93rd length : 80,487,511,283
94th length : 104,939,199,534
95th length : 136,819,183,789
96th length : 178,384,141,824
97th length : 232,576,318,416
98th length : 303,231,797,036
99th length : 395,352,043,407
100th length : 515,457,942,582Regards , R
Wrong again!
System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak -
Since the only requirement was to determine the length, it is not necessary to store the full string. A simple 100 level recursion that, at each level, returns the next digit in sequence suffices - it takes a long time to run, but does not need huge amounts of space. At each level above the first it is only necessary to store at most two digits - the digit of which you have just counted the repetitions, and the digit that broke the sequence. Each invocation at any level alternates between returning the count and returning the counted digit.
I didn't follow that.
-
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 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 Kreskowiak -
level 1 size = 1
level 2 size = 2
level 3 size = 2
level 4 size = 4
level 5 size = 6
level 6 size = 6
level 7 size = 8
level 8 size = 10
level 9 size = 14
level 10 size = 20
level 11 size = 26
level 12 size = 34
level 13 size = 46
level 14 size = 62
level 15 size = 78
level 16 size = 102
level 17 size = 134
level 18 size = 176
level 19 size = 226
level 20 size = 302
level 21 size = 408
level 22 size = 528
level 23 size = 678
level 24 size = 904
level 25 size = 1182
level 26 size = 1540
level 27 size = 2012
level 28 size = 2606
level 29 size = 3410
level 30 size = 4462
level 31 size = 5808
level 32 size = 7586
level 33 size = 9898
level 34 size = 12884
level 35 size = 16774
level 36 size = 21890
level 37 size = 28528
level 38 size = 37158
level 39 size = 48410
level 40 size = 63138
level 41 size = 82350
level 42 size = 107312
level 43 size = 139984
level 44 size = 182376
level 45 size = 237746
level 46 size = 310036
level 47 size = 403966
level 48 size = 526646
level 49 size = 686646
level 50 size = 894810
level 51 size = 1166642
level 52 size = 1520986
level 53 size = 1982710
level 54 size = 2584304
level 55 size = 3369156
level 56 size = 4391702
level 57 size = 5724486
level 58 size = 7462860
level 59 size = 9727930
level 60 size = 12680852
level 61 size = 16530884
level 62 size = 21549544
level 63 size = 28091184
level 64 size = 36619162
level 65 size = 47736936
level 66 size = 62226614
level 67 size = 81117366
level 68 size = 105745224
level 69 size = 137842560
level 70 size = 179691598
level 71 size = 234241786
level 72 size = 305351794
level 73 size = 398049970
level 74 size = 518891358
level 75 size = 676414798
level 76 size = 881752750
level 77 size = 1149440192
level 78 size = 1498380104
level 79 size = 1953245418
level 80 size = 2546222700
level 81 size = 3319186080
level 82 size = 4326816254
level 83 size = 5640348764
level 84 size = 7352630884
level 85 size = 9584715106
level 86 size = 12494412020
level 87 size = 16287462624
level 88 size = 21231903676
level 89 size = 27677468012
level 90 size = 36079732206
level 91 size = 47032657188
level 92 size = 61310766500
level 93 size = 79923316046
level 94 size = 104186199146
level 95 size = 135814773100
level 96 size = 177045063068
level 97 size = 230791944956
level 98 size = 300854953626
level 99 size = 392187941864
level 100 size = 511247092564
finished computation at Fri Dec 1 16:48:41 2017
elapsed time: 7205.75secsCongratulations! 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 Kreskowiak -
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.