Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The problem is defined as follows:

Create a function that takes an integer and returns a list of integers, with the following properties:

  • Given a positive integer input, n, it produces a list containing n integers ≥ 1.
  • Any sublist of the output must contain at least one unique element, which is different from all other elements from the same sublist. Sublist refers to a contiguous section of the original list; for example, [1,2,3] has sublists [1], [2], [3], [1,2], [2,3], and [1,2,3].
  • The list returned must be the lexicographically smallest list possible.

There is only one valid such list for every input. The first few are:

f(2) = [1,2]         2 numbers used
f(3) = [1,2,1]       2 numbers used
f(4) = [1,2,1,3]     3 numbers used
share|improve this question
5  
What's the winning criteria? –  ProgramFOX Jan 31 at 16:18
    
Wouldn't [1,2,1] be incorrect because elements 1 are the same? –  Timtech Jan 31 at 16:52
2  
I'm sorry, you're going to have to better define "lexicographically" better over the solution space. –  McKay Jan 31 at 16:52
    
e.g. why isn't [0,1] better than [1,2] for f(2)? –  McKay Jan 31 at 16:54
1  
@ProgramFOX and everyone who voted to close this, since this question is tagged as code-golf I think we do have an objective winning criterion? –  ace Jan 31 at 22:55
show 8 more comments

6 Answers

APL, 18

{+⌿~∨⍀⊖(⍵/2)⊤2×⍳⍵}

1 + number of trailing zeros in base 2 of each natural from 1 to N.

Example

      {+⌿~∨⍀⊖(⍵/2)⊤2×⍳⍵} 32
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6
share|improve this answer
add comment

GolfScript (20 18 chars)

{,{.)^2base,}%}:f;

This is a simple binary ruler function, A001511.

Equivalently

{,{).~)&2base,}%}:f;
{,{~.~)&2base,}%}:f;
{,{).(~&2base,}%}:f;
{,{{1&}{2/}/,)}%}:f;

Thanks for primo for saving 2 chars.

share|improve this answer
1  
).~)& -> .)^ for 2. –  primo Jan 31 at 18:37
add comment

Sclipting, 26 23 characters

감⓶上가增❷要❶감雙是가不감右⓶增⓶終終丟丟⓶丟終并

This piece of code generates a list of integers. However, if run as a program it will concatenate all the numbers together. As a stand-alone program, the following 25-character program outputs the numbers separated by commas:

감⓶上가增❷要감嚙是가不⓶增⓶終終丟丟⓶丟껀終合鎵

Example output:

Input: 4

Output: 1,2,1,3

Input: 10

Output: 1,2,1,3,1,2,1,4,1,2

share|improve this answer
add comment

Python 2.7, 65 characters

print([len(bin(2*k).split('1')[-1]) for k in range(1,input()+1)])

The number of trailing zeros in 2, 4, 6, ..., 2n.

share|improve this answer
add comment

Haskell, 40 characters

n&p=n:p++(n+1)&(p++n:p)
f n=take n$1&[]

Example runs:

λ: f 2
[1,2]
λ: f 3
[1,2,1]
λ: f 4
[1,2,1,3]
λ: f 10
[1,2,1,3,1,2,1,4,1,2]
λ: f 38
[1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,6,1,2,1,3,1,2]
share|improve this answer
add comment

Golfscript - 1 character

,

I'm pretty sure this meets the criteria, but it does seem weirdly worded.

share|improve this answer
    
It seems to me that something like this would work, +1. –  Timtech Jan 31 at 16:47
3  
Excuse me? For input 3 this would generate 1,2,3, which is wrong because 1,2,1 is correct and lexicographically smaller. –  Timwi Jan 31 at 16:48
    
Timwi's point aside, the convention for questions which ask specifically for a function is that GolfScript answers should define a named block and then clear it from the stack: i.e. the boilerplate is a prefix of { and a suffix of }:f; –  Peter Taylor Jan 31 at 17:17
1  
@PeterTaylor So, when they say "function", and most programming languages get to cut out crap like classes and using directives..., GolfScript has more boilerplate that has to be thrown on? –  McKay Jan 31 at 18:07
    
And even if actually creating a named block is important, why does it have to be dropped from the stack? –  McKay Jan 31 at 18:12
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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