25
\$\begingroup\$

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

\$\endgroup\$
  • 2
    \$\begingroup\$ very related: codegolf.stackexchange.com/questions/94540/build-a-nest/… \$\endgroup\$ – Destructible Lemon May 10 '17 at 23:12
  • 1
    \$\begingroup\$ This question asks for two functions whereas the duplicate only asks for the first half. \$\endgroup\$ – Ian Miller May 11 '17 at 11:49
  • 3
    \$\begingroup\$ Rats. I nearly posted the best answer I had written yet, and it doesn't qualify for the other challenge. \$\endgroup\$ – Caleb Kleveter May 11 '17 at 13:06
  • 2
    \$\begingroup\$ @IanMiller I would to say that the other challenge has different guidelines for encoding then this one does. \$\endgroup\$ – Caleb Kleveter May 11 '17 at 13:17
  • 1
    \$\begingroup\$ Perhaps it would make more sense for this question to be just the decoder? Because there's already a question about the encoder. \$\endgroup\$ – user62131 May 11 '17 at 15:22
7
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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

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 <-> [[[][]][[[][]]]]
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Sriotchilism O'Zaic May 11 '17 at 19:56
  • \$\begingroup\$ @WheatWizard Ah, good call. Will try to fix this. I didn't had enough bytes yet anyway. ;P \$\endgroup\$ – Kevin Cruijssen May 11 '17 at 19:57
  • \$\begingroup\$ @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. :) \$\endgroup\$ – Kevin Cruijssen May 11 '17 at 20:16
1
\$\begingroup\$

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

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

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

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

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ Doesn't work for more complex void lists: Try it online! \$\endgroup\$ – Jitse Jul 26 at 8:11
  • \$\begingroup\$ Ah, I somehow missed, that there should be a mapping for every void list... you're right. \$\endgroup\$ – movatica Jul 26 at 8:13
0
\$\begingroup\$

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

\$\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.