B​u​i​l​d a n​e​s​t

Question

The challenge is simple: write a program or function that, when given a finite non-negative integer, outputs a nested array.

The rules

• Your code must produce a unique valid nested array for every integer 0 ‌≤ n ‌< 2³¹.
• Every possible nested array with up to 16 open brackets must be outputted within this range. (This does not mean that your code can never output a nested array with more than 16 open brackets.)
• Your code may output a string representation of the nested array instead of an actual array (with or without commas).

One possible mapping:

0 -> []
1 -> [[]]
2 -> [[[]]]
3 -> [[], []]
4 -> [[[[]]]]
5 -> [[[], []]]
6 -> [[[]], []]
7 -> [[], [[]]]
8 -> [[], [], []]
9 -> [[[[[]]]]]
etc.

Scoring

This is code-golf, so the shortest code in bytes wins.

Answer 1

Python 2.7, 172 149 124 118 bytes

x=input();y="";z=0
for b in bin(x)[2+(x<1):]:y+="[]"[b<"1"];z+=b>"0"or-1;z+=99*(z<0)
print"["+(y,"[]"*(x+16))[z>0]+"]"

Explanation:

Define a bijection by [↔1 and ]↔0. Any arrangement of brackets can then be written as a binary number and vice versa, for instance [][]↔1010(10) and [[][]]↔110100(52). All valid arrangements of up to 15 open brackets (30 brackets in total) are covered by numbers with up to 30 bits (ignoring leading zeros), which are precisely the numbers less than 2³¹.

The first for-loop gives the inverse of this bijection, converting a number to an arrangement of brackets, while checking that the arrangement is valid.

Invalid arrangements are replaced within the print statement by long sequences of brackets to avoid collisions. For instance 11(3)↔[[ is not valid so we concatenate 3+16 brackets instead. This ensures all arrangements are unique.

The resultant arrangement is placed within a pair of brackets to make a nested array, so that 1010(10) becomes [[][]] and 110100(52) becomes [[[][]]]. The extra open bracket means we've now covered all arrays with 16 open brackets.

---

The following program can be used to figure out the number for a given array with up to 16 brackets.

s=raw_input();o="";
for c in s[1:-1]:
 if c=="[":o+="1"
 if c=="]":o+="0"
print int(o,2)

Answer 2

Python, 153 128 bytes

s=l=0;r="";n=input()
for d in bin(n)[2:]*(n>0):c=d<"1";l=[l,s>1][c];r+="]"*c+(1-l*c)*"[";s+=1-c-l*c
print"["+r+"["*l+"]"*(s+l+1)

We map a number n to a nested list by looking at its binary digits left-to-right. This algorithm works for any number, not just under 2³².

1. If the current binary digit is an 1, output [.
2. Otherwise, if the sequence of brackets we've output so far would get balanced by a single closing bracket, output ][.
3. Otherwise, if this is the last 0 in the binary number, output ][.
4. Otherwise output ].

Finally, we close any opened brackets.

Answer 3

Perl, 80 79 bytes

Again uses orlp's algorithm, but this time I first checked if it works...

Includes +1 for -p

Give input number on STDIN

nest.pl <<< 8

nest.pl:

#!/usr/bin/perl -p
($_=sprintf"%b",$_).=2x(s^.^$&or++$n-pos&&/.0/g?++$n%1:$`&&21^eg-$n);y;102;();

Linus's solution is 64 bytes in perl:

#!/usr/bin/perl -p
$_=sprintf"%b",/.+/g;$_=10x($&&&$&+16)if!/^(1(?1)*0)+$/;y;10;()

Dennis's solution is 59 bytes in perl (increasingly slower for large numbers):

#!/usr/bin/perl -p
1while$_-=(sprintf"%b",$n++)=~/^(1(?1)*0)+$/;$_=$&;y;10;()

Answer 4

Spoon, 63 bytes (501 bits)

000001001001001011001101001010011011111001010001000000101010
101101100110100101101001000101100010001000000100011000010000
000000000000001110111110010000001110110110010100100100100100
000110011010001000000110110000010000001010110011011011011001
000000011010010010010001000000111011011011101001001001000110
110110010100100101011001000100000011010001000000111011011001
010010010010010001101101101001000110110010110001101101101101
100100010001010010001010011011001000000011001101001001010010
000001100101001000111

This is the following brainfuck program converted to spoon:

-[+[+<]>>+]<+++.[->+>+<<]>>++>>,[>-[<->-----]+<+++[-<+<<.>>>>-<]>[-<<-[->+<]<<<[-]>>>>[-<+<<<+>>>>]<<.>>+<[>-]>[-<+<<.>>>>]<<>>]<,]<<<<[>.>.<<[-]]>>>+[-<.>]+

Reads an integer in binary on stdin, and outputs the nested list on stdin. Requires 0 to be input as the empty string (no digits), and requires a brainfuck interpreter with 8-bit cells. Same algorithm as my Python answer.

Readable version:

-[+[+<]>>+]<+++.           push open bracket and print it
[->+>+<<]                  dup
>>++                       increment to close bracket

>>,[                       read input loop
    >-[<->-----]+<+++          subtract 48 and set up if/else
    [-                         if c == 1
        <+                         increment s
        <<.>>>                     output open bracket
    >-<]>[-<                   else
        <-[->+<]                   decrement and move s
        <<<[-]                     zero l
        >>>>[-<+<<<+>>>>]          l = s and restore s
        <<.>                       output close bracket
        >+<[>-]>[-                 if s == 0
            <+                         undo s decrement
            <<.                        output open bracket
        >>>>]<<
    >>]<
,]

<<<<[                      if l
    >.>.                   output pair
<<[-]]
>>>+[-<.>]                 output close bracket s+1 times

Answer 5

Jelly, 28 bytes

ḃ2-*µSN;+\>-Ạ
1Ç#Ṫḃ2ṭ2;1ị⁾][

This iterates over all strings of the characters [ and ] that start with a [ and end with a ], verifies if the brackets match, and prints the n^th match.

Try it online!

Answer 6

Python 3, 120 114 bytes

def f(n,k=0):
 while~n:
  k+=1
  try:r=eval(bin(k).translate({48:'],',49:'['})[3:-1])+[];n-=1
  except:0
 print(r)

Test it on Ideone.

How it works

The defined function f takes input n and initializes k to 0. We'll keep incrementing k until n + 1 values of k result in a valid output. Every time we find such a value of k, n is decremented once it reaches -1, ~n yields 0, and the list r that corresponds to the last value of k is printed.

The partial mapping from the positive integers to nested lists (i.e., k ↦ r) has to be bijective, but there are no other constraints. The one used in this answer operates as follows.

1. Convert k to a binary string representation, staring with 0b.

   For example, 44 ↦ "0b101100".

2. Replace all 0's (code point 48) in the string representation with the string "]," and all 1's (code point 49) with [.

   For example, "0b101100" ↦ "],b[],[[],],".

3. Remove the first three characters (they correspond to "0b") and the trailing character (hopefully a comma).

   For example, "],b[],[[],]," ↦ "[],[[],]".

4. Try evaluating the generated code. If this results in an error, k isn't mapped to any list.

   For example, "[],[[],]" ↦ ([], [[]]).

5. Concatenate the result (if any) with the empty list. If this results in an error, k isn't mapped to any list.

   For example, ([], [[]]) + [] errors since + cannot concatenate lists and tuples.

Answer 7

Haskell, 71 bytes

p 1=["[]"]
p n=['[':h++t|k<-[1..n-1],h<-p k,_:t<-p$n-k]
((p=<<[1..])!!)

The main function on the last line indexes into a list of all nested arrays, sorted by size (number of open brackets). So, all the arrays of size at most 16 are listed first.

Let's first look at code that's nicer and shorter, but Haskell's typechecker refuses to accept.

p 1=[[]]
p n=[h:t|k<-[1..n-1],h<-p k,t<-p$n-k]
((p=<<[1..])!!)

The function p on input n gives a list of all nested arrays of size n (open brackets). This is done recursively. Each such array consists of some head h (first member) of size k and some tail t (other members) of size n-k, both sizes nonzero. Or, it's the empty array for size n==1.

The expression p=<<[1..] then flattens p(1), p(2), ... into a single infinite list of all arrays sorted by size

[ [], [[]], [[],[]], [[[]]], [[],[],[]], [[],[[]]], [[[]],[]], [[[],[]]], ...

and the main function indexes into it.

... Or, it would, if Haskell didn't whine about "construct[ing] the infinite type: t ~ [t]". Haskell cannot represent the infinite list above whose elements are arbitrarily nested arrays. All its elements must have the same type, but a type t cannot be the same as a list of t's. In fact, the function p itself cannot be assigned a consistent type without dependent typing, which Haskell lacks.

So, instead we work on strings of brackets, simulating the cons operation by acting on [ and ] characters. This takes an extra 9 bytes. The perils of golfing in a type-safe language.

Answer 8

Haskell, 87 82 bytes

0#0=[""]
n#m=['[':x|n>0,x<-(n-1)#m]++[']':x|n<m,x<-n#(m-1)]
(([0..]>>= \y->y#y)!!)

Outputs the array elements. Usage example: (([0..]>>= \y->y#y)!!) 3 -> "[][]".

Function # builds all nested arrays as strings for n open and m close brackets, by keeping track of how many of each are left over. Always starts with n == m. The main function calls y # y for every y <- [0,1,...] and picks the element at the index given by the input.

Answer 9

MATL, 31 bytes

O`@BEqXJYs0&)0>w~hA+tG>~]x92J-c

Try it online! Or verify the first few test cases (takes a few seconds).

The produced mapping is:

0 -> []
1 -> [[]]
2 -> [[][]]
3 -> [[[]]]
4 -> [[][][]]
5 -> [[][[]]]
6 -> [[[]][]]
7 -> [[[][]]]
...

Explanation

The code keeps testing increasing binary numbers, with digit 0 replaced by -1; that is, using 1 and -1 as digits. Digit 1 will represent '[' and -1 will represent ']'.

The program counts until n+1 valid numbers have been obtained. A number is valid if the following two conditions hold:

1. The sum of digits is zero (that is, there is an equal number of 1 and -1)
2. The cumulative sum of digits is always positive (that is, the accumulated number of 1 digits always exceeds that of -1) except at the end (where it is zero by condition 1).

Once n+1 valid numbers have been obtained, the last one is transliterated by changing 1 into [ and -1 into ], and then it is displayed.

Code:

O          % Push 0: initial count of valid numbers
`          % Do...while
  @        %   Push iteretation index k, starting at 1
  B        %   Convert to binary. For example, k=6 gives [1 1 0 0]
  Eq       %   Multiply by 2, subtract 1: transforms [1 1 0 0] into [1 1 -1 -1]
  XJ       %   Copy that to clipboard J, without popping it
  Ys       %   Cumulative sum: gives [1 2 1 0]
  0&)      %   Split array into its final element and the rest. Gives 0, [1 2 1]
  0>       %   Yields 1 for positive entries (condition 2). So in this case it
           %   gives [1 1 1]
  w        %   Swap: moves second-top element in the stack (0 in this case) to top
  ~        %   Negate: yields 1 if input is 0 (condition 1). Gives 1 in this case
  h        %   Concatenate horizontally. Gives [1 1 1 1]
  A        %   All: gives 1 if all elements are 1. Gives 1 in this case, meaning
           %   that this k is valid
  +        %   Add the result (0 or 1) to the count of valid numbers
  t        %   Duplicate
  G        %   Push input n
  >~       %   Loop condition: false (exit loop) if count exceeds input n
]          % End loop. At this point the result is in clipboard J, in 1/-1 format
x          % Delete count
92         % Push 92. Will be used to convert 1, -1 to '[', ']' (ASCII 91, 93)
J          % Push result in 1/-1 format
-          % Subtract: converts 1 to 91, -1 to 93
c          % Convert to char. Implicitly display