# Decode the Void

A void list is a list that at no level contains any non-list objects. Or if you prefer a recursive definition

• The empty list is void

• A list containing only other void lists is void

All void lists have a finite depth.

Here are some examples of void lists (using python syntax):

[]
[[]]
[[],[]]
[[[]]]
[[[]],[]]
[[],[[]]]


Here are some examples of things that are not void lists:

["a"]
[[...]]
[1]
2
[[],([],[])]


Write two separate functions (or programs if you prefer). One should take a positive integer (you may also include zero if you wish) as an argument and return a void list the other should take a void list and return it an integer. These two functions should always be inverses of each other. That is if you pass the output of f into g you should get the original input of f as the result of g. This means the mapping must be 1:1, i.e. for every integer, there may only exist exactly one void list for which g gives that integer and for every void list there should be exactly one integer for which f gives that void list.

You are essentially creating a Bijection

You may choose to use a string representation of a void list (with or without commas and spaces) instead of your languages native list type.

# Scoring

Your score will be the lengths of your two functions together. This is so you should aim to minimize this sum.

• May 10, 2017 at 23:12
• This question asks for two functions whereas the duplicate only asks for the first half. May 11, 2017 at 11:49
• Rats. I nearly posted the best answer I had written yet, and it doesn't qualify for the other challenge. May 11, 2017 at 13:06
• @IanMiller I would to say that the other challenge has different guidelines for encoding then this one does. May 11, 2017 at 13:17
• Perhaps it would make more sense for this question to be just the decoder? Because there's already a question about the encoder.
– user62131
May 11, 2017 at 15:22

# Pyth, 27 + 29 = 56 bytes

f:

L?bolNS{sm[d+d]Y]d)ytb]Y@y


Test suite

g:

L?bolNS{sm[d+d]Y]d)ytb]Yxyl


Test suite

The system is very simple: I generate all possible lists with no more than a certain number of ['s. Then, I sort them in such a way that the lists I haven't generated yet would be near the end. This is all done by the function y, identical in both programs. It is written as

L?bolNS{sm[d+d]Y]d)ytb]Y


Then, I index into this list for f, and search through it for g.

The number of lists I generate is chosen to be large enough that I have generated all possible lists which would appear at or before the desired location in the infinite sorted list.

The programs allow/return 0 as an option.

# Python 2, 96 bytes

Try it online! to test the bijection.

f=lambda l:len(l)and f(l[0])*2+1<<f(l[1:])


Takes void lists to non-negative integers. 42 bytes.

g=lambda n:n*[g]and[g(n/(n&-n)/2)]+g(len(bin(n&-n))-3)


Takes non-negative integers to void lists. 54 bytes. A more recursive attempt gave the same length.

g=lambda n,i=0:n*[g]and[g(n/2,i+1),[g(n/2)]+g(i)][n%2]


# Java 7, 725 bytes

f(int) (325 bytes):

String f(int i){String s="";for(int j=0,e=0;e<i;e+=v(s))s=Integer.toBinaryString(j++);return"["+s.replace("1","[").replace("0","]")+"]";}int v(String s){for(;!s.isEmpty();s=s.replaceFirst("1","").replaceFirst("0",""))if(s.replace("1","").length()!=s.replace("0","").length()|s.charAt(0)<49|s.endsWith("1"))return 0;return 1;}


g(String) (75 + 325 bytes):

int g(String s){int r=0;for(String i="10";!i.equals(s);i=f(++r));return r;}


Since method g uses method f to calculate it's result by looping over possible void-list until it founds the one equal to the one inputted, the bytes of f are counted twice (since both methods should be able to run without the other for this challenge).

Explanation:

In general, method f simply loops over all binary String-representations of integers, and increase a counter every time a valid one is found. Valid binary-Strings for this challenge comply to the following rules: They start with a 1, and end with a 0; they have an equal number of 1s and 0s; and every time you remove the first 1 and 0 and validate what is left again, these two rules still apply. After the counter equals the input, it converts that binary-String to a String void-list, by replacing all 1 with [ and all 0 with ].

As for method g: We start with "[]" (representing void-list 0), and then continue using method f while increasing an integer, until it matches the input-String.

String f(int i){         // Method f with integer parameter and String return-type
for(int j=0,e=0;e<i;   //  Loop as long as e does not equal the input
e+=v(s))           //    And append increase integer e if String s is valid
s=Integer.toBinaryString(j++);
//   Change s to the next byte-String of integer j
//  End of loop (implicit / single-line body)
return"["+             //  Return the result String encapsulated in "[" and "]"
s.replace("1","[").replace("0","]")+"]";
//  after we've replaced all 1s with "[" and all 0s with "]"
}                        // End of method f

int v(String s){         // Separate method with String parameter and integer return-type
for(;!s.isEmpty();     //  Loop as long as String s isn't empty
s=s.replaceFirst("1","").replaceFirst("0",""))
//    After each iteration: Remove the first "1" and "0"
if(s.replace("1","").length()!=s.replace("0","").length()
//   If there isn't an equal amount of 1s and 0s
|s.endsWith("1")) //   or the String doesn't end with a 0
return 0;          //    Return 0 (String is not valid)
//  End of loop (implicit / single-line body)
return 1;              //  Return 1 (String is valid)
}                        // End of separate method

int g(String s){         // Method g with String parameter and integer return-type
int r=0;               // Result integer
for(String i="[]";!i.equals(s);
//  Loop as long as i does not equal the input String
i=f(++r));         //   After each iteration: Set i to the next String in line
return r;              //  Return the result integer
}                        // End of method g


Example input & output cases:

Try it here. (NOTE: It's pretty slow for the last few test cases. Will take around 10-15 sec for all of them.)

0   <-> []
1   <-> [[]]
2   <-> [[][]]
3   <-> [[[]]]
4   <-> [[][][]]
5   <-> [[][[]]]
6   <-> [[[]][]]
7   <-> [[[][]]]
8   <-> [[[[]]]]
9   <-> [[][][][]]
10  <-> [[][][[]]]
11  <-> [[][[]][]]
12  <-> [[][[][]]]
13  <-> [[][[[]]]]
14  <-> [[[]][][]]
50  <-> [[[][[[]]]]]
383 <-> [[[][]][[[][]]]]

• I don't think that [][] is a list. Perhaps I am misunderstanding the way Java does its whatever. Adding [...] around all of them and having 0 map to [] should do the trick. May 11, 2017 at 19:56
• @WheatWizard Ah, good call. Will try to fix this. I didn't had enough bytes yet anyway. ;P May 11, 2017 at 19:57
• @WheatWizard Ok, it should be fixed now. Tough but fun challenge btw. It took a while before I understand what you meant, and even longer to write this answer, but it was fun. :) May 11, 2017 at 20:16

# K (ngn/k), 49 bytes

{$[#x;2/,/1,'&:'o'x;0]} {$[x;o'|-1+-1-':&|2\x;()]}


Try it online!

uses the formula from the example in Bijection: tree-like lists - natural numbers

# JavaScript (Node.js), 82 bytes

f=(n,i)=>n?n&1<<i?[f(i),...f(n>>-~i)]:f(n,-~i):[]
g=([a,...b])=>a?g(b)*2+1<<g(a):0


Try it online!

xnor's idea

# Python 3 - sign/abs, 73 bytes

f=lambda n:[[[]]*(n<0),[[]]*abs(n)]
g=lambda l:[-1,1][not l[0]]*len(l[1])


Try it online!

Straight forward implementation, supports negative numbers.

Integer i is encoded [sign(i), abs(i)], where sign(i)=[] if i > 0 else [[]] and abs(i)=[[]] * i, i.e. a list of empty lists with length abs(i).

# Python 3 - binary, 126 bytes

This is a more elaborate version (and a lot longer...), where the absolute value is encoded in a binary list representation.

f=lambda n:[[[]]*(n<0),[[[]]*int(i)for i in f"{n:+b}"[1:]]]
g=lambda l:[-1,1][not l[0]]*int(''.join(map(str,map(len,l[1]))),2)


Try it online!

• Doesn't work for more complex void lists: Try it online! Jul 26, 2019 at 8:11
• Ah, I somehow missed, that there should be a mapping for every void list... you're right. Jul 26, 2019 at 8:13

# Stax, 33 total bytes

These programs are inverses of each other. They convert to and from all void lists and all non-negative integers, so that includes 0. This seems like it's maybe a famous function from some kind of algebra I don't know. In order to wrap my head around it, I first implemented the programs as functions in python.

def convert_to_void(n):
lst = []
while n > 0:
n -= 1
choices = len(lst) + 1
choice = n % choices
cutpoint = len(lst) - choice
n //= choices
newgroup = lst[cutpoint:]
del lst[cutpoint:]
lst.append(newgroup)
return lst

def convert_from_void(lst):
n = 0
while lst != []:
newgroup = lst.pop()
n *= len(lst) + len(newgroup) + 1
n += len(newgroup) + 1
lst.extend(newgroup)
return n


The stax programs have the same behavior.

### Non-negative integer → Void list, 15 bytes

ƒâ₧~└3BI─¿-rÅ;ì


Run and debug it

### Void list → Non-negative integer, 18 bytes

Çäê[!σc↑Ö§░NR╥ç=Æ
`

Run and debug it