22
\$\begingroup\$

This question already has an answer here:

Definition1

A Kolakoski sequence is a self-describing infinite sequence {kn} of alternating blocks of 1's and 2's, given by the following rules:

  • k0 = 1
  • kn = the length of the (n+1)'th block

The Task

Given a positive integer n, generate the first n elements of the Kolakoski sequence.

Details

Input will be provided as a single command line argument n. Please write a full program that will print the first n elements of the Kolakoski sequence (in order) to STDOUT, with each element separated by your favorite whitespace.

Scoring

Lets count source code bytes this time with all whitespace included. Fewest number of bytes wins. In the event of a tie, the solution with the earliest submission time wins.

The Sequence2

1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1, 2, 1, 2, 2, ...


References

  1. John Smith, Ariel Scolnicov, yark. "Kolakoski sequence" (version 3). PlanetMath.org. Freely available at http://planetmath.org/KolakoskiSequence.html.
  2. The Online Encyclopedia of Integer Sequences http://oeis.org/A000002

Other resources

\$\endgroup\$

marked as duplicate by Martin Ender code-golf Mar 6 '18 at 11:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • \$\begingroup\$ Any particular reason n is command line arg? \$\endgroup\$ – CalculatorFeline Apr 1 '16 at 15:19
  • \$\begingroup\$ @CatsAreFluffy not originally, but i'll happily keep any requirement that adds a few irritating chars to the golf-oriented languages :) \$\endgroup\$ – ardnew Apr 1 '16 at 16:35
  • \$\begingroup\$ That's a cumbersome I/O format that makes many languages unable to participate. \$\endgroup\$ – Mego Apr 2 '16 at 5:26
  • \$\begingroup\$ @Mego thanks for the tip. but in fairness to the current submissions, let's not go changing preferential specs on a 4 year old question \$\endgroup\$ – ardnew Apr 2 '16 at 20:01
  • 11
    \$\begingroup\$ Note: reposting this question is being discussed on meta. \$\endgroup\$ – Peter Taylor Feb 21 '18 at 16:49

11 Answers 11

7
\$\begingroup\$

J - 23 char

A little late to the party, but I'd like to bust out a neat little J trick here.

1($1+2|I.)^:_~".>2{ARGV

Given input N, this verb operates by executing N&($1+2|I.) on a starting argument of 1 until it reaches a fixed point. If the item at index i in y is n, there will be n copies of i in I.y, so for instance I. 0 1 1 0 0 3 1 is 1 2 5 5 5 6. We mod the result of that by 2 and add one. Then, x $ y forces y into a list of length x, truncating it or extending it cyclically as necessary.

So here's what happens when the input is, say, 10.

   10 ($1+2|I.)^:a: 1
1 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1
1 2 1 2 1 2 1 2 1 2
1 2 2 1 2 2 1 2 2 1
1 2 2 1 1 2 1 1 2 2
1 2 2 1 1 2 1 2 2 1

We start with a row of all 1s and then "settle down" into the Kolakoski sequence. First, it turns into 1 2 1 2 1 2... as each contiguous block of ones or twos is described by length 1. Then we apply it again and it turns into 1 2 2 1 2 2 1 2 2... since the ones are described by 1 and the twos are described by 2. The we continue again and again until we see there is no change, at which point we stop and give the result.

Other "self-describing" sequences can be similarly derived in J using I. and ^:_.


Edit

Over a year ago, @ardnew asked:

what is the relationship between n and the number of those intermediate iterations required to generate the sequence of length n?

To make sure we're on the same page, I consider the calculation for n = 10 above to have taken 5 iterations.

If there are s terms settled at the i-th iteration for n, then at the (i+1)-th iteration, there will be (at least) k0 + k1 + ... + ks + 1 terms settled. The '+ 1' appears because the next term will also be correct, since it must be and is different from the term before it.

So if K(s) is the sequence of partial sums of kn, then we can lower bound the number of iterations for n by the least a such that (1+K)a(1) ≥ n. I don't how to prove we don't accidentally do a bit better (by picking up more correct terms than we expected in some iteration), but according to the numbers, we don't:

   k =: ($ 1 + 2 | I.)^:_&1               NB. Kolakoski seq
   pk =: +/\ @: k                         NB. partial sums ("K")
   ((1 + pk 2000) {~ <:) ::_:^:(i.20) 1   NB. iterating 1+K, say, 20 times
1 2 4 7 11 18 28 43 65 99 150 226 340 511 768 1153 1728 2590 _ _
   NB. compare with observed number of settled terms up to 2000:
   +/"1 }. (k <./\ . ="1 ($1+2|I.)^:a:&1) 2000
1 2 4 7 11 18 28 43 65 99 150 226 340 511 768 1153 1728 2000

The underscores are index errors (:: _:), telling us 20 iterations is too much for the first 2000 terms of kn to handle.

\$\endgroup\$
  • \$\begingroup\$ what is the relationship between n and the number of those intermediate iterations required to generate the sequence of length n? \$\endgroup\$ – ardnew May 4 '14 at 22:47
  • \$\begingroup\$ @ardnew Long overdue, but I took at look at how the iterations thing acts. \$\endgroup\$ – algorithmshark Feb 10 '16 at 22:14
5
\$\begingroup\$

Ruby (73 characters)

s=[1,2,2];n=2;ARGV[0].to_i.times{puts s[n-2];s[n].times{s+=[1+n%2]};n+=1}
\$\endgroup\$
3
\$\begingroup\$

GolfScript (48 chars)

You can't test this online because the online GS shell doesn't take command-line arguments, but:

;"#{ARGV[-1]}"~[1 2.]2{.2$=[1$2%)]*@\+\)}3$*;<n*

This takes input from stdin instead and works

~[1 2.]2{.2$=[1$2%)]*@\+\)}3$*;<n*
\$\endgroup\$
  • 2
    \$\begingroup\$ Your 48-char version does work if you change ARVG to ARGV ;o). E.g., golfscript.rb kola.gs 10. \$\endgroup\$ – r.e.s. Sep 19 '12 at 14:48
3
\$\begingroup\$

Python 93

Adapted from my solution to Calculate the nth term of Golomb's self-describing sequence:

import sys;n=int(sys.argv[1]);a=[1,2,2];
for i in range(3,n):a+=[~i%2+1]*a[i-1]
print a[:n]

Still trying to figure out how to do this with list comprehension which I just learned about today, but I'm running into problems with self-reference.

EDIT: Instead of breaking if list was too long, just printed the appropriate slice.

EDIT: Now pulling arg from command line

\$\endgroup\$
  • \$\begingroup\$ n is never set prior to being referenced (either hard coded or read in from user). The code fails to run successfully. \$\endgroup\$ – chucksmash Sep 19 '12 at 16:54
  • \$\begingroup\$ It's required to use command-line input of what you call n, which will add some characters; however, you can save some by indenting only one space.) That's a very nice approach! Here's a 69-char Ruby version: s=[1,2,2];n=3;ARGV[0].to_i.times{puts s[n-3];s+=[~n%2+1]*s[n-1];n+=1}. \$\endgroup\$ – r.e.s. Sep 19 '12 at 17:04
  • \$\begingroup\$ Reading from command line the way I did it (is there a better way?) would add 28 characters to this code for a total of 93 characters. Still cool and still kills my noob attempt but 65 chars, it ain't. \$\endgroup\$ – chucksmash Sep 19 '12 at 17:26
  • \$\begingroup\$ Yeah, it's the import sys and the lengthy sys.argv that really kills it. thanks for the tips. \$\endgroup\$ – scleaver Sep 19 '12 at 17:45
3
\$\begingroup\$

Python (87 chars)

My code turned out to be basically the same as scleaver's solution even though I wrote it independently. It saves a few characters by not shifting the index i by 1.

import sys
n=int(sys.argv[1])
l=[1,2,2]
for i in range(2,n):l+=[1+i%2]*l[i]
print l[:n]
\$\endgroup\$
3
\$\begingroup\$

Perl, 41 39 bytes

A trivial modification of the classic TPR(0,3) solution:

perl -E 'say$_=($.+=!--$.[$.])%2+1for@.=(0)x pop' 20
\$\endgroup\$
2
\$\begingroup\$

Haskell 157 144

Haskell is kind of verbose so I expect this will be significantly longer than the shortest answer, but here it is.

import System
a=1:2:drop 2(concat.zipWith replicate a.cycle$[1,2])
main=do args<-getArgs;putStr$concatMap((' ':).show)$take(read$args!!0::Int)a

Edit:

Implemented FUZxxl's suggestions and also a few other small fixes.

\$\endgroup\$
  • \$\begingroup\$ Try to separate the statements in the do block with semicolons instead of newlines. That might help. Ans: (\b->' ':show b) is equal to ((' ':).show). Additionally, you might want to factor out a into a global variable to get rid of the phony let. \$\endgroup\$ – FUZxxl Sep 19 '12 at 20:10
1
\$\begingroup\$

Python (118 characters)

Takes n as a command line argument. Could trim four more characters if the printing of first n requirement is relaxed to first n or n + 1. I can't think of any more fat to trim...will be interested to see what a more experienced Python golfer could do

import sys
k,b=[1,2,2],1
n=int(sys.argv[1])
while len(k)<n:k.extend([2,1][b%2]for z in range(k[b+1]));b+=1
print k[:n]
\$\endgroup\$
1
\$\begingroup\$

Perl, 59 chars

say"@{[map{push@a,(2-$_%2)x($b=$a[$_-1]||$_);$b}1..shift]}"

As usual, run with Perl 5.10+ and the -M5.010 switch to enable the say feature.

\$\endgroup\$
  • \$\begingroup\$ perl5.24.1 -M5.010 -E 'say"@{[map{push@a,(2-$_%2)x($b=$a[$_-1]||$_);$b}1..shift]}"' ; produces no digits ; perl5.24.1 -E 'print "@{[map{push@a,(2-$_%2)x($b=$a[$_-1]||$_);$b}1..shift]}"' ; also does nothing \$\endgroup\$ – Alexx Roche Jul 24 '17 at 13:23
  • 1
    \$\begingroup\$ @AlexxRoche: You need to give the number of elements you want as a command line parameter, e.g. perl -E 'print "@{[map{push@a,(2-$_%2)x($b=$a[$_-1]||$_);$b}1..shift]}"' 50 for the first 50 elements. If you omit the length, the code defaults to printing zero elements. \$\endgroup\$ – Ilmari Karonen Jul 24 '17 at 15:09
1
\$\begingroup\$

Brain-Flak, 128 bytes

(({}<((())<>)>)<{({}[()]<{{({}[()])<>(({}))<>}{}<>(()()()[{}])<>}<>{({}<>)<>}(())<>>)}>){({}[()]<({}<>)<>>)}{}{{}}<>{({}<>)<>}<>

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Javascript (414 Characters)

function range(n,e,t){if("undefined"==typeof e&&(e=n,n=0),"undefined"==typeof t&&(t=1),t>0&&n>=e||0>t&&e>=n)return[];for(var i=[],r=n;t>0?e>r:r>e;r+=t)i.push(r);return i}function kolakoskiGen(n){var e=[1,2,2],t=parseInt(n),r=range(2,t);for(i in r)if(-1!=r.indexOf(parseInt(i))){var f=[1+i%2];f.length=f.length*e[i],f[f.length-1]=f[0],2==f.length?(e[e.length]=f[0],e[e.length]=f[1]):e[e.length]=f[0]}console.log(e)}

Could probably be more Efficient

\$\endgroup\$
  • 3
    \$\begingroup\$ Hi Shubshub, welcome to the site! Since this is a code-golf challenge, all answers are expected to attempt to make the code as short as possible. You should look through this page giving tips on how to golf your code, and then edit this post to include your new shorter code. \$\endgroup\$ – DJMcMayhem Apr 28 '16 at 4:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.