Decode the Void

Question

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
[[],([],[])]

---

Task

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 code-golf so you should aim to minimize this sum.

Answer 1

Pyth, 27 + 29 = 56 bytes

f:

L?bol`NS{sm[d+d]Y]d)ytb]Y@y

Test suite

g:

L?bol`NS{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?bol`NS{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.

Answer 2

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]

Answer 3

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
  String s="";           //  Start with an empty String
  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.charAt(0)<49   //   or the String doesn't start with a 1
       |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 <-> [[[][]][[[][]]]]

Answer 4

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

Answer 5

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

Answer 6

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!

Answer 7

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