Count Up, Replace, Repeat!

Definition

Define the nth array of the CURR sequence as follows.

1. Begin with the singleton array A = [n].

2. For each integer k in A, replace the entry k with k natural numbers, counting up from 1 to k.

3. Repeat the previous step n - 1 more times.

For example, if n = 3, we start with the array [3].

We replace 3 with 1, 2, 3, yielding [1, 2, 3].

We now replace 1, 2, and 3 with 1; 1, 2 and 1, 2, 3 (resp.), yielding [1, 1, 2, 1, 2, 3].

Finally, we perform the same replacements as in the previous step for all six integers in the array, yielding [1, 1, 1, 2, 1, 1, 2, 1, 2, 3]. This is the third CURR array.

Write a program of a function that, given a strictly positive integer n as input, computes the nth CURR array.

The output has to be a flat list of some kind (and array returned from a function, a string representation of your language's array syntax, whitespace-separated, etc.).

This is . May the shortest code in bytes win!

Test cases

 1 -> [1]
2 -> [1, 1, 2]
3 -> [1, 1, 1, 2, 1, 1, 2, 1, 2, 3]
4 -> [1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4]
5 -> [1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5]
6 -> [1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6]

• Related: Count, Replace, Add Up! ._. – Dennis Jun 21 '16 at 7:58
• Can we take the input as a singleton array (like [2]) rather than an integer? – user45941 Jun 21 '16 at 8:13
• @Mego Let's keep it at integers. – Dennis Jun 21 '16 at 8:17
• I feel like there should be an OEIS sequence for this. – DanTheMan Jun 21 '16 at 16:31
• @DanTheMan It's not really an integer sequence in its current form, but I guess it could be turned into one by concatenating the results for all positive integers. – Dennis Jun 21 '16 at 16:53

Jelly, 3 bytes

R¡F


Try it online

Explanation

R¡F    Argument n

R      Yield range [1..n]
¡     Repeat n times
F    Flatten the result

• That is... simply brilliant... compared to my Jelly answer. – Leaky Nun Jun 21 '16 at 9:45
• Great first post! – Blue Jun 21 '16 at 10:18

Python, 50 bytes

lambda i:eval("[i "+"for i in range(1,i+1)"*i+"]")


Scope abuse! For example, for i=3, the string to be evaluated expands to.

[i for i in range(1,i+1)for i in range(1,i+1)for i in range(1,i+1)]


Somehow, despite using the function input variable i for everything, Python distinguishes each iteration index as belonging to a separate scope as if the expression were

[l for j in range(1,i+1)for k in range(1,j+1)for l in range(1,k+1)]


with i the input to the function.

• This trick works in Firefox 30+ too and saved me 3 bytes, thanks! – Neil Jun 21 '16 at 15:28
• @DigitalTrauma Both python and JavaScript have eval, obviously the code itself needs to be ported but I thought you could assume that anyway. – Neil Jun 22 '16 at 7:45
• @Neil Oh, I see - I completely misunderstood :) – Digital Trauma Jun 22 '16 at 15:10

05AB1E, 6 3 bytes

DFL


Explained

D     # duplicate input
F    # input times do
L   # range(1,N)


Try it online

Saved 3 bytes thanks to @Adnan

• DFL is 3 bytes shorter :) – Adnan Jun 21 '16 at 9:39
• @Adnan: Didn't know L worked like that on lists. A bit surprising that it flattens automatically. – Emigna Jun 21 '16 at 9:58
• It's actually a bug which I've never fixed :p. – Adnan Jun 21 '16 at 10:06

Retina, 33 bytes

.$*0 +%(M!&1.*(?=0)|^.+ O.+  Input and output in unary. Try it online! Even though I didn't use the closed form for the related challenge, adapting this answer was surprisingly tricky. • +%(M!& is the longest tag that I would ever see. – Leaky Nun Jun 21 '16 at 8:06 Python 2, 82 bytes lambda n:[1+bin(i)[::-1].find('1')for i in range(1<<2*n-1)if bin(i).count('1')==n]  This isn't the shortest solution, but it illustrates an interesting method: • Write down the first 2^(2*n-1) numbers in binary • Keep those with exactly n ones • For each number, count the number of trailing zeroes, and add 1. Actually, 9 bytes ;#@♂RΣn  Try it online! Explanation: ;#@♂RΣn ;#@ dupe n, make a singleton list, swap with n ♂RΣn call the following function n times: ♂R range(1, k+1) for k in list Σ concatenate the ranges  Thanks to Leaky Nun for a byte, and inspiration for another 2 bytes. • ;#@"♂R♂i"*ƒ saves a byte – Leaky Nun Jun 21 '16 at 8:19 • @LeakyNun Good catch - ;#@♂R♂in saves another one! – user45941 Jun 21 '16 at 8:28 • I was about to try summation, lol. – Leaky Nun Jun 21 '16 at 8:31 • I think 9 is going to be the optimal solution here – user45941 Jun 21 '16 at 8:35 • Your link is still outdated. – Leaky Nun Jun 21 '16 at 8:39 C#, 128 Bytes List<int>j(int n){var l=new List<int>(){n};for(;n>0;n--)l=l.Select(p=>Enumerable.Range(1,p)).SelectMany(m=>m).ToList();return l;  • With using static System.Linq.Enumerable, you can do this: int[]J(int n){var l=new[]{n};while (n-- > 0){l = l.Select(p => Range(1, p)).SelectMany(m => m).ToArray();}return l;} – die maus Jun 21 '16 at 20:13 APL, 11 bytes {∊⍳¨∘∊⍣⍵+⍵}  Test:  {∊⍳¨∘∊⍣⍵+⍵} 3 1 1 1 2 1 1 2 1 2 3  Explanation: • +⍵: starting with ⍵, • ⍣⍵: do the following ⍵ times: • ⍳¨∘∊: flatten the input, and then generate a list [1..N] for each N in the input • ∊: flatten the result of that • Simpler: {(∊⍳¨)⍣⍵⊢⍵} – Adám Jun 21 '16 at 20:07 • @Adám: Ah, yes, trains work differently from J. I'd started out with {(∊∘(⍳¨))⍣⍵+⍵} and then thought, how can I get rid of those braces? – marinus Jun 23 '16 at 14:16 CJam, 14 bytes {_a\{:,:~:)}*}  Test it here. Explanation _a e# Duplicate N and wrap it in an array. \ e# Swap with other copy of N. { e# Do this N times... :, e# Turn each x into [0 1 ... x-1]. :~ e# Unwrap each of those arrays. :) e# Increment each element. }*  Mathematica, 27 26 bytes 1 byte saved with some inspiration from Essari's answer. Flatten@Nest[Range,{#},#]&  Fairly straightforward: for input x we start with {x} and then apply the Range to it x times (Range is Listable which means that it automatically applies to the integers inside arbitrarily nested lists). At the end Flatten the result. Clojure, 59 bytes (fn[n](nth(iterate #(mapcat(fn[x](range 1(inc x)))%)[n])n))  Explanation: Really straight forward way to solve the problem. Working from the inside out: (1) (fn[x](range 1(inc x))) ;; return a list from 1 to x (2) #(mapcat (1) %) ;; map (1) over each item in list and flatten result (3) (iterate (2) [n]) ;; call (2) repeatedly e.g. (f (f (f [n]))) (4) (nth (3) n)) ;; return the nth value of the iteration  Python 3, 75 74 bytes def f(k):N=[k];exec('A=N;N=[]\nfor i in A:N+=range(1,i+1)\n'*k+'print(N)')  This is just a straightforward translation of the problem description to code. Edit: Saved one byte thanks to @Dennis. • Your print can go outside the exec. – xnor Jun 21 '16 at 8:42 • Yeah, that's what I had at first, but it simply prints [k] for some reason. I gave up trying to figure out if it was a scope issue or something else. – Andrew Epstein Jun 21 '16 at 8:44 • Yes, it looks like a scope issue. It works fine in Python 2. – xnor Jun 21 '16 at 8:48 R, 60 49 bytes Pretty straightforward use of unlist and sapply. y=x=scan();for(i in 1:x)y=unlist(sapply(y,seq));y  Thanks to @MickyT for saving 11 bytes • @MickyT thx for the tip, I can use seq to lower the byte count – bouncyball Jun 22 '16 at 12:48 • Sorry I misread the question – MickyT Jun 22 '16 at 17:20 php 121 Not really very much in the way of tricks behind this one. Flattening an array in php isn't short so it's necessary to build it flat in the first place <?php for($a=[$b=$argv[1]];$b--;)$a=array_reduce($a,function($r,$v){return array_merge($r,range(1,$v));},[]);print_r($a);

• Keeping it flat is a good idea. But callback functions aren´t short either. Beat You by 15 bytes. You can save 4 bytes with the short tag <? or 6 bytes with -r and no tag. – Titus Dec 6 '16 at 19:01

f n=iterate(>>= \a->[1..a])[n]!!n


Thanks to nimi for saving a byte.

A pointfree version is longer (35 bytes):

(!!)=<<iterate(>>= \a->[1..a]).pure

• iterate(>>= \a->[1..a]) for one byte less. – nimi Jun 21 '16 at 15:18

f=n=>eval([${for(n of Array(n+1).keys()).repeat(n--)}n+1])  Port of @xnor's Python answer. • I tried this with Firefox 42 (SyntaxError: missing : in conditional expression ) and Babel (Unexpected token (1:21)). What am I doing wrong? – Dennis Jun 21 '16 at 15:37 • @Dennis Sorry, but I have no idea; I do in fact have Firefox 42 on one of my machines for some reason and I double-checked and it ran fine there. (I also checked Firefox 37 and 47 just to be sure.) – Neil Jun 21 '16 at 18:24 • Huh, the page didn't refresh and I tested your old version. The new one works just fine. – Dennis Jun 21 '16 at 18:27 • @Dennis Ah, it looks like a stray ) crept into that version somehow. – Neil Jun 21 '16 at 18:29 J, 18 bytes ([:;<@(1+i.)"0)^:]  Straight-forward approach based on the process described in the challenge. Usage  f =: ([:;<@(1+i.)"0)^:] f 1 1 f 2 1 1 2 f 3 1 1 1 2 1 1 2 1 2 3 f 4 1 1 1 1 2 1 1 1 2 1 1 2 1 2 3 1 1 1 2 1 1 2 1 2 3 1 1 2 1 2 3 1 2 3 4  Explanation ([:;<@(1+i.)"0)^:] Input: n ] Identity function, gets the value n ( ... )^: Repeat the following n times with an initial value [n] ( )"0 Means rank 0, or to operate on each atom in the list i. Create a range from 0 to that value, exclusive 1+ Add 1 to each to make the range from 1 to that value <@ Box the value [:; Combine the boxes and unbox them to make a list and return Return the final result after n iterations  Pyth, 8 bytes usSMGQ]Q  Try it online! usSMGQ]Q input as Q u Q repeat for Q times, ]Q starting as [Q]: SMG convert each number in the array to its range s flatten then implicitly prints the result.  Jelly, 7 bytes Quick, before Dennis answers (jk) WR€F$³¡


Try it online!

WR€F$³¡ Main monadic chain. Argument: z W Yield [z]. ³¡ Repeat the following z times: R€ Convert each number in the array to the corresponding range. F Flatten the array.  F# , 63 bytes fun n->Seq.fold(fun A _->List.collect(fun k->[1..k])A)[n]{1..n}  Returns an anonymous function taking n as input. Replaces every entry k in A with [1..k], repeats the process n times, starting with A = [n]. Swift 3, 58 Bytes Meant to run directly in the a playground, with n set to the input: var x=[n];for i in 0..<n{x=x.reduce([]){$0+[Int](1...$1)}}  Ungolfed, with most short hand notation reverted: let n = 3 //input var x: Array<Int> = [n] for i in 0..<n { x = x.reduce(Array<Int>[], combine: { accumulator, element in accumulator + Array<Int>(1...element) }) }  Java, 159 Bytes Procedure int[] q(int y){int z[]=new int[]{y};for(int i=0;i<y;i++){int d=0,a=0;for(int c:z)d+=c;int[]r=new int[d];for(int c:z)for(int j=0;j<c;)r[a++]=++j;z=r;}return z;}  Usage public static void main(String[] args){String out = "["; int [] b = q(6);for(int c:b)out+=c+", ";System.out.println(out+"]");} public static int[] q(int y){int z[]=new int[]{y};for(int i=0;i<y;i++){int d=0,a=0;for(int c:z)d+=c;int[]r=new int[d];for(int c:z)for(int j=0;j<c;)r[a++]=++j;z=r;}return z;}  Sample output: [1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 1, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, ]  Python 2, 6968 66 bytes def f(n):a=[n];exec'a=sum([range(1,i+1)for i in a],[]);'*n;print a  Edit: Saved 1 byte thanks to @xnor. Saved 2 bytes thanks to @Dennis♦. • You can remove the parens around exec. In Python 2, it's a keyword, not a function. I count 68 bytes btw. – Dennis Jun 21 '16 at 15:32 • @Dennis Ah, that means I miscounted and it was originally 69 bytes... – Neil Jun 21 '16 at 18:26 Bash + GNU utilities, 49 • 1 byte saved thanks to @Dennis. Piped recursive functions FTW! f()((($1))&&xargs -l seq|f $[$1-1]||dd)
f $1<<<$1


n is passed on the command-line. Output is newline-separated.

The use of dd causes statistics to be sent to STDERR. I think this is OK, but if not, dd can be replaced with cat at a cost of 1 extra byte.

• Extraneous output to STDERR is allowed by default. You can replace {...;} with (...) to save a byte. – Dennis Jun 21 '16 at 22:24
• @Dennis yes, of course! Apparently you got this tip from me :) – Digital Trauma Jun 21 '16 at 22:34

Perl 5, 53 bytes

A subroutine:

{($i)=@_;for(1..$i){my@c;push@c,1..$_ for@_;@_=@c}@_}  See it in action as perl -e'print "$_ " for sub{($i)=@_;for(1..$i){my@c;push@c,1..$_ for@_;@_=@c}@_}->(3)'  Ruby, 61 bytes def f(n);a=[n];n.times{a=a.map{|i|(1..i).to_a}.flatten};a;end  • Hi! Welcome to PPCG. A short explanation would be nice! – TheCoffeeCup Jun 23 '16 at 2:41 • Welcome to PPCG! Unless the challenge overrules this all submissions need to be full programs or functions, not just snippets. (And in this case, the challenge actually confirms this requirement.) – Martin Ender Jun 27 '16 at 10:02 PHP, 100 98 bytes Run with php -r '<code>' <n>. for($a=[$n=$argv[1]];$n--;$a=$b)for($b=[],$k=0;$c=$a[$k++];)for($i=0;$i++<$c;)$b[]=$i;print_r($a);


In each iteration create a temporary copy looping from 1..(first value removed) until $a is empty. These two are still and will probably remain at 100 bytes: for($a=[$n=$argv[1]];$n--;)for($i=count($a);$i--;)array_splice($a,$i,1,range(1,$a[$i]));print_r($a);  In each iteration loop backwards through array replacing each number with a range. for($a=[$n=$argv[1]];$n--;)for($i=$c=0;$c=$a[$i+=$c];)array_splice($a,$i,1,range(1,$c));print_r(\$a);
`

In each iteration loop through array increasing index by previous number and replacing each indexed element with a range