Coding Challenge - Morris Sequence

[Kenneth Haugland]

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.

[Kenneth Haugland]

So how long did it take? Did you do something in parallell or?

[Dave Kreskowiak]

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

[AVNTizzy]

Still running...85 minutes in... currently at: Loop 76: Length 881752750

[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

[AVNTizzy]

I thought I would run out ot memory and did it writing to a file...not the smartest idea...now I just can't bring myself to stop the run.

[Dave Kreskowiak]

1. 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

[GuyThiebaut]

Yep - that's the count I get too :thumbsup:

“That which can be asserted without evidence, can be dismissed without evidence.”

― Christopher Hitchens

[AVNTizzy]

Good hints...gonna have another crack at this back home.

[AVNTizzy]

close...about 72 million off...

[PIEBALDconsult]

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.

[Dave Kreskowiak]

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

[PIEBALDconsult]

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).

[User 13520686]

340472211484 approx (via log extrapolation)

[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 Kreskowiak

[Dave Kreskowiak]

Nope, not even close.

System.ItDidntWorkException: Something didn't work as expected. C# - How to debug code[^]. Seriously, go read these articles.
Dave Kreskowiak

[PIEBALDconsult]

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.

[PIEBALDconsult]

What base? The length is 10 -- in some base I haven't determined yet.

[Kenneth Haugland]

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.Ope

[Dave Kreskowiak]

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