6
\$\begingroup\$

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
\$\endgroup\$
12
  • \$\begingroup\$ Wouldn't [1,2,1] be incorrect because elements 1 are the same? \$\endgroup\$
    – Timtech
    Jan 31 '14 at 16:52
  • 2
    \$\begingroup\$ I'm sorry, you're going to have to better define "lexicographically" better over the solution space. \$\endgroup\$
    – McKay
    Jan 31 '14 at 16:52
  • \$\begingroup\$ e.g. why isn't [0,1] better than [1,2] for f(2)? \$\endgroup\$
    – McKay
    Jan 31 '14 at 16:54
  • \$\begingroup\$ @Timtech: No, because the first 1 is in another sublist than the second 1. A sublist is a contiguous section of the original list, so there are three sublists: [1] [1,2] [1] \$\endgroup\$
    – ProgramFOX
    Jan 31 '14 at 16:55
  • 2
    \$\begingroup\$ @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? \$\endgroup\$
    – user12205
    Jan 31 '14 at 22:55
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ ).~)& -> .)^ for 2. \$\endgroup\$
    – primo
    Jan 31 '14 at 18:37
3
\$\begingroup\$

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

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

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.

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

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]
\$\endgroup\$
0
\$\begingroup\$

Japt, 9 bytes

õȤq1 ÌÊÄ

Try it

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

Haskell, 29 bytes

(`take`t)
t=1:do x<-t;[x+1,1]

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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