Code Golf Challenge #1 - Thue-Morse Sequence

Code Golf Challenge #1 - Thue-Morse Sequence - Printable Version

+- Sinisterly (https://sinister.ly)
+-- Forum: Coding (https://sinister.ly/Forum-Coding)
+--- Forum: Coding (https://sinister.ly/Forum-Coding--71)
+--- Thread: Code Golf Challenge #1 - Thue-Morse Sequence (/Thread-Code-Golf-Challenge-1-Thue-Morse-Sequence)

Pages: 1 2 3 4

Code Golf Challenge #1 - Thue-Morse Sequence - Shebang - 08-14-2015

What is code golf?

Code golfing is an activity where a bunch of people compete to complete a specific programming task, using as few bytes of code as possible to complete the task.

Now, onto the challenge!

Thue-Morse Sequence

In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the binary sequence (an infinite sequence of 0s and 1s) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus far. The first few steps of this procedure yield the strings 0 then 01, 0110, 01101001, 0110100110010110, and so on, which are prefixes of the Thue–Morse sequence. The full sequence begins:

Code:
01101001100101101001011001101001100101100110100101101001100101101001011001101001

This is sequence A010060 in OEIS.

The Challenge

You should create a program or function which takes input via some method (standard input, function parameters, etc) which will produce the first n characters in the Thue-Morse sequence. You are not allowed to hardcode the sequence into your program, as it should theoretically work for any value of n. You cannot use any external sources to obtain the digits, all of them must be calculated one the program is run. You should not plagiarize existing programs. Breaking any of these rules disqualifies your program.

Once you have written your program, it would be extremely helpful if you could post a link to http://repl.it or http://ideone.com , which are online code compilers for a bunch of languages. This is so I can test and make sure that it functions as it should.

Also, you must start out your post saying which language and version you are using, and the byte count, which can be obtained from here. If you are missing this, I will not count your score until you add it!

The challenge will run for 1 week, while I can still edit the main post. After that, the shortest answer that has not been disqualified will be crowned the winner, and the user will receive 84 NSP.

Example Input/Output

Output can be in the format of a list/array, string or binary sequence.

Code:
n = 6  --> [0,1,1,0,1,0]
n = 20 --> '01101001100101101001'
n = 1  --> 0
n = 0  --> 
n = 99 --> 011010011001011010010110011010011001011001101001011010011001011010010110011010010110100110010110011

Leaderboard

Code:
User           | Language      | Bytes
-----------------------------------------------
Stocking       | Python 2      | 79
Stocking       | Node.js       | 100
eclipse        | Python 2      | 119

Donate

If you'd like to increase the size of the prize pool, donate and I'll increase the size! Smile

Thanks to @Eclipse for donating 25 NSP, and @Panty for donating 39 NSP!

RE: Code Golf Challenge #1 - Thue-Morse Sequence - OversouL - 08-14-2015

This is an interesting challenge. I would've liked to try this out with C++, but I'm still just trying to learn it. I hope a lot will do this challenge.

RE: Code Golf Challenge #1 - Thue-Morse Sequence - Eclipse - 08-14-2015

I'll donate 25 NSP to the pot.

RE: Code Golf Challenge #1 - Thue-Morse Sequence - Eclipse - 08-14-2015

http://repl.it/BBso
119 bytes

Example outputs:

Code:
T0 --> 0
T1 --> 01
T2 --> 0110
T3 --> 01101001
T4 --> 0110100110010110
T5 --> 01101001100101101001011001101001
T6 --> 0110100110010110100101100110100110010110011010010110100110010110
T7 --> 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

EDIT: I may try golfing this further.

RE: Code Golf Challenge #1 - Thue-Morse Sequence - Shebang - 08-14-2015

(08-14-2015, 07:34 PM)OversouL Wrote: This is an interesting challenge. I would've liked to try this out with C++, but I'm still just trying to learn it. I hope a lot will do this challenge.

I'd love to see your answer!

(08-14-2015, 07:36 PM)eclipse Wrote: I'll donate 25 NSP to the pot.

Thanks!

(08-14-2015, 08:12 PM)Panty Wrote: I'll donate 15 NSP to the pot.

Thanks!

(08-14-2015, 08:52 PM)eclipse Wrote: http://repl.it/BBs9
138 bytes

Example outputs:

Code:
T0 --> 0 T1 --> 01 T2 --> 0110 T3 --> 01101001 T4 --> 0110100110010110 T5 --> 01101001100101101001011001101001 T6 --> 0110100110010110100101100110100110010110011010010110100110010110 T7 --> 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

Nice work! Just so you know, while you are printing out each iteration, the question is asking for the sequence up to the nth digit. So you should be producing 011010 for n=6. This shouldn't be a difficult change, you can fix it with just a few bytes Smile

. Once you do I can help shorten it more Wink

RE: Code Golf Challenge #1 - Thue-Morse Sequence - Eclipse - 08-14-2015

(08-14-2015, 09:22 PM)Shebang Wrote: Nice work! Just so you know, while you are printing out each iteration, the question is asking for the sequence up to the nth digit. So you should be producing 011010 for n=6. This shouldn't be a difficult change, you can fix it with just a few bytes . Once you do I can help shorten it more

Ahh. I've golfed that down to 118 bytes btw. I'll make the edits.

RE: Code Golf Challenge #1 - Thue-Morse Sequence - Shebang - 08-14-2015

(08-14-2015, 09:34 PM)eclipse Wrote: Ahh. I've golfed that down to 118 bytes btw. I'll make the edits.

It has good potential! I've golfed yours down to 86 bytes so far Smile

Quick tip, you don't need to put anything in the input prompt, plus input() works here instead of int(raw_input()).

RE: Code Golf Challenge #1 - Thue-Morse Sequence - Eclipse - 08-14-2015

(08-14-2015, 09:22 PM)Shebang Wrote: Nice work! Just so you know, while you are printing out each iteration, the question is asking for the sequence up to the nth digit. So you should be producing 011010 for n=6. This shouldn't be a difficult change, you can fix it with just a few bytes . Once you do I can help shorten it more

(08-14-2015, 09:34 PM)eclipse Wrote: Ahh. I've golfed that down to 118 bytes btw. I'll make the edits.

Edited my entry.

(08-14-2015, 09:39 PM)Shebang Wrote: It has good potential! I've golfed yours down to 86 bytes so far Quick tip, you don't need to put anything in the input prompt, plus input() works here instead of int(raw_input()).

Ahh, sorry. It's instinctive. I guess security isn't much of an issue.

EDIT: 86?! How?

RE: Code Golf Challenge #1 - Thue-Morse Sequence - Shebang - 08-14-2015

(08-14-2015, 09:40 PM)eclipse Wrote: Edited my entry.

Ahh, sorry. It's instinctive. I guess security isn't much of an issue.

No worries Smile

I'll give you a few more hints Smile

If you make that for into a while, you can make that loop a one-liner (think list comprehension). The while will not make it shorter, just ensure it actually finishes timely.
String slicing doesn't need a 0 placeholder.

(08-14-2015, 09:40 PM)eclipse Wrote: Edited my entry.

Ahh, sorry. It's instinctive. I guess security isn't much of an issue.

EDIT: 86?! How?

It's actually down to 75 now Tongue

To be fair, I have practice golfing, you don't Smile

A few of the tricks I'm using aren't stuff that would be common knowledge/practice to a lot of people.

RE: Code Golf Challenge #1 - Thue-Morse Sequence - Eclipse - 08-14-2015

(08-14-2015, 09:44 PM)Shebang Wrote: It's actually down to 75 now To be fair, I have practice golfing, you don't A few of the tricks I'm using aren't stuff that would be common knowledge/practice to a lot of people.

Fucking hell.. I didn't know golfing was a thing.